进化计算与人工生命

第5章进化计算与人工生命5.15.25.35.4人工生命5.1遗传算法目前，人工智能己从传统的基于符号处理的符号主义，向以神经网络为代表的连接主义和以进化计算为代表的进化主义方向发展，遗传算法是进化计算的一个重要分支。1、生物学中的进化思想查尔斯·达尔文（CharlesDarwin）用大量的科学事实证明了生物进化过程在总体上表现为：（1）从低级到高级，从简单到复杂，从不完善形式到完善形式，从单一适应到多种适应，从低的有序性到高的有序性，以及沿着物种数目日益增多的方向发展进化。（2）生物进化的动力和机制在于自然选择，自然选择是用变异作材料，通过生存斗争实现的。凡是具有适应环境的有利变异的个体，在生存斗争中将有更多机会生存和繁殖后代，而适应性较差的个体将被淘汰，因此，生物进化便是“物竞天择，适者生存”的过程。这种进化思想在后来成为遗传算法模拟的对象。2.生物进化理论生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异。达尔文的自然选择学说包括以下三个方面：（1）遗传：亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相似的性状。（2）变异：亲代和子代之间以及子代的不同个体之间总有些差异，这种现象，称为变异。（3）生存斗争和适者生存：自然选择来自繁殖过剩和生存斗争。这种自然选择过程是一个长期的、缓慢的、连续的过程。2.生物进化理论生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异。达尔文的自然选择学说包括以下三个方面：（1）遗传：亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相似的性状。（2）变异：亲代和子代之间以及子代的不同个体之间总有些差异，这种现象，称为变异。（3）生存斗争和适者生存：自然选择来自繁殖过剩和生存斗争。这种自然选择过程是一个长期的、缓慢的、连续的过程。遗传算法模拟的是怎样的生物进化模型呢？假设对相当于自然界中的一群人的一个种群进行操作：（1）选择：是以现实世界中的优胜劣汰现象为背景的；（2）重组交叉：相当于人类的结婚和生育；（3）变异：与自然界中偶然发生的变异是一致的。由于包含着对模式的操作，遗传算法不断地产生出更加优良的个体，正如人类向前进化一样。所采用的遗传操作都与生物尤其是人类的进化过程相对应。一群人随着时间的推移而不断地进化，并具备越来越多的优良品质。5.1.1基本概念1.个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。2.●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。3.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体9----1001（2，5，6）----0101011104.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(mutation，亦称突变)选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。NjjiixfxfxP1)()()(这里的选择概率P(xi)的计算公式为交叉就是互换两个染色体某些位上的基因。s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即变异就是改变染色体某个(些)位上的基因。例如,设染色体s=11001101将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。5.1.2基本遗传算法遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束算法中的一些控制参数：■种群规模■最大换代数■交叉率(crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.4～0.99。■变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1。基本遗传算法步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；步3计算S中每个个体的适应度f()；步4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。步5按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；步6按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；5.1.3遗传算法应用举例例5.1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。y=x231XY分析原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为ijjixPq1)(选择-复制设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色体适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，经复制得群体：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）变异设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第二代种群S2中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：s1’=11001（25）,s2’=01100（12）s3’=11011（27）,s4’=10000（16）做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因，得s1’’=11100（28）,s2’’=01001（9）s3’’=11000（24）,s4’’=10011（19）这一轮仍然不会发生变异。于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第三代种群S3中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）s3’’=11000（24）,s4’’=10000（16）这一轮仍然不会发生变异。于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。YYy=x28131924X第一代种群及其适应度y=x212162527XY第二代种群及其适应度y=x29192428XY第三代种群及其适应度y=x216242831X第四代种群及其适应度例5.2用遗传算法求解TSP。旅行商（TSP）问题的描述如下：已知个城市之间的两两距离，一个旅行商要到个城市推销商品，他从其中一个城市出发，到其他－1个城市销售商品，然后回到初始点，每个城市刚好经过一次并且总的行程最短。问旅行商应该如何走完这个城市？这就是著名的旅行商（TSP-Travelingsalesmanproblem）问题。如图5-1所示。旅行商问题是一个典型的组合优化问题，特别是当的数目很大时，用常规的方法求解，计算量太大。图5-1旅行商问题示意图分析由于其任一可能解——一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。（1）定义适应度函数我们将一个合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c