以变异概率Pm改变染色体的某一个基因,当以二进制 编码时，变异的基因由0变成1，或者由1变成0。 平均约1-2%。
1
1
0
1
0
0
0
1
变异基因
变异基因
0
1
0
1
0
1
0
1
比起选择和交叉操作，变异操作是GA中的次要操作，但 它在恢复群体中失去的多样性方面具有潜在的作用
停止准则(Termination Criteria)
如何编码？
选 择
交 叉
变 异
遗传算法的基本操作
选择(selection):
根据各个个体的适应值，按照一定的规则或方法，从第t代群体 P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。
交叉(crossover):
将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个 概率Pc (称为交叉概率，crossover rate)交换它们之间的部分染色体。
在完全图中寻找 一个最小圈
旅行商问题的应用
例5. 碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军 事情报获取等领域都有着重要的应用。传统上，拼接复 原工作需由人工完成，准确率较高，但效率很低。特别 是当碎片数量巨大，人工拼接很难在短时间内完成任务。 随着计算机技术的发展，人们试图开发碎纸片的自动拼 接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片 （仅纵切），建立碎纸片拼接复原模型和算法，并针对 附件1、附件2给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干预，请写出干预 方式及干预的时间节点。复原结果以图片形式及表格形 式表达（见【结果表达格式说明】）。
适应函数(Fitness Function)
适应函数常见形式：
直接将目标函数转化为适应函数
• 若目标函数为最大化问题：
Fitness(f(x)) = f(x)
• 若目标函数为最小化问题：
Fitness(f(x)) = -f(x)
适应函数(Fitness Function)
界限构造法
• 目标函数为最大化问题
选择(Selection)---轮盘赌演示
染色体被选的概率
染色体编号
1 01110 8
0.16 0.16
2 11000 15
0.3 0.46
3 00100 2
0.04 0.5
4 10010 5
0.1 0.6
5 01100 12
0. 24 0.84
6 00011 8
0.16 1
染色体
适应度 被选概率 累积
例子.单点交叉(1-point crossover)
随机产生一个交叉点 在交叉点位置分离双亲染色体 互换交叉点位置右边的基因码
父代 1 1 1 1 1 1 1 1 1 1 1 1
0
交叉点位置
0
0
0
0
0
0
0
0
0
0
0
子代
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
交叉(crossover处理—有约束最优化问题
有约束最优化问 题:
Minimize f ( x1 , x2 , xn ) gi ( x) 0, i 1, 2, , m hi ( x) 0, i 1, 2, , l li xi ui , i 1, 2, , n
方法一：把约束问题转化为无约束问题，在用无约束 问题方法求解，如罚函数法； 方法二：“巧妙”地设计交叉和变异方式，尽量避免 后代跑出可行域。
f ( x) Cmin , f ( x) Cmin Fitness( f ( x)) 0， others
其中Cmin为f(x)的最小估计值 • 目标函数为最小化问题
Cmax f ( x), f ( x) Cmax Fitness( f ( x)) 0， others
变异（基因突变）
生物进化与遗传算法对应关系
生物进化
个体 个体的竞争力
遗传算法
问题的一个解 适应函数
适者生存
染色体
适应值最大的解被保留的概率最大
解的编码
基因
群体
编码的元素
被选定的一组解
种群
交叉 变异
根据适应函数选择的一组解
以一定的方式由双亲产生后代的过程 编码的某些分量发生变化的过程
例子求函数f(x)=x2的最大值，x为自然数且0≤x≤31.
贪婪算法
min f(x)=xcos(πx) s.t. 0<x<6.
局部最优解 全局最优解
X=1.09
X=3.03
X=6
X=5.02
贪婪算法
“困于”局部最优； 过分依赖初始点的选取；
智能优化算法
应对困于局部最优的问题； 应对大规模穷举带来的计算时间过长的 问题
2017/1/
问题
传统算法寻找附近的局部最小值（以 求目标函数极小为例）
TSP复杂性
搜索空间庞大
TSP涉及求多个变量的函数的最小值，求解很困难。 其可能的路径条数随着城市数目n成指数增长，如， 5个城市对应12条路径；10个城市对应181 440条 路径；100个城市对应4.6663X10155条路径。如此 庞大的搜索空间，常规解法和计算工具都遇到计算上 的困难。只能寻找近似解法。
被选的染色体
随机数
0.27
0.93
0.45
0.70
0.13
0.56
所选号码
2
6
00011
2
11000
5
01100
1
01110
4
10010
所选染色体 11000
选择(Selection)
其他选择法：
随机遍历抽样(Stochastic universal sampling) 局部选择(Local selection) 截断选择(Truncation selection) 竞标赛选择(Tournament selection)
其中Cmaxn为f(x)的最大估计值
选择(Selection)
选择(复制)操作把当前种群的染色体按与适应值成正比例 的概率复制到新的种群中 主要思想: 适应值较高的染色体体有较大的选择(复制)机 会 “轮盘赌”选择(Roulette wheel selection) 将种群中所有染色体的适应值相加求总和，染色体适应 值按其比例转化为选择概率Ps 求选择概率的累加序列 产生一个在0与总和之间的的随机数r 观察r落在累加序列的什么位置
交叉(crossover, Recombination)
从交配池中随机选取两个个体，以概率Pc(交叉概率) 进行遗传交叉(杂交、交配)。 交配后，产生两个具有双亲的部分基因特点的新染 色体. 交叉产生两个子染色体，他们与其父代不同，且彼 此不同，每个子染色体都带有双亲染色体的遗传基 因。
种群中个体的最大适应值超过预设定值 种群中个体的平均适应值超过预设定值 种群中个体的进化代数超过预设定值
基本步骤
约束的处理--无约束最优化问题
无约束最优化问题:
Min f ( x1 , x2 , xn )
GA编码：
st li xi ui i 1, 2,, n
X=(x1,x2,…,xn)的各个变量可以按二进制编码方法分别编码。 对于变量xi的上、下限约束li≤xi ≤ ui(i=1,2,…,n)，依据解 的精度要求(有效位数)求得各个变量X=(x1,x2,…,xn)的二进制
例子:部分匹配交叉(PMX)
双亲P1,P2随机选取两个交叉点，得到一个匹配段,根据交 叉点中间段给出映射关系。
P1
1 2 3 4 5 6 7 8 9 9 3 7 8 2 6 5 1 4
映射关系： 4 8、5 2、7 5
P2

交换两个交叉点之间的编码,(X表示未定码)
c1 c2
码位数(m1,m2,…,mn)(确定方法类似于SGA实例2)，因此将 n个二进制位串顺序连接起来，构成一个个体的染色体编码，编 码的总位数m＝m1+m2+…+mn。
2017/1/
约束的处理--无约束最优化问题
GA解码：
解码时仍按各个变量的编码顺序分别实现常规的二进制编码 解码方法。
二进制遗传编码示意图如下：
关于交叉概率：交叉概率Pc 一般范围为(60%, 90%)， 平均约80% 例如，交叉概率为0.8，则80%的“夫妻”会生育后 代。每两个个体通过交配产生两个新个体，代替原 来的“老”个体，而不交配的个体则保持不变。 GA利用选择和交叉操作可以产生具有更高平均适 应值和更好染色体的群体
变异(Mutation)
传统做法
生成新的点进行尝试； 评价函数； 如果改进了之前的解，则接受新的解.
2017/1/
智能优化算法
如果不想在局部困住，则： 不能贪婪，不能总是接受好的解； 对于新的解，即使比之前的差，有时也 会被接受. 采用随机搜索（按照某种机制） 本质上是对某种自然现象的模拟 对不同现象的模拟，启发了对不同机制 的设定
选择(Selection)---轮盘赌演示
设种群的规模为N xi是i为种群中第i个染色体
染色体xi被选概率
ps ( xi )
F ( xi )
F (x )
j 1 j
N
1/6 = 17%
A
B