1、by simulated authentication.Keywords: Genetic algorithm； Matlab；Optimization1引言遗传算法（Genetic Algorithm）是模拟自然界生物进化机制的一种算法即遵循适者生存、优胜劣汰的法则也就是寻优过程中有用的保留无用的则去除. 在科学和生产实践中表现为在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法即找出一个最优解. 这种算法是1960年由Holland提出来的其最初的目的是研究自然系统的自适应行为并设计具有自适应功能的软件系统. 它的特点是对参数进行编码运算不需要有关体系的任何先验知识沿多种路线进行
2、平行搜索不会落入局部较优的陷阱，能在许多局部较优中找到全局最优点是一种全局最优化方法1-3. 近年来，遗传算法已经在国际上许多领域得到了应用. 该文将从遗传算法的理论和技术两方面概述目前的研究现状描述遗传算法的主要特点、基本原理以及改进算法，介绍遗传算法的应用领域，并用MATLAB实现了遗传算法及最优解的求解.2文献综述2.1国内外研究现状及评价国内外有不少的专家和学者对遗传算法的进行研究与改进. 比如：1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题
3、中，通过实验对其进行了验证. 2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题. 国内外很多文献都对遗传算法进行了研究. 现查阅到的国内参考文献1-19中, 周勇、周明分别在文献1、2中介绍了遗传算法的基本原理；徐宗本在文献3中探讨了包括遗传算法在内的解全局优化问题的各类算法，文本次论文写作提出了明确的思路；张文修、王小平、张铃分别在文献4、5、6从遗传算法的理论和技术两方面概述目前的研究现状；李敏强、吉根林、玄光南分别在文献7、8、9中都
4、不同程度的介绍了遗传算法的特点以及改进算法但未进行深入研究；马玉明、张丽萍、戴晓辉、柴天佑分别在文献10、11、12、13中探讨了遗传算法产生的背景、起源和发展；李敏强、徐小龙、林丹、张文修分别在文献14、15、16、17探讨了遗传算法的发展现状及以后的发展动向；李敏强，寇纪凇，林丹，李书全在文献18中主要论述了遗传算法的具体的实施步骤、应用领域及特点；孙祥，徐流美在文献19中主要介绍了Matlab的编程语句及基本用法. 所有的参考文献都从不同角度不同程度的介绍了遗传算法但都不够系统化不够详细和深入.2.2提出问题随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能
5、，也不现实，因而求出近似最优解或满意解是人们的主要着眼点之一. 很多人构造出了各种各样的复杂形式的测试函数，有连续函数，有离散函数，有凸函数，也有凹函数，人们用这些几何特性各异的函数来评价遗传算法的性能. 而对于一些非线性、多模型、多目标的函数优化问题用其他优化方法较难求解遗传算法却可以方便地得到较好的结果. 鉴于遗传算法在函数优化方面的重要性，该文在参考文献1-19的基础上，用Matlab语言编写了遗传算法程序, 并通过了调试用一个实际例子来对问题进行了验证，这对在Matlab环境下用遗传算法来解决优化问题有一定的意义.3遗传算法的理论研究3.1遗传算法的产生背景科学研究、工程实际与国民经济
6、发展中的众多问题可归结作“极大化效益、极小化代价”这类典型模型. 求解这类模型导致寻求某个目标函数（有解析表达式或无解析表达式）在特定区域上的最优解. 而为解决最优化问题目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的. 随着研究的深入，人们逐渐认识到：在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出近似最优解或满意解是人们的主要着眼点之一. 总的来说，求最优解或近似最优解的方法有三种: 枚举法、启发式算法和搜索算法.（1）枚举法. 枚举出可行解集合内的所有可行解以求出精确最优解. 对于连续函数，该方法要
7、求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解. 另外，当枚举空间比较大时该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解.（2）启发式算法. 寻求一种能产生可行解的启发式规则以找到一个最优解或近似最优解. 该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性不适合于其它问题.（3）搜索算法. 寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作以找到问题的最优解或近似最优解. 该方法虽然保证了一定能够得到问题的最优解，但若适当地利用一些启发知识就可在近似解的质量和求解效率上达到一种较好的平衡.随
8、着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题. 而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架开创了一种新的全局优化搜索算法.3.2遗传算法的起源与发展3.2.1 遗传算法的起源50年代末到60年代初，自然界生物进化的理论被广泛接受生物学家Fraser，试图通过计算的方法来模拟生物界“遗传与选择”的进化过程，这是遗传算法的最早雏形. 受一些生物学家用计算机对生物系统进行模拟的启发，Holland开始应用模拟遗传算子研究适应性. 在1967年，Bagley关于自适应下棋程序的论文中，他应用遗传算法搜索下棋游戏评价函数的参数集
9、并首次提出了遗传算法这一术语. 1975年，Holland出版了遗传算法历史上的经典著作自然和人工系统中的适应性，首次明确提出遗传算法的概念. 该著作中系统阐述了遗传算法的基本理论和方法，并提出了模式（schemat atheorem）4，证明在遗传算子选择、交叉和变异的作用下具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长. Holand创建的遗传算法，是基于二进制表达的概率搜索方法. 在种群中通过信息交换重新组合新串；根据评价条件概率选择适应性好的串进入下一代；经过多代进化种群最后稳定在适应性好的串上. Holand最初提出的遗传算法被认为是简单遗传算法的基础
10、，也称为标准遗传算法.3.2.2 遗传算法的发展（1）20世纪60年代，John Holland教授和他的数位博士受到生物模拟技术的启发，认识到自然遗传可以转化为人工遗传算法. 1962年，John Holland提出了利用群体进化模拟适应性系统的思想，引进了群体、适应值、选择、变异、交叉等基本概念.（2）1967年，J.D.Bagely在其博士论文中首次提出了“遗传算法”的概念.（3）1975年，Holland出版了自然与人工系统中的适应性行为（Adaptation in Natural and Artificial System）.该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的
11、基本定理模式定理，从而奠定了遗传算法的理论基础. 同年De Jong在其博士论文中，首次把遗传算法应用于函数优化问题对遗传算法的机理与参数进行了较为系统地研究并建立了著名的五函数测试平台.（4）20世纪80年代初，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统（Classifier System简称CS），开创了基于遗传算法的机器学习的新概念.（5）1989年，David Goldberg出版了搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search Optimization and Machine Learning）.该书全面系统地总结了
12、当时关于遗传算法的研究成果，结合大量的实例完整的论述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础.（6）1992年，John R.Koza出版了专著遗传编程（Genetic Programming）提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面. 随着遗传算法的不断深入和发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向.今天遗传算法的研究已经成为国际学术界跨学科的热门话题之一. 遗传算法是一种有广泛应用前景的算法，但是它的研究和应用在国内尚处于起步阶段. 近年来遗传算法已被成功地应用于工业、经济管理、交通运
13、输、工业设计等不同领域解决了许多问题.例如可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等.3.3 遗传算法的数学基础研究模式定理及隐含并行性原理被看作遗传算法的两大基石，后来又提出了建筑块假设，但是模式定理无法解释遗传算法实际操作中的许多现象，隐性并行性的论证存在严重漏洞，而建筑块假设却从未得到过证明. 对遗传算法的基础理论的研究主要分三个方面：模式定理的拓广和深入、遗传算法的新模型、遗传算法的收敛性理论.（1）模式定理的拓广和深入. Holland给出模式定理：具有短的定义长度、低阶、并且模式采样的平均适应值在种群平均适应值以上的模式在遗传迭代过程中将
14、按指数增长率被采样模式定理可表达为：m（H,t+1）m（H,t）. （1）其中m（Ht）：在t代群体中存在模式H 的串的个数.：在t 代群体中包含模式H 的串的平均适应值.t代群体中所有串的平均适应值.表示串的长度表示交换概率表示变异概率.Holland的模式定理奠定了遗传算法的数学基础根据隐性并行性得出每一代处理有效模式的下限值是其中n是种群的大小是小整数. Bertoui和Dorigo进行了深入的研究获得当,为任意值时处理多少有效模式的表达式. 上海交通大学的恽为民等获得每次至少产生数量级的结果. 模式定理中模式适应度难以计算和分析A.D.Berthke首次提出应用Walsh函数进行遗传算
15、法的模式处理并引入模式变换的概念采用Walsh函数的离散形式有效地计算出模式的平均适应度并对遗传算法进行了有效的分析. 1972年Frantz首先发现一种常使GA从全局最优解发散出去的问题，称为GA-欺骗题5. Goldberg最早运用Walsh模式转换设计出最小的GA-欺骗问题并进行了详细分析.（2）遗传算法的新模型. 由于遗传算法中的模式定理和隐性并行性存在不足之处，为了搞清楚遗传算法的机理，近几年来人们建立了各种形式的新模型最为典型的是马氏链模型遗传算法的马氏链模型6-7，主要由三种分别是种群马氏链模型、Vose模型和Cerf 扰动马氏链模型. 种群马氏链模型将遗传算法的种群迭代序列视为
16、一个有限状态马氏链来加以研究，运用种群马氏链模型转移概率矩阵的某些一般性质分析遗传算法的极限行为，但转移概率的具体形式难以表达妨碍了对遗传算法的有限时间行为的研究；Vose模型是在无限种群假设下利用相对频率导出，表示种群的概率的向量的迭代方程，通过这一迭代方程的研究，可以讨论种群概率的不动点及其稳定性，从而导致对遗传算法的极限行为的刻画，但对解释有限种群遗传算法的行为的能力相对差一些. Cerf扰动模型是法国学者Cerf将遗传算法看成一种特殊形式的广义模拟退火模型，利用了动力系统的随机扰动理论，对遗传算法的极限行为及收敛速度进行了研究. 还有其它改进模型，例如张铃、张钹等人提出的理想浓度模型，
17、它首先引入浓度和家族的概念，通过浓度计算建立理想浓度模型8-10，其浓度变化的规律为：c（Hi，t +1）=c（H，t） （2）c（Hi，t+1）表示模式Hi在t时刻的浓度，并对其进行分析，得出结论：遗传算法本质上是一个具有定向制导的随机搜索技术，其定向制导原则是导向适应度高的模式为祖先的染色体“家族”方向.（3）遗传算法的收敛性理论. 对于遗传算法的马氏链分析本身就是建立遗传算法的收敛性理论11-12， Eiben等用马尔可夫链证明了保留最优个体的遗传算法的概率性全局收敛，Rudolph用齐次有限马尔可夫链证明了具有复制、交换、突变操作的标准遗传算法收敛不到全局最优解，不适合于静态函数的优化
18、问题，建议改变复制策略以达到全局收敛，Back和Muhlenbein研究了达到全局最优解的算法的时间复杂性问题，近几年，徐宗本等人建立起鞅序列模型，利用鞅序列收敛定理证明了遗传算法的收敛性. 3.4遗传算法的组成要素遗传算法所涉及的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定，其具体内容如下：（1）参数编码. 遗传算法中常用的编码方法是二进制编码，它将问题空间的参数用字符集0，1构成染色体位串，符合最小字符集原则，操作简单，便于用模式定理分析.（2）适应度函数的设计. 适应度函数是评价个体适应环境的能力，使选择操作的依据，是由目标函数变换而成. 对适应度
19、函数唯一的要求是其结果为非负值. 适应度的尺度变换是对目标函数值域的某种映射变换，可克服未成熟收敛和随机漫游现象. 常用的适应度函数尺度变化方法主要有线性变换、幂函数变换和指数变换.13（3）遗传操作的设计. 包括选择、交叉、变异.选择（Selection）. 选择是用来确定交叉个体，以及被选个体将产生多少个子代个体. 其主要思想是个体的复制概率正比于其适应值，但按比例选择不一定能达到好的效果. 选择操作从早期的轮盘赌选择发展到现在最佳个体保存法、排序选择法、联赛选择法、随机遍历抽样法、局部选择法、柔性分段复制、稳态复制、最优串复制、最优串保留等.交叉（Crossover）. 交叉是指把两个父
20、代个体的部分结构加以替换重组而生成新个体的操作，其作用是组合出新的个体，在串空间进行有效搜索，同时降低对有效模式的破坏概率. 各种交叉算子均包含两个基本内容：确定交叉点的位置和进行部分基因的交换. 常用的交叉操作方法有单点交叉、双点交叉、一致交叉、均匀交叉、算术交叉、二维交叉、树结构交叉、部分匹配交叉、顺序交叉和周期交叉等等.变异（Mutation）. 变异是指将个体编码串中的某些基因值用其它基因值来替换,形成一个新的个体. 遗传算法中的变异运算是产生新个体的辅助方法，其目的是使遗传算法具有局部的随机搜索能力和保持群体的多样性. 变异算法包括确定变异点的位置和进行基因值替换. 常见的变异算子有
21、基本位变异、均匀变异、高斯变异、二元变异、逆转变异、自适应变异等.（4） 控制参数设定. 遗传算法中需要确定一些参数取值，主要有串长l，群体大小n，交叉概率pc、变异概率pm等，对遗传算法性能影响很大. 目前对参数根据情况进行调整变化研究比较多，而一般确定的参数范围是：n=20200，pc = 015 110，pm =00105.3.5遗传算法的基本原理在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个
22、体与由它们组成的新群体. 在特定的条件下，基因会发生突变,产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是真实模拟自然界生物进化机制进行寻优的. 在此算法中,被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体，个体用多维向量或矩阵来描述，组成矩阵和向量的参数相应于生物种组成染色体的基因，染色体用固定长度的二进制串表述，通过交换、突变等遗传操作，在参数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量，相当于得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被淘汰.14 由于遗传操作可
23、以越过位垒，能跳出局部较优点，到达全局最优点.遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成，每个解都有一目标函数给与评判，一次迭代成为一代. 经典的遗传算法结构图如下：图1 遗传算法的结构图3.6遗传算法在实际应用时采取的一般步骤（1）根据求解精度的要求，确定使用二进制的长度. 设值域的取值范围为,，若要求精确到小数点后6位，则由（-）106-1求得的最小长度，进而可求出位于区间的任一数：=+decimal（.15 （3）其中，i=1，2， .， Popsize；Popsize为种群中染色体的个数；（2）
24、利用随机数发生器产生种群；（3）对种群中每一染色体，计算其对应适应度eval（），i=1，2， ，Popsize；（4）计算种群适应度之和F：F= （4）（5）计算每个染色体选择概率Pi： （5）i=1，2， . ，Popsize ；（6）计算每个染色体的累加概率 （6）i=1， 2， .，Popsize ；（7）产生一个位于0，1区间的随机数序列，其长度为N，如果其中任意一数r，则选择第一个染色体，若r，则选择第i个染色体，i=1，2， . Popsize，这样可以获得新一代种群；（8）对新一代种群进行交叉运算：设交叉概率为，首先产生一个位于区间0,1内的随机数序列，其长度为N，如果其中任意
25、一数r，则对应染色体被选中（如果选中奇数个，则可以去掉一个），然后在1，m-1区间中产生随机数，个数为选中的染色体数的一半，然后根据随机数在对应位置进行交换操作，从而构成新的染色体；（9）变异操作：设变异概率为，产生mN个位于区间0，1上的随机数.如果某一随机数r，则选中对应位变异，构成新的种群；（10）第一代计算完毕，返回继续计算，直到达到满意的结果为止.3.7遗传算法的基本流程描述随机初始化种群p（0）=x1，x2，.，xn；t=0；计算p（0）中个体的适应值；while（不满足终止条件） 根据个体的适应值及选择策略从p（t）中选择下一代生成的父体p（t）；执行交叉,变异和再生成新的种群p
26、（t+1） ；计算p（t+1）中个体的适应值；t=t+1；伪代码为：BEGIN：I=0；Initialize P（I）；Fitness P（I）；While （not Terminate2Condition）I+；GA2Operation P（I）；END.3.8遗传算法的特点遗传算法不同于传统的搜索和优化方法. 主要区别在于：（1）自组织、自适应和自学习性（智能性）. 应用遗传算法求解问题时，在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索. 由于基于自然的选择策略“适者生存、不适者被淘汰”，因而适应度大的个体具有较高的生存概率. 通常适应度大的个体具有更适
27、应环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代. 进化算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规律的能力. 自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施.因此，利用遗传算法，我们可以解决那些复杂的非结构化问题.（2）遗传算法的本质并行性. 遗传算法按并行方式搜索一个种群数目的点，而不是单点. 它的并行性表现在两个方面，一是遗传算法是内在并行的（ inherent parallelism），即遗传算法本身非常适合大规模并行. 最简单的并行方式是让几百甚至
28、数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信（独立的种群之间若有少量的通信一般会带来更好的结果），等到运算结束时才通信比较，选取最佳个体.这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率没有太大影响. 二是遗传算法的内含并行性. 由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息. 使用这种搜索方式，虽然每次只执行与种群规模N成比例的计算，但实质上已进行了大约O（N3）次有效搜索，这就使遗传算法能以较少的计算获得较大的收益.（3）遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相
