遗传算法概述

遗传算法概述摘要：遗传算法（geneticalgorithms,GA）是人工智能的重要新分支，是基于达尔文进化论，在微型计算机上，模拟生命进化机制而发展起来的一门学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算机和问题求解。对许多用传统数学难以解决或明显失效的非常复杂的问题，特别是最优化问题，GA提供了一种行之有效的新途径。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业控制工程领域的成功应用，这种算法受到了广泛的关注。本文旨在叙述遗传算法的基本原理、操作环节和应用中的某些基本问题，以及为了改善SGA的鲁棒性而逐步发展形成的高级遗传算法（refinegeneticalgorithms,RGA）的实现办法。遗传算法的基本原理和特点遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个体进行筛选，从而使适值高的个体被保存下来，构成新的群体，新群体包含上一代的大量信息，并且引入了新一代的优于上一代的个体。这样周而复始，群体中各个体适值不停提高，直至满足一定的极限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂的空间进行全局优化搜索，并且含有较强的鲁棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如持续性、可微及单峰等）。同常规优化算法相比，遗传算法有下列特点。遗传算法是对参数编码进行操作，而非对参数本身。遗传算法首先基于一种有限的字母表，把最优化问题的自然参数集编码为有线长度的字符串。例如，一种最优化问题：在整数区间【0，31】上求函数f(x)=x2的最大值。若采用传统办法，需要不停调节x参数的取值，直至得到最大的函数值为止。而采用遗传算法，优化过程的第一步的是把参数x编码为有限长度的字符串，惯用二进制字符串，设参数x的编码长度为5，“00000”代表0，“11111”代表31，在区间【0，31】上的数与二进制编码之间采用线性映射办法；随机生成几个这样的字符串构成初始群体，对群体中的字符串进行遗产操作，直至满足一定的终止条件；求得最后群体中适值最大的字符串对应的十进制数，其对应的函数值则为所求解。能够看出，遗传算法是对一种参数编码群体进行的操作，这样提供的参数信息量大，优化效果好。遗传算法是从许多点开始并行操作，并非局限于一点，从而可有效避免搜索过程收敛于局部最优解。遗传算法通过目的函数计算适值，并不需要其它推导和附加信息，因而对问题的依赖性较小。遗传算法的寻优规则是由概率决定的，而非拟定性的。遗传算法在解空间进行高效启发式搜索，而非盲目的穷举或完全随机搜索。遗传算法对求解的优化问题没有太多的数学规定。由于它的进化特性，它在解的搜索中不需要理解问题的内在性质。遗传算法能够解决任意形式的目的函数和约束，无论是线性的还是非线性的，离散的还是持续的，甚至是混合的搜索空间。遗传算法含有并行计算的特点，因而可通过大规模并行计算来提高计算速度。遗传算法的模式理论模式一种模式（schemata）就是一种描述种群在位串的某些拟定位置上含有相似性的一组符号串。为了描述一种模式，在用以表达位串的两个字符｛0，1｝中加入一种通配符“*”，就构成了一种表达模式用的3个字符的符号表｛0，1，*｝。因此用三个元素符号表｛0，1，*｝能够构造出任意一种模式。当一种模式与一种特定位串相匹配时，意味着该模式中的1与位串中的1相匹配，模式中的0与位串中的0相匹配，模式中的“*”与位串中的0或1相匹配。例如，模式00*00匹配了两个位串，即｛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的位串中，全部可能包含的最大模式数为（k+l）l,因素是在l个位置中的任何一种位置上即能够取k个字符中的任何一种又能够取通配符“*”，即共有k+l个不同的表达，则l个位置的全排列数为（k+l）l。例如，对长度l=5,k=2(对应0，1)，则会有3×3×3×3×3=35=243=（k+l）l种不同的符号串，而位串的数量仅为kl=25=32。可见，模式的数量要不不大于位串的数量。对于由0、1和*定义且长度为l的符号串所能构成的最大模式数为（2+l）l。对于任一长度为l的给定位串，当任一位置上只有两种不同表达时，所含模式数为2l个，因此对于含有n个位串个体的种群可能包含的模式数在2l~n×2l之间。不难看出，遗产算法正是运用种群中位串之间的众多的相似性以及适值之间的有关性，来引导遗传算法进行有效地搜索。为了分辨不同类型的模式，对模式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被选中并进行复制。如果选择是有放回的抽样，且两代种群之间没有交叠（即若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,则上式又可写为m(H,t+1)=m(H,t)通过复制操作后，下一代中特定模式的数量H正比于所在位串的平均适值与种群平均适值的比值。若f(H)>,则H的数量将增加，若f(H)<，则H的数量将减少。即若包含H的个体位串的平均适值高于现在种群中全部个体位串的平均适值，则种群包含特模式的下一代中的数量将增加；反之，减少。操作中模式的增减在复制中是并行的，这恰恰体现了遗传算法隐含的并行性。为了进一步分析高于平均适值的模式数量的增加，假设（c是一种不不大于零的常数），则上式可写为：从原始种群开始（t=0），并假定是一种稳态的值，则有t可见，对于高于平均适值的模式数量将按指数规律增加（c>0）。从对复制的分析能够看到，即使复制过程成功的以并行方式控制着模式数量以指数规模增减，但由于复制只是将某些高适值个体全盘复制，或者裁减某些低适值个体，而决不会产生新的模式构造，因而性能的改善是有限的。交叉对模式的影响交叉过程是位串之间有组织的随机的信息交换。交叉操作对一种模式H的影响与模式的定义长度(H)有关，(H)越大，模式H被分裂的可能性越大，由于交叉操作要随机选择出进行匹配的一对位串上的某一随机位置进行交叉。显然(H)越大，H的跨度就越大，随机交叉点落入其中的可能性就越大，从而H的存活率就减少。例如位串长度l=7，有以下包含两个模式的位串A为A=01111000H1=*1****0,(H1)=5H2=***10**,(H2)=1随机产生的交叉位置在3和4之间A=H1=,Pd=5/6H2=,Pd=1/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在交叉中更容易受到破坏。普通状况下能够计算出任何模式的交叉存活概率的下限为Ps在上面的讨论中，均假设交叉的概率为1。若交叉的概率为Pc(即在选出进匹配集的一对位串上发生交叉操作的概率)，则存活率为Ps在复制交叉之后，模式的数量则为即因此，在复制和交叉的综合作用之下，模式H的数量变化取决于其平均适值的高低和定义长度的长短，f(H)越大，(H)越小，则H的数量就越多。变异对模式的影响变异是对位串中的单个位置以概率Pm进行随机替代，因而它可能破坏特定的模式。一种模式H要存活，意味着它全部的拟定位置都存活。因此，由于单个位置的基因值存活的概率为1-Pm，并且由于每个变异的发生是统计独立的，因此，一种特定模式仅当它的O（H）个拟定位置都存活是才存活，从而得到经变异后，特定模式的存活率为（1-Pm）O(H),即（1-Pm）自乘O(H)次，由于普通状况下Pm<<1,H的存活率可表达为（1-Pm）O(H)≈1-O(H)Pm综合考虑复杂、交叉和变异操作的共同作用，则模式H在经历复制、交叉、变异操作之后，在下一代中的数量可表达为也可近似表达为由上述分析能够得出结论：定义长度短的、拟定位数少的、平均适值高的模式数量将随着代数的增加呈指数增加。这个结论称为模式理论或遗传算法基本定理。根据模式理论，随着遗传算法一代一代地进行，那些定义长度短的，位数少的，高适值的模式将越来越多，因而可盼望最后得到的位串的性能越来越得到改善，并最后趋向全局最优点。遗传算法中适值的调节为了使遗传算法有效的工作，必须保持种群内位串的多样性和位串之间的竞争机制。现将遗传算法的运行分为开始、中间和结束三个阶段来考虑：在开始阶段，若一种规模不太大的种群内有少数不凡的个体（适值很高的位串），按普通的选择办法，这些个体会被大量的复制，在种群中占有大的比重，这样就会减少种群的多样性，造成多早收敛，从而可能丢失某些故意义的搜索点或最优点，而进入局部最优；在结束阶段，即使种群内保持了很大的多样性，但若全部或大多数个体都有很高的适值，从而种群的平均适值和最大值相差无几，则平均适值附近的个体和含有最高适值的个体被选中的机会相似，这样选择就成了一种近乎随机的环节，适值的作用就会消失，从而使搜索性能得不到明显的改善。因此，有必要对种群内各位串的适值进行有效的调节，既不能相差太大，又要拉开档次，强化位串之间的竞争性。窗口法它是一种简朴有效的适值调节办法，调节后的个体适值为Fj=fj-(fmin-a)其中，fj为原来个体的适值；为每代种群中个体适值的最小值；a为一常数。在进化的后期窗口法增加了个体之间的差别。函数归一法该法是将个体适值转换到最大值与最小值之间成一定比例的范畴之内，这一范畴由选择压力ksp决定。具体环节以下：根据给定的选择压力ksp,求种群中适值调节后的适值最小值为其中fmin和fmax是调节前种群个体适值的最小值和最大值。适值调节后种群中适值最大值为Fmax=kspFmin计算线性适值转换的斜率为△F=（3）计算每个个体的新适值为△其中，fj为调节前第j个个体适值。在进化的早期，函数归一化法缩小了种群内个体之间的差别，而在进化的后期又适宜增大了性能相似个体之间的差别，加紧了收敛速度。线性调节法线性调节法是一种有效的调节办法。设f是原个体适值，F是调节后个体的适值F=af+b，系数a、b可通过多个办法选用。但是，在任何状况下均规定Favg应与favg相等，即应满足的条件为Favg=favg，fmax=CmultFavg，其中Cmult是最佳种群所规定的盼望副本数，是一种经验值，对于一种不大的种群来说，可能在~2的范畴内取值。正常条件下的线性调节办法以下图正常条件下的线性调节正常条件下的线性调节法线性调节在遗传算法的后期可能产生一种问题是，某些个体的适值远远不大于平均适值与最大值，而往往平均适值与最大适值又十分靠近，Cmult的这种选择办法将原始适值函数伸展成负值，以下图，解决的办法是，当无法找到一种适宜的Cmult时，保持Favg=favg，而将fmin映射到Fmin=0。线性映射办法之一线性映射办法之一高级遗传算法的实现办法局部搜索算法局部搜索算法是从爬山法改善而来的，构想要爬一座自己从未爬过的高山，目的是爬到山顶，那么如何设计一种方略使得人们能够最快达成山顶呢在普通状况下，如果没有任何有关山顶的其它信息，沿着最陡的山坡向上爬，应当是一种不错的选择。这就是局部搜索算法中最基本的思想，即在搜索过程中，始终向着离目的最靠近的方向搜索。固然最优解能够是求最大值，也能够是求最小值，两者思想是同样的。在下面的讨论中如果没有特殊阐明，均假设最优解是最小值。局部搜索算法的普通过程是：随机选择一种初始的可能解x0∈D，xb=x0,P=N(xb)；D是问题的定义域，xb用于统计到目的位置得到的最优解，P为xb的领域。如果不满足结束条件，则结束条件涉及达成了规定的循环次数、P为空等。Begin选择P的一种子集P’,xn为p’中的最优解如果f(xn)<f(xb),则xb=xn,P=N(xb),转②；f(x)为指标函数。否则P=P-P’,转②。End输出计算成果结束在算法第4步，选择P的一种子集P’，能够根据问题的特点，选择适宜大小的子集。极端状况下，能够选择P’为P本身，或者是P的一种元素。后者状况下能够采用随机选择的方式从P中得到一种元素。设五都市旅行商问题以下图所示，用局部搜索办法求解该问题。假设从都市a出发，我们用都市的序列表达该问题的一种可能解。设初始生成的可能解为：x0=（a,b,c,d,e）则根据各都市间的距离计算得到旅行商的旅行距离：f(xb)=f(x0)=38首先选择两个都市间的位置变换方式得到一种可能解的领域，并在算法的第④步选择从p中随机选择一种元素的办法。则算法的执行过程以下：P={(a,c,d,b,e),(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，c，b，d，e)，f(xn)=42，f(xn)>f(xb)，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=(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)，xb=(a，b，e，d，c)，P={(a，e，b，d，c)，(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，e，b，d，c)，f(xn)=44，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)}。第八次循环：从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(xn)>f(xb)，P=P-{xn}={}。P等于空集，算法结束，得到成果为xb=(a，b，e，d，c)，f(xb)=34。在该问题中，由于初始值(abcde)的指标函数为38，已经是一种比较不错的成果了，在11次循环的搜索过程中，指标函数只下降了一次，最后的成果指标函数为34，这刚好是该问题的最优解。从局部搜索的普通算法能够看出，该办法非常简朴，但也存在某些问题。普通状况下，并不能上上例那样幸运得到问题的最优解。模拟退火算法模拟退火算法是局部搜索算法的一种扩展，该算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。作为求解复杂组合优化问题的一种有效的办法，模拟退火算法已经在许多工程和科学领域得到广泛应用。模拟退火算法是根据复杂组合优化问题与固体的退火过程之间的相似之处，在它们之间建立联系而提出来的。固体发热退火过程是一种物理现象，属于热力学和统计物理学的研究范畴。当对一种固体进行加热时，粒子的热运动不停增加，随着温度的不停上升，粒子逐步脱离其平衡位置，变得越来越自由，直达成到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。这就是固体的溶解过程。退火过程与溶解过程刚好相反。随着温度的下降，粒子的热运动逐步削弱，粒子逐步停留在不同的状态，其排列也从无序向着有序方向发展，直至到温度很低时，粒子重新以一定的构造排列。粒子不同的排列构造，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达成一种平衡态，则当温度趋于0时，系统的能量将趋于最小值。如果以粒子的排列或者对应的能量来体现固体所处的状态，则温度T下，固体所处的状态含有一定的随机性。首先，物理系统倾向于能量较低的状态，另首先，热运动又妨碍了系统精确落入低能状态。根据这一物理现象，Metropolis给出了从状态i转换为状态j的准则：如果E(j)≤E(i)，则状态转换被接受；如果E(j)＞E(i)，则状态转移被接受的概率为：，其中E(i)、E(j)分别表达在状态i、j下的能量，T是温度，K>0是波尔兹曼常数。Metropolis准则体现了这样一种现象：在温度T下，系统处在某种状态，由于粒子的运动，系统的状态发生微小的变化，并造成了系统能量的变化。如果这种变化使得系统的能量减少，则接受这种转换；如果变换使得系统的能量增加，则以一定的概率接受这种转换。在给定的温度T下，当进行足够多次的状态转换后，系统将达成热平衡。此时系统处在某个状态i的概率由Boltzmann分布给出：，其中为归一化因子，S是全部可能状态的集合。在给定的温度T下，设有i、j两个状态，E(i)<E(j)，则有：由于，因此因此有：，即在任何温度T下，系统处在能量低的状态的概率不不大于能量高的状态的概率。当温度很高时有：，其中表达系统全部可能的状态数。由上式能够看出，当温度很高时，系统处在各个状态的概率基本相等，靠近于平均值，与所处状态的能量几乎无关。当温度很低时则有：设Sm表达系统最小能量状态的集合，Em是系统的最小能量。上式分子、分母乘以有：=由上式能够看出，当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处在其它状态的概率为0。由于：==其中：是温度T下，各状态能量的盼望值。由于Pi(T)、K、T均不不大于0，因此有：由此能够看出，系统落入能量较低的状态的概率是随温度T单调下降的，而系统落入高能量状态的概率是随温度T单调上升的。也就是说，系统落入低能量状态的概率随着温度的下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。总结可得出以下结论：在高温下，系统基本处在无序状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率不不大于落入高能量状态的概率。这样在同一温度下，如果系统交换得足够充足，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减小，使得系统各状态能量的盼望值随温度的下降单调下降，而只有那些能量不大于盼望值的状态，其概率才随温度下降增加，其它状态均随温度下降而下降。因此，随着能量盼望值的逐步下降，能量低于盼望值的状态逐步减少，当温度趋于0时，只剩余那些含有最小能量的状态，系统处在其它状态的概率趋近于0。因此最后系统将以概率1处在含有最小能量的一种状态。固体退火过程，最后达成最小能量的一种状态，从理论上来说，必须满足下列3个条件：初始温度必须足够高；在每个温度下，状态的交换必须足够充足；温度T的下降必须足够缓慢。受固体退火过程的启发，Kirkpatrick等人意识到组合优化问题与固体退火过程的类似性，将组合优化问题类比为固体的退火过程，提出了求解组合优化问题的模拟退货算法。设一种定义在有限集S上的组合优化问题，i∈S是该问题的一种解，f(i)是解i的指标函数。由组合优化问题与退火过程的类比关系，i对应物理系统的一种状态，f(i)对应当状态的能量E(i)，一种用于控制算法的进程、其值随算法进程递减的控制参数t对应固体