下载文档原格式
1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。
遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。
这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。
另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。
然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。
在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。
其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。
遗传算法的概念
遗传算法（Genetic Algorithm）是基于生物学进化理论的一种优化算法。
它是模拟自然界的进化过程，通过筛选、交叉、变异等元素不断筛选出能够适应环境的个体，最终得到最优解或次优解的一种算法。
遗传算法的基本思想是将问题看作一个个体，使用种群的方式不断迭代，将群体中优劣个体进行适应度评估并进行优胜劣汰，简单来说就是不断筛选出最优的解决方案来。
遗传算法被广泛应用于各类优化问题，例如旅行商问题、机器学习和函数优化等。
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
遗传算法遗传算法是一种借鉴生物遗传和进化机制寻求最优解的计算方法。
该方法模拟生物进化中的复制、交换、变异等过程，并通过模拟自然选择压力的方式推动问题解集向最优解方向移动。
遗传算法为解决多种难以采用传统数学方法求解的复杂问题提供了新的思路。
1. 遗传算法的发展历史研究者采用计算机模拟生物进化过程并解决优化问题的尝试始于20世纪40至50年代。
20世纪60年代中期，美国密歇根大学的Holland教授提出了位串编码技术，这种编码技术适用于变异操作和交叉操作，他指出在研究和设计人工自适应系统时可借鉴生物遗传的机制，以群体的方式进行自适应搜索。
70年代中期，Holland提出遗传算法的模式定理（Schema Theorem），奠定了遗传算法的理论基础。
11967年，Holland教授的学生De Jong首次将遗传算法应用于函数优化中，2设计了遗传算法执行策略和性能评价指标。
他挑选的5个专门用于遗传算法数值实验的函数至今仍被频繁使用，而他提出的在线(on-line)和离线(off-line)指标则仍是目前衡量遗传算法优化性能的主要手段。
1989年，Goldberg出版专著“Genetic Algorithm in Search, Optimization, and Machine learning”3。
该书全面阐述了遗传算法的基本原理及应用，并系统总结了遗传算法的主要研究成果。
该书对遗传算法科学基础的奠定做出了重要贡献。
1991年，Davis编辑出版了专著“Handbook of Genetic Algorithms”，该书中介绍了遗传算法在工程技术和社会生活中的大量应用实例。
41992年，美国斯坦福大学的Koza出版专著“Genetic Programming, on the Programming of Computers by Means of Natural Selection”，在此书中，他将遗传算法应用于计算机程序的优化设计和自动生成，并在此基础上提出遗传编程（Genetic Programming, GP）的概念5。
1994年，他又出版了上述专著的第二版“Genetic Programming II, Automatic Discovery of Reusable Program”，深化了遗传程序设计的研究6。
从20世纪80年代中期起，遗传算法和进化计算的研究到达一个高潮，以遗传算法和进化计算为主题的国际学术会议在世界各地定期召开。
1985年，第一届国际遗传算法会议（international conference on genetic algorithms, ICGA）在美国卡耐基·梅隆大学召开，以后每两年召开一届。
此外，进化规划年会（annual conference on evolutionary programming, ACEP）于1992年在美国的加州召开第一届会议，以后每隔两年召开一届；进化计算会议（IEEE conference on evolutionary computation）也于1994年开始定期召开。
2. 遗传算法的生物学基础遗传算法源于生物的进化与遗传原理在计算科学中的运用，了解生物学范畴的进化、遗传概念，有助于快速理解遗传算法的运行机理。
生物学对进化的认识经历了从宏观到微观两个阶段。
在宏观阶段，达尔文创建了自然选择学说。
该学说认为在特定的有限的资源条件下，生物时刻处在选择压力之中。
生物种群内部压力、种群间压力和环境压力不断淘汰劣势个体，保留优质个体。
在进化过程中，父代和子代之间存在性状的遗传和变异。
遗传是指父代和子代之间性状上的相似性，变异则是指父代与子代之间以及子代个体之间形状上的差异性。
遗传让子代能够继承父代的优良性状，而变异则让子代可能产生新的更适应环境的性状。
生物种群内部的遗传与变异，和生物种群面临的选择压力，三者共同作用，使生物种群向适应环境生存的方向发展进化。
20世纪生命科学中对染色体和基因的研究，使人类对生物进化的认识进入微观层面。
现代分子生物学研究显示，生物的外在性状是由生物细胞内染色体上的基因所决定的。
对于某一性状而言（如虹膜的颜色），基因型不同，则生物的外在表型也不同。
在遗传过程中，染色体发生连锁互换，基因型的组合发生变化，表型的组合也随之发生变化，有效增加更适应环境的表型组合出现的机率。
染色体上的基因发生突变，使生物可能获得新的突变后表型。
进化的实质，是基因的交换和突变创造出具有多样基因型和外在性状的种群，环境的选择压力再对种群进行筛选淘汰，保留具有适应环境的基因和性状的个体。
种群内个体的遗传突变和环境对个体的筛选持续进行，最终带来种群的进化。
3. 基本遗传算法为了解决不同的问题，不同的学者设计了许多不同的编码方法来表示问题的可行性，并开发出了不同的遗传算子来模仿不同环境下的生物遗传特性7。
这些遗传算法有着共同的特点，即通过对生物进化过程中的交叉、变异、遗传、选择过程进行模仿。
基于上述特点，Goldberg总结出了基本遗传算法（Simple Genetic Algorithms, SGA）3。
基本遗传算法简单易懂，是其他遗传算法的基础。
3.1 基本遗传算法的运算过程基本遗传算法的基础用语和运算过程与生物遗传过程存在着对应关系。
与生物进化类似，遗传算法会首先生成一个初始种群，标记为X。
X中包含问题的多个潜在解x1, x2, x3, …..，x n。
初始种群生成后，因遗传算法不能直接处理解空间的潜在解数据，因此需要通过基因编码的方式，将解数据表达成遗传算法可处理的基因型串结构数据，即染色体。
染色体经过遗传算子（Genetic Operators）操作，按照优胜劣汰的规则将适应度较高的个体的染色体更多的传递给后代，经过多次的遗传选择操作，第N代的种群中将会得到一个优良的个体x, x将达到或接近问题的最优解x*。
遗传算法中的遗传算子包括选择、交叉、变异三种：选择（selection ）：根据个体的适应度，按照一定的规则从第t 代种群中选择出优良个体遗传到t+1代群体中。
交叉（crossover ）：将第t 代种群内的个体随机搭配成对，每一对个体以某个交叉概率交换他们之间的部分染色体。
变异（mutation ）：对第t 代种群内的个体，以某一较低的变异概率改变染色体上的某一个或者某一些基因，使原基因值变为其他等位基因值。
基本遗传算法的运算过程如图表1所示。
其运算过程如下：① 随机建立初始群体。
② 计算各个体的适应度。
③ 根据遗传概率，用下述操作产生新群体：a. 复制，即选择，将已有优良个体复制后添入新群体中，删除劣质个体。
b. 交换，将选出的两个个体进行交换，所产生的新个体进人新群体。
c. 突变，随机改变某个体的某一字符后，将新个体添入新群体。
④ 反复执行②及③，直至达到终止条件，选择最佳个体作为遗传算法的结果。
图表1：基本遗传算法运算过程选择运算交叉运算 变异运算解码 个体评价编码解集和第t+1代群第t 代群体 遗传编码空间 解空间3.2 遗传编码遗传算法不对求解问题的实际决策变量进行直接操作，而是对可行解的个体编码进行选择、交叉、变异等遗传操作并达到优化目的。
把一个问题的可行解从解空间转化到遗传算法能够进行操作处理的空间的转化过程就是编码。
编码问题是应用遗传算法时的首要问题。
常用的编码方法有二进制编码、格雷码编码、浮点数编码、符号编码方法几类。
3.2.1 二进制编码1二进制编码是遗传算法中最常用的一种编码方法。
它具有编码解码过程简单易行、遗传算子操作便于实现、复合最小字符编码原则等优点。
二进制编码的符号串长度与问题所要求的精度有关。
若某一解集的取值范围为[U min, U max]，采用长度为a 的二进制编码符号串表示该参数，则可产生的编码有2a 种，编码精度为：δ=Umax−Umin2a−1编码长度越长，所对应的编码精度就越大，阶跃值就越小编码过程举例：求实数区间[0, 3] 上函数f ( x ) = − ( x − 1) 2+6最大值。
假设使用二进制编码形式，可以采用长度为5 的位串表示变量x，即从“00000”到“11111”。
并将中间的取值映射到实数区间[0, 3] 内。
由于从整数上来看，5位长度的二进制编码位串可以表示0到31，所以对应[0, 3] 的区间，每个相邻值之间的阶跃值为3/31 ≈0.0968，这个就是所谓的编码精度。
3.2.2 格雷码编码7对于一些连续优化问题, 二进制编码由于遗传算法的随机特性而使其局部搜索能力较差。
为改进这一特性, 人们提出用格雷码进行编码。
格雷码编码又称灰度编码，是二进制编码方法的一种变形。
格雷码编码的连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的, 其余码位都完全相同。
数字1到10 的二进制编码和格雷码编码分别如图表2所示。
图表2：二进制编码与格雷码编码若有一个长度为m的二进制编码为B=b m b m-1…b2b1，对应的格雷码为G=g m g m-1…g2g2，由二进制编码到格雷码的转换公式为：{g m=b mg i=b i+1⨁b i,i=m−1,m−2,…,1由格雷码到二进制编码的转换公式为：{b m=g mb i=g i+1⨁g i,i=m−1,m−2,…,1对于采用二进制编码的个体，变异操作是虽然只是改变某一个基因座，但可能造成对应的解的参数值的较大的差异。
但采用格雷码对个体进行编码，变异操作造成编码串之间的一位差异，对应的解参数值也只是发生微小差异，这就相当于增强了遗传算法的局部搜索能力，便于算法进行局部空间搜索。
3.2.3 浮点数编码对于高维、连续优化问题，采用二进制编码会带来一些不便之处。
由于从一个连续量离散化为一个二值量本身存在误差，使得算法很难求得精确解。
而要提高解的精度又必须加长编码串的长度，从而增加了编码的组合方式，造成解空间扩大，算法效率下降。
同时，二进制编码也不利于反映所求问题的特定知识，对问题信息和知识利用得不充分也会阻碍算法效率的进一步提高。
为了解决二进制编码产生的问题，人们在解决一些数值优化问题尤其是高维、连续优化问题时采用浮点数编码方法。
浮点数编码方法，是每个个体的每个基因值用实数表示，个体编码的长度等于其决策变量的个数。
因为此种方法采用决策变量的真实值，所以又称实属编码法或者真值编码法。
3.2.4 符号编码方法符号编码是指组成个体编码串的码值无数值含义而仅有字符含义。
这些符号可以是字符, 也可以是数字。
例如, 对于旅行商问题, 假设有n 个城市分别记为C1 , C2 , … , C n , 则[ C1, C2 , … , C n ] 就可构成一个表示旅行路线的个体。
符号编码的主要优点是便于在遗传算法中利用所求问题的专门知识及相关算法。
