遗传算法及其MATLAB实现

遗传算法及其matlab实现报告人遗传算法生物学基础遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织，自适应人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。在自然界，由于组成生物群体中各个个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新的个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优化方向前进，遗传算法是真实模拟自然界生物进化机制进行寻优的。1、个体编码2、初始群体的产生3、适应度计算4、新种群的选择复制5、新种群的交配（交叉运算)6、新种群的变异运算算法步骤算法流程图遗传算法步骤以一个案例来说明遗传算法的具体过程：8.51.41.120.3..)20sin()4sin(5.21),(max21221121xxtsxxxxxxf函数的三维图形1、个体编码•遗传算法的对象运算是表示个体的符号串，所以必须把变量编码为一种符号串即将变量转换成二进制数串。数串的长度取决于所要求的精度。例如，变量x的区间是（L，U），要求的精度是小数点后四位，也就意味着每个变量应该被分成至少个部分。对一个变量的二进制数串位数用以下公式计算：本例精度要求保留小数点后四位，则目标函数的俩个自变量x1及x2所构成的染色体串位数m1=18，m2=15，即本例中任何一染色体串为33位，前18位表示x1后15位表示x2。1210)(21141mmLU自变量二进制十进制实际值x10000010101001010015417-2.687969x2101111011111110243185.361653染色体编码2、初始群体的产生•遗传算法是对群体进行的进化操作，需要给其准备一些起始搜索点的初始群体数据•初始群体太小时会产生病态基因，且造成有效等位基因先天缺乏•初始群体太大会导致结果难以收敛且浪费资源，稳健性下降•建议值0~100假设初始种群中有10个个体，其染色体可随机生成如下：U1=[000001010100101001101111011111110]U2=[001110101110011000000010101001000]U3=[111000111000001000010101001000110]U4=[100110110100101100000000010111001]U5=[000010111101100010001110001101000]U6=[111110101011011000000010110011001]U7=[110100010111110001001100111011101]U8=[001011010111111100010110011001100]U9=[111110001011101100011101000111101]U10=[111101001110101010000010101101010]相应的十进制实际值[x1,x2]为：U1=[2.687969,5.361653],U2=[0.474101,4.170144]U3=[10.419457,4.661461],U4=[6.159951,4.109598]U5=[-2.301286,4.477282],U6=[11.788084,4.174346]U7=[9.342067,5.121702],U8=[-0.330256,4.694977]U9=[11.671267,4.873501],U10=[11.446273,4.171908]3、适应度计算•遗传算法以个体适应度来评定各个个体的优劣程度从而决定其遗传机会的大小对一个染色体数串的适应度的评价由下列三个步骤组成。①将染色体串进行反编码（解码），转换成真实值，即②评价目标函数③将目标数值转为适应度值。对于极大值问题，适应度可作为目标函数值：,...3,2,1),,(21kxxxkkk,...3,2,1),()(kxfUevalkK在遗传算法中，评价函数扮演自然进化中环境的角色，它通过染色体的适应度对其进行评价。上述染色体的适应度如下：eval（U1）=f（-2.687969,5.361653）=19.805119同理可得，eval（U2）=17.370896eval（U3）=9.590546eval（U4）=29.406122eval（U5）=15.686091eval（U6）=11.900541eval（U7）=17.958717eval（U8）=19.763109eval（U9）=26.401669eval（U10）=10.252480依照染色体的适应度值进行新种群的复制，步骤如下：①计算染色体的适应度值②计算种群的适应度值总和③计算每个染色体被复制的概率④计算每个染色体被复制的累积概率kU,...2,1),()(kxfUevalkksizepopkkUevalF1)(kjkkPQ1FUevalPkk)(4、新种群的选择复制•依照轮盘选择法，转动轮盘10次（假设种群的染色体），每次选择一个作为新种群的染色体，这样，适应度越大的就越有机会复制到下一代依照轮盘选择法，转动轮盘10次，每次选择一个作为新种群的染色体。假设10次产生的0~1随机数序列如下：0.3014310.3220620.7665030.8818930.3508710.5383920.1776180.3432420.0326850.197577根据以上的计算方法，可以先计算出种群中每个染色体的适应度和概率，如表所列：种群每条染色体的适应度、被复制概率和被复制的累积概率染色体适应度值U119.8051190.1111800.111180U217.3708900.0975110.208695U39.5905460.0538390.262534U429.1061220.1650770.427611U515.6860010.0880570.515668U611.9005410.0668080.582475U717.9587170.1008150.683290U819.7631900.1009150.794234U926.4016690.1182110.912416U1010.2524800.0575540.100000kPkQ第一个随机数为0.301431，大于Q3小于Q4，所以U4被选中；第二个随机数为0.322062，大于Q3小于Q4，所以U4再次被选中；……第十个随机数为0.197577，大于Q1小于Q2，所以U2被选中；依照轮盘转法，新种群的染色体组成如下：U1=[100110110100101101000000010111001]U2=[100110110100101101000000010111001]U3=[001011010100001100010110011001100]U4=[111110001011101100011101000111101]U5=[100110110100101101000000010111001]U6=[110100010111110001001100111011101]U7=[001110101110011000000010101111000]U8=[100110110100101101000000010111001]U9=[000001010100101001101111011111110]U10=[00111010110011000000010101001000]这种轮盘选择法的机理是：染色体的适应度大意味着[,]区间跨度就大，随机数发生器发生的均匀随机数就会有更大的概率落在较大长度的[,]区间里，这样具有较大值的染色体自然更有机会复制到下一代。kQ1kQkQ1kQkP5、新种群的交配（交叉运算)①交配染色体数量的确定交配染色体的数量等于染色体总量乘以交配概率。这里假设交配概率为0.25，染色体总量为10条，所以参加交配的染色体数量为[2.5]条。符号[]表示取整，这里取整数2，即交配的染色体数目为2条。②交配染色体对象的确定用计算机产生[0,1]区间的10个随机数如下：0.6257210.2668230.2886440.2951140.1632740.5674610.0859400.3928650.7707140.548656•交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交互两个个体之间的部分染色体•先对群体进行随机配对，其次随机设置交叉点位置，最后再相互交换配对染色体之间的部分基因•交叉概率一般取0.4~0.99假定其分别对应U1~U10这10个个体，则其中低于交配概率0.25的U5和U7参加交配。这样操作的原因是：交配概率越低，低于交配概率以下的随机数的数量就越少，所以参加交配的染色体数量与交配概率可能会成正比。③在交配池发生交配染色体U5和U7被选中作为交配的父辈，交配点的选择以随机数产生。交配的种类有单点交配和多点交配，这里取单点交配。计算机随机生成一个介于0~32的整数。假设所产生的整数为1，那么两个染色体自1位置开始分割，在染色体1位置右端部分进行交换而生成新的子辈染色体，即U5=[100110110100101101000000010111001]U7=[001110101110011000000010101001000]U5*=[101110101110011000000010101001000]U7*=[000110110100101101000000010111001]cP6、新种群的变异运算依照突变运算规则并假设突变几率为0.01，亦即种群内所有基因都有0.01的概率进行突变。本例中共有33×10=330个基因，即希望每一代中有3.3个突变基因，每个基因的突变几率是相等的。因此，将产生330个介于0~1之间的随机数，然后将该随机数小于0.01者选出，并将其对应的基因值加以翻转，假设330次中产生0~1之间的随机数，其值小于0.01者如右表所列。右表第一列显示的是具体在哪些染色体以及在染色体的什么位置进行了突变。例如第一行表示的是在第4条染色体第6个基因上发生了突变。•变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，是产生新个体的一种操作方法•首先确定出各个个体的基因变异位置，然后依照某一概率将变异点的原有基因值取反基因突变位置基因位置染色体位置基因位数随机数105÷33=4…6460.009857164÷33=5…325320.003113199÷33=7…1710.000946329÷33=10…3210320.001282在突变后，最终新种群的染色体组成如下：U1=[100110110100101101000000010111001]U2=[100110110100101101000000010111001]U3=[001011010100001100010110011001100]U4=[111111001011101100011101000111101]U5=[101110101110011000000010101001010]U6=[110100010111110001001100111011101]U7=[100110110100101101000000010111001]U8=[100110110100101101000000010111001]U9=[000001010100101001000000010111001]U10=[001110101110011000000010101001010]新一代的对应实际值[x1,x2]和适应度值如下：eval（U1）=f（6.159951,4.109598）=29.406122eval（U2）=29.4061