毕业设计（论文）-基于小生境遗传算法的多峰函数优化问题的研究.doc

编号： 本科毕业设计（论文）题目：（中文）基于小生境遗传算法的多峰函数优化问题的研究（ENGLISH)Niche Genetic Algorithm For Multimodal Function Optimization Problems学院信息科学与工程学院专业电气工程与自动化班级自动化学号 姓名 指导教师职称完成日期2015年2月5日基于小生境遗传算法的多峰函数优化问题的研究诚 信 承 诺我谨在此承诺：本人所写的毕业论文基于小生境遗传算法的多峰函数优化问题的研究均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。承诺人（签名）： 年 月 日摘 要【摘要】遗传算法由于其良好的搜索特性，在函数优化问题上取得了很多的应用。但简单遗传算法（SGA）的解决多峰函数的优化问题时，具有诸多不足之处，主要是早熟收敛现象。为了提高遗传算法的性能，提出基于淘汰机制的小生境的遗传算法。在matlab上实现算法，测试了8个函数与SGA相比较，无论是一维的还是多维的多峰函数，小生境遗传具有更快的收敛速度，收敛概率以及收敛精度，更好的效果，更高的可靠性。【关键词】遗传算法；多峰函数优化；淘汰小生境英文题目Abstract【ABSTRACT】 because of its excellent search features,Genetic algorithms made a lot of applications in function optimization problems . But the simple genetic algorithm(SGA)has many shortcomings when solve multimodal function optimization problems,mainly premature convergence phenomenon.In order to improve the performance of genetic algorithm, iproposed a niche genetic algorithm based on elimination mechanism.Algorithmed in matlab, and test eight function compared with the SGA, both one-dimensional or multi-dimensional multi-peak function, niche genetic algorithmwith has faster convergence rate, better convergence probability and better convergence precision, better results and more high reliability.【KEYWORDS】Genetic algorithms;multimodal function optimization;niche .目 录第一章 绪论11.1 函数优化与优化算法11.1.1 最优化问题11.1.2 函数优化和组合优化11.1.3 优化算法11.2 智能优化算法：遗传算法的应用21.3 遗传算法的国内外研究现状31.4 本论文的选题意义41.5 本论文的主要工作4第二章 遗传算法的基本理论62.1 遗传算法的生物学基础62.2 遗传算法的发展概况72.3 遗传算法的结构与实现72.3.1 遗传算法的结构72.3.2 遗传算法概要72.3.3 遗传算法的实现82.4 遗传算法的操作102.4.1 编码策略102.4.2 适应度函数122.4.3 遗传算子132.5 遗传算法的运行参数162.6 遗传算法的特点172.7 遗传算法的不足172.8 遗传算法的改进182.9 本章小结19第三章 基于小生境的遗传算法203.1 物种形成与小生境技术203.2 常用的小生境技术213.2.1 基于预选择(Preseleetio）机制的小生境213.2.2 基于排挤(crowding）机制的小生境213.2.3 基于共享（sharing）机制的小生境223.3 小生境遗传算法的结构与实现233.4 小生境遗传算法的发展状况243.5 本章小结24第四章 基于淘汰机制的小生境遗传算法264.1 淘汰小生境遗传算法264.2 淘汰小生境算法的实现264.3 与基本遗传算法的比较294.3.1 测试函数294.3.2 数据分析304.4 本章小结33第五章 结论与展望34参考文献35致 谢36附录3745第一章 绪论1.1 函数优化与优化算法1.1.1 最优化问题在工程应用中，经常会遇到最优化的问题，比如在安排生产计划方面，如何在现有的人力，物力等条件下，合理的安排生产，使总生产和总利润最高，这就是一个实际应用中的一个最优化问题，即从多个可能的方案中选出最合理的、能实现预定最优目标的方案，这个方案就叫做最优方案。然后找到最优方案的方法就叫最优化方法。然后找到最优方案的方法就叫最优化方法。优化问题涉及到的区域很多，总的来说可以分为函数优化和组合优化。函数优化对应的是连续函数，组合优化对应的是离散函数。12。1.1.2 函数优化和组合优化函数优化的一般问题描述：令S为R上的一个子集（即变量的定义域），为n维实质数，函数f在定义域内的求解最小值优化问题就是寻求点使得在S这个域上全局最小，即 （1-1）组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令为所有状态构成的解空间，为状态si对应的目标函数值，要求寻找最优解，使得对于所有的，有。组合优化往往涉及排序、分类、筛选等问题，它属于运筹学的一个分支。组合优化的典型问题有旅行商问题（Traveling Salesman ProblemTSP）、0-1背包问题（Knapsack Problem）等。这些问题描述非常简单，并且有很强的工程代表性，但是求解却显得非常的困难，因为如果运用已有的算法去求解的话将要花费相当大的时间和存储空间，很难再目前的计算机上完成。正是这样的困难的问题的出现激起了众多学者们去对它进行研究。1.1.3 优化算法所谓优化算法，就是搜索最优解的过程中的一种规则或协议。通过一定的途径或规则来得到满足用户的问题的解。就优化机制与行为来分，目前工程中常用的优化算法主要可分为：经典优化算法、智能优化算法、构造型优化算法、混合型优化算法。1) 经典优化算法以传统运筹学中的线性规划和整数规划等为代表，算法计算规模一般很大，一般适用于小规模的优化问题。2） 构造型优化算法快速的构造问题的解，但是一般算法的优化性能差，不能达到相应的要求。例如，调度问题中的典型构造方法也有：johnson法、Palmer法、Gupta法、CDS法NEH法等3） 智能优化算法智能优化算法是通过仿真一些某些自然规律或现象而来的，也像一般的搜索方法一样是通过不断的迭代来显示的，无需利用到函数的的微分和倒数等的特性，是从产生第一组解开始，同时把问题用一种规则进行编码，反映成一种可以进行启发操作的数学构造，只需用到问题的函数值，就没有必要用到倒数微分等信息，从而减小了计算的复杂性，而且整个搜索过程是随机进行的。优点：具有良好的具有优化能力，具有鲁棒性，通用性能好，应用比较广泛，尤其适合在大规模的场合下进行。主要有进化算法、蚁群算法等等。4) 混合算法指上述算法从结构或者操作上相混合而产生的各类算法，取长补短，提高算法的性能，有着更多应用。1.2 智能优化算法：遗传算法的应用遗传算法以其鲁棒性，众多的优点被成功应用到优化问题中，但是在许多其他的领域也获得了许多的应用。（1)函数优化函数优化是遗传算法最早也最成功应用的领域。因此人们构造了许多的测试函数来评价各种遗传算法的优劣。在一些非线性的、多峰函数等等，以前的哪些优化算法不能求解，然后对于遗传算法却是轻松加愉快。 （2）组合优化 对于离散的组合优化问题，以前可以用枚举的方法来求解，但是如果更复杂，规模更大的问题，枚举话显得有些吃力了。遗传算法也成功的应用到组合优化领域，成功的解决了TSP等组合优化问题。（3）生产调度问题生产调度一般是通过把问题建立数学模型后来求解的，不说建模的过程是不是准确，是不是能实现，就算是建模完成后，问题的求解可能也会比较困难。遗传算法的发展也成功解决了这一难题，在生产车间中获得了许多的应用。（4）自动控制其实属于优化问题中的一类。因为自动控制的过程也是需要求解的。（5）机器人学遗传算法算法是仿生的，机器人学也是属于仿生学，是不是能将两个仿生学成功的结合呢。也是一个方向。（6）图像处理对于复杂的图像处理系统。遗传算法也能成功的应用，在识别，特征选择和特征提取等方面取得较好的效果。（7） 人工生命人工系统一个很重要的方面就是需要有自适应能力和学习能力。遗传算法本来就是自适应的搜索算法，加上他的知识约简的发展，将会很快的应用到人工生命。（8）遗传编程1989年，美国斯坦福大学的Koza教授提出了遗传编程。通过学习自适应的编写出程序，还处于启蒙阶段。（9） 机器学习自适应系统的一个重要能力就是学习知识。相信通过遗传算法能实现一种分类器，类似于神经网络等等。（10）数据挖掘Sunil已成功地开发了一个基于遗传算法的数据挖掘工具13。1.3 遗传算法的国内外研究现状20世纪90年代，是遗传算法发展的繁荣时期，对它的论文眼还是对它的应用的研究都是非常活跃的。理论基础的不断完善也增加了它在各个领域的实际应用，从以前简单的函数优化应用到各种更复杂的更系统的实际工程应用中。而且理论的研究也不断的浮现，各种改善的遗传算法不断的出现，例如各种混合的遗传算法，还有小生境遗传算法等等。现在对遗传算法的研究主要主要集中在以下几个：（1） 机器学习。这个的应用是遗传算法从一种原有的搜索算法到知识学习算法的一种巨大的转变，给遗传算法发展注射了新的血液。（2） 混合的遗传算法取长补短经常是用来解决一些问题的方法手段，这在遗传算法的发展上也有着同样的效果，遗传算法与其他算法的结合有着重大的意义。（3） 并行的遗传算法D.Whitey提出了领域交叉算子。成功的应用到了TSP问题中。D.H.Ackley等提出了随机迭代遗传爬山法。他们模仿了人们选举干部的一个过程，并成功的应用到遗传算法，与经典的遗传算法相比有着更好的性能。H.Bersini和G.Seront又对遗传算法的交叉算子进行了研究和改良，提出了一种多亲交叉算子，与传统的交叉算子相比，这种算子具有很好的性能。国内的研究主要有以下代表：戴晓明等的并行遗传算法，多个种群并行的进行搜索，而且不同的种群应用进行相对应的遗传操作，提高了遗传算法在局部搜索能力不足的问题。赵宏立等提出了并行遗传算法，编码方式是采用了一种新的基因快编码方式，能有效的解决复杂的组合优化问题性能不足的问题。后面江雷研究发现了一种弹性策略，利用这种策略来保持种群的多样性，避免算法的局部收敛，成功的应用到求解TCP问题。1.4 本论文的选题意义对于目标函数的多个极值点，通常人们只关心目标函数的全局最优点，但有时函数的多个、甚至所有极值点都是有意义的。像在很多实际应用问题中,如工程设计、组合优化、决策等问题中都存在多个解,算法的任务就并不是简单的找到最优解，甚至要找到全部的解,这些问题经过简化处理后,可以归结为多峰函数求解问题。所以对多峰函数求解方法的研究具有较重要的应用价值。对于解决复杂的函数优化问题，遗传算法是通常解决的方法，但是遗传算法的一个主要缺点就是早熟收敛现象，主要表现在：种群进化到后期在一个极值点出停滞不前。另外就是虽然遗传算法具有较强的全局优化能力，但是局部优化能力不足。简单遗传算法(SGA)在每次收敛时，一般能找到函数的一个全局最优解（或者是局部的）。但是要得到多峰函数的多个极值点，一种最直接的方法就是用SGA算法对可行解空间进行重复多次的搜索，可能能找到多个解。但是这种方法的缺点在于计算效率比较低，而且求解结果随机性，如果假定算法的每次搜索过程都是互相独立的，并且算法搜索到目标函数q个极值点的概率都是相同的，那么算法要得到目标函数的所有极值点就平均需要搜索 （1-2）次1。如果概率不同的话，那搜索的次数更是难以想象的，而且搜索的随机性，难免会进行对同一区域重复搜索，所以效率不行，精度更是不可靠。针对遗传算法的不足，我们可以引入小生境的概念，本来遗传算法的搜索过程是整个种群单一性的进行的，我们可以将种群分为多个小生境，每个小生境同时执行一个子任务即进行搜索的过程，这样即避免了重复搜索，也挺高了搜索的效率。所以本文提出了小生境遗传算法。“物以类聚,人以群分”是对生物学中小生境(niche) 现象的一种概括，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代，引入小生境的方法提高了种群的多样性，对于求解多峰函数的全局最优解有着良好的效果。经过8个复杂的多峰函数测试，小生境遗传算法具有更好的可靠性与更快的收敛速度。总体效果明显优与简单遗传算法（SGA）1.5 本论文的主要工作在文章的上面提到，工程领域设计中会存在各种优化问题，遗传算法是通常解决的方法，但是遗传算法一个最主要的缺陷就是它的早熟收敛现象，导致算法收敛到局部最优解，还有就是它的局部搜索能力不行，虽然变异算子有效的提高了他的局部搜索能力，但仅靠那么低的变异概率是完全不够的。所以本论文就是基于遗传算法在解决多峰函数问题时表现的缺陷与不足，提出了改进。从执行策略部分对遗传算法进行改进，即提出小生境的遗传算法，所谓“物以类聚人以群分”，这这就是生物小生境的思想。小生境遗传算法是用来解决多峰优化问题的有效手段。目前，小生境遗传算法中用得最多的是基于共享函数的遗传算法。这类算法需要事先估计解空间的峰半径和峰个数。然而，实际多峰优化问题的峰半径往往无法事先估计5。针对上述问题，本文在阅读大量国内外文献的基础上，对小生境遗传算法进行了深入的理论研究和试验分析，主要包括以下内容:（1）简要介绍了遗传算法的发展历史和研究现状，并阐述了遗传算法的基本原理、基本概念以及主要实现技术，同时分析了遗传算法的局限性，并提出算法所需解决的关键问题与改进部分。设计在在matlab上完成了基本遗传算法的编程。（2）首先介绍了小生境技术的生物学原理，再详细介绍了目前常见的3种小生境遗传算法。阐述了每一种小生境算法的主要思想和算法步骤，并对三种算法进行了简单的分析，然后介绍了小生境遗传算法的发展历史。（3）针对遗传算法在解决多峰函数问题时的早熟收敛问题，提出了基于淘汰机制的小生境遗传算法，详细的介绍了淘汰机制的原理及其实现。并用几个多峰函数进行测试，与基本遗传算法进行对比分析。基于淘汰机制的小生境遗传算法在收敛概率、收敛速度、和收敛精度上都明显优于基本遗传算法，最优保存策略的引入也保证了算法的收敛与加快了收敛速度。但是淘汰机制的小生境遗传算法受限与小生境半径L。以下是论文每章的主要内容：第1章 概述了遗传算法的发展历史应用领域，并简述了论文的主要内容。第2章 阐述了遗传算法的基本概念和基本原理，详细介绍了遗传算法实现技术的五大要素。内容包括参数编码、初始群体的设定、适应度函数的设定、遗传算子、遗传算法的控制参数。在此基础上，分析了遗传算法的局限性并提出需要解决的关键性问题。第3章 详细介绍小生境技术和三种小生境遗传算法，内容包括：适应值共享遗传算法、拥挤遗传算法、阐述了每一种小生境算法的主要思路和算法步骤，并做了简单的分析。简单的描述了小生境的发展历史。第4章 提出一种基于淘汰机制的小生境遗传算法，介绍了它的基本原理与详细的实现方法，并用8个多峰函数进行了测试，做了定性的分析第五章总结本文的主要内容与突出点，并分析论文不足之处，提出了展望。第二章 遗传算法的基本理论2.1 遗传算法的生物学基础“适者生存”生物想要在自然界生存，生物必须有良好的自适应能力，否则将会被淘汰。通过对生物学上的研究，人们发现可以将这个模仿到人工的自适应系统里。遗传算法就是这写研究的产物。通过模仿生物学上的复制和进化，遗传算法让各类人工系统具有良好的自适应能力和优化能力。遗传算法的生物学基础。生长、复制、选择与变异是生命的基本特征。也就是生命都是通过进化的而来的。伟大的达尔文在1858年用自然选择(natural selection)来诠释物种的起源和生物的进化，给我们带来深刻的影响，思想包括以下三个方面：（1） 遗传(heredity)。我们很小的时候就知道 “种瓜得瓜，种豆得豆”，也就是父代把生物的遗传信息传递给子代，子代根据接收到的信息发育、分化，所以子代总是和父代具有相似的性状。这是生物的普遍特征，正是这个特性征，物种才能延续下去。（2） 变异(variation)。父代和子代之间以及不同的子代之间肯定会有差异，这就是变异。变异是在遗传和分化时随机发生的，这是产生新物种或者高适应的物种所必要的条件，（3） 生存斗争和适者生存。“优胜劣汰，适者生存”，这是自然界永恒的规律。变异是随机的，但如果朝着能适应环境的方向的变异的话，该个体将会被保存下来，因为他适应了这个环境，同时，变异后不能适应的个体将会被环境所淘汰。适应的过程是长期的缓慢的，通过一代代的变异，适应，从而最终会产生一个能适应这个环境然后与它的祖先有着完全不一样的特征的个体。遗传算法是一种模拟生物进化过程的随机优化方法，我简单列举几个生物学的基本概念和术语：染色体(chromosome)，遗传信息的载体，由DNA、RNA和蛋白质构成的，其形态和数目具有种系的特性。遗传因子(gene)，DNA或RNA长链结构中占有一定位置的基本遗传单位，也称为基因。个体(individual)，具有特征染色体的实体。种群(population)，个体的集合称为种群。该集合内个体数目的多少称就是种群的大小的大小。进化(evolution)，生物为了生存，为了适应环境不多的进行体质的优化，这种生命现象称为进化。适应度(fitness)，个体对环境的适应能力。选择(selection)，一定的概率从种群中选择若干个体的操作。基本上是进行优胜劣汰。复制(reproduction)，细胞在分裂时，DNA转移到新个体的过程。交叉(crossover)，又称基因重组，有性个体互换染色体从而产生新个体的过程变异(mutation)，在细胞进行复制时微小的概率产生一些复制的差异，因而会使DNA发生某种差异从而产生出不同特征的染色体。编码(coding)，DNA里遗传信息在一个长链上按一定的模式排列。解码(decoding)，从遗传子型到表现型的映射10。2.2 遗传算法的发展概况遗传算法最早是在20世纪60年代在密歇根大学启蒙的，Holland博士对大自然和各种的自适应系统进行了研究，并发现也可以叫这些思想应用到优化问题中，而且发现了选择、交叉、变异的必要性。然后Bagley最早给他命名为“遗传算法”，与此同时，他还发表了最早的一种二倍体编码，能够模仿生物学上的复制、突变等情况。Holland对遗传算法的起步时做了巨大的贡献的，他接着在1968年之后的三年内，不断的晚上了遗传算法的一个模式理论，并介绍了二进制编码和格雷编码的优缺点，还给出了许多不同的遗传算子，接着在1975年发表了自然系统和人工系统的自适应性一书，介绍了遗传算法的基本理论，并在数学上对遗传算法进行了证明，对后面的学者们具有很好的指导意义。1975年是遗传算法不平凡的一年，De Jong将的智慧结晶都浓缩到遗传自适应系统的行为分析这著作上，该书深入的阐述了遗传算法的原理，并有大量的实用的实验数据，并做了许多正确的结论，对遗传算法在今后研究和发展具有划时代的意义。到了80年代，各种人工智能优化算法不断的出现和发展起来。Bridle提出了6个选择算子，很好的解决了轮盘选择的不足。之后对遗传算法研究比较有名的应算是Goldberg，他再1989年出版了搜索、优化和机器学习中的遗传算法一书，该书可以说是遗传算法的白皮书，从各方面详细的介绍了遗传算法的基本原理，组成，应用和实现19。90年代是遗传算法的鼎盛时期，经过30年的发展，遗传算法不断的完善和发展，各种自适应和混合遗传算法等等改良遗传算法层出不穷，这也是切合实际应用发展所需要的。遗传算法也不断的成功应用到新的领域里。2.3 遗传算法的结构与实现2.3.1 遗传算法的结构遗传算法(Genetic Algorithms, GA)是一类仿生物学上的遗传进化的随机机化搜索算法。它模拟生物学上的自然选择，遗传学里的复制，杂交和基因突变等过程，你每一代迭代中选取一个准最优解，并根据一定的规则确定一个为最终解，不断的重复这个过程，以找到最优解。2.3.2 遗传算法概要求函数最大值或最小值的优化问题已经是一个老生常谈的问题了，以下我们建立数学规划模型来进行分析： 式中，为决策向量，式(2-1)为约束条件，满足式（2-1）的解X称为可能解，所有可能解的组成了可能解集合。它们之间的联系如下：图2.1最优化问题的可能解区域及可能解总和以上我们提到的最优化的问题，由于目标函数和约束条件类型复杂，除了线性、非线性，连续、离散，还有单峰值和多峰值的。经过长期的研究，我们渐渐明白要在很多复杂情况下要想完全精确的求出其最优解几乎是不可能的，因此，学者们就退而求其次，致力于求出其近似最优解或满意解。一般我们会用一下三种方法进行求解：（1） 枚举法。所谓枚举法就是把可能解集合内的所有可能解列举出来，并从中找出认为是精确的最优解。当然，枚举法也存在缺陷，问题小点还好，就是当枚举空间比较大时，可能解集合将会很大，这种求解速率就显得很低，甚至还会找不到。（2） 启发式求解。通过寻求一种可能性解的启发式规则，以找到一个近似最优解。这种方法的优点就是求解速率较高，但是每个问题需要对应不同的规则，这就限制了他的应用。（3） 搜索算法。顾名思义就是在一个指定区域内不断的搜索，这个区域就是可能解的一个子集。从而在这个子集中搜索出最优解或近似最优解。但是这种方法不一定能找到最优解，还需一定的启发知识。由于问题规模的不断扩大，种类的复杂多变，以目前的能力来解决这些最优化问题几乎是一个登天的难题。但是，遗传算法为我们提供了有效的求解工具，具有良好的全局优化能力2.3.3 遗传算法的实现遗传算法里，将n维决策向量用n个记号来表示：（2-2） Xi的所有可能值称等位基因，所以X就是一个染色体。一般n是固定的，但也可以不是固定的，但情况较少。等位基因可以是数组成，或者是实数值，更能使一组记号，这就是所需要的编码策略。最早的等位基因就是以1和0组成的，对应的染色体就可以又一串二进制的来表示，即二进制编码。X就是一个个体，按照一定的策略求出他的适应度，适应度大的个体就更接近目标个体；反之，越小越远离。决策变量X就是函数解空间。通过搜索X的最大适应度个体来找到最优解，所有X就是函数的搜索空间。生物进化是呈群体性的。M个个体组成了遗传算法里面的群体。生物的进化是一代代进行的，遗传算法的运算过程也是不过的迭代的过程。从第一代开始，进化到第t代，群体就记作P(t),再经过一次遗传进化，得到P（t+1）代。整个群体就不过的进行优胜略太的方式迭代下去，直到找打最佳个体既适应度最高的个体。所对应的X就是最优解X*。遗传算法如同生物学上的进化，进化是通过遗传操作完成的，既选择交叉变异。选择(selection):以预定的规则策略，根据个体的适应度大小，在群体P（t）中挑选出一些相对优良的个体遗传到下一代群体P（t+1）中。交叉（crossover):随机配对p（t）群体里的两个个体，以一定的概率交叉互换染色体，从而产生新的个体遗传到P（t+1）中变异（mutation）：以很小的概率改变染色体中的一个部分，从而产生新的染色体。具体流程：1）：开始。选定进化代数T，用以停止算法；随机生成初始群体P（0）。2）：计算个体适应度。用适应度函数计算群体P（t）中各每个个体的适应度大小。3）：选择。群体进行选择操作。4）：交叉。群体进行交叉操作。5）：变异。群体进行变异操作。产生新一代群体P（t+1）。6）：停止。是否达到最大迭代次数，若否，转到步骤二；若是，停止算法输出最优个体。遗传算法的流程图如下：图2.2 遗传算法的流程图2.4 遗传算法的操作2.4.1 编码策略 实际问题如果要进行求解的话就要转换为数学模型，这个数学模型就是对该问题的一个映射，而遗传算法不仅仅是转换为一个数学模型，它与传统优化算法的区别也更是在此，遗传算法进行时需要对问题按照一定的策略映射到可以搜索的空间，这就是所谓的编码。经过编码的参数我们可以称为个体。遗传算法的运行过程就是不断的搜索，直到找到最优个体的过程。遗传算法的操作对象所以不在是函数实际的决策变量，而是经过编码后的编码串。所以，编码是遗传算法的一个前提，编码策略决定了染色体的构成，同时有怎么样的编码方式就需要怎么样的解码方式与之相对应。同时遗传算子的选择也与编码方式息息相关，例如，二进制的编码方式交叉算子就用简单的单点交叉，而，用实数编码编码情况下则是用均匀交叉算子。综上所诉，选择一个正确的稳定的编码方式对遗传算法的性能和实现有着至关重要的作用。从二进制编码的开始，学者们对编码方式的研究从没停止过，然而一个完美无瑕的编码方式现在来说至少只是一种追求。今天对编码方式的研究也是对遗传算法的研究的一个重要的方向。作者在编写简单遗传算法的时候都尝试了这两种方法编码方式，在解决一维的多峰函数时，两种编码方式的选择差别不大，浮点数编码的运行速度将优于二进制的编码，但对于二维或者更高维的更复杂的多峰函数，二进制的编码方法将产生很大的矩阵，编码方式相对较难，利用浮点数编码明显算法实现比较简单，综合性能优于二进制的编码方式。接下来我将简单的介绍下两种常用的编码方式。（1） 二进制编码方法二进制是最早最简单的编码方式，编码串又一串0和1的字符串组成。求解精度与字符串的长度有关。如果取值范围是，长度为l，关系如下 则精度为： (2-3)假设某一个体的编码是 (2-4)则对应的解码公式为 (2-5)二进制编码方法的优点也很明显：1）编码和解码都很简单。2）在一些遗传操作如选择，变异等方面实践起来比较容易。3）在原则上也符合最小字符集编码的原则。4）对该算法进行理论分析也是一个很好的选（2）浮点数编码方法在一些连续函数的优化问题上，有的多目标、高精度的要求用二进制的编码来表示其实有很多的不方便。一个是出现字符串的情况，比如海明悬崖。这种字符串所表示的解到一个临近解的转变需要经过多个位的字符转变。在海明悬崖存在时，二进制的编码方式将影响局部搜索能力。另一个是最优解达不到希望的高精度。二进制编码字符串的长度与我们所要求的解的精度相挂钩。总的来说，就是如果需要的的精度要求越高，对应的编码字符串就会更长，从而计算将会更复杂。我们总结二进制的种种缺点，经过分析探讨，专家学者们又提出了一个新的方法浮点数编码方法。这里的浮点数变法方法也就是用指定范围内的一个实数（浮点数）来表示个体的一个基因，所以，决策向量的个数就是编码的长度。浮点数编码的优点比较多，主要有：1）适用于区域较大的数。2）适合高精度场合3)能搜索大空间。4)提高了计算能力。5)便于实现混合的应用遗传算法。6)适用于具有复杂的约束条件的问题。2.4.2 适应度函数遗传算法在的搜索时根据适应度来进行的，所以一般不会用到其他的信息，所以他对搜索的效率和性能有着至关的影响。 (1)我们平时比较常见的适应度函数主要有这几种：1) 直接以目标函数为适应度函数，即若最大值问题 (2-6)若最小值问题 (2-7)这种函数是最简单，最直接的方法，对于一般的函数有着良好的效果。本文的适应度函数采用的就是这种方法。而这种方法也存在不足：一个是无法满足轮盘选择的概率一定要正或者为0的要求；另一个是求解的函数值太过平均，这样将不能准确的反应种群的平均适应度，既而降低其效率等等。另一种处理最小化问题 （2-8）2)若最小值问题，则 (2-9)式中为的最大估计。若最大值问题，则 (2-10) 式中为的最小值估计。3)若最小值问题 (2-11)若最大值问题 (2-12)这种方法与第二种方法类似，c就是目标函数(2)适应度函数的作用在选择操作时会出现以下问题：适应度函数可能会产生的问题：1)在初期，有时会出现一些超常的个体，如果用比例法来筛选，会因为这些个体的竞争力太强而影响算法的全局搜索性能，不过这只是出现在初期。2)在算法后期接近收敛时，因为各个个体的适应度比较平均差异不大，没有继续进化能力，可能只能获得某个局部最优解。我们上面讲的两种情况，值的分部对搜索来说是非常不合理的，因此，适应度函数的设计是遗传算法设计一个非常重要的方面。 (3) 要设计适应度函数要注意满足一下四点：1)最简单也是最基本的条件就是单值、连续、非负和最大化。2)合理性和一致性。用适应度来表示解孰优孰劣，这就有一定难度了。3)计算量小。理由很简单，如果适应度函数的设计过于复杂，在计算会有很大麻烦，计算成本自然增加，因此，还是尽可能简单的好。4)通用性强。说实话，如果这一点必须要满足的话就有点强人所难了。就目前的水平而言，只能说是尽可能同用，最好是必须改变参数，当然也只是希望而已。2.4.3 遗传算子(1)选择算子在环境的严峻考验下，适应性成了生物的关键要素。在遗传上，适应度高的物种遗传的几率也高，这个是很容易理解的。当然，反之也成立。如果要模拟这个优胜劣汰的过程，我们一般会用选择算子的方法来进行操作，作用就是根据使用度来选择性的将适应度高的个体遗传到下一代的概率更大。比例选择算子，即轮盘式选择算子，是我们最常用的算子。本文的编程过程中也采用了该算子。但各种文献表明它并不是一个独一无二的选择，后来学者们又提出了其他方法。接下来我将主要介绍下轮盘式选择，并简要给大家介绍下几种平时用的比较多的选择算子15。1)比例选择这种方法是一种放回式随机抽取的方法，因为这种选择方式与赌博中的轮盘操作原理颇为相似，所以也叫做轮盘式选择。轮盘原理：如下图为轮盘示意图。整个轮盘被分为大小不同的一些扇面，分别对应着不同的倍数。开始旋转轮盘后，等待轮盘的自然停止，指针所指到的扇面就是赌博者所获得的赔偿倍数。因为指针停止的位置是随机发生的，我们不能保证和估计指针停止的位置，但是我们容易发现，扇面面积大的扇面停到该扇面的概率就会比较大，反之，指针停到的位置的概率就较小。所以，类似的，在遗传算法里，整个种群的全部适应值的总和可以看做整个圆，种群里面的所有个体分割了这个轮盘，如果他们的适应值较大，获得轮盘的面就就相对的较大，然后被遗传到下一代的概率就会更大.总之，适应度值越大，遗传到下一代的几率就越大反之更小。图2.2 轮盘示意图对于轮盘式，我们的原则是：每个个体被挑中的几率和它与环境的适应度是成正比的，但选择却是随机的，所以选择误差可能会比较大，就算是适应度高的个体也会被淘汰掉。设个体遗传概率概率Pis如下： (2-13)由由上式可得知，适应度与个体遗传的的概率是成正比的。具体操作流程：首先要把所有个体的适应度总和求出来。然后分别求出各个个体的适应度与适应度总和的比值，也就是遗传的概率。然后开始转动轮盘（产生0到1之间的随机数）进行选择。 (2).交叉算子要想产生新的染色体，就得进行交配重组，这也是生物进化的一个重要环节。我们操作这个环节，一般采用交叉算子的方法。交叉算法的定义就是将两个配对的染色体互相交换部分基因，既而形成两个新的个体，为遗传算法起着举足轻重的作用，是产生新个体的最重要的算子，它也是使遗传算法区别于其他进化算法的重要特征之一。上面我们提到在重组之前要先将群体中的个体进行配对，目前我们在这一步上主要还是采用随机配对的方法。交叉算子的设计与问题息息相关，不能为了产生好的新个体而破坏太多的编码串，这就要我们把握这个度，进行适当合理的配对。交叉算子的设计一般包括下面这两个方面的内容：怎样确定交叉的位置？基因互换是怎么进行的？在交叉算子中，平时我们用的最频繁的就是单点交叉算子。本文里利用二进制的编码的遗传算法采用的是单点交叉算子，单点交叉交叉算子对于二进制编码的GA有着良好的效果。而采用十进制编码的本文使用的是非均匀的单点算术交叉方法。下面将详细介绍这两种方法1)单点交叉在二进制的编码情况下，在编码串中随机的找到一个点作为交叉点，接着在这个店上互换两个个体的基因。它的实现过程：随机两两配对种群中的M个个体，则有M/2对相互配对的个体组。对每个配对的配对组，随机产生一个交叉点。对每个配对的配对组，根据交叉概率pc，在交叉点互换染色体，生成两个新的个体。示意图如下： 交叉点图2.3 交叉互换基因示意图2）算术交叉两个个体进行算术交叉运算从而产生新的个体。对象一般是实数编码的，所以本文的浮点数编码是用该选择算法。两个个体，交叉后产生两个新个体： （ 2-14）式中，为一参数，如果是一个实常数，则称为均匀交叉运算；如果又迭代次数决定则成为非均匀的算术交叉。本文所用到的就是非均匀的算术交叉，其 ，T为最大迭代次数，t为当前迭代次数。 (3)变异算子不管是遗传还是进化，误差总是难免的，这就促使变异的产生，进而产生带有新的生物性状的新的染色体，虽然说以这种方式产生的新物种的可能性不大，但也不是完全不存在。我们在研究或模仿时也要注意。我们所说的变异运算，就是随机的替换掉原有基因座里的一个基因，进而产生一个新的个体，这就进行了一个变异的过程。在本文的研究设计中，对于二进制编码的个体，就是在一个变异点做取反的操作；对于浮点数编码，就是用指定范围内的一个随机值替换掉原有的染色体，从而产生新个体。如果单从生产新个体的能力来说，交叉运算比变异运算要好很多，也就是说交叉是主，变异是次。前者决定了全局搜索能力，后者起辅助作用，两者相辅相成，在全局和局部搜素方面相互配合，从而使得遗传算法能很好的全局搜索和局部搜索能力。因而，我们研究变异算子的目的可分为以下几点：提高遗传算法的局部优化能力。利用交叉算子从全局上我们能找到较好的编码个体，但交叉算子对于局部的较好个体没有效果，限制了算法的局部搜索能力，有时候我们可能会需要知道他的局部解，所以变异算子有效的提高了遗传算法的局部搜索能力，提高了遗传算法的整体性能。维持多样性，防止早熟现象。变异产生新的个体，防止相似的个体在某一处停滞不前，产生早熟熟练的现象。要了解变异算子，就得了解以下两种：基本位变异算子和均匀变异算子。前者用于二进制编码，后者用于浮点数编码。本文主要采用的就是均匀变异算子1)均匀变异算子均匀变异是指实数编码的情况下用特定范围内的一个随机数代替以很小的概率代替原有的个体从而产生新的个体。如一个个体变异过程如下： （2-15）式中r为0,1中的随机数。2.5 遗传算法的运行参数（1） 编码串的长度l：在二进制编码时，编码串的长度选取与问题的求解精度有关；而浮点数编码时，编码串的长度即为函数的维数。（2） 种群大小M：种群大小M表示种群中个体的数量。M去的小点，减小了矩阵的大小，这种方案虽然可以提高算法的计算的速率，可是会影响种群的多样性，甚至出现早熟熟练现象。相反的，M如果取的太大优惠降低遗传算法的计算效率。所以种群大小要择中选择，一般取20100.（3） 因为遗传算法中新个体的产生主要是依靠交叉操作的，所以pc一般是选择大的值。但也要有限度，若取得太大，会淘汰一些优良个体，破坏优良性，影响进化。但如果取的太小，个体产生的速度会变慢，影响收敛速度。所以收敛概率的一般选择时0.40.99。一般取0.8以上，为了提高 它的性能，Davis提出了自适应的遗传算法，较差的个体给予想较大的交叉概率，防止优良的个体被破坏；反之交叉的个体给予较小的交叉概率，以便完成进化。优良的给他根据迭代的代数进行调整。（4） 对pm的取值很有讲究，取大的话可能会有交叉算子的效果，但同时会破坏优良性，使良好的个体也被淘汰了，若取太小，又达不到他原有的效果。一般取0.00010.1。同上面的交叉概率pc，Davis的自适应算法也对变异概率pm也根据个体的优良在进化过程中给予调整，较差的个体给予较小的变异概率。优良的给他根据迭代的代数进行调整。（5） 终止迭代次数T：终止迭代次数T表示遗传算法运行结束的条件的参数。一般建议取值范围是：1001000。2.6 遗传算法的特点遗由于遗传算法具有鲁棒性，与其他优化方法相比有明显的特点：(1)以决策变量的编码作为运算对象。一般优化算法是利用本身来优化的，但遗传算法是经过编码策略编码的。编码操作使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图）进行操作）。所有一些无意义的情况遗传算法也可以解决。 (2)遗传算法同时使用多个搜索点的搜索信息。传统的优化算法是基本上都是从选择一个起始点开始搜索的。这个过程不断的进行的了单个搜索，效率不高，而且信息不全，有时甚至无法继续搜索。另一个问题是它从一组个体组成的初始种群开始搜索，不像单个搜索那样，它可以自动去除一些不可靠的点，也更可靠，这就是它特有的并行性。(3)遗传算法直接以目标值作为搜索信息。因为它只用适应度函数值来评估个体，不受一些辅助信息如微分导数的影响，约束条件可以随意的设定，从而增加了它的应用范围。(4)遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的数据，选择交叉变异就是排错的过程所有具有很强的容错能力。(5)遗传算法使用概率搜索技术。一般的优化算法都是从一个点到另一个点的搜索，缺点是容易使过程停止，限制了算法的应用范围。遗传算法中的选择、交叉和变异都是随机操作，并没有固定的规则。交叉表示了他的全局搜索能力，变异表现了他的局部搜索能力。 2.7 遗传算法的不足1)早熟收敛问题 遗传算法是根据适应度的大小来评价解或者说是个体的优良情况，虽然这看起来是比较切合实际的，但在实际应用时同时会产生这么一个问题，如果种群中产生一个适应度异常大的个体，根据优胜略太的特点，良好的基因总是受欢迎的，所以这个优良的基因会经过不断的遗传复制，具有差不多这种的优良个体不断的产生，从而使整个群体早早的失去了多样性，这样就会使算法收敛到一个局部的位置，从而不能找到全局的最优解。 (2)遗传算法的局部搜索能力问题上文我们也提到，交叉算子的应用使遗传算法具有很好的全局搜索性能，但是对于局部寻优能力，遗传算法的搜索性能很有限，仅仅是靠很低的变异概率来提高他的局部搜索能力，但毕竟这样太有限了。在进化的后期，熟练的效率将会大大的降低，甚至是会产生无法收敛到全局最优。(3)遗传算子的无方向性进化的过程中，选择算子可以挑选出优良的个体，而交叉算子与变异算子的作用仅仅局限在了产生新的个体，不能保证产生的新个体都是优良的，能做到那一步，遗传算法的性能将会大大的提高，无论是收敛速度还是精度上都是可以得到了保证。这也是遗传算法目前的局限性。现在还没有一个完美的算法，遗传算法如果要获得很多的实际应用，还是任重而道远的。2.8 遗传算法的改进传算法的出现解决了很多复杂的优化问题以及其他的很多实际应用中。但传统的遗传算法有着其自身的很多不足。文章上面已经详细的介绍了传统遗传算法的缺陷与不足，正是这些不足限制了遗传算法的应用。所以为了提高遗传算法的性能，继续研究和探索遗传算法，并对其进行改进显的很有必要。对传统遗传算法的改进可以从四个方面进行：对编码方式的改进，对遗传算子的改进，对控制参数的赶紧以及对实行策略的改进。（1） 对编码方式的改进传统的遗传算法用的比较多的编码方式还是二进制的编码方式。它的优点在于编码过程简单，实现过程方便。但其缺点是在于精度要求较高时，个体编码串较长，是算法的搜索空间急剧扩大，遗传算法的性能降低。因此人们对编码方式进行了探讨，格雷码的编码方式克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算不杂性，并省去了解码这个步骤，提高了算法的性能。还有对不同的问题需进行不同的编码。（2） 对遗传算子的