遗传进化算法课件

达尔文的生物进化论与遗传算法遗传—生命之特征或性状的传承染色体（chromosome)DNA(deoxyribonucleicacid)RNA(ribonucleicacid)

双螺旋结构基因(gene)

四进制编码（A,T,C,G)

复制(reproduction)

交叉(crossover)

变异(mutation)达尔文的生物进化论与遗传算法进化—“物竞天择，优胜劣汰，适者生存”遗传信息（基因）寓于染色体，染色体决定生物特征，特征决定对环境的适应度。遗传与进化之过程均发生在DNA之上。遗传通过繁殖完成，繁殖由基因复制实现，复制的基本方式是交叉重组。交叉与变异产生新的物种，变异是物种进化的保证。适应度决定物种的存活，适应性强者遗传机会更大。竞争是物种进化的促进剂。有竞争就有选择，自然选择是进化的基本规律遗传进化算法的基本概念编码、个体与种群(encoding,individualandpopulation)适应度函数(fitnessfunction)选择算子(selectionoperator)交叉算子(crossoveroperator)变异算子(mutationoperator)遗传编码(geneticencoding)二进制编码灰度编码可拼接/可分解编码实数编码可变精度实数编码符号编码混乱编码混合编码编码(encoding)与解码(decoding)式中A所表示的有限字符串称为优化变量X的遗传（染色体）编码，记为

,A中的字符称为基因，字符所有可能的取值称为等位基因，L称为编码长度；X称为A的解码，记为。编码的重要性：1）基因的排列决定遗传操作的作用方式；

2）决定搜索的难度与复杂性；

3）决定问题求解的精度。个体空间与种群空间一个问题可行解的遗传编码称为个体，或者说一群染色体的组合称为个体设表示等位基因，为给定的编码长度，则所有基因可能排列成的编码构成整个个体空间对任何正整数m，乘积称为m阶种群空间，其中的元素称为m阶种群个体空间中的一群个体称为一个种群与编码相关的定义1）编码格式e是从HL到的一个映射，且对任何，存在唯一与之对应的解码；2）当且仅当任何唯一对应一个个体A，则称编码格式是正则的；3）如果一个L编码和一个K编码的拼接有意义且是一个L+K码，则称其为是可拼接的；反之则称之为是可分解的

设个体空间为：其可行解空间为：二进制编码二进制编码：以字符0和1为等位基因的定长字符串编码。对实数xi给定编码精度，取mi

为满足的最小整数，则mi

长的0-1字符串唯一对应实数xi

，定义为：设且二进制编码示例Xi的

二进制编码个体：

0000000000000000000000000010.0009767…………00010001000101.088043811111111111118.0001497设

则mi=13，从中任选n个个体可构成一个种群,任选m次就可构成m个种群二进制编码的优缺点优点：二进制编码简明、通用、易于各种进化操作。缺点：不具备正则性，可能破坏可行解空间的拓扑连续性。

对于高维、连续优化问题存在离散化误差，高精度要求将产生很长的编码；不便于表达反映所求问题的特定知识。例如:在整数集[0,10]中的数7和8最邻近，但它们的二进制编码0111和1000的海明距离为4，最远.海明距离：两染色体编码所有相应位置中取不同数值的位置数灰度编码假定已有二进制编码：其修正（灰度）编码：两者相互转换公式：即：其中表示异或运算，即：二进制与灰度编码转换示例二进制编码0111(7),1000(8),1011(11),1100(12),前两个编码的海明距离为4,后两个编码海明距离为3.其相应灰度编码为0

0

11,1011,1001,1101,显然前后两个编码的海明距离均为1,新编码保持了原空间的连续性.其灰度变换计算:其逆变换计算:个基因，和分别表示第表示染色体，这里表示染色体的第个基因解空间的上限和下限。实数与二进制的混合编码设采用混合编码产生初始种群的算法如下：随机产生一个随机数，实数与二进制的混合编码

；(2),重复N次，就产生一个染色体(3)重复步骤(1)、(2)M次，就产生一个包含M个染色体的初始种群。适应度函数(fitnessfunction)1）对应某种生物群体在给定环境下的适应性度量；2）优化变量X对应生物群体中的个体；3）遗传进化对应于实现该优化过程的演化过程。

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

适应度函数的设计原则退化现象：遗传算法运行后期阶段，群体越来越集中，个体之间的差异减小，相互之间的竞争力也随即减弱。这必然造成个体被选择到下一代中的概率接近，使进化过程失去竞争力，退化为随机选择过程。适应度函数的选取应该克服这种退化现象，使算法在运行后期阶段能够扩大最佳个体适应度与其它个体适应度之间的差异，提高个体之间的竞争性。适应度函数的常用变换线性尺度变换乘幂尺度变换指数尺度变换适应度函数设计举例

设计一个分段的非线性变换的适应度函数这里,表示变换过后的适应度函数；表示种群的适应度比例值、、和均为常数。其中的主要作用一方面用于保证恒为正，另一方面调控不同个体被选择的概率；为幂指数，可在1-1.2之间选择；、为0-1的实数，是不同函数的切换条件。选择算子(selectionoperator)模拟“优胜劣汰、适者生存”自然进化原理决定父代种群中个体以多大可能被选中遗传到下一代的进化操作。选择原则：1）依据适应度评价；

2）选择最优个体；

3）避免无效搜索；

4）快速搜索到最优解。定义：选择算子S是一个随机映射，它满足：

选择算子(selectionoperator)比例选择（轮盘赌选择）变尺度比例选择杰出者选择期望生存数选择确定式采样选择排序选择Boltzmann局部退火选择种群偏差度选择排除算子选择基于正交表的选择比例选择轮盘赌选择（RouletteWheelSelection）

每一个染色体适应度函数值决定其在轮盘上面积的大小。此面积大小与轮盘总面积的比率就染色体被挑选至下一代之概率，也就是在轮盘上任意取n点，面积比率较大者，选择并复制至交叉池（MatingPool）的个体数相对较多。P1P2PNPN-1轮盘赌选择示例设有四个染色体Cl＝l，C2＝4，C3＝10，C4＝15，其适应度函数（FitnessFunction）为F（X）＝X，相应之适应函数值为f1＝1，f2＝4，f3＝10，f4＝15，占据轮盘的面积，Pcl＝1/30＝0.03，Pc2＝4/30＝0.13，

Pc3＝10/30＝0.33，Pc4＝15/30＝0.51，其中Cl与C2所占比率较小，可能在下一代被C3及C4所取代。交叉算子

(crossoveroperator)定义：模拟生物的自然进化过程中，两个同源染色体通过交配重组形成新染色体，产生新个体和物种的进化操作，称为交叉算子。交叉操作步骤：1.从种群个体中分别任意选取两个个体组成母体对。2.对任一母体对独立重复实施交叉操作生成子代个体。交叉算子

(crossoveroperator)单点交叉多点交叉均匀交叉洗牌交叉部分匹配交叉顺序交叉循环交叉单点交叉在母体个体变量排序中任选一交叉点，并以该点为分界相互交换交叉点后的变量，形成新的子代个体。例如：母个体对：

10111001010100011110

子代个体对：

10110111100100100101顺序交叉两个母体交叉时，通过选择母体1的一部分，并保留母体2中相应码位的相对顺序，而生成子个体。顺序交叉操作能保留母体的排列并融合不同排列的有序结构单元。母个体对：

123456789452187693

子代个体对的两个交叉点之间的中间段保持不变：

XXX|4567|XXXXX|1876|XX

子个体1由2的排序93-452-1876中去掉中间段4567获得

21

8|4567|93

子个体2由1的排序89-1234-567之间去掉中间段1876获得

34

5|1876|9

2

可变精度的交叉在实数编码的两个母体交叉时，首先选择一个交换点，然后将母体两个染色体交叉点右边的部分交换，接着再计算交换点的线性组合，这样产生两个新的子代个体。即：

母体对：子代个体对：其中：

分别表示第个基因解空间的上限和下限，是一个随机数，

新的基因由随机变量和产生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以扩展。变异算子(mutationoperator)定义：模拟种群内部分个体染色体中基因发生突变，产生新的个体和物种的进化操作，称为变异（突变）算子。变异的作用是可以恢复一些在遗传进化过程中丢失的部分基因，增加种群内个体的多样性，避免进化的早熟和局部收敛。操作步骤：

1）在母体经过交叉产生的子代个体中按一定（极小的）概率挑选出少量的个体；

2）对挑选出的个体中的部分基因，按一定的方式进行变异，产生新的物种。变异算子(mutationoperator)点变异均匀变异正态变异非一致变异大规模反馈式突变二进制编码的点变异按某一概率独立地改变个体的某几位基因的进化操作变异前的个体

110010111011

变异后的个体

111111110010

种群中选择进行变异的个体的概率一般很小大约0.01-0.001,因此对优秀的个体的影响较小.

实数编码的高精细变异变异时，单个染色体的两个基因被随机地选择进行凸组合的变异。假设染色体:

的第i个基因和第k个基因被选择进行变异，变异生成新的染色体为:

其中，两个基因分别为：这里为随机数，。这种变异方式的目的就是为了增强变异的精细调节能力。大规模反馈式突变采用轮盘赌选择和最优个体保存策略，随着进化的进行，某些好的个体产生的后代越来越多，整个种群适应度也越来越高，这时种群中基因的多样性变得越来越差,以至于进化进行非常缓慢甚至完全停滞，种群陷入早熟。大规模反馈式突变,就是用随机生成的新的个体代替通过突变被消灭的个体，可以大大提高种群的多样性，同时保持了种群大小的稳定。假设通过反馈式突变的产生的新的染色体的数目为L，那么就利用混合编码的方式随机产生L个新的染色体，代替种群中原来适应度值排在最后的L个染色体。Step1.（编码与初始化）确定种群规模，交叉与变异概率，初始种群随机生成；Step2.（个体评价）估计种群中各个体的适应度；Step3.（种群进化）

3.1选择（母体）

3.2交叉依交叉概率形成中间个体；

3.3变异对中间个体依变异概率执行变异，形成候选个体；

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