用Matlab编程实现遗传算法

用Matlab编程实现遗传算法摘要：遗传算法是模拟自然界生物进化过程的计算模型，是当今在性质比较复杂的最优化问题中比较常用的方法.本文阐述了遗传算法的基本原理，分析了实现该算法的基本步骤及常用方法.然后建立了旅行商(TSP)问题的数学模型，给出了遗传算法解决旅行商(TSP)问题的基本方法，并结合具体实例，借助Matlab数学软件编程实现了该算法，从而证明了该方法的可行性和有效性.关键词：遗传算法；选择；交叉；变异；旅行商问题MatlabprogramminggeneticalgorithmHeNa(2002E410107Class1Grade2002Information&ComputingScienceSchoolofMathematics&

Information)Abstract：Geneticalgorithmwhichsimulatesnaturalbiologicalevolutionaryprocessisthecalculationmodelinthenatureoftoday'smorecomplexoptimizationproblemsandmorecommonlyusedmethods.Inthisarticlethebasicprinciplesofgeneticalgorithmsareexpoundedandthebasicstepsandcommonlyusedmethodsofthealgorithmareanalyzed.ThenTSPmathematicalmodelsareestablished,ageneticalgorithmtosolveTSPbasicmethodisprovided,andspecificexamplesfromMatlabmathematicalsoftwareprogrammingtoachievethealgorithmisintegrated,Thusitprovedthatthemethodwasfeasibleandeffective.Keyword:GeneticAlgorithm；selection；crosser；variation；TSP1引言巡回旅行商问题(TSP)，也称为货郎担问题，是一个较古老的问题.1948年，由美国兰德公司推动，TSP逐渐成为近代组合优化领域的一个典型难题.应该说，TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题，它已经被认明属于NP难题.几十年来、出现了很多近似优化算法，如近邻法(neareatneighbor)>贪心算法(greedya1gorithm)、最近插入法(nearestinsertion)、最远插入法(fartherinscrtion)、双极小生成树法(doubleminimumspanningtree)等等［11近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法、模拟退火方法以及遗传算法.本文给出了遗传算法应用于旅行商问题的详细过程,通过具体实例证明了遗传算法是解决该问题行之有效的方法，并用Matlab编程实现了该算法.2旅行商(TSP)问题的描述TSP(TravelingSalesmanProblem)问题简述如下：有n个城市C1,C2,C3，,C,某旅行商从某一城市出发，各城市均需访问一次后回到出发地，要求找出一条最短路线.用图论来描述TSP，给出一个图G(V,E)，每边eeE上令非负权值W(e)，寻找G的Hamilton圈C，使得C的总权W(C)=2w(e)最小.这是一个典型的优化组合问题，已被证明属于NP完全问题，e即没有确定的算法能在多项式时间内得到问题的解.TSP搜索空间随着城市数n的增加而增大，所有的旅程路线组合数为(n-1)!/2.5个城市的情形对应120/10=12条路线，10个城市的情形对应3628800/20=181440条路线，100个城市的情形则对应有4.6663xl0155条路线.在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难.借助遗传算法的搜索能力解决TSP问题，是很自然的想法.因此，我们选择使用遗传算法来解决旅行商问题.3遗传算法遗传算法(GA)是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，由美国［Holland教授提出⑵其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息.因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化，机器学习，自适应控制，规划设计和人工生命领域.GA是一种群体型操作，该操作以群体中的所有个体为对象.选择，交叉和变异是遗传算法的三个主要算子，他们构成了遗传算法的主要操作，使遗传算法具有了其它传统方法所没有的特性.选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体，交叉是结合来自父代交配种群中的信息产生新的个体，交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化.遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是完全随机搜索.它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集.这样一代代地不断进化，最后收敛到一个最适应该环境的个体上，求得问题的最优解.遗传算法中包含了如下五个基本要素：1.参数编码,2.初始群体的设置,3.适应度函数的设计，4.遗传操作设计,5.控制参数设定，这个五个要素构成可遗传算法的核心内容.遗传算法的搜索能力是由选择算子和交叉算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力.而遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释.在使用遗传算法解决问题的同时还需要设置一些参数，比如说种群的大小、染色体长、交叉率、变异率、最大进化代数等，这些参数对GA的性能都有很重要的影响.一般我们将这些参数的设置如下：种群大小N=200~1000,交叉概率p=0.4~0.9，变异概率P=0.001~0.2，最大进化代数maxgen=1000~1500.C遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：选择编码策略，把参数集合X和域转换为位串结构空间S；定义适应值函数f(x)；确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率，变异概率等遗传参数；随机初始化生成群体P；计算群体中个体位串解码后的适应值f(x)；按照遗传策略、运用选择、交叉和变异算子作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者巳完成预定迭代次数，不满足则返回步骤(6)，或者修改遗传策略再返回步骤(6),满足则退出迭代，输出结果.遗传算法的基本流程图如下：4遗传算法求遗传算法求解旅行商问题下面我们结合9个城市的TSP,讨论遗传算法在TSP问题上的应用.遗传算法对于旅行商问题的实现过程如下：4.1群体的初始化在该环节中，需要做以下初始化工作，确定种群规模M、杂交概率p、变异概率P、及最大进化代数maxgen.这些参数的选取将直接会影响到运算速度及结果."4.2编码策略：路径表示与交叉路径表示(pathrepresentation)是表示旅程对应的基因编码的最自然、最简单的表示方法.例如，旅程(5—1—7—8—9—4—6—2—3)可以直接表小为(517894623)，基于路径表示的编码方法，要求一个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任一个城市必须而且只能访问一次的约束.这样，基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件.为此.人们提出了一组称为重排操作的新的操作来处理这类表示问题，常见的有三种操作：部分匹配交叉、顺序交叉、循环交叉，本文主要就前两种进行详细介绍.4.2.1部分匹配交叉1985年，Goldberg等针对TSP提出了基于路径表示的部分匹配交叉[1](PMX)操作，PMX操作要求随机选取两个交叉点，以便确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体.PMX步骤步骤1：在字串上均匀随机地选择两点，由这两点定义的子串称为映射段;步骤2：交换双亲的两个子串，产生原始后代；步骤3：确定两映射段之间的映射关系；步骤4：根据映射关系将后代合法化.例如，对下面两个父个体的表示，随机地选择两个交叉点“|”P(123I4567I89)P(452I1876I93)首先，两个交叉点之间的中间段交换，得到：d(xxxI1876Ixx)d(xxxI4567Ixx)其中x表示暂未定义码(下同)，得到中间段的映射关系，有：1—4，8—5，7—6，6—7然后，对子个体1、子个体2中x部分，分别保留从其父个体小继承末选定城市码2，3，9，得到：a(x23I1876Ix9)51(xx2I4567I93)最后，根据中间段的映射关系，对于上面子个体1的第一个乂，使用最初父码1，由1--4交换得到第一个x为4,类似地子个体1的第二个x使用最初父码8,由8--5交换得到子个体1的第二个x为5.如果映射关系中存在传递关系，即备选交换有多个码，则选择此前未确定的一个码作为交换.类似地进行操作，最终得到的子个体为：5(423I1876I59)

a21(182I4567I93)4.2.2顺序交叉1985年，Davis等针对TSP提出了基于路径表示的顺序交叉(OX)操作.0乂操作能保留排列并融合不同排列的有序结构单元.两个父个体交叉时，通过选择父个体1的一部分，保存父个体2中城市码的相对顺序生成子个体.顺序交叉步骤步骤1：从第一双亲中随机选一个子串；步骤2：将子串复制到一个空字串的相应位置，产生一个原始后代；步骤3：删去第二双亲中子中已有的城市，得到原始后代需要的其他城市的顺序；步骤4：按照这个城市顺序，选择某个位置将这些城市定位到后代的空缺位置上.例如，对下面两个父个体的表示，与PMX操作一样随机地选择两个交义点“|“P(123I4567I89)P(452I1876I93)首先，两个交叉点之间的中间段保存不变，得到：5(xxxI4567Ixx)5(xxxI1876Ixx)然后，记取父个体2从第二个交叉点开始城市码的排列顺序，当到达表尾时，返回表头继续记录城市码，直至到达第二个交叉点结束，这样便获得了父个体2从第二个交叉点开始的城市码排列顺序为9—3—4—5—2—l—8—7—6.对于父个体1而言，已有城市码有4,5,6,7将它们从父个体2的城市码排列顺序中去掉，得到排列顺序9-3-2-1-8，再将这个排列顺序复制给父个体1，复制的起点也是从第二个交叉点开始，以此决定子个体1对应位置的未知码x这样子个体1生成为8(218456793)同样，可以产生子个体2为：182(345187692)4.3变异策略过去10年里，提出了几种用于表达变异的运算，如反转、插入、移位等变异方法，下面分别进行简单介绍.反转变异反转变异是在染色体上随机地选择两点，将两点之间的子串反转.插入变异插入变异是随机地选择一个城市，并将它插入到一个随机的位置中.移位变异移位变异是随机地选择一个子串，并将其插入到一个随机的位置中.4.4评价方法：适应函数(评价函数)的定义对于本问题采用巡回路程作为评价函数，即完成一次巡回的路程总和,目标函数g3)定义如下：g(x)=£w(e)，(w为每边eeE上的非负权值)TSP问题为最小化问题，建立如下适应函数f(x)和目标函数g(x)的映射关系：0,elsef(x)"max-g⑴,f，g⑴Tax0,else其中，c可以是一个输入值或是理论上的最大值.或者是到当前所有代或最近kmax代中g(x)的最大值，此时cmax随着代数会有变化.计算实例及程序实现例8个城市(匕,十..,七)之间有一个公路网(如图所示)，每条公路为图中的边，边上的权数表示通过该公路所需的时间.那么各个城市均到到达且仅到达一次应选择什么路径使所需的时间最少？对于本例按如下方法对种群初始化，种群大小N选择500,杂交概率p定为0.8、变异概率七定为0.1,采用路径编码方式进行顺序交叉、反转变异，经过20代遗传进化后，最后得到如下解：(vTVTVTVTVTVTVTV)，其2 1 3 4 5 6 7 8总时间为16.Matlab完整程序实现见附录.结论本文论述了遗传算法的基本原理以及用该算法解决组合优化中的典型问题一旅行赏(TSP