[硕士论文精品]用遗传算法解决货郎担问题

随机过程课程论文SC10023033用遗传算法解决货郎担问题SC10023033何岸泓摘要货郎担问题也叫旅行商问题，即TSP问题。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。在实际运用中，由于TSP问题的复杂度极高，运用面极广，故任何对TSP问题的突破都将受到关注，传统的穷举法在TSP问题中无法实施，而GA算法由于其高度的适应性，近年来受到广泛的关注，本文将试图使用GA算法解决TSP问题，并在文末附上算法结果。关键字TSP，货郎担问题，遗传算法，GA，计算机仿真一背景介绍遗传算法（GENETICALGORITHM）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法由密歇根大学的约翰霍兰德和他的同事于二十世纪六十年代在对细胞自动机进行研究时率先提出。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。1989年，纽约时报作者约翰马科夫写了一篇文章描述第一个商业用途的遗传算法进化者（EVOLVER）之后，越来越多种类的遗传算法出现并被用于许多领域中，财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。遗传算法的发展大致可分为以下几个时期1）萌芽期50年代后期至70年代初期；随机过程课程论文SC100230332）成长期70年代初期至80年代末期；3）发展期90年代至今；1）萌芽期50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。直到1965年，德国的LRECHENBERG等人正式提出进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有变异一种。1965年，美国的LJFOGEL正式提出进化规划，在计算中采用多个个体组成的群体，而且只运用变异操作。美国JHHOLLAND在研究自适应系统时，提出系统本身与外部环境相互协调的遗传算法。1968年，JHHOLLAND教授又提出模式理论，它成为遗传算法的主要理论基础。在模式理论提出之后，1967年，BAGLEY发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（GENETICALGORITHM）”一词。2）成长期1975年，JHHOLLAND教授的专著自然界和人工系统的适应性ADAPTATIONINNATURALANDARTIFICIALSYSTEM正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志，HOLLAND也被视作遗传算法的创始人。其后，作为HOLLAND的学生，DEGOLDBERG博士在1985年出版专著遗传算法搜索、优化及机器学习GENETICALGORITHMSINSEARCH，OPTIMIZATIONANDLEARNING，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的经典教科书。1987年，美国DLAWRENCE总结人们长期从事遗传算法的经验，公开出版遗随机过程课程论文SC10023033传算法和模拟退火GENETICALGORITHMANDSIMULATEDANNEALING一书，以论文集形式用大量实例介绍遗传算法。在国际上，自1985年起开始在美国举行遗传算法国际学术会议INTERNATIONALCONFERENCEONGENETICALGORITHMS，简称ICGA），与会者交流运用遗传算法的经验，该会议每两年举行一次，进一步加速了遗传算法的发展。3）发展期进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。目前遗传算法的研究主要划分为以下几个领域1表示与遗传操作符2GA技术及特征3GA数学分析4并行GA5分类器系统和其它基于规则的方法6遗传编程随机过程课程论文SC100230337GA和神经网络8GA应用调度问题、组合择优等货郎担问题也叫旅行商问题，即TSP问题（TRAVELINGSALESMANPROBLEM），是数学领域中著名问题之一，其一般提法为有N个城市，用1，2，N表示，城I,J之间的距离为DI,J，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短货郎担问题有多重等效提法，该问题通常简称为TSP问题。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。有很多实际问题可归结为货郎担问题。例如在一条装配线上用一个机械手去紧固待装配部件上的螺帽问题。机械手由其初始位置该位置在第一个要紧固的螺帽的上方开始，依次移动到其余的每一个螺帽，最后返回到初始位置。机械手移动的路线就是以螺帽为结点的一个图中的一条周游路线。一条最小成本周游路线将使这机械手完成其工作所用的时间取最小值。注意，只有机械手移动的时间总量是可变化的。另一个例子是产品的生产安排问题。假设要在同一组机器上制造N种不同的产品，生产是周期性进行的，即在每一个生产周期这N种产品都要被制造。要生产这些产品有两种开销，一种是制造第I种产品时所耗费的资金1IN，称为生产成本，另一种是这些机器由制造第I种产品变到制造第J种产品时所耗费的开支CI,J称为转换成本。显然，生产成本与生产顺序无关。于是，我们希望找到一种制造这些产品的顺序，使得制造这N种产品的转换成本和为最小。由于生产是周期进行的，因此在开始下一周期生产时也要开支转换成本，它等于由随机过程课程论文SC10023033最后一种产品变到制造第一种产品的转换成本。于是，可以把这个问题看成是一个具有N个结点，边成本为CI,J图的货郎担问题。随机过程课程论文SC10023033二用遗传算法解决货郎担问题的数学形式1遗传算法的具体形式遗传算法的通常实现为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串）。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，这一过程称为编码。一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集0，1组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如X100111001000101101就可表示一个个体，该个体的染色体长度是L18。下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的，其中繁殖包括交配CROSSOVER和突变MUTATION。选择则是根据新个体的适应度进行的，适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率，范围一般是061，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为08，则80的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的随机过程课程论文SC10023033“老”个体，而不交配的个体则保持不变。交配父母的染色体相互交換，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段並不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数，通常是01或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。2基遗传算法的形式化定义基本遗传算法可定义为一个7元组GAM,F,S,C,M,PC,PMM群体大小；F个体适应度评价函数；S选择操作算于；C交叉操作算子M变异操作算于；PC交叉概率；PM变异概率；随机过程课程论文SC100230333遗传算法的优点遗传算法作为一种快捷、简便、容错性强的算法，是一类可用于复杂系统优化的具有鲁棒性的搜索算法。在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。跟传统的爬山算法相比，遗传算法能够跳出局部最优而找到全局最优点。而且遗传算法允许使用非常复杂的适应度函数（或者叫做目标函数），并对变量的变化范围可以加以限制。而如果是传统的爬山算法，对变量范围进行限制意味着复杂的多的解决过程。遗传算法的主要优点有以下方面1）遗传算法以决策变量的编码作为运算对象。搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。2）搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性。3）采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。4）对搜索空间没有任何特殊要求（如连通性、凸性等），直接以适应度作为搜索信息，不需要导数等其它辅助信息，适应范围更广。5）使用多个点的搜索信息，具有隐含并行性,易于并行化。由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，随机过程课程论文SC10023033对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。在很多其他方法不能解决或者很难解决的时候，遗传算法给出了一个“有胜于无”的退而求其次的求解途径。下面是遗传算法的一些主要应用领域1工业工程与运作管理2物流系统设计3生产调度4制造系统控制5系统优化设计6汽车设计，包括材料选择、多目标汽车组件设计、减轻重量等。7机电系统设计。8分布计算机网络的拓扑结构。9电路设计，此类用途的遗传算法叫做进化电路。10电子游戏设计，例如计算平衡解决方案。11机器智能设计和机器人学习。12模糊控制系统的训练。13移动通讯优化结构。14时间表安排，例如为一个大学安排不冲突的课程时间表。15神经网络的训练，也叫做神经进化。随机过程课程论文SC10023033三将遗传算法运用于货郎担问题货郎担问题为一个最优化问题，对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数学规划模型MAXFXSTXRRU其中XX1,X2,XN为决策变量；FX为目标函数；U是基本空间；R是U的一个子集；满足约束条件的解X称为可行解；集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。在遗传算法中，N维决策向量XX1,X2,XN用N个记号XII1,2,N所组成的符号串X来去示XXLX2XNXX1，X2，,XN把每一个XI看作一个遗传基因，这样，X就可看做是由N个遗传基因所组成的一个染色体。在通用的遗传算法中，等位基因可以是一组整数。也可以是某一范随机过程课程论文SC10023033围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。在利用遗传算法解决货郎担问题时候，假设有N个城市，这里用XI表示第I次到达的城市，比如X1X2X3X4XN18573表示从第一个城市出发，先到第8个城市，再从第8个城市到第5个城市，最后到第3个城市，并从第3个城市回到第1个城市。显然，每个城市在X中将会出现一次。由于这里在整个可行域内求解，所以RU，如果现在在某个可行域子域中求解时，相等关系不满足。在货郎担问题中，可行域内可行解为全体城市编号的一个排列N，并且由于每个可行解为一个回路，故可行解总数为N再除以N，亦即为N1。对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。在货郎担问题中，目标函数为使得“整个路径最短”，故CI,J越大，其“适应度”越小。适应度函数的设计主要满足以下条件A）单值、连续、非负、最大化；B合理、一致性；C）计算量小；D）通用性强。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。在本货郎担问题中，适应度函数定义为当前路径的权值之和中最小的M个（M为每代中存在的个体总数）。随机过程课程论文SC10023033生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程第T代群体记做PT，经过一代遗传和进化后，得到T1代群体，记做PT1,这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解。4）算法中初始值的选取遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略A根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。B先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。在货郎担问题中，假设城市的在地图上的分布为均匀，则那些从地图一头跨越到另一头的路径选中的概率较小，更加可能的选择方法为就近原则，即货郎先到附近某个城市（不一定为最近）去，而非立即选择一个最远的城市。然而为了编程简单，在文末附上的代码中的初始解为随机设定的。随机过程课程论文SC100230335）遗传操作遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度适应度评估施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼进最优解。遗传操作包括以下三个基本遗传算子GENETICOPERATOR选择SELECTION交叉CROSSOVER变异MUTATION这三个遗传算子有如下特点个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。个体适应度越大，其被选择的概率就越高、反之亦然。在货郎担问题中，选择的方式很简单，那些路径总和较小的选中概率较高。在自然界生物进化过程中起核心作用的是生物遗传基因的重组加上变异。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉时根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。在实际运用中，交叉方法很多。最常用的交叉算子为单点交叉ONEPOINTCROSSOVER。具体操作是在个体串中随机设随机过程课程论文SC10023033定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子个体A10011111001000新个体个体B00110000011111新个体由于货郎担为题中XI表示的为第I次到达的城市，故直接的单点交叉不能使用，但是注意到整个可行路径实际上为一个圆环，可以改变其起始城市，然后将可行的结点序予以交叉。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异时候需要选择变异的个体。一般先对群中所有个体以事先设定的编译概率判断是否进行变异，然后对选中要变异的个体，对其随机选择变异位进行变异。遗传算法导引入变异的目的有两个一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。在货郎担问题中，变异方法比交叉方法简单，随机选择X序列中的两个位，进行交换位置即可。这样便改变了货郎的选择路径，实现了变异。文末程序中在变异后对适应度较低的个体进行了淘汰。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取000101，如果较大，将出现计算过程中“解振荡”。程序中变异概率取为1。算法终止条件遗传算法终止条件一般为当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100500代。程序中通过一个宏随机过程课程论文SC10023033DEFINE_TIMES100来设置迭代的次数为100，亦即遗传算法中进化的“代数”。如果求解货郎担问题中节点数目较多，则需要将此值设置得大一些。不然将难以获得最优或者次优解。随机过程课程论文SC10023033三计算机仿真实现在文章末附上该算法的仿真结果，整体为使用VC实现。在程序中设置了以下重要的常数DEFINE_CITY_AMOUNT10DEFINE_GENERATION_AMOUNT200DEFINE_TIMES500DEFINE_GENE_ABERRANCE10这几个变量为货郎担问题和遗传算法的参数控制，其中_CITY_AMOUNT表示货郎担问题的城市个数，这里设置为20，那么如果直接使用穷举法，其数量级在19左右。_GENERATION_AMOUNT为控制整个种群的大小，这里设置为200个，遗传算法每迭代一次，将会淘汰掉适应度较低的个体，保留较为优秀的个体，淘汰表现为控制种群的大小恒定。_TIME表示遗传算法的迭代次数，迭代次数在任何一种算法中都是收到特别关注的，迭代次数若较小，可能无法收敛到最优值或者收敛到局部最优值，迭代次数较大，则会影响到算法运行时间。这里的_TIMES的设置需要根据_CITY_AMOUNT来确定，当_CITY_AMOUNT增大时，_TIMES需要相应增大。实际运用中多是根据经验设定一个经验值即可。_GENE_ABERRANCE为控制遗传算法的变异率，在实际运用的遗传算法中，变异概率都会设置的很低，通常为0100001之间，如果设置过大，会导致算法振荡不收敛，变异率如果设置的过小，则相当于遗传算法中没有变异的影响，仅有染色体交叉。这对求解过程跳出局部最优解是不利的。本次算法中变异概率设置为01。在实际运行中，由于遗传算法为依该如此收敛到最优值，故在设定的迭代次随机过程课程论文SC10023033数中可能并没有获得全局最优，但是遗传算法总能给出一个不错的“次优值”，这对实际生产生活来说有重要的意义。在程序中使用的城市规模为20，其矩阵CCI,J为以下给出运行的结果第一次运行最短路径为2935127410161315171411619101882路径长度为31收敛过程为595149454141414141414140404040403938383838363636363636363636363636363636363636363