遗传算法概述

1、遗传算法归纳大纲：遗传算法（geneticalgorithms,GA）是人工智能的重要新分支，是基于达尔文进化论，在微型计算机上，模拟生命进化体系而发展起来的一门学科。它依照适者生计、优胜劣汰等自然进化规则来进行找寻计算机和问题求解。对好多用传统数学难以解决或显然无效的特别复杂的问题，特别是最优化问题，GA供应了一个卓有收效的新路子。近来几年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用，这种算法碰到了广泛的关注。本文旨在阐述遗传算法的基根源理、操作步骤和应用中的一些基本问题，以及为了改进SGA的鲁棒性而逐渐发展形成的高级遗传算法（refinegeneticalgo

2、rithms,RGA）的实现方法。一、遗传算法的基根源理和特色遗传算法将生物进化原理引入待优化参数形成的编码串集体中，按着必然的适值函数及一系列遗传操作对各个体进行精选，进而使适值高的个体被保留下来，组成新的集体，新集体包括上一代的大量信息，而且引入了新一代的优于上一代的个体。这样周而复始，集体中各个体适值不断提高，直至满足必然的极限条件。此时，集体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂的空间进行全局优化找寻，而且拥有较强的鲁棒性；其他，遗传算法对于找寻空间，基本上不需要什么限制性的假设（如连续性、可微及单峰等）。同老例优化算法对照，遗传算法

3、有以下特色。1）遗传算法是对参数编码进行操作，而非对参数自己。遗传算法第一基于一个有限的字母表，把最优化问题的自然参数集编码为有线长度的字符串。比方，一个最优化问题：在整数区间【0，31】上求函数f(x)=x2的最大值。若采用传统方法，需要不断调治x参数的取值，直至获取最大的函数值为止。而采用遗传算法，优化过程的第一步的是把参数x编码为有限长度的字符串，常用二进制字符串，设参数x的编码长度为5，“00000”代表0，“11111”代表31，在区间【0，31】上的数与二进制编码之间采用线性照射方法；随机生成几个这样的字符串组成初始集体，对集体中的字符串进行遗产操作，直至满足必然的停止条件；求得最

4、后集体中适值最大的字符串对应的十进制数，其相应的函数值则为所求解。能够看出，遗传算法是对一个参数编码集体进行的操作，这样供应的参数信息量大，优化收效好。2）遗传算法是从好多点开始并行操作，其实不是限制于一点，进而可有效防范找寻过程收敛于局部最优解。3）遗传算法经过目标函数计算适值，其实不需要其他推导和附加信息，所以对问题的依赖性较小。4）遗传算法的寻优规则是由概率决定的，而非确定性的。5）遗传算法在解空间进行高效启示式找寻，而非盲目的穷举或完好随机找寻。6）遗传算法对求解的优化问题没有太多的数学要求。由于它的进化特色，它在解的找寻中不需要认识问题的内在性质。遗传算法能够办理任意形式的目标函数和

5、拘束，无论是线性的还是非线性的，失散的还是连续的，甚至是混杂的找寻空间。7）遗传算法拥有并行计算的特色，所以可经过大规模并行计算来提高计算速度。二、遗传算法的模式理论1、模式一个模式（schemata）就是一个描述种群在位串的某些确定地址上拥有相似性的一组符号串。为了描述一个模式，在用以表示位串的两个字符0，1中加入一个通配符“*”，就组成了一个表示模式用的3个字符的符号表0，1，*。所以用三个元素符号表0，1，*能够构造出任意一种模式。当一个模式与一个特定位串相般配时，意味着该模式中的1与位串中的1相般配，模式中的0与位串中的0相般配，模式中的“*”与位串中的0或1相般配。比方，模式00*0

6、0般配了两个位串，即00100，00000；模式*111*能够和01110，01111，11110，11111中的任何一个相般配；模式0*1则般配了长度为5，第一位为0、第三位为1的八个位串，即00100，00101，00110，00111，01100，01101，01110，01111。模式的思路供应了一种简单而有效的方法，使能够在有限符号表的基础上谈论有限长位串的慎重定义的相似性。应重申的是，“*”可是一个代表其他符号的一个元符号，它不能够被遗传算法直接手理，但能够据此计算出所有可能的模式。一般地，假设符号表的基数是k，比方0，1的基数是2，则定义在该符号表上的长度为l的位串中，所有可能包

7、括的最大模式数为（k+l）l,原因是在l个地址中的任何一个地址上即能够取k个字符中的任何一个又能够取通配符“*”，即共有k+l个不相同的表示，则ll5个地址的全排列数为（k+l）。比方，对长度l=5,k=2(对应0，1)，则会有33333=3=243=（k+l）l种不相同的符号串，而位串的数量仅为kl=25=32。可见，模式的数量要大于位串的数量。对于由0、1和*定义且长度为l的符号串所能组成的最大模式数为（2+l）l。对于任一长度为l的给定位串，当任一地址上只有两种不相同表示时，所含模式数为2l个，所以对于含有n个位串个体的种群可能包括的模式数在2ln2l之间。不难看出，遗产算法正是利用种群

8、中位串之间的众多的相似性以及适值之间的相关性，来引导遗传算法进行有效地找寻。为了区分不相同种类的模式，对模式H定义两个量：模式位数（order）和模式的定义长度（defininglength）分别表示为O(H)和(H)。O(H)是H中有定义的非“*”位的个数，模式定义长度(H)是指H中左右两端有定义地址之间的距离。这两个量为解析位串的相似性及解析遗传操作对重要模式的影响供应了基本手段。2、复制对模式的影响设在给准时间（代）t，种群A（t）包括m个特定模式H，记为m=m(H，t)在复制过程中，A（t）中的任何一个位串Ai以概率Pi=fi/fi被选中并进行复制。假如选择是有放回的抽样，且两代种群之

9、间没有交叠（即若A（t）的规模为n，则在产生A（t+1）时，必定从A（t）中选n个位串进般配集），能够希望在复制完成后，在t+1时刻，特定模式H的数量为：m(H,t+1)=m(H,t)nf(H)/fi其中，f(H)是在t时刻对应模式H的位串的平均适值，由于整个群的平均适值f=fi/n,则上式又可写为f(H)m(H,t+1)=m(H,t)f经过复制操作后，下一代中特定模式的数量H正比于所在位串的平均适值与种群平均适值的比值。若f(H)f,则H的数量将增加，若f(H)0）。从对复制的解析能够看到，诚然复制过程成功的以并行方式控制着模式数量以指数规模增减，但由于复制可是将某些高适值个体全盘复制，也许

10、裁汰某些低适值个体，而决不会产生新的模式构造，所以性能的改进是有限的。2、交织对模式的影响交织过程是位串之间有组织的随机的信息交换。交织操作对一个模式H的影响与模式的定义长度(H)相关，(H)越大，模式H被分裂的可能性越大，由于交织操作要随机选择出进行般配的一对位串上的某一随机地址进行交织。显然(H)越大，H的跨度就越大，随机交织点落入其中的可能性就越大，进而H的存活率就降低。比方位串长度l=7，有以下包括两个模式的位串A为A=01111000H1=*10,(H1)=5H2=*10,(H2)=1随机产生的交织地址在3和4之间A=0111000H1=*1*0,Pd=5/6H2=*10*,Pd=1

11、/6模式H1定义长(H1)=5，若交织点向来是随机地从l-1=7-1=6个可能的地址采用，则模式H1被破坏的概率为Pd=(H1)/(l-1)=5/6它的存活概率为Ps=1-Pd=1/6近似的，模式H2的定义长度(H2)=1，它被破坏的概率为Pd=1/6,它存活的概率为Ps=1-Pd=5/6.所以，模式H1比模式H2在交织中更简单碰到破坏。一般情况下能够计算出任何模式的交织存活概率的下限为(H)Ps1l1在上面的谈论中，均假设交织的概率为1。若交织的概率为Pc(即在选出进般配集的一对位串上发生交织操作的概率)，则存活率为(H)Ps1Pcl1在复制交织此后，模式的数量则为m(H,t1)m(H,t)

12、f(H)Ps即m(H,t1)m(H,t)f(H)1Pc(H)ffl1所以，在复制和交织的综合作用之下，模式H的数量变化取决于其平均适值的高低和定义长度的长短，f(H)越大，(H)越小，则H的数量就越多。3、变异对模式的影响变异是对位串中的单个地址以概率Pm进行随机代替，所以它可能破坏特定的模式。一个模式H要存活，意味着它所有的确定地址都存活。所以，由于单个地址的基因值存活的概率为1-Pm，而且由于每个变异的发生是统计独立的，所以，一个特定模式仅当它的O（H）个确定地址都存活是才存活，进而获取经变异后，特定模式的存活率为（1-Pm）O(H),即（1-Pm）自乘O(H)次，由于一般情况下Pm1,H

13、的存活率可表示为1-Pm）O(H)1-O(H)Pm综合考虑复杂、交织和变异操作的共同作用，则模式H在经历复制、交织、变异操作此后，在下一代中的数量可表示为m(H,t1)m(H,t)f(H)1Pc(H)1O(H)Pmfl1也可近似表示为m(H,t1)m(H,t)f(H)1Pc(H)O(H)Pmfl1由上述解析能够得出结论：定义长度短的、确定位数少的、平均适值高的模式数量将随着代数的增加呈指数增加。这个结论称为模式理论或遗传算法基本定理。依照模式理论，随着遗传算法一代一代地进行，那些定义长度短的，位数少的，高适值的模式将越来越多，所以可希望最后获取的位串的性能越来越获取改进，并最后趋向全局最优点。

14、三、遗传算法中适值的调整为了使遗传算法有效的工作，必定保持种群内位串的多样性和位串之间的竞争体系。现将遗传算法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一个规模不太大的种群内有少许非凡的个体（适值很高的位串），按平时的选择方法，这些个领悟被大量的复制，在种群中占有大的比重，这样就会减少种群的多样性，以致多早收敛，进而可能扔掉一些有意义的找寻点或最优点，而进入局部最优；在结束阶段，即便种群内保持了很大的多样性，但若所有或大多数个体都有很高的适值，进而种群的平均适值和最大值相差无几，则平均适值周边的个体和拥有最高适值的个体被选中的机遇相同，这样选择就成了一个近乎随机的步骤，适值的作用

15、就会消失，进而使找寻性能得不到显然的改进。所以，有必要对种群内各位串的适值进行有效的调整，既不能够相差太大，又要拉开品位，增强位串之间的竞争性。1、窗口法它是一种简单有效的适值调整方法，调整后的个体适值为Fj=fj-(fmin-a)其中，fj为原来个体的适值；为每代种群中个体适值的最小值；a为一常数。在进化的后期窗口法增加了个体之间的差异。2、函数归一法该法是将个体适值变换到最大值与最小值之间成必然比率的范围之内，这一范围由选择压力ksp决定。详尽步骤以下：（1）依照给定的选择压力ksp,求种群中适值调整后的适值最小值为fminfmaxFminksp1其中fmin和fmax是调整前种群个体适值

16、的最小值和最大值。适值调整后种群中适值最大值为Fmax=kspFmin（2）计算线性适值变换的斜率为F=FmaxFminfmaxfmin（3）计算每个个体的新适值为FjFminF(fjfmin)其中，fj为调整前第j个个体适值。在进化的早期，函数归一化法减小了种群内个体之间的差异，而在进化的后期又合适增大了性能相似个体之间的差异，加快了收敛速度。3、线性调整法线性调整法是一个有效的调整方法。设f是原个体适值，F是调整后个体的适值F=af+b，系数a、b可经过多种方法采用。但是，在任何情况下均要求Favg应与favg相等，即应满足的条件为Favg=favg，fmax=CmultFavg，其中Cm

17、ult是最正确种群所要求的希望副本数，是一个经验值，对于一个不大的种群来说，可能在2的范围内取值。正常条件下的线性调整方法以以下图正常条件下的线性调整法线性调整在遗传算法的后期可能产生一个问题是，一些个体的适值远远小于平均适值与最大值，而经常平均适值与最大适值又十分凑近，Cmult的这种选择方法将原始适值函数伸展成负值，以以下图，解决的方法是，当无法找到一个合适的Cmult时，保持Favg=favg，而将fmin照射到Fmin=0。线性照射方法之一四、高级遗传算法的实现方法1、局部找寻算法局部找寻算法是从爬山法改进而来的，设想要爬一座自己从未爬过的顶峰，目标是爬到山顶，那么如何设计一种策略使得

18、人们能够最快到达山顶呢在一般情况下，若是没有任何相关山顶的其他信息，沿着最陡的山坡向上爬，应该是一种不错的选择。这就是局部找寻算法中最基本的思想，即在找寻过程中，向来向着离目标最凑近的方向找寻。自然最优解能够是求最大值，也能够是求最小值，二者思想是相同的。在下面的谈论中若是没有特别说明，均假设最优解是最小值。局部找寻算法的一般过程是：随机选择一个初始的可能解x0D，xb=x0,P=N(xb)；D是问题的定义域，xb用于记录到目标地址获取的最优解，P为xb的领域。若是不满足结束条件，则结束条件包括达到了规定的循环次数、P为空等。Begin选择P的一个子集P,xn为p中的最优解若是f(xn)f(x

19、b)，P=P-xn=(a，d，c，b，e)，(a，e，c，d，b)，(a，b，d，c，e)，(a，b，e，d，c)，(a，b，c，e，d)。第二次循环：从P中随机选择一个元素，假设xn=(a，d，c，b，e)，f(xn)=45，f(xn)f(xb)，P=P-xn=(a，e，c，d，b)，(a，b，c，d，e)，(a，b，e，d，c)，(a，b，c，e，d)。第三次循环：从P中随机选择一个元素，假设xn=(a，e，c，d，b)，f(xn)=44，f(xn)f(xb)，P=P-xn=(a，b，d，c，e)，(a，b，e，d，c)，(a，b，c，e，d)。第四次循环：从P中随机选择一个元素，假设xn

20、=(a，b，d，c，e)，f(xn)=44，f(xn)f(xb)，P=P-xn=(a，b，e，d，c)，(a，b，c，e，d)。第五次循环：从P中随机选择一个元素，假设xn=(a，b，e，d，c)，f(xn)=34，f(xn)f(xb)，P=P-xn=(a，d，e，b，c)，(a，c，e，d，b)，(a，b，d，e，c)，(a，b，c，d，e)，(a，b，e，c，d)。第七次循环：从P中随机选择一个元素，假设xn=(a，d，e，b，c)，f(xn)=39，f(xn)f(xb)，P=P-xn=(a，c，e，d，b)，(a，b，d，e，c)，(a，b，c，d，e)，(a，b，e，c，d)。第八次循

21、环：从P中随机选择一个元素，假设xn=(a，c，e，d，b)，f(xn)=38，f(xn)f(xb)，P=P-xn=(a，b，d，e，c)，(a，b，c，d，e)，(a，b，e，c，d)。第九次循环：从P中随机选择一个元素，假设xn=(a，b，d，e，c)，f(xn)=38，f(xn)f(xb)，P=P-xn=(a，b，c，d，e)，(a，b，e，c，d)。第十次循环：从P中随机选择一个元素，假设xn=(a，b，c，d，e)，f(xn)=41，f(xn)f(xb)，P=P-xn=(a，b，e，c，d)。第十一次循环：从P中随机选择一个元素，假设xn=(a，b，e，c，d)，f(xn)=41，f

22、(xn)f(xb)，P=P-xn=。P等于空集，算法结束，获取结果为xb=(a，b，e，d，c)，f(xb)=34。在该问题中，由于初始值(abcde)的指标函数为38，已经是一个比较不错的结果了，在11次循环的找寻过程中，指标函数只下降了一次，最后的结果指标函数为34，这恰巧是该问题的最优解。从局部找寻的一般算法能够看出，该方法特别简单，但也存在一些问题。一般情况下，其实不能够上上例那样好运获取问题的最优解。2、模拟退火算法模拟退火算法是局部找寻算法的一种扩展，该算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问

23、题。作为求解复杂组合优化问题的一种有效的方法，模拟退火算法已经在好多工程和科学领域获取广泛应用。模拟退火算法是依照复杂组合优化问题与固体的退火过程之间的相似之处，在它们之间建立联系而提出来的。固体发热退火过程是一种物理现象，属于热力学和统计物理学的研究范围。当对一个固体进行加热时，粒子的热运动不断增加，随着温度的不断上升，粒子逐渐走开其平衡地址，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完好的无序状态。这就是固体的溶解过程。退火过程与溶解过程恰巧相反。随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不相同的状态，其排列也从无序向着有序方向发展，直至到温度很低时，粒

24、子重新以必然的构造排列。粒子不相同的排列构造，对应着不相同的能量水平。若是退火过程是缓慢进行的，也就是说，温度的下降若是特别缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0时，系统的能量将趋于最小值。若是以粒子的排列也许相应的能量来表达固体所处的状态，则温度T下，固体所处的状态拥有必然的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又阻挡了系统正确落入低能状态。依照这一物理现象，Metropolis给出了从状态i变换为状态j的准则：若是E(j)E(i)，则状态变换被接受；E(i)E(j)若是E(j)E(i)，则状态转移被接受的概率为：eKT，其中E(i)、

25、E(j)分别表示在状态i、j下的能量，T是温度，K0是波尔兹曼常数。Metropolis准则表达了这样一种现象：在温度T下，系统处于某种状态，由于粒子的运动，系统的状态发生渺小的变化，并以致了系统能量的变化。若是这种变化使得系统的能量减少，则接受这种变换；若是变换使得系统的能量增加，则以必然的概率接受这种变换。在给定的温度T下，当进行足够多次的状态变换后，系统将达到热平衡。此时系统处于某个状态i的概率由Boltzmann分布给出：E(i)E(j)eKT，其中ZTeKT为归一化因子，S是所有可能状态的会集。Pi(T)ZTjs在给定的温度T下，设有i、j两个状态，E(i)E(j)，则有：E(i)E

26、(j)E(i)eKTeKT1eKTPi(T)Pj(T)ZTe(1ZTZTeE(j)E(i)由于E(i)E(j)，所以eKT1E(j)E(i)E(j)E(i)KT1KT1KTE(i)eeKTZT所以有：Pi(T)Pj(T)0，即在任何温度T下，系统处于能量低的状态的概率大于能量高的状态的概率。当温度很高时有：E(i)lim(Pi(T)eKT1，其中s表示系统所有可能的状态数。limE(j)STTeKTjs由上式能够看出，当温度很高时，系统处于各个状态的概率基实情等，凑近于平均值，与所处状态的能量几乎没关。当温度很低时则有：E(i)lim(Pi(T)limeKTE(j)T0T0eKTjS设Sm表示

27、系统最小能量状态的会集，E(i)Emlim(Pi(T)limeKTE(j)EmT0T0eKTjSmEmEm是系统的最小能量。上式分子、分母乘以eKT有：E(i)EmlimeKTE(j)EmE(j)EmT0eeKTKTjSmjSmE(i)Em1，若是iSmeKT=limSmE(j)EmT00,若是iSmeKTjSm由上式能够看出，当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。由于：E(i)E(i)E(i)Pi(T)eKTE(i)eKT1ZTE(i)Pi(T)ZTT()KT2ZTZT2eKTTKT2Pi(T)TTZTZTE(j)E(j)E(i)Pi(T)

28、1Pi(T)eKTPi(T)E(j)eKT(E(i)E(j)=2ZTKT2KT2)KTjSjSZT=Pi(T2)(E(i)E(j)Pj(T)Pi(T2)(E(i)ET)KTjSKT其中：ETE(j)Pj(T)是温度T下，各状态能量的希望值。由于Pi(T)、K、T均大于0，jS所以有：Pi(T)0.若是E(i)ETT0,若是E(i)ET由此能够看出，系统落入能量较低的状态的概率是随温度T单调下降的，而系统落入高能量状态的概率是随温度T单调上升的。也就是说，系统落入低能量状态的概率随着温度的下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。总结可得出以下结论：在高温下，系统基本处于无

29、序状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于落入高能量状态的概率。这样在同一温度下，若是系统交换得足够充分，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐渐增加，而落入高能量状态的概率逐渐减小，使得系统各状态能量的希望值随温度的下降单调下降，而只有那些能量小于希望值的状态，其概率才随温度下降增加，其他状态均随温度下降而下降。所以，随着能量希望值的逐渐下降，能量低于希望值的状态逐渐减少，当温度趋于0时，只剩下那些拥有最小能量的状态，系统处于其他状态的概率趋近于0。所以最后系统将以概率1处于拥有最小能量的一个状态。固体退火过程，最

30、后达到最小能量的一个状态，从理论上来说，必定满足以下3个条件：初始温度必定足够高；在每个温度下，状态的交换必定足够充分；温度T的下降必定足够缓慢。受固体退火过程的启示，Kirkpatrick等人意识到组合优化问题与固体退火过程的近似性，将组合优化问题类比为固体的退火过程，提出了求解组合优化问题的模拟退货算法。设一个定义在有限集S上的组合优化问题，iS是该问题的一个解，f(i)是解i的指标函数。由组合优化问题与退火过程的类比关系，i对应物理系统的一个状态，f(i)对应该状态的能量E(i)，一个用于控制算法的进度、其值随算法进度递减的控制参数t对应固体退火中的温度T，粒子的热运动则用解在领域中的交换来代替。这样就将一个组合优化问题与固体退火过程建立了联系。在求解组合优化问题时，第一给定一个比较大的t值，这相当于给定一个比较高的温度T。随机给定一个问题的解i，作为问