遗传算法的研究和改进

遗传算法的研究和改进 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题，本论文研究内容包括：小生境遗传算法的改进、自适应遗传算子的设计、免疫的进化算法。本文主要工作如下：（1）遗传算法的起源、其基本概念以及研究概况;（2）遗传算法的基本理论.主要介绍了模式定理、积木块假说、内在并行性、Walsh模式变换、欺骗问题等;（3）基本遗传算法.主要介绍了编码、适应度函数、遗传操作等.（4）遗传算法的改进.主要介绍了分层遗传算法、CHC算法、messy遗传算法、自适应遗传算法、基于小生境技术的遗传算法、混合遗传算法等几种遗传算法的改进.（5）遗传算法的应用. 关键词：遗传算法;进化计算;进化规划;进化策略;遗传操作;适应度函数;Walsh函数ABSTRACT Genetic algorithm is a kind of random searching method using lives natural selection and genetic mechanism. Its application predominance lies in complicated and non-linear problems, which are difficult for traditional searching methods. Three improved algorithms are proposed in the dissertation: improved niche genetic algorithm, improved adaptive genetic algorithm, genetic algorithm based on immune mechanism. They are summarized as following: Firstly, the dissertation analyses characters of several traditional genetic algorithms for niche. Following this, a new method, combined parallelism evolution technique for niches based on local competition with parent mutation mechanism, is proposed which improved the genetic algorithms for niche. Compared with genetic algorithm with sharing, it has some improvements in both converging velocity and precision. Secondly, analyzing the inadequacies of the evaluation indices for premature convergence, a novel improved adaptive genetic algorithm (IAGA) is described. The calculation result of an example shows that IAGA is able to get the real-time information of population diversity during the process of evolution. Finally, applying the immune mechanism to genetic algorithm, the immune genetic algorithm expatiated on this paper comes over the phenomenon of premature in some extent. The result of experiment shows that the global convergence and searching velocity are both improved. Keyword: genetic algorithms, evolution strategy, Walsh function第一章 绪论 1.1 引言 遗传算法（Genetic AlgorithmGA），是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法 1。它借鉴生物界自然选择和自然遗传机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的最优解。 遗传算法的兴起是在80年代末90年代初期，但是它的历史可以追溯到60年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的研究特点是侧重于对一些复杂的操作的研究。其中像自动博弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象，但总的说来，这是一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具的开拓。这种现象直到70年代中期由于Holland和DeJong的创造性研究成果的发表才得到改观 1,2。1967年，Bagley在他的论文中首次提出了遗传算法（genetic algorithm）这一术语，并讨论了遗传算法在自动博弈中的应用 3。1970年，Cavicchio把遗传算法应用于模式识别中 4。第一个把遗传算法应用于函数优化的是Hollstien 5，1971年他在论文计算机控制系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。1975年在遗传算法研究的历史上是十分重要的一年，Holland出版了他的著名专著自然系统和人工系统的适配 1，该书系统的阐述了遗传算法的基本理论和方法，并提出了对遗传算法理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。J. Holland教授和他的研究小组围绕遗传算法进行研究的宗旨有两个：一是抽取和解释自然系统的自适应过程，二是设计具有自然系统机理的人工系统。同年，DeJong完成了他的重要论文遗传自适应系统的行为分析，他把Holland的模式理论和他的计算实验结合起来，这可以看作遗传算法发展过程中的一个里程碑，尽管DeJong和Hollstien一样主要侧重于函数优化的研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术，为遗传算法及其应用打下了坚实的基础。进入80年代，遗传算法迎来了兴盛发展时期，理论研究和应用研究都成了十分热门的话题。 遗传算法有其自身的特点：智能性与本质并行性。遗传算法的智能性包括自组织、自适应和自学习等，应用遗传算法求解问题时，在确定了编码方案、适应值函数及遗传算子后，算法将应用演化过程中获得的信息进行自组织搜索，适者生存的选择策略赋予了遗传算法自适应的能力，同时也赋予了它根据环境的变化自动发现环境的特征和规律的能力；遗传算法的本质并行性表现在两个方面：一是遗传算法的内在并行性，即其本身非常适合大规模并行，二是遗传算法的内含并行性，即它可以同时搜索解空间内的多个区域，并且相互之间进行信息交流，这种搜索方式使得遗传算法可以以较少的计算获得较大的收益。这些特点使得遗传算法广泛应用于控制、规划、设计、组合优化、图像处理、信号处理、机器人、人工生命等多个领域。 1.2 遗传算法简介 1.2.1 遗传算法的基本概念 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征才能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理产生的直接搜索优化方法，所以在这个算法中要用到各种进化和遗传学的概念。这些概念如下： 一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。 二、种群 (Population) 个体的集合称为群体，串是种群中的元素 三、种群大小(Population Size) 在种群中个体的数量称为种群的大小。 四、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1011这4个元素分别称为基因。基因所取的的值称为等位基因(Alletes)。 五 、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置在串中由左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。 六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 七、串结构空间S S 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 八、参数空间S P 这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 九、适应度(Fitness) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。 1.2.2 遗传算法的基本原理 遗传算法GA把问题的解表示成“染色体”，在算法中也就是二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串b i处，即求出最优解。 长度为L的n个二进制串bi(i1，2，n)组成了遗传算法的初始解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种： 1选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。 2交叉(Crossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。交叉算子示意如图1.1。图1.1 交叉算子示意图 3变异(Mutation) 这是在选中的个体中，对个体中的某些基因按变异概率P m执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成 0；反亦反之。 1.2.3 遗传算法的步骤和意义 1初始化 选择一个群体，即选择一个串或个体的集合b i，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。 通常以随机方法产生串或个体的集合b i,i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。 2选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f，则f(bi)称为个体bi的适应度。以公式（1-1） nbjfiiPnj1)(选 中为选中bi为下一代个体的次数。 显然从上式可知： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少，甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。 3交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交叉概率P。取值为0.250.75。 4变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，4位置的基因进行变异，则有 S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为当所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 5全局最优收敛(Convergence to the global optimum) 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。 图1.2中表示了遗传算法的执行过程 图1.2 遗传算法原理 1.3 遗传算法研究现状 近年来有关遗传算法的期刊论文和会议论文每年都有数百乃至上千篇，这些文献主要是从某个方面对遗传算法进行不同形式的改进，并且都有针对性的用于解决某类实际问题。下面从几个方面进行讨论： 1编码表示 Holland在运用模式定理分析编码机制时，建议使用二进制编码，但二进制编码不能直接反映问题的固有结构，精度不高，个体长度大，占用计算机内存多。Gray编码是将二进制编码通过一个变换进行转换得到的编码，其目的是克服Hamming悬崖的缺点 6，动态编码 7（dynamic encoding）GA是当算法收敛到某局部最优时增加搜索的精度，从而使得在全局最优解附近可以进行更精确的搜索，增加精度的办法是在保持串长不变的前提下减小搜索区域，对于问题的变量是实向量的情形，可以直接采用实数进行编码，这样可以直接在解的表现形上进行遗传操作从而便于引入与问题领域相关的启发式信息以增加算法的搜索能力 8,9。复数编码10的GA是为了描述和解决二维问题，基因用x+yi表示；它还可以推广到多维问题的描述中，多维实数编码 11GA使无效交叉的可能性大大降低，同时其合理的编码长度也有助于算法在短时间内获得高精度的全局最优解。当问题表示的是树和图时，我们还可以使用结构式编码。 2适应度函数 适应度函数是用来区分群体中个体好坏的标准，是自然选择的唯一标准，选择的好坏直接影响算法的优劣。引入适应值调节和资源共享策略可以加快收敛速度和跳出局部最优点。对适应值进行调节就是通过变换改变原适应值间的比例关系，常用的比例变换有线性变换、乘幂变换和指数变换等；对于一个问题采用什么变换才能达到较优的效果。V. Kreinobich12等做了较详细的讨论，而S W Mahfoud采用了共享的技术 13，对子群的形成和稳定起了一定作用，文中主要用子群消失时间的近似形式估计Sharing的界。V Petridis采用了依据搜索进展可变的适应值函数 14，并用于分割问题，取得了较好的效果。杨旭东等设计了自适应选取遗传算法的适应值函数的方法 15，该方法的计算量要比排序选择的计算量小的多，而且有效的避免了算法的早熟收敛。 3选择策略 优胜劣汰的选择机制使得适应值大的个体有较大的存活机会，不同的选择策略对算法的性能有较大的影响。赌轮选择是使用最多的选择策略，但这种策略可能会产生较大的抽样误差，于是对此提出了很多的改进方法，如繁殖池选择 16，Boltamann选择 17等等，但是这几种策略都是基于适应值比例的选择，常常会出现早熟收敛和停滞现象。为此又提出了非线性排名选择 8，这种选择不仅避免了上述问题，而且可以直接采用原始适应值进行排名选择，而不需对适应值进行标准化；但这种选择在群体规模很大时，其额外计算量（如计算总体适应值和排序）也相当可观，甚至在进行并行实现时会带来一些同步限制。基于局部竞争机制的选择如（）选择 18，它使双亲和后代有同样的生存竞争机会，在一定程度上避免了这些问题。D T Pham等采用了类似梯度的方式来选择 19，不仅使较差的染色体比较好的染色体得到更大的改进，而且还不断产生新的个体，从而不断拓展了新的空间。D Nover等引入了Harvesting Strategies来分析遗传算法的性能 20，Harvesting Strategies是指在每一代交叉和突变后进行两次乃至多次筛选作为下面的群体。T Kao采用了Disruptive Selection21，它吸收了优等和劣等个体，实验结果表明了两级分化有可能更容易找到最优解。为了提高种群的多样性，高峰提出了一种基于免疫多样性的选择算子 22，该选择算子依赖于串的稠密度和适应值，串的稠密度越大，其保留下来的可能性就越小，具体事例证明改进算法是有效的。 4控制参数 控制参数一般都有种群大小、交换概率、变异概率等，这些参数对遗传算法性能影响较大。在标准遗传算法中采用经验进行估计，这将带来很大的盲目性，而影响算法的全局最优性和收敛性。目前许多学者意识到这些参数应该随着遗传进化而自适应的变化，Davis提出自适应算子概率方法 23，即用自适应机制把算子概率与算子产生的个体适应性相结合，高适应性值被分配高算子概率。Whitley提出一种自适应突变策略与一对父串间的Hamming距离成反比 24，结果显示能有效的保持种群的多样性。张良杰等通过引入i位改进子空间概念，采用模糊推理技术来确定选取突变概率的一般性原则 25。Arabas等设计了一种群体规模可变的遗传算法 26，它提出每个个体应该有年龄和生命周期的概念并淘汰年龄大于生命周期的个体，从而使遗传算法动态的控制了群体数目，这种方法可以找出一个接近最小代价的遗传算法，同时尽量将群体规模保持在现有水平，防止群体规模指数级增长，以降低计算的开销。丁承明等提出利用正交试验法去优化选取GA控制参数 27，这种方法利用正交试验的均衡分布性使得通过较少的试验就可搜索绝大部分参数组合空间，而且还可以确定那个参数对GA结果影响最显著，然后针对性的进行精确搜索，从而使得GA参数问题得到圆满的解决。为保证种群的有用多样性，提出动态种群法 28，即当迭代到一定代数，若目标函数的值相同，则现存种群中的较差的N个染色体被随机产生的N个染色体所代替，使进化过程中不断有新个体引入。刘丽利用模糊规则对选择概率和变异概率进行控制 29，在线改变其值，相应的算例表明其有较好的性能。 5遗传算子 基本遗传算法中采用单点交叉算子和简单的变异算子。它们操作比较简单，计算量小，但是在使用过程中有很大的局限性，例如：由于单点交叉破坏模式的概率较小，致使搜索到的模式数也较少，使算法具有较低的搜索能力。Feng etal. 对多维连续空间的GA复杂多样性进行了分析，通过建立相应的数学模型，Feng等解释了在多维连续空间和大规模群体中使用均匀杂交算子 30是如何探索新的解空间区域，为了使得变异能够根据解的质量自适应的调整搜索区域，从而能较明显的提高搜索能力，提出自适应变异算子 31。为了保护适应值较高的模式，提出了自适应交叉和变异 32，如果遇到适应值较高的模式，则通过随机引入模式外的位进行保护。为了克服早熟，引入多种群GA 33，不同种群赋以不同的参数，实现不同的搜索目的，通过移民算子联络各种群，通过人工选择算子保存各种群每个进化代中的最优个体。为了防止近亲繁殖，扩大种群的多样性，抑制超长个体快速繁殖，引进近亲繁殖算子，两个个体是否为近亲可以通过基因片段的Hamming距离来判断，距离越大，则为近亲的可能性越小；为了加强局部搜索能力，增加漂移算子，将染色体各基因片段的后二分之一的基因分别按一定的概率做1的漂移，排位越后的基因漂移的概率越大，由此产生一定数量的新个体，用基因预选机制的小生境技术控制漂移方向 34。因为格点法产生的点集能均匀的分布于搜索空间，并且佳点又是最好的格点，所以可以用数论中的佳点集理论设计交叉算子 35，结果表明它的搜索效果要比纯随机方法好，而且有效的避免早熟现象。基于生物免疫性提出的免疫算子 36，能够明显抑制进化过程中的退化现象，减轻GA的后期波动，从而提高了搜索效率和收敛速度。 6综合方面 孙建永等提出了可分解/可拼接GA编码 37，并基于此编码分别在种群层次和编码层次发展了动态变异和动态选择操作，这种方法很大程度上避免了早熟问题。增强型GA中 38，引入了几个新算子和新的种群迁移策略，并用其对模糊逻辑控制器进行设计，得到了便于理解的模糊集和模糊规则。用小波分析中的多尺度分析对GA中的染色体进行多尺度分解，这样分解后的染色体长度变短，基因交换、变异等遗传操作更为彻底，有效的克服了基因丢失引起的早熟问题39。小生境技术不仅能够保证种群中解的多样性，而且具有很强的引导进化能力，所以小生境技术的引入，提高了GA处理多峰函数优化问题能力 40。将模拟退火过程引入遗传算法 41，在优选交叉和变异个体的过程中加入一定的“扰动”，以达到保持种群内位串的多样性和位串之间的竞争机制，克服了算法易陷入局部极小点的问题，使得搜索沿着全局最优方向进行。广义遗传算法 42，它以多点突变操作为主，以基因交叉操作为辅，实现了从一个局部最优状态到另一个局部最优状态的转移，使得算法获得全局最优。为了使GA用于约束最优化，提出了一种非稳态罚函数GA 43，非稳态罚函数是遗传代数的函数，当代数增加时，罚函数也随着增大，同时给GA也带来更多的选择压力，促使GA找到可行解。综合遗传算法的全局性和神经网络的并行快速等特点，提出的遗传神经网络算法 44，可克服遗传算法最终进化至最优解速度较慢和神经网络易陷入局部最优解的缺陷，具有较好的全局性和收敛速度。采用面向对象技术设计了面向对象遗传算法 45，这种方法改变了传统的GA中各个函数间只有参数的传递，而没有代码的继承性的状况，从概念上提高了软件的可重用性，用户可以更方便的实现自己的编码方案和遗传算子。变异基遗传算法 46，采用变异算子进行局部优化搜索，并利用随机初始化技术使算法在局部搜索能力提高的同时仍有可能找到全局最优解。贪婪遗传算法 47在二次分配问题中取得了较好的效果，在该算法中引入了新的交叉算子和移民算子，保证了种群的多样性，并且通过比赛竞争使得各种群得到进化，很好的解决了种群多样性及对个别好个体偏爱之间的矛盾。 1.4 本文主要内容 近年来，遗传算法在许多领域都得到了广泛的应用。本文在对大量的相关文献资料进行研究的基础上，针对现有的遗传算法的不足，提出了几种改进的算法。本文内容安排如下： 第一章简要介绍了遗传算法的基本概念、原理、步骤及意义，并概述了遗传算法的发展现状。 第二章叙述了遗传算法的主要理论：模式定理、内含并行性，以及最优保留遗传算法的收敛性。 第三章在对现有的小生境技术的研究基础上，基于遗传算法作用机理分析，将小生境技术与双亲变异相结合，提出了一种改进的小生境遗传算法，相对于基于共享的小生境遗传算法，其收敛速度