深入浅出遗传算法

一、初探遗传算法维基百科对遗传算法所给的解释：遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初 是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及 杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称 为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即 0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代 发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它 们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为 当前种群。基本遗传算法的框图:执行M/2次基本遗传算法的框圉产生初始群体比例选择运算计算适应度值足+揄出结罷LI满足停止准则？.否CZ基本柱变异运算4产生新一代群体遗传算法基本步骤是：1）初始化t-0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P(t)；2)3)4)5)6)个体评价 选择运算 交叉运算 变异运算终止条件判断计算P （t）中各个个体的适应度值；将选择算子作用于群体；将交叉算子作用于群体；将变异算子作用于群体，并通过以上运算得到下一代群体P （t + 1）; tWT： t- t+1转到步骤2；tT：终止输出解。好的，看下遗传算法的伪代码实现:Procedures GA：伪代码begininitialize P(0);t = 0;/t是进化的代数，一代、二代、三代.while（t 二 T） dofor i =1 to Mdo/M是初始种群的个体数of P（t）; /计算P （t）中各个个体的适应度Evaluate fitnessendforfori =1 toMdoSelect operation to P(t);/将选择算子作用于群体endforfori =1 toM/2doCrossoveroperation to P(t);/将交叉算子作用于群体endforfori =1 toMdoMutationoperation to P(t);/将变异算子作用于群体endforfori =1 toMdoP( t+1)=P(t);/得到下一代群体P（t + 1）endfort = t +1;/终止条件判断tWT： t t+1转到步骤2end whileend二、深入遗传算法1、智能优化算法概述智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理 的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内 找到最优解或近似最优解。遗传算法属于智能优化算法之一。常用的智能优化算法有：遗传算法、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。（本经典算法研究系列，日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。）2、遗传算法概述遗传算法是由美国的J. Holland教授于1975年在他的专著自然界和人工系统的适应性 中首先提出的。借鉴生物界自然选择和自然遗传机制的随机化搜索算法。模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选 择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。基本遗传算法（Simple Genetic Algorithms, GA）又称简单遗传算法或标准遗传算法），是 由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其 它一些遗传算法的雏形和基础。3、基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数1、编码遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。 正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。基本遗传算法（SGA）使用二进制串进行编码。初始种群：基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种 群。初始种群中个体的数量称为种群规模。2、适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越 好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准， 它的设计应结合求解问题本身的要求而定。3.1、选择算子遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中 的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。基本遗传算法（SGA）中选择算子采用轮盘赌选择方法。轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值大 小成正比。设群体大小为N,个体xi的适应度为f(xi),则个体xi的选择概率为：尸 d =三厂轮盘赌选择法可用如下过程模拟来实现：(1) 在0, 1内产生一个均匀分布的随机数r。(2) 若rWql,则染色体xl被选中。若qk-1rWqk(2WkWN),则染色体xk被选中。其中的qi称为染色体xi (i=1, 2, , n)的积累概率，其计算公式为:积累概率丈例71匚弹黑槪率0,140.斗90600.140.63 0.695=乞只弓)轮盘赌选择方法的实现步骤：(1) 计算群体中所有个体的适应度值；(2) 计算每个个体的选择概率；(3) 计算积累概率；(4) 采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率 进行匹配)来确定各个个体是否遗传到下一代群体中。例如，有染色体 s1= 13 (01101) s2= 24 (11000) s3= 8(01000)s4= 19 (10011)假定适应度为f(s)=s2，则f (s1) = f(13) = 132 = 169f (s2) = f(24) = 242 = 576f (s3) = f(8) = 82 = 64f (s4) = f(19) = 192 = 361染色休的选样概率为169=0.14-巩心=)169 + 576 + 石4 + 361=0.49=0.317-1-169 + /5 76 -h 6436164X Z(J y169 + 576 +64 +3617-1./(孔)361=0.06W宀3 fy-L壬心0.140,490.060.31AZ-_ i人0.140.63 0.69例如设从区间0,1中产生4个随机数:r1 = 0.450126,r2 = 0.110347r3 = 0.572496,r4 = 0.98503染色体适应度选择概率积累概率选中次数=011011690.140J41=110005760.490.6323=01000640.060.690S4-100113610.311.0013.2、交叉算子交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因, 从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。基本遗传算法（SGA）中交叉算子采用单点交叉算子。单点交叉运算亦叉O1 000（0111 000000001 OOOO11-1 OOIOOOOO11-11-1-1 OOO1 O1立叉EO1 OOO|000001 -l-l-l-l-l OOO1 O1-111OOIO11100000000100003.3、变异算子变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力，保持种群多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法（SGA）中变异算子采用基本位变异算子。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0,则将其变为1;反之，若原有基因值为1，则将其变为0。基本位变异算子的执行过程：变昇前：变异点OOOOO111OOOOOOOO1OOOO变异后二OOOOO111OOQIOOOO1OOOO4、运行参数（1） M:种群规模（2） T:遗传运算的终止进化代数（3） Pc:交叉概率（4）Pm :变异概率三、浅出遗传算法遗传算法的本质遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良 模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。 通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。遗传算法的主要有以下八方面的应用：（1）组合优化（2）函数优化（3）自动控制（4）生产调度（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘四、遗传算法的应用遗传算法的应用举例、透析本质（这个例子简明、但很重要 已知x为整数，利用遗传算法求解区间0, 31上的二次函数y=x2的最大值。分析原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。个体：0, 31中的任意点x适应度：函数值f(x)=x2解空间：区间0, 31这样，只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。(1) 设定种群规模，编码染色体，产生初始种群。将种群规模设定为4用5位二进制数编码染色体；取下列个体组成初始种群S1s1= 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) = 13人2 = 169f (s2) = f(24) = 24人2 = 576f (s3) = f(8) = 8人2 = 64f (s4) = f(19) = 19人2 = 361再计算种群S1中各个体的选择概率:由此可求得P(s1) = P(13) = 0.14P(s2) = P(24) = 0.49P(s3) = P(8) = 0.06P(s4) = P(19) = 0.31再计算种群SI中各个体的积累概率:7-1选择复制设从区间0, 1中产生4个随机数如下: r1 = 0.450126,r2 = 0.110347r3 = 0.572496,r4 = 0.98503设从区间O? 1 中产生4个随机数如下: 7 = (L450L26,r2=O, 10347心=0.572496, q = 0.98503染色体适应度选择槪率积累概率选中次数=011011690.140.141卑10005760.490.6323=01000640.060.6904=100113610.311.001于是，经复制得群体：s1 =11000 (24) ,s2 =01101 (13)s3=11000 (24)(24 被选中俩次)， s4=10011 (19)交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设si与s2配对，s3与s4配对。si=11000（24）,s2=01101 （13）s3=11000（24）,s4=10011 （19）分别交换后两位基因，得新染色体：s1 =11001 （25） ,s2 =01100 （12）s3 =11011 （27） ,s4 =10000 （16）变异设变异率pm = 0.001。这样，群体S1中共有5x4x0.001 = 0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：s1 = 11001 （25） , s2 = 01100 （12）s3 = 11011（27）,s4=10000（16）第二代种群S2中各染色体的情况：第二代种群中各染芭体的情况染色体适应度选择概率积累概率估计的 选中次数110016250.360.361ssQUOO1440.080.4403 = 110117290.410,&52=100002560.151假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体:S1=11OO1（25）, S2= 01100（12）S3=11O11（27）, s4= 10000（16）做交叉运算，让si与S2, S3与S4分别交换后三位基因，得S1=111OO (28) ,S2 = 01001 (9)S3 =11000 (24) , s4 = 10011 (19)这一轮仍然不会发生变异。于是，得第三代种群S3：s1 = 11100(28), s2 = 01001(9)s3=11000(24), s4=10011(19)第三代种群S3中各染色体的情况：第三代种群鸟中各染邑体的情况染色体适应度选择概率积累概率估计的 选中次数=111007840.440,4422=01001810.040.4803=110005760.320.801s+=10O113610.201.001设这一轮的选择-复制结果为：si=11100 (28) ,s2=11100(28)s3=11000 (24) ,s4=10011(19)做交叉运算，让s1与s4，s2与s3分别交换后两位基因，得si =11111(31), s2=11100(28)s3 =11000(24), s4=10000(16)这一轮仍然不会发生变异。于是，得第四代种群S4：si=iiiii (31)(出现最优解),s2=11100 (28)s3=ii000 (24) , s4=10000 (16)显然，在这一代种群中已经出现了适应度最高的染色体S1=11111。于是，遗传操作终止，将染色体(11111)作为最终结果输出。 然后，将染色体“11111”解码为表现型，即得所求的最优解：31。s将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。所以，综合以上各代群的情况，如下:91.9 24 2S1624 2S St曲戸代科群及真玷岚皮n 代科群及応辿两愆诧一代种供娠比：适应度