遗传算法综合

1、遗传算法综合遗传算法综合1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 6 0 0 1 0 0 1 1 0个体（染色体）个体（染色体） 00100110 表现型表现型 2 6编码解码基因遗传算法是一种基于种群的，迭代的元启遗传算法是一种基于种群的，迭代的元启发式优化算法发式优化算法0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）个体

2、染色体适值选择概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174个体染色体适值选择概率累积概率1000110000082010111100153000000010

3、124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000在0-1之间产生随机数：个体染色体适应度选择概率累积概率10001100000820101111

4、00153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.

5、5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100001011

6、010110111100001001110100000110011101001100000001101010100010100100110.7553610.3215460.5689220.9251400.1542320001010110 1111011011 1100000100 1001110100 10101010111110100000 1000010110 1001110001 1100000001 00010100100001010110 1111011011 1100000100 1001100100 10101010111110100000 1000010110 10010100

7、01 1100000001 01010100001122334410011002999997ffffffff选择压力小，差别选择压力小，差别小，选优功能弱化小，选优功能弱化0254444433422411ffffffffffff选择压力大，差别放选择压力大，差别放大，选优功能强化了大，选优功能强化了Fafb1a minbf minFff1a maxbfmaxFff kkFa fb1ka minkkkbf minkkFff1ka maxkkkbfmaxkkFff kkkkM0rkk1999. 0 , 9 . 0rkFflnFafbbfFaecwFaffwfminfwfminmaxminffrFf

8、frkkFa fbrffakminmax1minmaxminkfrbffr1iiNPiifPf1(1)iiPqq1111111iNPNPiqqqq 11jjqqpNPqqq11个体12345678910适应度2.01.81.61.41.21.00.80.60.40.2选择概率0.180.160.150.130.110.090.070.060.030.02累计概率0.180.340.490.620.730.820.890.950.981.00个体12345678910适应度2.01.81.61.41.21.00.80.60.40.2选择概率0.180.160.150.130.110.090.07

9、0.060.030.02累计概率0.180.340.490.620.730.820.890.950.981.00设定设定n为需要选择的个体数为需要选择的个体数目，等距离选择个体，选择目，等距离选择个体，选择指针的距离为指针的距离为1n。第一个。第一个指针的位置由指针的位置由0，ln区间区间的均匀随机数决定。如图所的均匀随机数决定。如图所示，需要选择示，需要选择6个个体，指个个体，指针间的距离为针间的距离为l60.167，第一个指针的随机位置为第一个指针的随机位置为0.1，按这种选择方法被选中作为按这种选择方法被选中作为交配集个体为：交配集个体为：1，2，3，4，6，8。 编号 价 格 饮 料

10、速 度二进制表示 1 高 可乐 快 011 2 高 酒 快 001 3 低 可乐 慢 110 4 高 可乐 慢 010表表1 1 饭店问题的表示方案（其中的饭店问题的表示方案（其中的4 4个）个）l初始种群初始种群群体规模群体规模N N4 4 第0代 i 串xi 适应值f（xi） 1 011 3 2 001 1 3 110 6 4 010 2 总和 12 最小值 1 平均值 3.00 最大值 6表表2 2 初始群体中经营决策的适应值初始群体中经营决策的适应值（2 2）适应度函数）适应度函数 第0代 交配池 i 串xi适应值f（xi） F(xi) / f(xi) 串 f（xi） 1 011 3

11、0.25 011 3 2 001 1 0.08 110 6 3 110 6 0.50 110 6 4 010 2 0.17 010 2 总和 12 17 最小值 1 2 平均值 3.00 4.25 最大值 6 6表3 使用复制算子后产生的交配池-选适应度高的选适应度高的（3-13-1）复制算子复制算子：采用赌盘选择：采用赌盘选择(3-2) (3-2) 杂交算子杂交算子：采用一点杂交：采用一点杂交l作用过程：作用过程：a a）产生一个在）产生一个在1 1到到l1 1之间的随机数之间的随机数i i b b）配对的两个串相互对应的交换从）配对的两个串相互对应的交换从i i1 1到到l l的位段的位段

12、例如：从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符| |表示），杂交算子作用的结果为： 01 | 1 010 11 | 0 111对交配池中指定百分比的个体应用杂交算子，假设杂交概率pc50，交配池中余下的50个体仅进行复制运算，即复制概率pr50。 第 0 代 交 配 池 第 1 代 i串xi适应值f(xi)F(xi)/ f(xi) 串 f(xi)杂交点 xiF(xi) 1 011 3 0.25 011 3 2010 2 2 001 1 0.08 110 6 2111 7 3 110 6 0.50 110 6 110 6 4 010 2 0.17 010 2 010 2

13、总和 12 17 17最小值 1 2 2 平均值 3.00 4.25 4.25最大值 6 6 7表表4 4 使用使用复制和复制和杂交杂交算子算子的作用结果的作用结果 很小的概率pm随机改变染色体串上的某些位 对二进制串，就是将相应位上的0变为1或将1变为0例如：选交配池中编号为4的串进行变异，且变异点在2，则 010 000l变异算子相对而言，是变异算子相对而言，是次要算子次要算子，但在恢，但在恢复群体中失去的多样性方面具有潜在的作用。复群体中失去的多样性方面具有潜在的作用。(3-3)(3-3)变异算子：采用一点变异变异算子：采用一点变异l 上述遗传算法描述了从第上述遗传算法描述了从第0 0代

14、产生第代产生第1 1代的代的过程，然后遗传算法过程，然后遗传算法迭代迭代地执行这个过程，地执行这个过程，直到满足某个直到满足某个停止准则停止准则。l 在每一代中，算法首先计算群体中每个个在每一代中，算法首先计算群体中每个个体地适应值，然后利用适应值信息，遗传算体地适应值，然后利用适应值信息，遗传算法分别法分别以概率以概率p pc c、p pr r 和和p pm m 执行复制、杂交和执行复制、杂交和变异操作变异操作，从而产生新的群体。，从而产生新的群体。 （4）控制算法运行的参数）控制算法运行的参数 例：求下述二元函数的最大值：例：求下述二元函数的最大值： max f(x1,x2) = x12+

15、x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 解题时不是直接找最大解题时不是直接找最大max f，而是寻找哪，而是寻找哪对对（ x1, x2 ）产生产生max f 。l 遗传算法的运算对象是表示个体的符号串，遗传算法的运算对象是表示个体的符号串，必须把变量必须把变量x1,x2x1,x2编码为一种符号串编码为一种符号串。l 用用3位位无符号二进制整数来表示无符号二进制整数来表示x，则，则x1, x2连接在连接在一起组成一起组成6位无符号二进制数，形成个体的基因型，位无符号二进制数，形成个体的基因型，表示一个可行解。表示一个可行解。 例例. 基因型基因型 X

16、101110 的表现型是的表现型是x 5,6 l 个体的表现型个体的表现型x和基因型和基因型X之间可通过之间可通过编码和解码编码和解码程序相互转换。程序相互转换。x1, x2 1,2,3,4,5,6,7 遗传算法是对群体进行的进化操作，需要给遗传算法是对群体进行的进化操作，需要给其淮备一些表示其淮备一些表示起始搜索点起始搜索点的初始群体数据的初始群体数据。 本例中，群体规模的大小取为本例中，群体规模的大小取为4，即群体由，即群体由4个个体组成，每个个体可通过个个体组成，每个个体可通过随机随机方法方法产生产生。 例如：例如：011101，101011，011100，111001v 怎么从这怎么从

17、这4个个体产生出许多新个体个个体产生出许多新个体 遗传算法以个体适应度的大小来评定其优劣遗传算法以个体适应度的大小来评定其优劣程度，从而决定其遗传机会的大小。程度，从而决定其遗传机会的大小。本例是求目标函数本例是求目标函数(=0)最大值为优化目标，最大值为优化目标，故直接利用故直接利用目标函数值目标函数值作为个体的适应度。作为个体的适应度。 （运算）运算）选择运算把当前群体中选择运算把当前群体中适应度较高的个体适应度较高的个体按按某种规则或模型某种规则或模型遗传到下一代遗传到下一代群体中。群体中。一般要求一般要求适应度较高适应度较高的个体将有的个体将有更多的机会更多的机会遗传到下一代群体中。遗

18、传到下一代群体中。 本例采用本例采用及适应度成正比的概率及适应度成正比的概率来确定各来确定各个个体复制到下一代群体中的数量。具体：个个体复制到下一代群体中的数量。具体： 计算出群体中所有个体的计算出群体中所有个体的适应度的总和适应度的总和 fi ( i=1.2,M ); 计算每个计算每个个体的相对适应度的大小个体的相对适应度的大小 fi / fi ，即每个个体被即每个个体被遗传遗传到下一代群体中的到下一代群体中的概率概率，每个概率值组成一个区域，全部概率值之和每个概率值组成一个区域，全部概率值之和为为1； 最后再产生一个最后再产生一个0到到1之间的之间的随机数随机数，依据该，依据该随机数出现在

19、上述随机数出现在上述哪一个概率区域哪一个概率区域内来确定内来确定各个个体被选中的次数。各个个体被选中的次数。0124%24%17%35%1#2#3#4#个体编个体编号号初始群体初始群体p(0)适值适值占总数的占总数的百分比百分比总和1234011101101011011100111001343425500.240.240.170.351431 选择选择次数次数选择选择结果结果1102011101111001101011111001(不对应不对应) x1 x23 55 33 47 1f(x1,x2)=x12+x22落入 交叉运算是遗传算法中交叉运算是遗传算法中产生新个体产生新个体的主要的主要操作

20、过程，它以某一操作过程，它以某一概率相互交换概率相互交换某两个个某两个个体之间体之间的部分的部分染色体。染色体。 本例采用单点交叉的方法，具体操作过程：本例采用单点交叉的方法，具体操作过程： 先对群体进行随机配对；先对群体进行随机配对； 其次随机设置交叉点位置；其次随机设置交叉点位置； 最后再相互交换配对染色体之间的部分基因。最后再相互交换配对染色体之间的部分基因。选择结果选择结果01 110111 10011010 111110 01配对情况配对情况 交叉点位置交叉点位置个体编号个体编号12341-23-41-2：23-4：4交叉结果交叉结果011001 111101101001111011

21、可以看出，新个体可以看出，新个体“111101”、“111011”的的适应度较原来两个个体的适应度都要高：适应度较原来两个个体的适应度都要高：f2=49+25, f4=49+9f(x1,x2)=x12+x22 变异运算是对个体的变异运算是对个体的某一个或某一些某一个或某一些基因座基因座上的基因值按某一上的基因值按某一较小的概率较小的概率进行改变，它进行改变，它也是产生新个体也是产生新个体的一种操作方法。的一种操作方法。 本例采用基本位变异的方法来进行变异运算：本例采用基本位变异的方法来进行变异运算： 确定出各个个体的基因确定出各个个体的基因变异位置变异位置，下表所示，下表所示为为随机随机产生的变异点位置，其中的数字表示产生的变异点位置，其中的数字表示变异点设置在该基因座处；变异点设置在该基因座处； 依照某一依照某一概率概率将变异点的原有将变异点的原有基因值取反基因值取反。l对群体对群体P(t)进行一轮进行一轮选择、交叉、变异选择、交叉、变异运运算之后可得到新一代的群体算之后可得到新一代的群体p(t+1)。个体编号个体编号1234交叉结果交叉结果011001 111101101001111011变异结果变异结果变异点变异