s4 0.31
s30.06
s1 0.14 s2 0.49
赌轮选择示意
在算法中赌轮选择法可用下面的子过程来模拟:
① 在［0, 1］区间内产生一个均匀分布的随机数r。
② 若r≤q1,则染色体x1被选中。
③ 若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。 其中的 qi称为染色体xi (i=1, 2, …, n)的累计概率, 其计算 公式为
2014-2-27
遗传算法的起源
6
遗传算法的生物学基础
遗传学的基本结论
1. 生物的所有遗传信息都包含在其染色体中,染色体决定了生物的 性状 2. 染色体是由基因及其有规律的排列所构成.遗传和进化过程发生 在染色体上 3. 生物的繁殖过程是由基因的复制过程来完成的 4. 通过染色体间的交叉和变异会产生新的物种,使生物呈现新的性 状 5. 对环境适应性好的基因或染色体比适应性差的基因或染色体有更 多的机会遗传到下一代
遗传算法及遗传编程
Ⅰ遗 传 算 法
生物进化
什么是遗传算法 （Genetic Algorithm）
生命自从在地球上诞生以来，就开始了漫长的生
物演化历程，低级、简单的生物类型逐渐发展为 高级、复杂的生物类型。这一过程已经由古生物 学、胚胎学和比较解剖学等方面的研究工作所证 实。生物进化的原因自古至今有着各种不同的解 释，其中被人们广泛接受的是达尔文的自然选择 学说。 生物进化
选择方法
比例选择法（轮盘赌）
锦标赛选择法
比例选择法（轮盘赌）

基本思想
各个个体被选中的概率与其适应度大小成正比。 设群体大小为M，个体 i 的适应度大小为F ( xi ) ，则 个体i 被选中的概率为
Pi
F ( xi )
F (x )
i 1 i
M
比例选择法（轮盘赌）
①计算各基因适应度值和选择概率及累计概率
组成M/2对配对个体组，交叉操作就是在这些 配对个体组中的两个个体之间进行
二进制编码染色体的交叉
单点交叉
基因位数为 l ，交叉点k的范围为[1, l -1],在该点为分界相互交 换变量(保证第一个交叉点左边子串不交换)
例如：
子个体1 子个体2
0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0
最优解与具有最大适应值得个体相对应。 适应值能够反映个体质量的差异。 计算量应尽可能小

例:当优化问题为maxf(x),适应度函数可取为f(x)
当优化问题为minf(x),适应度函数可取为-f(x)
个体适应度评价
f ( x)
f ( x)
f ( x)
f ( x)
f ( x)
f ( x)
F（x）
2014-2-27
5
20世纪60年代中期，美国Michigan（密西 根）大学的John Holland提出了位串编码技 术，这种编码既适合于变异又适合杂交操 作，并且他强调将杂交作为主要的遗传操 作。随后，Holland将该算法用于自然和人 工系统的自适应行为的研究之中，并于 1975年出版其开创性的著作《Adaptation in Natural and Artificial Systems》。后来， Holland与他的学生们将该算法加以推广并 应用到优化及机器学习等问题之中，而且 正式定名为遗传算法。遗传算法的通用编 码技术及简单有效的遗传操作为其广泛的 应用和成功奠定了基础。
二进制编码染色体的交叉
多点交叉
多点交叉的破坏性可以促进解空间的搜索
二进制编码染色体的交叉
均匀交叉
两个配对个体的染色体每个基因位以相同的交叉概率进行交 换 具体步骤
随机产生一个与个体编码串长度等长的屏蔽字W＝ 12 l
按下列规则交叉两个父本的基因
若i=0，则父代第i个基因不相互交换 若i=1，则父代第i个基因相互交换

某个优化问题含有6个变量，则它的一个基因表达为
X: 2.50 9.54 3.25 0.25 4.25 7.00
对应的表现型为 x=[2.50,9.54,3.25,0.25,4.25,7.00]
编码与解码
符号编码
个体基因值取自一个无数值含意，而只有代码含义的符号集。 符号集可以是字母，也可以是数字序号。 如血型A，B，AB，O可以分别用[a,b,c,d]表示，或者 [a1,a2,a3,a4],也可表示为[1，2，3，4]

遗传算法基本要素与实现技术
个体适应度评价
为正确计算个体的遗传概率，个体的适应度必须为正 数或者为零，不能为负数。 适应函数的作用是对每一个个体指定一个适应值，使 得我们可以区分种群中个体的好坏，适应值越大，个体越 好，反之。适应函数是区分种群中个体好坏的唯一方式， 是进行选择的基础。
设计适应函数遵循原则
二进制编码染色体的变异
具体步骤

随机产生一个与个体编码串长度等长的屏蔽字W＝ 12 l i 为[0,1]间的随机数 按下列规则对基因进行变异

i Pm，则父代基因第i位变异 若
i > Pm，则父代基因第i位不变异 若
浮点编码染色体的变异
浮点编码变异
算法中的一些控制参数：
遗传算法的生物进化模型
选择 遗传 变异
优胜劣汰 保持特性 产生新特性
ห้องสมุดไป่ตู้
遗传算法的基本术语

编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射


解码：从遗传域到问题域的映射。即将DNA序列解释成个体的性状
适应度：种群的某个个体对生存环境的适应程度。适应度高的个体 可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比 较少，甚至逐渐灭绝 选择：以一定概率从种群中选择若干个体的操作。一般而言，选择 就是基于适应度的优胜劣汰的过程 交叉：在一个或多个染色体的相同位置处被切断，分别交换组合形 成新的染色体
均匀交叉
例如
浮点编码染色体的交叉
线性交叉
交叉公式
子个体＝父个体1*f＋父个体2*(1-f)
f为[0,1]间的均匀分布随机数
遗传算法基本要素与实现技术
变异算子
将个体染色体编码串中的某些基因位编码与字符集 的其它字符替换
二进制编码染色体的变异
编码字符集为{0,1},变异操作就是将变异点上的基因 取反（即若是1，则取0，若是0，则取1） 变异点是按概率Pm在染色体基因位上指定的
②在［0, 1］区间内产生一个均匀分布的随机数r。
③ 若r≤q1,则染色体x1被选中。
若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。
qi P( x j )
j 1
i
比例选择法（轮盘赌）
举例
染色体的适应度和所占的比例
锦标赛选择法
基本思想
每次随机选取K个个体，比较之后选择其中适应度最高 的个体做为下一代种群的父体，这个过程反复进行N次。

编码公式
U max U min
2l 1
l
解码公式
x U min ( bi 2
i 1
i 1
U max U min ) 2l 1
编码与解码


浮点编码
个体的基因值用某一范围内决策变量的一个浮点数来表示， 个体的编码长度等于其决策变量的个数。 浮点编码使用的是决策变量的真实值
遗传算法基本要素与实现技术

交叉算子
选择是对优秀个体的复制，不能产生新个体，交叉对相互 配对的染色体按某种方式相互交换其部分基因，从而形成 两个新的个体。交叉操作是产生新个体的主要方法

主要关注
1. 2. 3.
如何对染色体进行配对 如果确定交叉点的位置 如何进行部分基因交换
随机配对
将选择出的种群中的M个个体以随机的方式
再计算种群S1中各个体的选择概率。 选择概率的计算公式为
P ( xi ) f ( xi )
f (x )
j 1 j
N
由此可求得 P(s1) = P(13) = 0.14
P(s2) = P(24) = 0.49
P(s3) = P(8) = 0.06
P(s4) = P(19) = 0.31
● 赌轮选择法
(3) 计算各代种群中的各个体的适应度 , 并
对其染色体进行遗传操作,直到适应度最高的个
体(即31（11111）)出现为止。
首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361
■ M ：种群规模
■ T ：最大换代数
■
一般为20-100
一般为100-500
Pc ：交叉率(crossover rate)就是参加交叉运 算的染色体个数占全体染色体总数的比例，取 值范围一般为0.4～0.99。 rate)是指发生变异的基 因位数所占全体染色体的基因总位数的比例， 取值范围一般为0.0001～0.1。


遗传算法的基本思想
遗传算法基本要素与实现技术
编码与解码 问题域（解空间） 优化变量 二进制编码 浮点数编码 符号编码 . . .
映射
遗传域（基因空间） 优化变量的代码表示
编码与解码
二进制编码

二进制编码是遗传算法中最常用、最原始的一种编码方法，它将 原问题的解空间映射到二进制空间上，然后进行遗传操作。找到 最优个体后再通过解码过程还原原始的数据形式。 二进制编码的串长度 l 取决于求解的精度