是
个体2入选
0.9501<0.636 ?
是
否 是
个体2入选
0.9501<0.691 ?
否
个体3落选
0.9501<1 ?
个体2落选
个体4入选
3、轮盘赌选择方法的实现步骤
• （1） 计算群体中所有个体的适应度函数值 （需要解码）； • （2） 利用比例选择算子的公式，计算每个 个体被选中遗传到下一代群体的概率； • （3） 采用模拟赌盘操作（即生成0到1之间 的随机数与每个个体遗传到下一代群体的 概率进行匹配）来确定各个个体是否遗传 到下一代群体中。
若目标函数中有冲突，则一般不存在唯一最优解，而存在 若干个可行解。
f2 X A B
Min [f1, f2]
解点A, B, C是Pareto最优点 A Pareto支配X C Pareto 支配Y Y C f1
Pareto最优解示意图
Pareto最优解不一定对其他所有解占优，但是所有其他解 都不能对它占优。
几个术语
个体（染色体）
• 基因型：1000101110110101000111 基因 • 缺点是什么？ 解码
多维优化如何编码？ 编码
• 表现型：0.637197
初始种群
• GA可采用随机方法生成若干个个体 的集合，该集合称为初始种群。初 始种群中个体的数量称为种群规模。
如何随机生成？
适应度函数
变异算子
• 所谓变异运算，是指依据变异概率 Pm 将个
体编码串中的某些基因值用其它基因值来替
换，从而形成一个新的个体。遗传算法中的
变异运算是产生新个体的辅助方法，它决定
了遗传算法的局部搜索能力，同时保持种群 的多样性。交叉运算和变异运算的相互配合， 共同完成对搜索空间的全局搜索和局部搜索。 GA中变异算子可采用基本位变异算子。
二、遗传算法的数学原理
2 max x12 x2 模式是指种群个体 个体编码串 适应度 基因串中的相似样板
模式的概念
个体编码串
适应度
011101
34
34 25 50
011101 111111 111001
101011 011100 111001
平均适应度
?
34 98 50 53 58.75
111***
2
0.636
3
0.691 0.4860 0.6068
4
1 0.9501
0.9501 否 是
0.2311
0.6068
0.4860
最终选择了 3个个体 1个个体 4? 0.2311<0.144 ? 0.2311 <0.636 个体 1落选 2，
个体2入选
0.6068<0.636 ? 0.4806<0.636 ?SGAຫໍສະໝຸດ 框图产生初始群体是
输出结果并结束 是否满足停止准则
否
计算个体适应度值
执行M/2次
比例选择运算
单点交叉运算 基本位变异运算
产生新一代群体
遗传算法的特点
• （1）群体搜索，易于并行化处理； • （2）不是盲目穷举，而是启发式搜索； • （3）适应度函数不受连续、可微等条件的 约束，适用范围很广。
交叉算子
• 所谓交叉运算，是指对两个相互配 对的染色体依据交叉概率 Pc 按某种方式相 互交换其部分基因，从而形成两个新的个 体。交叉运算是遗传算法区别于其他进化 算法的重要特征，它在遗传算法中起关键 作用，是产生新个体的主要方法。 GA中交 叉算子可采用单点交叉算子。
单点交叉运算示例
• • • • • • 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 如何决定哪对个体应交叉？ • 实数编码如何交叉？ 00000|00000111111000101 11100|01110000000010000 交叉点
f ( x) x sin(10 x) 2.0
x∈[-1,2] ，求解结果精确到6位小数。
•
• 由于区间长度为3，求解结果精确到6位小数 • 可将自变量定义区间划分为3×10^6等份。 • 又因为2^21 < 3×10^6 < 2^22 ，所以本例的二 进制编码长度至少需要22位。 • 本例的编码过程实质上是将区间[-1，2]内对应 的实数值转化为一个二进制串（b21b20…b0）。
小。选择操作的任务就是按某种方法从父
代群体中选取一些个体，遗传到下一代群
体。GA中选择算子可采用轮盘赌选择方法。
1、个体被选择概率的计算 被选择概率
1
0 0.144
2
0.636
3
0.691
4
1
各个体被分配的区间
2、轮盘赌选择方法（或 比例选择算子）
各个体区间 有序随机数 产生随机数
1
0 0.144 0.2311
30 28 26 24 22
Fitness
20 18 16 14 12 10
0
5
10
15
20
25 epoch
30
35
40
45
50
实数编码GA运行结果
四、多目标优化简介
一、问题定义
minF ( x) f1 ( x), f 2 ( x),..., f m ( x)
g i ( x) 0, i 1,2,..., I s.t. h j ( x) 0, j 1,2,..., J
模式阶用来反映不同模式间确定性
的差异，模式阶数越高，模式的确定性
就越高，所匹配的样本数就越少。在遗
传操作中，即使阶数相同的模式，也会
有不同的性质，而模式的定义距就反映 了这种性质的差异。
模式定理
• 模式定理：具有低阶、短定义距以及 平均适应度高于种群平均适应度的模式在 子代中呈指数增长。
•
模式定理保证了较优的模式（遗传算法 的较优解）的数目呈指数增长，为解释遗 传算法机理提供了数学基础。
变异前： 000001110000000010000 实数编码个体 变异后： • 如何决定哪个个体变异？ 如何变异？ 00000111000 1000010000
变异点
运行参数
• （1）M ： 种群规模（ 20-100 ） • （2）T ： 遗传运算的终止进化代数 （100～500） • （3）Pc ： 交叉概率 （0.4～0.9） • （4）Pm ： 变异概率 （0.001～0.01）
111010
平均适应度
35.75
第1代群体
第2代群体
模式的阶与定义距
– 模式 H 中确定位置的个数称为模式 H 的阶， 记作O(H)。例如O(10**1)=3 。 – 模式 H 中第一个确定位置和最后一个确定 位置之间的距离称为模式 H 的定义距，记 作δ(H)。例如δ(10**1)=4 。
模式的阶和定义距的含义
T
• • • •
具有多个目标函数。 各个函数之间在最优化方向上存在冲突。 往往需要人的参与。 目标函数集要么是求极大，要么是求极小， 两者只能取其一。
二、发展简史
法国经济学家V. Pareto，1896年提出
Von. Neumann和J. Morgenstern提出多目标决策问题， 1944年
T. C. Koopmans 多目标最优化问题 ，Pareto最优解概 念，1951年 H. W. Kuhn和A. W. T. Tucker 向量极值问题的Pareto最 优解的概念 Z. Johnsen系统地提出了关于多目标决策问题的研究 报告， 1968年
模式定理的含义
• 从模式定理可看出，有高平均适应度、
短定义距、低阶的模式，在连续的后代里
获得至少以指数增长的串数目，这主要是
因为选择使最好的模式有更多的复制，交
叉算子不容易破坏高频率出现的、短定义
长的模式，而一般突变概率又相当小，因
而它对这些重要的模式几乎没有影响。
积木块假设
• 积木块假设：遗传算法通过短定义距、 低阶以及高平均适应度的模式（积木块）， 在遗传操作下相互结合，最终接近全局最优 解。 模式定理保证了较优模式的样本数呈指 数增长，从而使遗传算法找到全局最优解的 可能性存在；而积木块假设则指出了在遗传 算子的作用下，能生成全局最优解。
max 进化算法的解更新过程示意
同时考虑最大化主产物浓度CB和最小化生产 时间tf
多目标优化方案的Pareto最优前沿
基本位变异算子
• 基本位变异算子是指对个体编码
串随机指定的某一位或某几位基因作变异
运算。对于基本遗传算法中用二进制编码 符号串所表示的个体，若需要进行变异操 作的某一基因座上的原有基因值为0，则 变异操作将其变为1；反之，若原有基因 值为1，则变异操作将其变为0 。
基本位变异算子的执行过程
• • • •
•
三、遗传算法的应用示例
测试函数
max f x1 , x2 i cosi 1x1 i i cosi 1x2 i
i 1 i 1 5 5
• Pc = 0.8; Pm = 0.05; b = 2; • popSize = 30; epochs = 50;
五、基于进化算法的求解方法 • 每轮迭代可以找到多个Pareto近似最优解 • 迄今为止还没有找到其他方法比EAs更能有 效地解决MOP问题。 • 在许多复杂应用问题中搜索最优解还存在 一定的困难。
如何使用GA求解多目标规划问题
• 适应度函数值 • 解集的均匀分布要求 • 对非劣解集的分析
min
GA的组成
（1）编码（产生初始种群） （2）适应度函数 （3）遗传算子（选择、交叉、变异）
（4）运行参数
编码
• GA是通过某种编码机制把对象抽象