基本位变异算子
•
基本位变异算子是指对个体编码
串随机指定的某一位或某几位基因作变异
运算。对于基本遗传算法中用二进制编码
符号串所表示的个体，若需要进行变异操
作的某一基因座上的原有基因值为0，则
变异操作将其变为1；反之，若原有基因
值为1，则变异操作将其变为0 。
基本位变异算子的执行过程
• 变异前：
变异点
平均适应度 58.75
第1代群体
第2代群体
模式的阶与定义距
– 模式 H 中确定位置的个数称为模式 H 的阶， 记作O(H)。例如O(10**1)=3 。
– 模式 H 中第一个确定位置和最后一个确定 位置之间的距离称为模式 H 的定义距，记 作δ(H)。例如δ(10**1)=4 。
模式的阶和定义距的含义
几个术语 个体（染色体）
• 基因型：1000101110110101000111
• 缺点是什么？
基因
解码
多维优化如何编码？ 编码
• 表现型：0.637197
初始种群
• GA可采用随机方法生成若干个个体 的集合，该集合称为初始种群。初 始种群中个体的数量称为种群规模。
如何随机生成？
适应度函数
• 遗传算法对一个个体（解）的好坏用适应 度函数值（通常为正实数）来评价，适应 度函数值越大，解的质量越好。适应度函 数是遗传算法进化过程的驱动力，也是进 行自然选择的唯一标准，它的设计应结合 求解问题本身的要求而定。
模式定理的含义
• 从模式定理可看出，有高平均适应度、 短定义距、低阶的模式，在连续的后代里 获得至少以指数增长的串数目，这主要是 因为选择使最好的模式有更多的复制，交 叉算子不容易破坏高频率出现的、短定义 长的模式，而一般突变概率又相当小，因 而它对这些重要的模式几乎没有影响。
积木块假设
•
积木块假设：遗传算法通过短定义距、
min F(x) f1(x), f2 (x),...,fm (x)T
s.t.hgji
(x) (x)

0, 0,
i 1,2,...,I j 1,2,...,J
• 具有多个目标函数。 • 各个函数之间在最优化方向上存在冲突。 • 往往需要人的参与。 • 目标函数集要么是求极大，要么是求极小，
模式阶用来反映不同模式间确定性 的差异，模式阶数越高，模式的确定性 就越高，所匹配的样本数就越少。在遗 传操作中，即使阶数相同的模式，也会 有不同的性质，而模式的定义距就反映 了这种性质的差异。
模式定理
• 模式定理：具有低阶、短定义距以及 平均适应度高于种群平均适应度的模式在 子代中呈指数增长。
• 模式定理保证了较优的模式（遗传算法 的较优解）的数目呈指数增长，为解释遗 传算法机理提供了数学基础。
低阶以及高平均适应度的模式（积木块），
在遗传操作下相互结合，最终接近全局最优
解。
•
模式定理保证了较优模式的样本数呈指
数增长，从而使遗传算法找到全局最优解的
可能性存在；而积木块假设则指出了在遗传
算子的作用下，能生成全局最优解。
三、遗传算法的应用示例
5
5
测试函数 max f x1, x2 i cosi 1x1 i i cosi 1x2 i
占优的解组成的一组解。当P是整个搜索空间时，所得的非劣解 集P’被称为Pareto最优解集。
若目标函数中有冲突，则一般不存在唯一最优解，而存在 若干个可行解。
f2
Min [f1, f2]
X A
B Y
C
解点A, B, C是Pareto最优点 A Pareto支配X C Pareto 支配Y
f1
Pareto最优解示意图 Pareto最优解不一定对其他所有解占优，但是所有其他解 都不能对它占优。
• 11100|00000111111000101
• 交叉后：如何•决实定数哪编对码个如体何应交交叉叉？？ • 00000|00000111111000101
• 11100|01110000000010000
变异算子
• 所谓变异运算，是指依据变异概率 Pm 将个 体编码串中的某些基因值用其它基因值来替 换，从而形成一个新的个体。遗传算法中的 变异运算是产生新个体的辅助方法，它决定 了遗传算法的局部搜索能力，同时保持种群 的多样性。交叉运算和变异运算的相互配合， 共同完成对搜索空间的全局搜索和局部搜索。 GA中变异算子可采用基本位变异算子。
Z. Johnsen系统地提出了关于多目标决策问题的研究 报告， 1968年
三、多目标优化的最优性判断
1 由人来判断（非Pareto机制） • 基本原则：通过加入决策者判断，缩小
多目标问题有效解集的范围。
2 不由人来判断(Pareto optimality) • 基本原则：多目标问题优化解的自身特
3、轮盘赌选择方法的实现步骤
• （1） 计算群体中所有个体的适应度函数值 （需要解码）；
• （2） 利用比例选择算子的公式，计算每个 个体被选中遗传到下一代群体的概率；
• （3） 采用模拟赌盘操作（即生成0到1之间 的随机数与每个个体遗传到下一代群体的 概率进行匹配）来确定各个个体是否遗传 到下一代群体中。
性来搜索多目标问题有效解集的范围。
由人来判断
• 加权: 由决策者决定每个目标函数不同的 权重因子，将所有的目标函数整合为一个 目标函数。
• 目标规划：由决策者确定每个目标函数所 能达到的目标值，然后将这些值作为附加 的约束整合进问题中，从而优化目标转换 为最大或最小化目标值和目标函数值之间 的绝对偏差。
1、个体被选择概率的计算
被选择概率
1
2
3
4
0 0.144
0.636 0.691
1
各个体被分配的区间
2、轮盘赌选择方法（或 比例选择算子）
各个体区间 有序随机数
1
2
0 0.144
0.2311
3
4
0.636 0.691
1
0.4860 0.6068 0.9501
产生随机数
0.9501 0.2311 0.6068 0.4860
交叉算子
•
所谓交叉运算，是指对两个相互配
对的染色体依据交叉概率 Pc 按某种方式相
互交换其部分基因，从而形成两个新的个
体。交叉运算是遗传算法区别于其他进化
算法的重要特征，它在遗传算法中起关键
作用，是产生新个体的主要方法。 GA中交
叉算子可采用单点交叉算子。
单点交叉运算示例
• 交叉前：
交叉点
• 00000|01110000000010000
• 000001110000000010000
• •
变 00异00后0实•1如：数1如何1编0何变0码决0异1个定0？0体哪00个10个0体00变异？
运行参数
• （1）M ： 种群规模（ 20-100 ） • （2）T ： 遗传运算的终止进化代数
（100～500） • （3）Pc ： 交叉概率 （0.4～0.9） • （4）Pm ： 变异概率 （0.001～0.01）
同时考虑最大化主产物浓度CB和最小化生产 时间tf
多目标优化方案的Pareto最优前沿
•人有了知识，就会具备各种分析能力， •明辨是非的能力。 •所以我们要勤恳读书，广泛阅读， •古人说“书中自有黄金屋。 •”通过阅读科技书籍，我们能丰富知识， •培养逻辑思维能力； •通过阅读文学作品，我们能提高文学鉴赏 •培养文学情趣； •通过阅读报刊，我们能增长见识，扩大自 •有许多书籍还能培养我们的道德情操， •给我们巨大的精神力量，
SGA的框图
产生初始群体
是
输出结果并结束
是否满足停止准则
否
计算个体适应度值
执行M/2次
比例选择运算 单点交叉运算
基本位变异运算
产生新一代群体
遗传算法的特点
• （1）群体搜索，易于并行化处理； • （2）不是盲目穷举，而是启发式搜索； • （3）适应度函数不受连续、可微等条件的
约束，适用范围很广。
适应度函数的编制影响求解效果
选择算子
• 遗传算法使用选择运算来实现对群体中的 个体进行优胜劣汰操作：适应度高的个体 被遗传到下一代群体中的概率大；适应度 低的个体，被遗传到下一代群体中的概率 小。选择操作的任务就是按某种方法从父 代群体中选取一些个体，遗传到下一代群 体。GA中选择算子可采用轮盘赌选择方法。
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）。
0.2311<0.144 ?最终否选择了个体3个1落个选体2，01.2个311个<0.体6364? 是
是
个体2入选
0.4806<0.636 ?
个体2入选
是 0.6068<0.636 ?
个体2入选
否
个体3落选
0.9501<0.691 ?
是 0.9501<1 ?
个体4入选
0.9501<0.636 ? 否 个体2落选
遗传算法简介
主要内容 1、遗传算法的原理和组成； 2、遗传算子； 3、遗传算法的实现； 4、遗传算法的数学理论； 5、遗传算法的应用。
一、遗传算法（Genetic algorithm，GA）
GA的寻优机制
GA模拟自然选择和自然遗传过程中发生的 繁殖、交叉和基因突变现象，在每次迭代中都 保留一组候选解美，国并J按. H某o种lla指nd标教从授解群中选取 较优的个体，利用遗传19算75子年(选择、交叉和变异) 对这些个《体自进然行界组和合人，工产系生新统一的代适的应候性选》解群， 重复此过程，直到满足某种收敛指标为止。