遗传进化算法课件

1、第5章 遗传进化算法基本概念、基本原理、基本算法第1页，共41页。达尔文的生物进化论与遗传算法遗传生命之特征或性状的传承 染色体（chromosome) DNA (deoxyribonucleic acid) RNA (ribonucleic acid) 双螺旋结构 基因(gene) 四进制编码（A,T,C,G) 复制(reproduction) 交叉(crossover) 变异(mutation)第2页，共41页。达尔文的生物进化论与遗传算法 进化“物竞天择，优胜劣汰，适者生存”遗传信息（基因）寓于染色体，染色体决定生物特征，特征决定对环境的适应度。遗传与进化之过程均发生在DNA之上。遗传通

2、过繁殖完成，繁殖由基因复制实现，复制的基本方式是交叉重组。交叉与变异产生新的物种，变异是物种进化的保证。适应度决定物种的存活，适应性强者遗传机会更大。竞争是物种进化的促进剂。有竞争就有选择，自然选择是进化的基本规律第3页，共41页。遗传进化算法的基本概念编码、个体与种群 (encoding, individual and population)适应度函数 (fitness function)选择算子 (selection operator) 交叉算子 (crossover operator) 变异算子 (mutation operator)第4页，共41页。遗传编码 (genetic enco

3、ding)二进制编码灰度编码可拼接/可分解编码实数编码可变精度实数编码符号编码混乱编码混合编码第5页，共41页。编码(encoding)与解码(decoding)式中A 所表示的有限字符串称为优化变量X 的遗传（染色体）编码，记为 ,A 中的字符称为基因，字符所有可能的取值称为等位基因，L 称为编码长度；X 称为A 的解码，记为 。编码的重要性： 1）基因的排列决定遗传操作的作用方式； 2）决定搜索的难度与复杂性； 3）决定问题求解的精度。第6页，共41页。个体空间与种群空间一个问题可行解的遗传编码称为个体，或者说一群染色体的组合称为个体设 表示等位基因， 为给定的编码长度，则所有基因可能排列

4、成的编码构成整个个体空间对任何正整数 m，乘积 称为m 阶种群空间，其中的元素称为 m 阶种群个体空间中的一群个体称为一个种群第7页，共41页。与编码相关的定义1）编码格式 e 是从HL 到 的一个映射，且对任何 ， 存在唯一 与之对应的解码 ；2）当且仅当任何 唯一对应一个个体A，则称编码格式是正则的；3）如果一个L 编码 和一个K 编码 的拼接 有意义且是一个L+K码，则称其为是可拼接的；反之则称之为是可分解的 设个体空间为：其可行解空间为：第8页，共41页。二进制编码二进制编码：以字符0和1为等位基因的定长字符串编码。对实数xi 给定编码精度 ，取 mi 为满足 的最小整数，则 mi 长

5、的0-1字符串唯一对应实数xi ，定义为：设且第9页，共41页。二进制编码示例Xi 的 二进制编码个体： 0000000000000 0 0000000000001 0.0009767 0001000100010 1.0880438 1111111111111 8.0001497设 则mi =13，从中任选n个个体可构成一个种群,任选m次就可构成m个种群第10页，共41页。二进制编码的优缺点优点：二进制编码简明、通用、易于各种进化操作。缺点：不具备正则性，可能破坏可行解空间的拓扑连续性。 对于高维、连续优化问题存在离散化误差，高精度要求 将产生很长的编码；不便于表达反映所求问题的特定知识。例如

6、:在整数集0,10中的数7和8最邻近，但它们的二进制编码0111和1000的海明距离为4，最远.海明距离：两染色体编码所有相应位置中取不同数值的位置数第11页，共41页。灰度编码假定已有二进制编码： 其修正（灰度）编码：两者相互转换公式：即：其中 表示异或运算，即：第12页，共41页。二进制与灰度编码转换示例二进制编码 0 1 1 1 (7), 1 0 0 0 (8), 1 0 1 1 (11), 1 1 0 0 (12), 前两个编码的海明距离为4, 后两个编码海明距离为3.其相应灰度编码为0 0 1 1, 1 0 1 1, 1 0 0 1, 1 1 0 1, 显然前后两个编码的海明距离均为

7、1, 新编码保持了原空间的连续性.其灰度变换计算: 其逆变换计算:第13页，共41页。个基因，和分别表示第表示染色体，这里表示染色体的第个基因解空间的上限和下限。实数与二进制的混合编码设第14页，共41页。采用混合编码产生初始种群的算法如下：随机产生一个随机数 ，实数与二进制的混合编码 ；(2) ,重复 N 次，就产生一个染色体(3)重复步骤(1)、(2)M次，就产生一个包含 M 个染色 体的初始种群。第15页，共41页。适应度函数(fitness function)1）对应某种生物群体在给定环境下的适应性度量；2）优化变量X对应生物群体中的个体；3）遗传进化对应于实现该优化过程的演化过程。

8、适应度函数是评价群体中个体好坏的标准，是模拟自然选择的唯一依据。从而适应度函数选取的优劣直接影响遗传算法的收敛速度及能否找到最优解。第16页，共41页。适应度函数的设计原则早熟现象：遗传算法运行初期阶段，群体中或许会出现适应度极好的个体，最终这些个体可能会充斥整个群体，使用于产生新个体作用较大的交叉操作失去作用，从而使得群体的多样性降低，遗传算法提前收敛到某个局部最优解。适应度函数的选取应尽量的避免早熟现象，即缩小适应度较高的个体与其他个体适应度之间的差异，限制其复制数量以维护群体的多样性 第17页，共41页。适应度函数的设计原则退化现象：遗传算法运行后期阶段，群体越来越集中，个体之间的差异减

9、小，相互之间的竞争力也随即减弱。这必然造成个体被选择到下一代中的概率接近，使进化过程失去竞争力，退化为随机选择过程。适应度函数的选取应该克服这种退化现象，使算法在运行后期阶段能够扩大最佳个体适应度与其它个体适应度之间的差异，提高个体之间的竞争性。第18页，共41页。适应度函数的常用变换线性尺度变换乘幂尺度变换指数尺度变换第19页，共41页。适应度函数设计举例 设计一个分段的非线性变换的适应度函数 这里 , 表示变换过后的适应度函数； 表示种群的适应度比例值 、 、 和 均为常数。其中 的主要作用一方面用于保证 恒为正，另一方面调控不同个体被选择的概率； 为幂指数，可在1-1.2之间选择； 、

10、为0-1的实数，是不同函数的切换条件。第20页，共41页。选择算子 (selection operator)模拟“优胜劣汰、适者生存”自然进化原理决定父代种群中个体以多大可能被选中遗传到下一代的进化操作。选择原则：1）依据适应度评价； 2）选择最优个体； 3）避免无效搜索； 4）快速搜索到最优解。定义：选择算子 S 是一个随机映射，它满足： 第21页，共41页。选择算子 (selection operator)比例选择（轮盘赌选择）变尺度比例选择杰出者选择期望生存数选择确定式采样选择排序选择Boltzmann局部退火选择种群偏差度选择排除算子选择基于正交表的选择第22页，共41页。比例选择第2

11、3页，共41页。轮盘赌选择（Roulette Wheel Selection） 每一个染色体适应度函数值决定其在轮盘上面积的大小。此面积大小与轮盘总面积的比率就染色体被挑选至下一代之概率，也就是在轮盘上任意取n点，面积比率较大者，选择并复制至交叉池（Mating Pool）的个体数相对较多。 P1P2PNPN-1第24页，共41页。轮盘赌选择示例设有四个染色体Cll，C24，C310，C415，其适应度函数（Fitness Function）为 F（X）X ，相应之适应函数值为f11，f24，f310，f415，占据轮盘的面积，Pcl1/300.03，Pc24/300.13， Pc310/30

12、0.33，Pc415/300.51，其中Cl与C2所占比率较小，可能在下一代被C3及C4所取代。第25页，共41页。交叉算子 (crossover operator)定义：模拟生物的自然进化过程中，两个同源染色体通过交配重组形成新染色体，产生新个体和物种的进化操作，称为交叉算子。交叉操作步骤：1. 从种群个体中分别任意选取两个个体组成母体对。2. 对任一母体对独立重复实施交叉操作生成子代个体。第26页，共41页。交叉算子 (crossover operator)单点交叉多点交叉均匀交叉洗牌交叉部分匹配交叉顺序交叉循环交叉第27页，共41页。单点交叉在母体个体变量排序中任选一交叉点，并以该点为分

13、界相互交换交叉点后的变量，形成新的子代个体。例如： 母个体对： 1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 子代个体对： 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1第28页，共41页。顺序交叉两个母体交叉时，通过选择母体1的一部分，并保留母体2中相应码位的相对顺序，而生成子个体。顺序交叉操作能保留母体的排列并融合不同排列的有序结构单元。 母个体对： 1 2 3 4 5 6 7 8 9 4 5 2 1 8 7 6 9 3 子代个体对的两个交叉点之间的中间段保持不变： X X X|4 5 6 7|X X X X X|1 8 7

14、 6|X X 子个体1由2的排序93-452-1876中去掉中间段4567获得 2 1 8|4 5 6 7|9 3 子个体2由1的排序89-1234-567之间去掉中间段1876获得 3 4 5|1 8 7 6|9 2 第29页，共41页。可变精度的交叉在实数编码的两个母体交叉时，首先选择一个交换点，然后将母体两个染色体交叉点右边的部分交换，接着再计算交换点的线性组合，这样产生两个新的子代个体。即： 母体对： 子代个体对： 其中： 分别表示第个基因解空间的上限和下限， 是一个随机数， 新的基因由随机变量和产生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以扩展。 第30页，共41页。

15、变异算子 (mutation operator)定义：模拟种群内部分个体染色体中基因发生突变，产生新的个体和物种的进化操作，称为变异（突变）算子。变异的作用是可以恢复一些在遗传进化过程中丢失的部分基因，增加种群内个体的多样性，避免进化的早熟和局部收敛。操作步骤： 1）在母体经过交叉产生的子代个体中按一定（极小的）概率挑选出少量的个体； 2）对挑选出的个体中的部分基因，按一定的方式进行变异，产生新的物种。第31页，共41页。变异算子 (mutation operator)点变异均匀变异正态变异非一致变异大规模反馈式突变第32页，共41页。二进制编码的点变异按某一概率独立地改变个体的某几位基因的进

16、化操作 变异前的个体 1 1 0 0 1 0 1 1 1 0 1 1 变异后的个体 1 1 1 1 1 1 1 1 0 0 1 0 种群中选择进行变异的个体的概率一般很小大约0.01-0.001,因此对优秀的个体的影响较小. 第33页，共41页。实数编码的高精细变异变异时，单个染色体的两个基因被随机地选择进行凸组合的变异。假设染色体: 的第i个基因和第k个基因被选择进行变异，变异生成新的染色体为: 其中 ， 两个基因分别为： 这里 为随机数， 。 这种变异方式的目的就是为了增强变异的精细调节能力。第34页，共41页。大规模反馈式突变采用轮盘赌选择和最优个体保存策略，随着进化的进行，某些好的个体

17、产生的后代越来越多，整个种群适应度也越来越高，这时种群中基因的多样性变得越来越差,以至于进化进行非常缓慢甚至完全停滞，种群陷入早熟。大规模反馈式突变,就是用随机生成的新的个体代替通过突变被消灭的个体，可以大大提高种群的多样性，同时保持了种群大小的稳定。 假设通过反馈式突变的产生的新的染色体的数目为L，那么就利用混合编码的方式随机产生L个新的染色体，代替种群中原来适应度值排在最后的L个染色体。第35页，共41页。Step1.（编码与初始化）确定种群规模，交叉与变异概率，初始种群随机生成；Step2.（个体评价）估计种群中各个体的适应度；Step3.（种群进化） 3.1 选择（母体） 3.2 交叉

18、 依交叉概率形成中间个体； 3.3 变异 对中间个体依变异概率执行变异，形成候选个体； 3.4 选择（子代）从候选个体中依适应度选择合适个体组成新种群；Step4. （终止校验）满足终止准则，输出最优解，否则继续转步3。标准遗传进化算法的基本运算过程(Holland1969, De Jong1975, Goldberg1989)第36页，共41页。计算的典型执行技巧研究：搜索机理研究：收敛性理论研究：复杂性理论研究；有效性理论研究。遗传进化算法的基本理论研究在原始的遗传算法中存在着早熟收敛、收敛速度慢、计算效率低、精度不高、搜索能力弱、容易陷入局部最优等问题，因此展开如下众多基本理论研究。第37页，共41页。遗传计算的典型执行技巧适应值共享策略并行（群体分组、搜索空间分解）实现策略混合（神经网络、梯度下降、列表寻优、贪婪变换）策略自适应（稳态、动态、混合编码、选择）策略；第38页，共41