遗传算法毕业论文.doc

《遗传算法毕业论文.doc》由会员分享，可在线阅读，更多相关《遗传算法毕业论文.doc（56页珍藏版）》请在三一办公上搜索。

1、遗遗传算法毕业论文【摘要】遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想基于Darwin的进化论和Mendel的遗传学。遗传算法的广泛应用和发展潜能使很多学者深入研究遗传算法，并出版了很多关于它的书籍。TSP问题是古老的经典的问题，有关的研究有几百年的时间。TSP旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。 论文首先介绍了遗传算法的基本原理、遗传算法的特点,遗传算法的发展方向和它的主要应用领域；接着针对TSP 问题论述了遗传算法在编码表示和遗传算子（包括选择算子，交叉算子，变异算子这三种算子

2、）等方面的应用情况，简单讨论几种编码方法，并改进了交叉算子。接着对改进的遗传算法做了实验，得出结果并分析了数据。最后我做了一个TSP简单应用。【关键词】遗传算法；TSP；遗传算子 ；编码【Abstract】Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm ，develop rapidly in recent years, the basic idea of the theory is Darwin and Mendels genetics. Extensive

3、use of genetic algorithms and development potential make many scholars in-depth study of genetic algorithms, and published many books about it.TSP problem is the old classic question and about its research have hundreds of years of time. TSP Traveling Salesman Problem is a kind of a typical NP-compl

4、ete problem, genetic algorithms to solve NP problems is a more desirable method.Paper first introduces the characteristics, development direction and major applications of basic genetic algorithms, and then discussed for the TSP problem of genetic algorithms and genetic coding that operator (includi

5、ng the selection operator, crossover operator, mutation operator of these three operator) and other aspects of the application, make a brief discussion about several coding methods, and improved crossover operator. Then use improved genetic algorithm to do the experiment, get the outcome and analyze

6、 the data. Finally, I do a simple suing about TSP.【Keywords】genetic algorithm; TSP; genetic operator; coding目录第一章 遗传算法理论41.1遗传算法的起源41.2遗传算法概念61.3 遗传算法的原理71.3.1遗传算法在应用中关键的问题91.3.2遗传算法基本操作91.4遗传算法的特点101.5遗传算法几个主要应用领域111.6遗传算法发展方向13第二章遗传算法的基本原理和实现技术152.1 模式定理152.2编码技术162.2.1 群体设定162.2.2适应度函数172.2.3 遗传操

7、作172.3混合遗传算法19第三章TSP问题描述与实算203.1 旅行商问题描述203.2编码选择213.2.1群体设定213.2.2 适应函数度213.2.3 选择算子的设计213.2.4 交叉算子的设计223.2.5变异算子的设计243.3 对TSP遗传算法的改进：253.3.1 TSP遗传算法参数实验253.3.2 改进的交叉算子：产生多个个体的部分映射与顺序交叉结合的算子.293.4 TSP算法实例353.5 附录（求51个城市最短距离算法）39总结51参考文献52致谢53第一章 遗传算法理论1.1遗传算法的起源当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程

8、科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。1967年，Holland的学生在博士论文中首次提出“遗传算法”（Genetic Algorithms）一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年Holland出版了他的著名专著自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把197

9、5年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得并行性的重要性。同年，K.A.De Jong完成了他的博士论文一类遗传自适应系统的行为分析（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien

10、一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genet

11、ic Algorithms ，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次Pa

12、rallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计”。1994年，他又出

13、版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在Artificial Intelligence、Machine Learning、Information science、Parallel Computing、Genetic Programming and Evoluable Machines、IEEE Transactions on Neural Networks、IEEE Transactions on Signal Processing等杂志上发表。1993年，MIT出版社创刊了新杂志Evolutionar

14、y Computation。1997年，IEEE又创刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。遗传算法(Genetic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其

15、学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传程序设计是借鉴生物

16、界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域

17、的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者1.2遗传算法概念遗传算法和字面意思一样，原理是关于遗传的算法。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而

18、启发得出的一种全局优化算法。遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的不是对遗传算法系统研究而是说明自然和人工系统的自适应过程。遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后

19、十年的计算技术有重大影响的关键技术”。遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存

20、下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。19这些概念如下：(1)串(String)它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。(2)群体(Population)个体的集合称为群体，“串”是群体的元素（3）群体大小(Population Size)在群体中个体的数量称为群体的大小。（4）基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因。（5）基因位置(Gene

21、 Position)一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串从左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。（6）基因特征值(Gene Feature)在用“二进制串”表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。（7）串结构空间（SS）在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。（8）参数空间SP这是“串空间”在物理系统中的映射，它对应于遗

22、传学中的表现型(Phenotype)的集合。（9）适应度(Fitness)表示某一个体对于环境的适应程度。1.3 遗传算法的原理遗传算法GA把“问题的解”表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，“一代一代”地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体

23、一般被表达为简单的字符串或数字串，不过也有其他的表示方法适用，这一过程称为编码。一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的“个体”被按照适应度排序，适应度高的在前面。这里的“高”是相对于初始的种群的“低适应度”来说的。下一步是产生下一代个体并组成种群。这个过程是通过选择和交叉完成的，其中繁殖包括(crossover)和突变(mutation)。选择则是根据新个体的适应度进行的，适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以

24、通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率，范围一般是0.01-1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0.8，则80%的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而没交配的个体则保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变

25、常数，通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并“一代一代”向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个“个体”被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。遗传算法的基础理论是摸式定理。它的有关内容如下：(1)摸式(Schema)概念1一个基因串用符号集0，1，*表示，则称为一个因式；其中*可以

26、是0或1。例如：H=1 x x 0 x x是一个模式。(2)摸式的“阶”和“长度”摸式中0和1的个数称为模式的阶，并用0(H)表示。模式中第1个数字串和最后一个数字串间的距离称为模式的长度，并用(H)表示。对于模式H1xx0xx，有0(H)2，(H)4。(3)Holland摸式定理低阶，短长度的模式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的模式数目为0(n3)。1.3.1遗传算法在应用中关键的问题（1）串的编码方式这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大（2）适应函数的确定适应函数(

27、fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。（3）遗传算法自身参数设定遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏“高适应值”的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm001-02。1.3.2遗传算法基本操作（1）初始化选择一个

28、群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。通常以随机方法产生串或个体的集合bi,i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。5（2）选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度选择原则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。适应度较高的个体，繁殖下一代的数目较多。适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。（3）交叉对于选中用

29、于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P交叉。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体S1=100101S2=010111选择它们的左边3位进行交叉操作，则有S1=010101S2=100111一般而言，交叉概率P取值为0.250.75。（4）变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些“位”执行变异。在变异时，对执行变异的串的“对应位”求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。例如

30、有个体S101011。对其的第1，4位置的基因进行变异，则有=001111单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质.（5）全局最优收敛(Convergence to the global optimum)当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。1.4遗传算法的特点（1）遗传算

31、法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。遗传算法从“串集”开始搜索，覆盖面大，利于全局择优。（2）遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用“适应值”这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需“适应值”和串编码等通用信息，故几乎可处理任何问题。（3）遗传算法有极强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串，这是一个强烈的滤波过程，并且是一个并行滤波机制。

32、故而，遗传算法有很高的容错能力。（4）遗传算法最优迫近。遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。（5）遗传算法具有隐含的并行性。1.5遗传算法几个主要应用领域虽然在各种应用领域中，算法的具体实施细节有各自的特点，但遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域。遗传算法主要应用于以下几个主要领域：1713（1）函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人工构造的各种各样复杂形式的测

33、试函数，有连续函数也有离散函数，有单峰函数也有多峰函数等，利用这些函数来评价遗传算法的性能。对于非线性、多目标的函数优化问题，用其他算法通常较难求解，但使用遗传算法却很方便并可以得到较好的结果。（2）组合优化随着问题规模的扩大，组合优化问题的搜索空间急剧增大，甚者有时无法求到精确最优解。对于这类复杂问题，使用遗传算法求解可行解就显得更加有实际价值。这类问题包括旅行商问题、背包问题、装箱问题和图形划分等。（3）生成调度 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也因简化太多而使得求解结果与实际相差甚远。因此目前现实生产中也主要靠一些经验进行调度。

34、遗传算法已经成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制 在自动控制领域中有很多与优化相关的问题需要求解。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和“权值”学习等。都显出了遗传算法在这此领域中应用的可能性。（5）机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自

35、于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。12 （6）图像处理 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一次误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。（7）人工生命 人工生命是用计算机、机械等

36、人下媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人下生命的两大主要特征。人下生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人下生命现象的重要基础理论。虽然人下生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人下生命的研究提供一个有效的下具，人下生命的研究也必将促进遗传算法的进一步发展.12（8）遗传编程 1989年，美国Standford大学的Koza教授发展了遗传编程的概念，其基本思想是:采用树型结构表示计算机程

37、序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚未成热，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。目前公开的遗传编程实验系统有十多个。（9）机器学习 学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。9（10）数据挖掘 数据挖掘是近几年出现的

38、数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。1.6遗传算法发展方向遗传算法发展方向其实就是和其他方法结合优化问题，单方面改进遗传算法的各种算子不能取得明显进展。遗传算法以其基本思想简单、便于实现

39、和并行搜索的优点赢得了众多学者和各种工程人员的青睐，是目前应用最广的优化搜索算法之一。但遗传算法存在收敛速度慢和易于陷入局部最优的问题，在需要优化的参数较多时，更凸现了遗传算法的不足。遗传算法如何提高遗传算法跳出局部最优的能力和如何提高遗传算法的收敛速度成为近年来遗传算法的研究热点。许多学者从不同的角度对遗传算法进行了改进，使遗传算法的寻优能力有了不同程度的提高。和其它方法结合的遗传算法才有生命力。目前，对遗传算法的研究主要集中在数学基础、各环节的实现方式以及与其他算法的结合方面。其中，尤以遗传算法与其他算法相结合方面的研究最为引人关注。由于遗传算法具有开放式的结构，与问题的关联性不大，很容易

40、和其他算法进行结合，所以融合了其他的算法思想和遗传算法思想的混合遗传算法成了目前改进遗传算法研究的一个重要方向。现将比较常见的混合遗传算法介绍如下。（1）模拟退火遗传算法模拟退火算法的基本思想是通过模拟高温物体退火过程的方法来找到优化问题的全局最优或近似全局最优解。从统计物理学的观点看，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。遗传算法的局部搜索能力较差，但把握搜索过程总体的能力较强；而模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但它却对整个搜索空间的了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。

41、但如果将遗传算法和模拟退火算法相结合，互相取长补短，则有可能开发出性能优良的新的全局搜索算法。目前，已有许多学者将退火机制引入到遗传操作中，使遗传操作产生优良个体的概率增加，并使遗传算法的寻优能力有了明显的提高。（2）免疫遗传算法人工免疫算法受生物免疫系统原理的启发，针对求解问题特征进行人工疫苗接种，可充分利用问题本身的信息，和遗传算法结合时，遗传算法的全局搜索能力及免疫算法的局部优化相配合，可大大提高搜索效率。我们可以通过注射疫苗的方法来减少遗传操作的盲目性，加强遗传算法收敛性能，多次的测试结果证明了该改进方法的有效性。4（3）小生境遗传算法生物学上，小生境指在特定环境中的一种组织功能，它将

42、每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表，组成一个新种群，再在同一种群中以及不同种群之间进行杂交、变异，产生新一代个体群，同时采用“预选择”机制或排挤机制或共享机制完成选择操作。“解空间”中峰周围的子空间中的个体具有相对独立生长繁衍的特性。常用的小生境遗传算法大多在对群体进行选择操作前，计算个体之间的海明距离，如小于事先设定值，则对“适应值”低的个体处以罚函数，降低其适应值。这样可以保护解的多样性，也可以避免大量重复的解充斥整个解空间。用小生境思想来实现遗传算法的选择操作，使遗传算法的全局寻优能力得到了明显提高。（4）模糊遗传算法模糊遗传算法，即融合模糊优化

43、设计思想的遗传算法，它把模糊优化和遗传算法优化结合起来，构成一种混合优化的设计方法。其目的是利用模糊优化设计的优点，克服一般遗传算法优化设计存在的不足，从而使得系统的优化设计更灵活、方便，取得好的设计效果。首先，在模糊遗传算法中引入“论域”的概念。在这里，“论域”即指用隶属函数来表示遗传算法的优化过程中所采用的约束条件的区间范围。用隶属函数来表示遗传算法的约束条件，以使约束条件能够更容易得到表达，又能够保证遗传子代的选择中能够拥有更广泛的群体组成。其次，在模糊遗传算法中，采用权变理论中的以变应变的思想。模糊遗传算法运用模糊控制的思想来自适应改变遗传算法的种群规模、交叉概率、变异概率、适应度函数

44、以及控制策略等。（5）混沌遗传算法混沌是自然界广泛存在的一种非线性现象，它充分体现了系统的复杂性。混沌运动具有类似随机变量的杂乱表现，具有随机性；“混沌”能在一定范围内按其自身特性不重复地历经所有状态，具有遍历性；初值条件极其微弱的变化会引起混沌系统行为的巨大变化，具有对初始条件的极度敏感性。混沌运动的上述性质作为避免陷入局部极小的优化搜索机制，恰好可以弥补遗传算法易陷入局部最优、收敛速度慢的缺陷。可以利用混沌的遍历性产生初始种群，也可以运用混沌的遍历性对优良个体进行变异操作，混沌遗传算法增强了遗传算法的全局寻优能力。（6）量子遗传算法量子遗传算法是量子计算思想与遗传算法结合的产物。与遗传算法

45、类似，它也是一个产生检验的过程，但其实现同标准遗传算法不一样。在表达方式上，量子遗传算法将量子的态矢量表述引入染色体编码；在演化机制上，它利用量子门实现染色体演化。这些区别，使得量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜索能力和更快的收敛速度。还有其他的算法已被引入到遗传算法中来（如禁忌并行 ，分层），在此，就不再过多介绍。遗传算法与其他算法和理论的结合已经成为改进遗传算法的一个非常有效的手段。随着人们对遗传算法研究的不断深入，可以预见，会有更多的理论和方法被引入到遗传算法中来。相信通过遗传算法与其他算法的结合以及自身实现方式的不断改进，在不久的将来，遗传算法的优化能力会有

46、一个质的提高.第二章遗传算法的基本原理和实现技术前一章讲了遗传算法的原理，概念，这一章就具体将编码。2.1 模式定理（1） 模式模式（schema）是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。例如二值字符集 0，1 ，由此可以产生通常的 0,1 字符串。现在增加一个通配符“*” ，“*”既可以被当作“0”，又可以被当作“1”。这样二值字符集 0,1 就可扩展成三值字符集 0，1，* 。4定义 2.1 基于三值字符集 0，1，* 所产生的能描述具有某些结构相似的0、1 字符串称作模式。引入模式概念并不是仅仅为了描述上的方便。在引入模式概念前，我们看到的遗传算法是：在某一代中

47、，N个互不相同的串在选择、交叉、变异等遗传算子的作用下产生下一代的 N 个新的互不相同的串。那么，两代之间究竟保留了什么性质，破坏了什么性质，我们无法知到，因为我们所看到的“串”都是相互独立的，互不联系的。在引入模式概念后，我们看到的一个串实际上隐含着多个模式，一个模式可以隐含在多个串中，不同的“串”之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。（2） 模式定理首先定义两个重要的概念：模式阶（schema order）和定义长度（schema defining length）。定义 2.2 模式 H 中确定位置的个数称作该模式的模式阶，记作 O(H ) 。2比如模式 110*10*的阶为 5，而模式 0*的阶为1。显然，一个模式的“阶数”越高，其样本数就越少，因而确定性越高。但是，模式的“阶”并不能反映模式的所有性质。既使具有“同阶”的模式，在遗传操作下，也会有着不同的性质。为此，在引入定义长度的概念。定义 2.3 模式 H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距离或定义长度，记作 (H ) 。比如模式 110*10*的定义长度为 4，而模式 0*定义长度 0。【定义】（模式定理） 在遗传算子选择，交叉和变异