第七章-遗传算法

聆听ゝ╮锦云漫卷的柔暖梦里、诉说着对你的思念聆厅、埖雨幸福，挂在嘴边的微笑普罗旺斯的花海℡永不湮灭月光丶散漫的印在身上陪我看细水长流岁月苍老后我们依然相爱ゞ茶蘼花开丶我们相偎相依爱上你是我唯一的心情ご被幸福包围的夏天♂蘰踄繧鍴￡你在我的航程上心云间、凝听花前月下，只为你如痴如醉丶阳光灿烂下的、小幸福许我天荒地老感受浅蓝的淡然维也纳、旋转的音律给她ヽ夏天般的幸福ゞ面具下╮那暧昧不清旳尔巴赫的爱情是我的憧憬若你能共我唱首歌┛你用单手遮住了我的眼°那岸的向日葵依然灿烂ζ守望の幸福℡浅\笑、如夏゛ろ回眸爱〃记录这一切美好的微笑ぃ情醉转角处、守候※蝶恋﹏▃_那年夏天的小情歌笑灼如花雨、其实也美天晴,雨依旧低吟、幸福小情歌牵着你的手、看着日落。最美的风景ゞ┆风居住的味道卍演绎、都市繁华.℡憧憬巴黎街头的黎明、▼╰╮抬头触摸那⒈抹阳光つ-那一束未触就斜过身旁的光半梦半醒间越过时空相见﹌雨天留下一把伞っ▲秋千摇摆的三水年华若有来生╰只为你动心回忆丶回忆里的微笑。轻描丶淡写的幸福。爱琴海边的独唱，只属于你一切不再遥远。如果还囿下辈子心、似命顾惜-遥望法国浪漫都市≈谁惊艳了岁月俄为迩暖手“第七章遗传算法7.1遗传、变异、进化理论7.2遗传算法进化计算是一种模拟自然界生物进化过程与机制，进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。7.1进化计算概述遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象;变异理论：变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。染色体：细胞中含有的一种微小的丝状化合物。生物的所有遗传信息都包含在这个复杂而又微小的染色体中；DNA:染色体主要是由一种叫做脱氧核糖核酸(DNA)的物质所构成。DNA在染色体中有规则地排列着；基因：基因就是DNA长链结构中占有一定位置的基本遗传单位；遗传理论生命是由细胞组成细胞里面包括细胞核细胞核里面是染色体染色体是由很长的DNA组成DNA在那里进化论：达尔文的自然选择学说认为：生物通过遗传和变异，依照“适者生存”的原则，从简单的生物发展到复杂的高级生物。进化论7.2遗传算法基本概念遗传算法三要素基本遗传算法应用举例特点遗传算法的概念1975年由美国Michigan大学的JohnHolland提出；遗传算法(GeneticAlgorithms)是一种计算机模拟过程。是模拟生物在自然环境下的遗传和进化过程而形成的一种全局优化搜索算法。是优化计算：对于一个最优化问题，从一定数量的候选解的集合开始逐渐向更好的解集合进化。个体，模拟生物个体，对应问题中的一个可行解；染色体是解的编码，一般以字符串形式的编码表示；个体编码9----10015----0101基因：串中的一个字符（一个二进制位）也就称为基因（gene）。个体、染色体与基因种群种群(population)：也称群体，模拟生物种群，由若干个体组成，是一个可行解的集合；种群即选定的一组可行解；例如：种群（2，5，6）由三个个体组成，其编码：（0010,0101,0110）进化计算过程进化从完全随机的个体种群开始，之后一代一代发生在每一代中，整个种群的适应度被评价若满足适应度要求，进化计算结束若未满足适应度要求，则从当前种群中基于适应度选择个体通过选择、交叉和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。基本遗传算法遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束遗传算法的三个基本要素1.编码与译码编码：将问题结构变换为位串形式编码表示的染色体译码：将染色体表示变换为原问题结构。2.适应度函数对染色体适应性进行度量的函数。通过适应度函数来决定染色体的优劣程度，体现了自然进化中的优胜劣汰原则。对优化问题，适应度函数就是目标函数f(x)。3.遗传算子简单遗传算法的遗传算子主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。编码方法常用编码方法：二进制码、格雷码、实数编码和字符编码等。二进制编码：假设变量x的定义域为[5，10]，要求计算精度为10-5，将[5，10]至少分为6*105个等长小区间每个小区间用一个二进制串表示。二进制串长至少等于20，原因是：219600000220对应于区间[5，10]内满足精度要求的每个值x，都可用一个20位编码的二进制串b19,b18,…,b0来表示：00000000…00000000＝0500000000…00000001＝15+10-500000000…00000010＝25+2*10-5……11111111…11111111=220–110解码：将二进制串变为对应的变量x真实值选择算子NjjiixfxfxP1)()()(选择概率P(xi)的计算公式为：选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择或轮盘式选择；轮盘式选择：使个体被选中的概率与其适应度大小成正比；对于一个规模为N的种群S，按每个染色体xi∈S的选择概率P(xi)所决定的选中机会，分N次从S中随机选定N个染色体,并进行复制。种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)适应度f(x)=x2。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.31P(x1)P(x2)P(xN)……P(xi)2πp(xi)轮转选择法从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，1()22()()iiNijjfxpxfx轮盘选择种群S1中各个体的选择概率s40.31s20.49s10.14s30.060.6900.140.63设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.9850300.140.630.691交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。单点一致交叉：选择一交叉的位置，称为交叉点，然后将两个个体交叉点后面的部分交换。例如,设染色体s1=1001011,s2=0110011,交换其后4位基因,s1′=1000011,s2′=0111011可以看做是原染色体s1和s2的子代染色体。交叉算子1001011011001110000110111011交叉算子双点交叉在个体编码串中随机设置了两个交叉点，然后进行部分基因交换。例如,设染色体s1=1001010,s2=0110011,s1′=1000010,s2′=0111011可以看做是原染色体s1和s2的子代染色体。交叉算子1001010011001110000100111011变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。一致变异法反转操作法如将该基因位翻转（0变1，1变0）例如,设染色体s=11001101将其第三位上的0变为1,即s=11001101s′=11101101。s′也可以看做是原染色体s的子代染色体。变异算子一致变异法以概率pm对种群中所有个体的每一位进行变异。对于个体pi的第j位，在[0,1]的范围内随机地生成一个数r,如果rpm,则对第j位取反，否则保持第j位不变。反转操作法1)从当前群体中随机选择一个染色体2)从中随机选择两个数i’和j’,并定义i=min{i',j'},j=max{i',j'};3)颠倒a中位置i、j之间的部分,产生新的染色体lsssa...21ljijjissssssss.........12121S=10101101S`=10110101遗传算法中的一些控制参数：■种群规模：即群体中包含的个体的数量。■最大换代数:遗传算法终止的进化代数。■交叉率(crossoverrate)：参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc，取值范围一般为0.4～0.99。发生交叉的概率较大。■变异率(mutationrate)：发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1。发生变异概率较小，遗传算法举例例4.1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值（整数）。y=x231XY原问题可转化为在区间［0,31］中搜索能使y取最大值的点x的问题。那么，［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.060.6900.140.63设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496r4=0.9850300.140.630.691选择-复制操作设从区间［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位，所以本轮遗传操作不做变异。变异操作s1=11001（25）,s2=01100（12）s3=11011（27）,