董素媛遗传算法

1、遗传算法简介Genetic Algorithm (GA)-An Brief Introduction-一、遗传算法的概述 起源和特点：遗传算法是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，是由美国Michigan（密西根）大学的J.Holland教授于1975年首先提出的，是搜索最优解的一种随机化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，是近十多年来备受关注的一种算法。搜索机制 ：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体

2、进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 群体竞争种群婚配子群变异淘汰生物进化循环图 构造初始种群计算个体（染色体）的适应值选择交叉变异遗传算法基本流程遗传算法概要： 对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数学规划模型： max f(X) (1-1) s.t. X属于R (1-2) R属于U (1-3) 其中：Xx1,x2,xnT为决策变量，f(X)为目标函数， (1-2)、(1-3)为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解； 集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。对于上述最优

3、化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。 总的来说，求最优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。遗传算法中： 将n维决策向量Xxl,x2,xn

4、T用n个记号Xi(i=1,2,n)所组成的符号串X来表示： Xxlx2xn T Xx1，x2， ,xnT 把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。 这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。 这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。 对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，适应度越小。 遗传

5、算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。 生物的进化是以集团为主体的。与此对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程： 第t代群体记做 P(t)， 经过一代遗传和进化后，得到 t+1 代群体，记做 P(t+1), 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X

6、*。二、遗传算法的基本流程：Step1 给出一个有N个染色体的初始群体pop(1),t=1；Step2 若停止规则满足，则算法停止；否则，对群体pop(t)中每一个染色体popi(t)计算其适应值；Step3 从群体pop(t)中随机选一些染色体构成一个种群newpop(t+1)=popj(t)|j=1,2,N;Step4 通过交叉，交叉概率为Pc,得到有N个染色体的crosspop(t+1)Step5 对每个新个体依变异概率Pm进行变异，形成mutpop(t+1);t=t+1,新的群体pop(t)=mutpop(t);返回Step2注意：1）newpop(t+1)集中可能重复选pop(t)中

7、的某个元素2）最好的染色体不一定出现在最后一代，所以在进化开始，必须把最好的染色体保留下来，记为V0，如果在新的种群中又发现了更好的染色体，则用它代替原来的染色体V0,在进化完成之后，这个染色体就可以看作是最优问题的解。三、遗传算法实现的技术问题：解的编码；初始群体的设定；适应值函数的设计；遗传算子(选择规则；交叉规则；变异规则；)约束条件的处理；结束准则；运行参数的选择；GA的流程框图编码的主要方法：常规码（二进制编码）(1)每个实数都可以用二进制数表示例（连续变量的编码）：对于给定的区间a,b,设采用二进制编码长为n,则任一变量 x=a+a1(b-a)/2+ a2(b-a)/22+ an(

8、b-a)/2n 对应二进制编码a1 a2 an，二进制码与实际变量的最大误差为(b-a)/2 n (2)有些问题的解可以用0，1变量来表示例（01背包问题）：设有一个容积为b的背包，n个体积分别为ai（i=1,2,n）的价值分别为ci （i=1,2,n）的物品，如何以最大的价值装包？在这个问题中可以定义xi为决策变量，其中xi1表示第i个物品装包， xi0表示第i个物品不装包，于是可以按(x1,x2,xn)的取值形成一个自然编码。浮点码：每一个染色体由一个向量表示，如用向量 x=(x1,x2,xn)表示最优化问题的解，相应的染色体也是V= (x1,x2,xn)（常用于一些多维，高精度要求的连续

9、函数优化问题 ）非常规码：非常规的编码与问题联系紧密（基因值取决一个无数值意义，而只有代码意义的符号集） 例（TSP旅行商问题）：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。?群体的设定:遗传算法的两个主要特点之一就是基于群体搜索的策略，群体的设定，尤其是群体规模的设定，对遗传算法性能有着重要的影响。这中间包括两个问题：1）初始群体如何设定；2）进化过程中各代的规模如何维持？初始群体的设定：遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始群体的设定可以采用如下的策略：（1）根据问题固有知识，

10、设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。群体规模的设定：若群体规模太大，群体中个体的多样性越高，算法陷入局部最优解的危险就越小。另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛（premature convergence）现象。实际应用中群体规模一般取几十几百。适应值函数的设计：在传统的优化方法中，判断一个解集的好坏是根据目标函数值的大小，而在遗传算法中，则是根据适应值的

11、大小。因此存在目标函数到适应值函数的对应问题。一般来讲，适应值函数应该满足：（1）非负性；（2）目标函数的优化方向对应适应值增大方向。如果目标函数本身已经满足上述两个条件，可以直接用目标函数代替适应值函数。否则就要设计适当的适应值函数，下面介绍几种使用比较方便的适应值函数的设计方法。简单适应函数（目标函数的简单变形）max f(x),且在可行域内不是非负函数可适当取适应值函数fitness(x)=f(x)+M,其中M为常数，且保证fitness(x)0min f(x)可适当取适应值函数fitness(x)=M-f(x),其中M为常数，且保证fitness(x)0排序适应函数（计算同一代群体中N

12、个染色体的目标函数值）使染色体由好到坏进行排序，即一个染色体越好其序号越小。设参数（0，1）给定，定义基于序的适应函数为p（Vi）= (1- )i-1 (i=1,2,N)将染色体由坏到好进行排序，即一个染色体越好其序号越大。定义基于序的 适应函数为 p（Vi）=(i=1,2,N)遗传算子：遗传操作是模拟生物基因遗传的操作。包括三个基本遗传算子（genetic operator）：选择，交叉和变异。这三个遗传算子具有一些特点：（1）这三个算子的操作都是在随机扰动情况下进行的。换句话说，遗传操作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方

13、法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。选择规则:从群体中选择优胜个体，淘汰劣质个体的操作叫选择。根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中；适应度比例选择：最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关，通常采用轮盘赌（roulette wheel

14、）方式实现。这种方式首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为n的群体，个体的适应度值为，其选择概率为：步骤1 对每个染色体Vi，计算累积概率qi步骤2 从区间0, qN中产生一个随机数r;步骤3 若qi-1 r qi ，选择第i个染色体Vi (1i N) ；步骤4 重复步骤2和步骤3共N次，这样可以得到N个染色体(可能会有重复)交叉规则：群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率 (称为交叉概率）交换它们之间的部分染色体.交叉

15、操作一般分为以下几个步骤：（1）从配对池中随机取出要交配的一对个体；（2）根据位串长度L，对要交叉的一对个体，随机选取1, L-1中一个或多个整数k作为交叉位置；（3）根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，形成新的一对个体。注意：任何交叉算子需满足交叉算子的评估准则，即交叉算子需保证前一代中优秀个体的性状能在下一代的新个体中尽可能得到遗传何继承。此外，交叉算子设计和编码设计需协调操作常规码的交叉规则：交叉概率连续改变染色体多个基因位上的遗传信息息交叉位Pccross父代个体子代个体1212非常规码的常规交叉法 随机选一个交叉位，两个后代交叉位之前的基因分别继承

16、双亲的交叉位之前的基因，交叉位之后的基因分别按异方基因顺序选取不重基因。如父A 1 2 3 | 4 5 6 7 8 9 10 子A 1 2 3 | 4 7 8 5 9 6 10父B 4 7 8 | 3 2 5 9 1 6 10 子B 4 7 8 | 1 2 3 5 6 9 10浮点码的交叉操作 从开区间（0，1）中产生一个随机数c，然后，按以下形式在Vi和Vj之间进行交叉操作，并产生两个后代X和Y： 如果可行集是凸的，这种凸组合交叉运算在两个父代可行的情况下，能够保证两个后代也是可行的但是，在许多情况下，可行集不一定是凸的，或很难验证其凸性，此时必须检验每一后代的可行性如果两个后代均可行，则用

17、它们代替其父代，否则，保留其中可行的（如果存在的话），然后，产生新的随机数c，重新进行交叉操作，直到得到两个可行的后代或循环给定次数为止无论如何，仅用可行的后代取代其父代 变异规则：变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，对群体P(t)中的每一个个体，变异算子通过按变异概率pm随机反转某位等位基因的二进制字符值来实现。注意：变异操作作用于个体位串的等位基因上，由于变异概率比较小，在实施过程中一些个体可能根本不发生一次变异，造成大量计算资源的浪费。给定一个较小的变异概率Pm（0.0010.01）, i=1到N重复下列过程：从区间

18、0,1中产生随机数r，如果r< Pm ，则选择染色体Vi作为变异的父代常规码：如果某一位被选中进行变异，则0变为1，1变为0即可非常规码：非常规码变异时，变异位一般成对选择，变异规则是将两个变异位上的数据互换，如1 2 3 4的变异位是1，3位，则变异后成为3 2 1 4当交叉操作产生的后代个体的适应值不再比它们的前辈更好，但又未达到全局最优解时，就会发生成熟前收敛或早熟收敛（Premature convergence）。这时引入变异算子往往能产生很好的效果。一方面，变异算子可以使群体进化过程中丢失的等位基因信息得以恢复，以保持群体中的个体差异性，防止发生成熟前收敛；另一方面，当种群规模

19、较大时，在交叉操作基础上引人适度的变异，也能够提高遗传算法的局部搜索效率。在群体进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的，变异算子仅仅充当背景性的角色（background role）。约束条件的处理：为了保证染色体是可行的，必须对遗传操作过程中得到的每一个染色体进行检查对每个最优化问题，最好设计一个程序，其输出值1表示染色体是可行的，0表示不可行 例如，对约束条件gj (x) 0,j=1,2,p，可以作如下的一个子函数： 从j1开始循环 若gj (x) >0 ，返回0 直到jp结束 返回 1结束准则：（1）最简单的结束准则是给定一个最大的遗传

20、代数MAXGEN,算法迭代代数达到MAXGEN时停止（2）给定问题一个下界LB，当进化中达到要求的偏差度时，算法终止，即当|V*(t)-LB|< 时停止( V*(t)为第t代所得的最优目标值，即 )（3）自适应规则： 用V*(t)进行监控，如果监控到算法已经K代没有进化到一个更好的解，则算法停止。运行参数的选择：在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始阶段或群体进化过程中需要合理的选择和控制，以使 GA以最佳的搜索轨迹达到最优解。主要参数包括染色体位串长度L，群体规模n，终止进化代数maxGen，交叉概率Pc以及变异概率Pm。许多学者进行了大量实验研究

21、，给出了最优参数建议。位串长度L：位串长度L的选择取决于特定问题解的精度。要求的精度越高，位串越长，但要更多的计算时间。群体规模popSize（N）：一般建议为20100终止进化代数maxGen：1001000交叉概率pc：0.40.99变异概率pm：0.0010.01实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂，参数选择就越困难。从理论上来讲，不存在一组适用于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数以使遗传算法的性能得到改善，还需要结合实际问题深人研究，以及有赖于遗传算法理论研究的新进展。GA的流程框图 ：实际问题参

22、数集编码群体t计算适值运算：复制交叉变异群体t+1满足要求？解码改善或解决实际问题群体t+1Þ群体tYN四、遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。例：求下述二元函数的最大值： max f(x1,x2)=x12+x22 s.t. x1 Î 1,2,3,4,5,6,7 x2 Î 1,2,3,4,5,6,7(1) 个体编码：遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数来表示。因 x1, x2 为 0 7之间的整数，所以分别用3位

23、无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。 例如，基因型 X101110 所对应的表现型是：x 5，6 。 个体的表现型x和基因型X之间可通过编码和解码程序相互转换。(2) 初始群体的产生：遗传算法是对群体进行的进化操作，需要淮备一些表示起始搜索点的初始群体数据。 本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。 如：011101，101011，011100，111001(3) 适应度汁算：遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。 本例中，目标函数总取非负值，并

24、且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。(4) 选择运算：选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是： 先计算出群体中所有个体的适应度的总和 Sfi ( i=1.2,M ); 再计算出每个个体相对适应度的大小 fi / Sfi ，即每个个体被遗传到下一代群体中的概率， 每个概率值组成一个区域，全部概率值之和为1； 最后产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。个体编号初始群体p(0)适值占总数的百分比总和1234011101101011011100111001343425500.240.240.170.351431选择次数选择结果1102011101111001101011111001x1 x2 3 5 5 3 3 4 7 10124%24%17%35%1#2#3#4#(5) 交叉运算：交叉运算是遗传算法中产生新个体的主要操