基因算法PPT学习教案

1、会计学1基因算法基因算法第1页/共75页Basic Ideas of Evolutionary Algorithms (EAs)第2页/共75页第3页/共75页 Evolutionary Biology第4页/共75页 遗传学遗传学 GA 染色体（染色体（Chromosome） 数据、数组、位串数据、数组、位串 基因（基因（gene） 位位 等位基因（等位基因（allele） 特性值特性值 基因座（基因座（locus） 串中位置串中位置 基因型（基因型（genotype） 解结构（基因空间）解结构（基因空间） 表现型（表现型（phenotype） 解结构（问题空间）解结构（问题空间） 第5页/

2、共75页第6页/共75页初始群体评估每个个体选择交叉结束是否优解？开始解编码评估函数遗传操作标准的遗传算法标准的遗传算法是具有是具有“生成生成 + + 检测检测（generate-and-testgenerate-and-test）迭代过程的搜索算法。迭代过程的搜索算法。遗传算法通过遗传算法通过迭代进化迭代进化，从一群初始解找到所期从一群初始解找到所期望望的解的解新群体变异遗传算法（遗传算法（SGA）第7页/共75页GA versus “Traditional” search/optimization algorithmsl 模拟退火算法允许以一模拟退火算法允许以一定的概率降低到较小的定的概率

3、降低到较小的适应度，从而获得越过适应度，从而获得越过低谷，爬上全局高峰的低谷，爬上全局高峰的机会机会第8页/共75页第9页/共75页遗传算法的特点遗传算法的特点第10页/共75页GA应用：应用：D o m a inA p p lic a t io n T y p e sC o n t r o lg a s p ip e lin e , p o le b a la n c in g , m is s ile e v a s io n , p u r s u itD e s ig ns e m ic o n d u c to r la y o u t, a ir c r a ft d e s ig

4、 n , k e y b o a r dc o n fig u r a tio n , c o m m u n ic a tio n n e tw o r k sS c h e d u lin gm a n u fa c tu r in g , fa c ility s c h e d u lin g , r e s o u r c e a llo c a tio nR o b o t ic str a je c to r y p la n n in gM a c h in e L e a r n in gd e s ig n in g n e u r a l n e tw o r k s ,

5、 im p r o v in g c la s s ific a tio na lg o r ith m s , c la s s ifie r s y s te m sS ig n a l P r o c e s s in gfilte r d e s ig nG a m e P la y in gp o k e r , c h e c k e r s , p r is o n e r s d ile m m aC o m b in a t o r ia lO p t im iz a t io ns e t c o v e r in g , tr a v e llin g s a le s

6、m a n , r o u tin g , b in p a c k in g ,g r a p h c o lo u r in g a n d p a r titio n in g第11页/共75页13SGA中的关键要素第12页/共75页SGASGA采用二进制编码，这是最简单也较常用的个体表采用二进制编码，这是最简单也较常用的个体表示方法示方法Chromosomes could be: Bit strings (0101 . 1100) Real numbers (43.2 -33.1 . 0.0 89.2) Permutations of element (E11 E3 E7 . E1 E

7、15) Lists of rules (R1 R2 R3 . R22 R23) Program elements (genetic programming) . any data structure .nRepresentation（encoding）第13页/共75页EvaluationEvaluatedgenerationgenerationnEvaluation： GAGA基本上不用外部信息，仅用适应度函数来评估每个个体基本上不用外部信息，仅用适应度函数来评估每个个体。 评估时需要评估时需要decodingdecoding，即把，即把genotypegenotype解转换为解转换为phe

8、notypephenotype解，以便利用评估函数或适应函数。解，以便利用评估函数或适应函数。第14页/共75页X(=39)Coding and decoding 解（个体）在问题空间和遗传空间的转换，即解（个体）在问题空间和遗传空间的转换，即phenotypephenotype 解和解和genotypegenotype解之间的转换解之间的转换。第15页/共75页利用赌轮（ roulette wheel）法 fitness proportionate expected no. of representatives of each individual is proportional to it

9、s fitnesssizepopjfitnessfitnessprobjjii.1,n选择（Selection）第16页/共75页f1f2f3f4f5f6f7n=7roulette wheel根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为选择时转动轮盘，参考点r落到扇形i则选择个体i 。ip2第17页/共75页从一对父辈产生一对子辈单点交叉交叉概率 pc typically in range 0.5, 1.0Crossover 是GA最本质的遗传算子: 在进化中，能加速搜索 能形成schemata的有效组合(subsolutions on different chromosomes)n

10、Crossover(recombination)三、SGA第18页/共75页One-Point Cross-Over三、SGAparentsChildren第19页/共75页 bitwise mutation probability of mutation: pm equal probability for each gene/bit typically chosen to be small rang: 0.001, few mutations per individual depends on nature of problemnMutation第20页/共75页Before: (1 1 1

11、 1 0 1 1 0)After: (1 1 1 0 0 1 1 0)Before: (1.38 -69.4 326.44 0.1)After: (1.38 -67.5 326.44 0.1)三、SGAExamples: 第21页/共75页 example2：problem : correctly spelling “SEQUENCE” with GACrossover and mutation第22页/共75页第23页/共75页优解逼近。优解逼近。第24页/共75页第25页/共75页 kfkHfkHm, kfWhat will happen if only selection is used

12、 in GAs ?第26页/共75页cp1lHpc11lHpcmp HOpm1The crossover and mutation can generate new and possibly better individuals, they can also destroy good individuals. Do you have any idea to avoid this problem ?第27页/共75页 HOplHpkfkHfkHmkHmmc111,第28页/共75页隐并行性（隐并行性（implicit parallelism）第29页/共75页第30页/共75页l遗传算法主要是通

13、过遗传操作对遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体群体中具有某种结构形式的个体进行重组处理，形成并优化积木进行重组处理，形成并优化积木块以逐渐逼近最优解。块以逐渐逼近最优解。l通过编码和译码操作，解在两个通过编码和译码操作，解在两个空间转换空间转换l编码策略和交叉策略是互为依存编码策略和交叉策略是互为依存的。恰当的设计编码和交叉方法的。恰当的设计编码和交叉方法对于对于GAGA的有效运作是十分重要的的有效运作是十分重要的l积木块原则积木块原则：编码应易于生成与编码应易于生成与所求问题相关的短距、低阶积木所求问题相关的短距、低阶积木快快l最小字符集原则：最小字符集原则：编码应采用

14、最编码应采用最小字符集小字符集GA空间遗传空间12c12c第31页/共75页 X值二进制码非二值码适应度 13 24 8 1901101110000100010011 N Y I T16957664561 二进制码个体的相似性易于观测，每位可提供最多的二进制码个体的相似性易于观测，每位可提供最多的模式数，这是最小字符集编码原则的优点，符合遗传操模式数，这是最小字符集编码原则的优点，符合遗传操作的特点作的特点第32页/共75页l20,maxmin,UU12 lUUminmax第33页/共75页Gray coding for binary coding,Hamming distance betwe

15、en consecutive integers may be 1 example: 5 bit binary representation： 14: 01110 15: 01111 16: 10000Probability of changing 15 into 16 by independent bit flips (mutation) is not same as changing it into 14 Gray coding solves problem. example: 3-bit Gray Code Integer 0 1 2 3 4 5 6 7 binary 000 001 01

16、0 011 100 101 110 111 gray 000 001 011 010 110 111 101 100 (Hamming distance 1)第34页/共75页二值编码：问题空间的相邻解在编码空间并不相邻不利于解的搜索格雷码：问题空间的相邻解在编码空间相邻有利于解的搜索第35页/共75页第36页/共75页 kkppprlplplpbSS99.296868.0279.150100101001112121Binary-coded and Real-coded 实数编码实数编码第37页/共75页.二进制编码的缺点第38页/共75页.实数编码的优点第39页/共75页第40页/共75页2

17、2l第41页/共75页第42页/共75页 0 xgCxfmax maxCxg其他情况 可以是一个合适的值，也可采用迄今为止进化过程中可以是一个合适的值，也可采用迄今为止进化过程中g(x)g(x)的最大值或当前群体中的最大值或当前群体中g(x)g(x)的最大值的最大值maxC 最大化问题：最大化问题：将利润函数等最大化函数将利润函数等最大化函数u(x)u(x)转化为适应度函数转化为适应度函数 0minCxuxf 0minCxu其他情况 可以是合适的输入值，也可以是当前一代或前可以是合适的输入值，也可以是当前一代或前K K代中代中u(x)u(x)的最小值的最小值minC第43页/共75页 适应度函

18、数标定适应度函数标定(scaling)(scaling) 在应用在应用GAGA尤其用尤其用GAGA处理小规模群体时常常会出现一些处理小规模群体时常常会出现一些 不利于优化的现象和结果：不利于优化的现象和结果：l进化初期的未成熟收敛现象：基于比例选择策略，进化初期的未成熟收敛现象：基于比例选择策略，一些异常个体竞争力太强而处于主宰地位一些异常个体竞争力太强而处于主宰地位 解决办法：降低异常个体的竞争力，即适应度解决办法：降低异常个体的竞争力，即适应度l进化后期的随机漫游现象：群体的平均适应度已接进化后期的随机漫游现象：群体的平均适应度已接近最佳个体的适应度，此时，个体间竞争力减弱近最佳个体的适应

19、度，此时，个体间竞争力减弱 解决办法：提高个体间竞争力，即适应度解决办法：提高个体间竞争力，即适应度第44页/共75页maxavgmultfCf xfxfavgavg和为了控制原适应度最大的为了控制原适应度最大的个体可贡献子孙数。个体可贡献子孙数。通常取通常取0221.multC为了保证在以后的选择处为了保证在以后的选择处理中平均每个个体可贡献理中平均每个个体可贡献一个期待的子孙到下一代一个期待的子孙到下一代第45页/共75页avgf2avgfminfminfavgfmaxf avgf2avgfavgfmaxfminfminfA 正常线性定标B 出现负适应度地线性定标一些坏个体适应度远小于群体

20、平均适应一些坏个体适应度远小于群体平均适应度和最大适应度，且度和最大适应度，且群体群体平均适应度又平均适应度又比较接近最大适应度时，为了拉开他比较接近最大适应度时，为了拉开他们，使低适应度经定标后变成负值们，使低适应度经定标后变成负值第46页/共75页kiiffcfffii第47页/共75页第48页/共75页第49页/共75页ifniiisiffP1第50页/共75页第51页/共75页of the rank第52页/共75页第53页/共75页第54页/共75页第55页/共75页cP第56页/共75页第57页/共75页旧个体旧个体A 001111A 001111旧个体旧个体B 111100B 1

21、11100-屏蔽字屏蔽字 010101010101-新个体新个体A A 011110 011110新个体新个体B B 101101 101101Uniform crossover is the extreme case of multipoint crossover第58页/共75页05001000150020002500300035004000450001000200030004000500060007000800090001000010571814215341112136905001000150020002500300035004000450001000200030004000500060

22、00700080009000100001814215341112136910573.其他交叉方法（以TSP求解为例）第59页/共75页第60页/共75页A 9 8 4 |5 6 7| 1 3 2 0A 9 8 4 |5 6 7| 1 3 2 0B 8 7 1 |2 3 0| 9 5 4 6B 8 7 1 |2 3 0| 9 5 4 6二点交叉二点交叉A A 9 8 4 9 8 4 2 3 02 3 0 1 1 3 2 03 2 0B B 8 8 7 7 1 1 5 6 75 6 7 9 9 5 5 4 4 6 6 问题：匹配区域外出 现遍历重复 对策：依据匹配区域 内的位置映射 关系，进行对

23、换 对A A 有有 25 36 07 对B也有相应的位置映射关系A 9 8 4 2 3 0 1 6 5 7A 9 8 4 2 3 0 1 6 5 7B 8 0 1 5 6 7 9 2 4 3B 8 0 1 5 6 7 9 2 4 3- Crossover OX第61页/共75页Step (1)a) Determine the cut pointsb) Copy the segments between the cut points to the offspringStep (2)a) Start from the second cut point of one parent, the cities of the other parent are copied, keeping their order: 6-3-4-5-2-1-8-7b) Remove the cities al