1、1,第三章 遗传算法,2,第三章 遗传算法,一.导言 二.Holland的基本GA 三.计算举例 四.Holland的结构理论 五.GA的各种变形 六.应用 七.学习GA的几点体会,3,遗传算法(GA)的产生1975年，Holland提出GA著名的书：Adaptation in Natural and Artificial System(中文名称：自然与人工系统中的自适应性)后来，DeJong和Goldberg做了大量工作，使GA更加完善。,一.导言（1）,4,遗传算法(GA)的来源：遗传学的“优胜劣汰”“自然选择”的思想。缺点：体现不出人的主动干预 ；来源的方法有以下几个： 定向培育 随机算
2、法网格法,一.导言（2）,5,定向培育过程如下：第一：一个种群，大量的生物个体；第二：选择具有需要特性的若干个体；第三：进行繁殖；第四：重复第二，直到满意为止。,一.导言（3）,6,随机算法：在解空间随机产生多个解，选择最好的 网格法：根据最好解的几何分布，来不断的缩小搜索范围。,一.导言（4）,7,遗传算法的基本思想 根据问题的目标函数构造适值函数(Fitness Function)； 产生一个初始种群 (100-1000，或更小更大)； 根据适值函数的好坏，不断选择繁殖； 若干代后得到适值函数最好的个体即最优解。,一.导言（5）,8,遗传算法的构成要素 种群(Population), 种群
3、大小(Pop-size) 基因表达法编码方法(Encoding Scheme; Gene Representation),一.导言（6）,9,遗传算子(Genetic Operator)：交叉(Crossover)，变异(Mutation) 选择策略:一般为正比选择 停止准则(Stopping Rule/Criterion):一般是指定最大代数,一.导言（7）,10,算法框架与步骤见下页,二.Holland的基本GA（1）,11,二.Holland的基本GA（2）,12,解空间与编码空间的转换遗传运算是对编码空间操作的，所以要进行 两个空间的转换。见下页示意图,二.Holland的基本GA（3
4、）,13,二.Holland的基本GA（4）,14,各个步骤的实现 初始种群的产生 编码方法 适值函数 遗传运算 选择策略 停止准则,二.Holland的基本GA（5）,15,初始种群的产生随机产生(依赖于编码方法)；种群的大小(依赖于计算机的计算能力和计算复杂度)。 例：0,1编码产生 ， 0.5， =1；0.5， =0,二.Holland的基本GA（6）,16,编码方法二进制编码二进制编码，用0，1字符串表达。例：0110010，适用以下三种情况 背包问题： 1，背；0，不背,二.Holland的基本GA（7）,17,实优化：精度高时编码长，一般不采用此法而用实值函数。 指派问题 二进制编
5、码缺点：编码长不利于计算； 二进制编码优点：便于位值计算，包括的实数范围大,二.Holland的基本GA（8）,18,适值函数根据目标函数设计适值函数 是标定(Scaling)目标函数 获得的采用方法 或 。 遗传运算(遗传算法的精髓)交叉和变异下面我们就介绍一下交叉和变异,二.Holland的基本GA（9）,19,交叉(Crossover) 单切点交叉 随机产生一个断点(Cutting Point)1，n-1 例：,二.Holland的基本GA（10）,20,双切点交叉(交换中间段)例：不是所有点都交叉，设定一个交叉概率 ，一 般为0.9,二.Holland的基本GA（11）,21,变异(M
6、utation) 初始种群中没有需要的基因，在种群中按变异 概率 任选若干位基因改变位值01或10， 有意想不到的结果， 一般设定得比较小，在 5%以下。,二.Holland的基本GA（12）,22,选择策略最常用的正比选择(Proportional Selection) 对于个体 ，适值 ，选择概率如下式可计算NPNumber of Population,二.Holland的基本GA（13）,23,得到选择概率后，我们采用旋轮法(Roulette Wheel) 令 ， 随机产生 当 ，选择个体,二.Holland的基本GA（14）,24,如下图所示:注： 优良种得到较多的繁殖机会，后代很 像
7、 ； 而很可能失去繁殖的机会。,二.Holland的基本GA（15）,25,停止准则 指定最大代数(NGNumber of Max Generation)很少用 ，麻烦,二.Holland的基本GA（16）,26,例1： ， ，NP=5 简单分析： 编码为五位的0，1编码，推导如下 设编码长度 ，取决于 ，令 即： =5,三.计算举例（1）,精度,27,，最大值，最小值,三.计算举例（2）,28,步骤： 产生初始种群NG=10,t=0 判断停止准则 计算适值 用旋轮法正比选择,三.计算举例（3）,29,计算生成的列表：,三.计算举例（4）,表1 表2,30,观察结果 整个种群在改善 ：2325
8、 2992 模板 0较好，而 1 较差 “好坏”数量的变化 ：2 3 ； ：3 2,三.计算举例（5）,31,结果(3)数量变化可由表1中的数据推导出：同理：=0.9 =0.02,三.计算举例（6）,32,双亲的选择方法： 随机选：产生 ， 比例选:产生 ，当 ，选择个体 父亲优选，母亲随机选：选 ，,三.计算举例（7）,33,又称模板理论(Schema Theory) 1.模板的概念：若干位确定，若干位不确定的一类个体的总称，用表示，如0和1 。,四.Holland的结构理论（1）,34,模板的长度 ： 模板第一个确定位与最后一个确定位之间的长度。 模板的阶数 ：模板中确定位的个数。例如：
9、110 ， =4， =3,四.Holland的结构理论（2）,35,常识： n位编码总长n-1; 阶数为 的概型， 中的个体总数为 ; 对于一个n位二进制表达，染色体长度为n模板数个体数( ) ，即分类方法数个体总数。 因模板因子、个体因子分别为(0，1， )、 (0，1) 。,四.Holland的结构理论（3）,36,模板理论 引理1：在正比选择下，模板在第 代的期望 个体数为： 其中 是 第 代 模板中所有个体的适值均值与种群中所 有个体的适值均值的比， 是第 代 的个 体数。 如例1中： 0 ，=1.4858， =2， =3,四.Holland的结构理论（4）,37,证明：,四.Holl
10、and的结构理论（5）,38,注释: 种群的适值和为： ，则选择概率为：为 中的个体总数，且 下标随遗传的进行而变化；,四.Holland的结构理论（6）,39,为 模板中所有个体的适值均值;为种群的适值均值 只要均值 1，则好的种群的个体会越来越多。 问题：以上证明没有考虑交叉变异，那么交叉变异会不会破坏种群模板 ？概率有多大？,四.Holland的结构理论（7）,40,引理2：第 代以概率 做交叉，对长度为 的概型 ，则在第 代中个体数为概型 的概 率下界为：其中 为第 代个体为 的概率。,四.Holland的结构理论（8）,41,引理2的证明 证明：交叉破坏 的条件 做了交叉： 交叉点在
11、 内: 配偶 不在 中： 则不被破坏的概率：,四.Holland的结构理论（9）,42,思考：若 不属于概型 ，是否能产生后代为概型 ？答案：可以,四.Holland的结构理论（10）,43,引理3：若第 代以 做变异，对于一个阶数为 的模板 ,则在第 代仍为 的概率的下界 为： 证明：对于 ，当 =1，不破坏的概率为 当 1，不破坏的概率为 取其泰勒展开式的第一项：,四.Holland的结构理论（11）,44,主定理(概型定理)： 第 代以概率 和 做交叉和变异时，长度 为 ，阶数为 ，适值均值比为 的概 型 在第 代的期望个体数的下界为：当 时， 随代数 的增加而增加。,四.Holland
12、的结构理论（12）,45,其它编码方法 顺序编码：用1到N的自然数的不同顺序来 编码，此种编码不允许重复，即 且 ，又称自然数编码。 该法适应范围很广：指派、旅行商问题，单机调度。 合法性问题：是否符合采用的编码规则的问题,五.GA的各种变形（1）,46,实数编码 特征：方便运算简单，但反映不出基因的特征 整数编码应用于新产品投入，时间优化，伙伴挑选 例：3212345 对顺序编码来说是不合法的，而 对整数编码来说是合法的；010200不合法的01 编码；,五.GA的各种变形（2）,47,练 习（1）,对于编码长度为7的01编码，判断以下编码的合法性 (1) 1 0 2 0 1 1 0 , (
13、2) 1 0 1 1 0 0 , (3) 0 1 1 0 0 1 0 , (4) 0 0 0 0 0 0 0 , (5) 2 1 3 4 5 7 6 .,48,练 习（2）,对于编码长度为7的顺序编码，判断以下编码的合法性 (1) 7 1 2 0 4 3 5 , (2) 1 3 6 2 4 7 , (3) 2 1 3 5 4 7 6 , (4) 8 1 4 3 2 5 7 , (5) 2 1 3 2 5 7 6 .,49,练 习（3）,对于编码长度为7的实数编码，判断以下编码的合法性 (1) 3.5 1.9 2 7 1.8 1.7 0 , (2) 89.05 4.78 2 1 4.3 6.9
14、, (3) 0 1 1 0 0 1 0 , (4) 0 0 0 0 0 0 0 , (5) 2 1 3 4 5 7 6 .,50,遗传运算中的问题在顺序编码遗传运算的过程中会遇见不合法 的编码，应对的策略有二:拒绝或修复。 例如：经交叉后，后代编码不合法21 345 67 21 125 6743 125 76 43 345 76 我们采用下面的修复策略使以上的编码合法。,五.GA的各种变形（3）,51,顺序编码的合法性修复： 交叉修复策略它分为以下几种 部分映射交叉 顺序交叉 循环交叉,五.GA的各种变形（4）,52,部分映射交叉(PMX)( Partially Mapped Crossove
15、r) PMX步骤： 选切点X,Y； 交换中间部分； 确定映射关系； 将未换部分按映射关系恢复合法性。,五.GA的各种变形（5）,53,PMX例题：,五.GA的各种变形（6）,54,顺序交叉( OX )Order Crossover OX步骤： 选切点X,Y； 交换中间部分； 从切点Y后第一个基因起列出原序，去掉已有基因； Y后第一个位置起填入。,五.GA的各种变形（7）,55,OX例题：,五.GA的各种变形（8）,56,OX的特点： 较好的保留了相邻关系、先后关系满足了TSP 问题的需要，但不保留位值特征。,五.GA的各种变形（9）,57,循环交叉(CX) Cycle Crossover 基本
16、思想：子串位置上的值必须与父母的相同 位置上的位值相等。 CX步骤： 选 的第一个元素作为 的第一位，选 的第一个元素作为 的第一位；,五.GA的各种变形（10）,58, 到 中找 的第一个元素赋给 的相对位置，重复此过程，直到 上得到 的第一个元素为止，称为一个循环； 对最前的基因按 、 基因轮替原则重复以上过程； 重复以上过程，直到所有位都完成。,五.GA的各种变形（11）,59,CX 例题：,五.GA的各种变形（12）,60,CX的特点： 与OX的特点不同的是， CX较好的保留了位值 特征，适合指派问题；而OX较好的保留了相邻 关系、先后关系满足了TSP问题的需要。,五.GA的各种变形（
17、13）,61,练 习,P1： 6 1 2 8 9 5 4 7 10 3 P2： 10 7 4 1 3 6 2 8 5 9 PMX： C1： C2：OX： C1： C2:,62,练 习（2）,P1： 6 1 2 8 9 5 4 7 10 3 P2：10 7 4 1 3 6 2 8 5 9 CX： C1： C2：,63,变异的修复策略 换位变异(最常用)例：4 3 1 2 5 6 7 4 5 1 2 3 6 7 移位变异：任选一位移到最前例：4 3 1 2 5 6 7 5 4 3 1 2 6 7,五.GA的各种变形（14）,64,实数编码的合法性修复交叉 单切点交叉,五.GA的各种变形（15）,切
18、点,65,双切点交叉(与单切点交叉类似)该方法最大的问题：如何在实优化中保持 可行性。,五.GA的各种变形（16）,66,凸组合交叉约束是个凸集，可行性可以保持，问题是分散 性太差，向中间汇集的问题需要解决。,五.GA的各种变形（17）,67,变异 位值变异：任选一位加，例：,五.GA的各种变形（18）,68,向梯度方向变异 缺点：只能用于目标函数可微的问题例:,五.GA的各种变形（19）,69,适值函数的标定(Scaling),五.GA的各种变形（20）,70,标定的目的：使适值函数不会太大，有一定差别 选择压力的概念：选择压力是种群中好、坏个体被选中的概率之差，差大称为选择压力大。,五.G
19、A的各种变形（21）,71,局部搜索、广域搜索与选择压力的关系局部搜索与广域搜索是GA中的一对矛盾， 好的算法要将以上二者综合考虑。算法开始重 广域搜索，选择压力小；随迭代进行，逐步偏 重于局部搜索，选择压力大。,五.GA的各种变形（22）,72,适值的标定方法 线性标定：函数表达式 , 为目标函数， 为适值函数,五.GA的各种变形（23）,73,对 ，=1， = ，函数表达式 ： +， 对 ， =-1， = , 函数表达式： +，,五.GA的各种变形（24）,74,动态线性标定(最常用) 优点：计算容易不占用时间函数表达式： ， 为迭代指标 最常用极大化：=1 , 函数表达式：,五.GA的各
20、种变形（25）,75,加入的意义：加入使最坏个体仍有繁殖的可能， 随 而减小 的取值：， ， ，调节 和 ，从而来调节,五.GA的各种变形（26）,76,引入目标的目的：调节选择压力，即好坏个体选择概率的 差，使广域搜索范围宽保持种群的多样性，而 局域搜索细保持收敛性。如下图表示：开始：希望选择压力小后来：希望选择压力大,五.GA的各种变形（27）,77,幂律标定：函数表达式： 的取值， 1时选择压力加大1时选择压力减小 对数标定：函数表达式：对数标定的作用：缩小差别,五.GA的各种变形（28）,78,指数标定：函数表达式：对数标定的作用：扩大差别 窗口技术：函数表达式：为前W代中的最小目标值
21、，它考虑了各代 的波动，这样 具有记忆性,五.GA的各种变形（29）,79,正规化技术：函数表达式：正规化技术的作用：将 映射到(0,1)区间，抑制超级染色体正规化技术的实质：特殊的动态标定即其中：,五.GA的各种变形（30）,80,选择策略传统的GA选择和遗传是一起进行的，即使 后代不如父代，却无法纠正。下面介绍的选择 策略都是先遗传后选择。这样，样本空间扩大 了，可供选择的个体增多了。,五.GA的各种变形（31）,81,截断选择：选择最好的前T个个体，让每一个有1/T的选择概率，平均得到NP/T个繁殖机会。 例：NP=100,T=50 即100名学生，成绩前50名的选出。每人的选择概率为1
22、50，有平均2个机会。 这种方法计算量在排序上。,五.GA的各种变形（32）,82,顺序选择： 步骤： 从好到坏排序所有个体 定义最好个体的选择概率为 ,则第 个个体的选择概率为：,五.GA的各种变形（33）,83, 由于有限时要归一化，则有下面的两个公式：顺序选择的缺点：把选择概率固化了，选择压力不可调,五.GA的各种变形（34）,84,举例:且：采用旋轮法，随机产生 当 ，选择个体,五.GA的各种变形（35）,85,正比选择：令： ， 用动态标定来调节选择压力，采用旋轮法来共 同完成种群的选择。,五.GA的各种变形（36）,86,停止准则 指定最大代数 检查种群中适值的一致性，保持历史上最
23、好的个体。计算公式：或 第二种方法因很难实现，所以很少使用。,五.GA的各种变形（37）,87,背包问题个物品，对物品 ，价值为 ，重量为 ， 背包容量是 。如何选取物品装入背包，使背 包中的价值最大。,六.应用（1）,88,模型:，装入物品 ，不装入物品,六.应用（2）,89,如何处理约束来保持可行性 拒绝策略： 可行解不易达到时，很难达到一个初始种群 修复策略： 将不可行解修复为可行的，但将失去多样性。,六.应用（3）,90,惩罚策略：设计惩罚函数，但设计不好会掩盖目标函 数的优化。下面，我们将分别采用惩罚策略及优先适 合启发式来处理上面的背包问题。,六.应用（4）,91,罚函数法 令适值
24、函数 ，其中 是目标函数 令 ，其中 注： 与 是 的两个端点,六.应用（5）,92,函数式的意义： 的作用是使 ，保证 可行也罚，只有当 不罚。 罚函数法目的：把解拉向边界，尽量装满。,六.应用（6）,93,解码法解码法是修复程序(修复可行性的方法) 步骤： 将选上物品按 降序排列； 选前 个物品，使 ； 解码法的关键：如何在GA中解决可行性问题 编码方法：采用顺序编码 First Fit Heuristic(优先适合启发式),六.应用（7）,94,例： =7 用顺序( 3 2 1 5 4 6 7 )表示选择物品的顺序 用优先适合启发式保留前K位，使解可行即：=3， ( 3 2 5 ) 问题
25、：编码长度是可变的，如何做交叉和变异,六.应用（8）,95,变长顺序编码的遗传算法插入式交叉算法 在 上选一个随机的断点； 在 上随机选一个基因片断插入 的断点处； 去掉 上的重复基因； 按优先适合启发式得到可行解 见下页例题,六.应用（9）,96,例题：,六.应用（10）,97,最小生成树问题(Minimum Spanning Tree) 问题的提出 难点：对于下面的红色的图形，如何设计 一个合适的编码方法？,六.应用（11）,98,传统的编码方法： 节点表示法：无法避免回路，很难做遗传运算，如：(1,2),(2,3),(2,5),(2,6),(4,6),六.应用（12）,99,边编码法：无
26、法保证是树无法保证可行性1,2,4,5,10 缺点：麻烦，无法做遗传运算，无法保持合法性,六.应用（13）,100,为解决以上问题，人们提出了最小生成树 的(Prfer数)的编码方法。 最小生成树的定义：用n-2位自然数唯一的表达出一棵n个节点的 生成树，而且交叉变异仍是一棵生成树。,六.应用（14）,101,叶子：树中度数为1的节点 例如：1，3，4，5最小生成树应用条件： 覆盖所有顶点 连通的 没有回路,六.应用（15）,102,编码步骤 设节点i是标号最小的叶子 令j是编码中的第一个数字，若i与j相连 删去边(i , j) 转,直到剩下一条边为止,六.应用（16）,103,图解：i=1,
27、( i , j )=(1,2),j=2 ; i=3,( i , j )=(3,2) , j=2i=4,( i , j )=(4,6),j=6 ; i=5,( i , j )=(5,2), j=2 编码：（2 2 6 2）,六.应用（17）,104,解码步骤 令Prfer数中的节点集为 ,不包含在 中的节点集为 ； 若i为 中最小标号的节点，j为 上最左边数字连接边(i , j)，并从 中去掉i，从 中去掉j，若j不再在 中，将j加入 中。,六.应用（18）,105,重复，直到 中没有节点(即为空)， 中剩下(s,r) 连接(s,r) 图解过程见下页,六.应用（19）,106,例： = 2，2，
28、6，2， = 1，3，4，5(1,2) = 2，6，2， = 3，4，5(3,2) = 6，2， = 4，5(4,6) = 2， = 5，6(5,2) = ， = 2，6,六.应用（20）,107,最小生成树的的优点： 对于一个 个节点的Prfer数的个数为 ，生成树的个数也是 。 最小生成树实现了解空间和编码空间的一一对应，交叉变异不破坏合法性。 一个好的编码方法对遗传算法至关重要。,六.应用（21）,108,1,7,6,5,2,3,4, 2 3 2 4 4 ,练习:,109,1,7,5, 6 3 2 4 4 ,P= 1 5 7 ,4,2,3,6,练习:,110,作业: 为极大化权和的匹配问
29、题设计一种编码方式,1,2,3,4,5,6,1,2,4,3,5,7,6,8,9,10,111,二次指派问题机器布置问题(QAP) 机器布置问题 Facility Layout Quadratic Assignment Problem,六.应用（22）,112,问题的提出：台机器，要布置在 个地方，机器i与k之 间的物流量为 ，位置j与L之间的距离为 ， 如何布置使费用最小。 设： 表示机器i布置在位置j；其它。 同理对 。,六.应用（23）,113,数学模型：二次0-1规划,六.应用（24）,114,用GA求解 编码顺序编码表示机器i 放在位置 ， 是1到n中的数 如： 4 , 3 , 1 ,
30、 2 , 5 机器1放在位置4；机器2放在位置3；机器3放在位置1； ；,六.应用（25）,115,该编码的优点：没有重复，保证了编码的合法性,六.应用（26）,116,函数表达式变为：优点：使其更加简洁，便于计算。 缺点：变量出现在下标，任何数学规划不可用 解决方法：遗传算法(GA),六.应用（27）,117,用GA求解的设定 编码方法：顺序编码 适值公式： 动态线性标定：其它：用CX做交叉；换位变异；正比选择，就可以解决该问题。,六.应用（28）,118,编码是成功的关键(如最小树问题) 最好能使编码空间与解空间一一对应 减少编码冗余，编码应尽可能短 便于遗传运算有利于保持合法性、可行性实
31、在没有办法保持，要设计合理的修复程序，尽可能保持父辈的特征。,七.学习GA的几点体会（1）,119,遗传算子的设计有最大的创新空间 选择压力的调整使多样性和收敛性得到合适的分配。开始时多样性重要，重广域搜索；刚要结束时收敛性重要，重局域搜索。 调整方法：适值函数的构造；合适的标定方法,七.学习GA的几点体会（2）,120,在GA的研究中我们要做一些什么 扩大GA的应用, GA应用面广，适应性最好 算法改进方向的研究 理论研究 算法开发中的几个技术(见下页),七.学习GA的几点体会（3）,121,参数整定：经验加反复试验(Tuning) 如： ， ，NG，NP几种参数的选定 判断好坏算法的办法： 快 能解的问题大 达优率高，大问题50%的达优率,七.学习GA的几点体会（4）,122,算例的选择： 自己编的没有说服力，但可以解释算法 随机产生的适合没有前例的例子 文献的例子面较大 网上的例子典型问题QAP,TSP,七.学习GA的几点体会（5）,
