基于遗传算法的组合优化问题的研究

论文总字数：22395字

目 录

一.绪论 1

1.1研究目的和意义 1

1.2 国内外研究现状 2

1.3 研究内容和相关课题 4

1.4 旅行商问题简介 5

二 遗传算法基本原理和实现 5

2.1 遗传算法的基本原理 5

2.2 遗传算法的基本步骤 7

2.3 TSP问题遗传算法实现 7

2.3.1 编码 8

2.3.2 交叉操作 8

2.3.3 变异操作 9

2.3.4 遗传算法基本步骤的Java语言实现 10

2.3.5 逆转操作 12

2.3.6 基于遗传算法TSP的matlab语言实现 13

2.3.6.1 前期准备 13

2.3.6.2 matlab模拟实现 14

三 过程分析与说明： 15

3.1关于适应度函数、交叉参数、变异参数的说明 15

3.2关于迭代次数的思考 16

3.3 灵敏度分析 16

3.3.1加大种群数量，控制迭代次数，观察收敛速度和精度 16

3.3.2控制种群数量，增加迭代次数，观察收敛速度和精度 17

四 结果分析 18

4,1 优势与创新 18

4.2 改进与缺陷分析 18

4.3 总结与展望 19

五 附录 20

5.1 相关程序 20

参考文献： 23

致谢 24

一.绪论

1.1研究目的和意义

遗传算法本身是我们通过自然界得出的一种智慧结晶，我们基于自然选择学、生物遗传学的观点，在一系列操作过后（编码、选择、交叉，变异）并构造相应选择、编码方法和制定相应算子（交叉算子、变异算子等等），结合实际问题，给定一定数量的城市个数N（城市个数对应遗传算法中的染色体个数）和城市之间的距离矩阵（不存在路径的用正无穷表示），在能够接受时间内，分析规划出一个（或多个）闭合的旅程，让每个城市经过且仅经过一次且旅行距离的总和最短（TSP问题）且要能够达到算法要求的精度，同时对选择的算法做出适当的分析和评估。

旅行商问题，作为遗传算法应用领域内的一个既经典又困难的问题；经典在于遗传算法在应用之初就涉及并应用到组合优化问题，而困难就困难在当种群数量足够大，迭代次数足够多的时候，就会导致整个无法题目解答出来，没法最终求得收敛后的最小路径，也就是我们所常说的NPC问题（在城市数量很大的情况下，计算会变得异常复杂，达到人类乃至高性能计算机无法解决的程度），所以诸如此类的NPC组合优化问题，一旦有大幅度减轻运算量的优秀算法都值得被推崇，常见的算法有枚举法、启发式算法、搜索算法。

在我们开始运算遗传算法时，需要事先人工确定和判断一串遗传参数，比如所熟知的种群初始数量、迭代次数、选择算子、选择概率、交叉算子、交叉概率、变异算子、变异概率、文章里又创新的加入了逆转进化机制和逆转算子，为了模拟实现生物的逆进化过程和解释自然中所谓的“返祖现象”，这些算子对我们极大地左右了遗传算法的效率和性能，在本文中，一方面，我们模拟了遗传算法的基本原理并对遗传算法的数学原理和机制加以深刻了解，另一方面，我们也借助matlab实例的实验对应证实了迭代次数和种群数目，以及新加入的遗传逆转机制算子对遗传算法的深刻影响,根据之前的科学家的各项试验和本次实验共同证明，较大数目的初始种群可以同时处理并解决更多种不同的解集情况，但会相应增加每次迭代的时间和复杂度，在算法效率较低时，一般取20~200；种群大小和染色体基因个数、染色体长度等往往决定了变异的概率，一般发生变异的情况很小，在0.001~0.1之间都较为合理，文中取的是常用值0.05，原因在于较高的变异概率虽然有增加子代个体种类多样性的优势，但同时是引起基因片段的不稳定因素，也同时要求我们在增加种群大小和染色体基因长度和个数的同时，适当减小选取的变异概率；交叉操作的频率受到交叉概率约束，交叉概率能够提高全局收敛的速率，所以交叉概率一般取值比较大，常常在0.4~0.9，本文为了尽可能早的实现收敛，把此概率定在了0.9；而进化迭代次数需要设定一个MAX值，本文为了体现出种群大小和迭代次数的相应关系，所以取到了一组数值不同的迭代值，仅仅是为了看出对应关系，常见的迭代次数在100~1000都比较合理，最大迭代次数MAXGEN视具体的问题具体分析，如果对于具体的问题而言，我们所设定并加以不断调整更新的参数很难再提高遗传算法的效率和全局收敛的速度，那么我们只能对基本算法的本身加以改进和修正，在本文中的改进方式便是调整了适应度的比例并加入了逆转进化机制。

关于遗传算法的一些数学原理的基础，常常要提到的是“模式定理”的概念，鉴于遗传算法执行过程中存在着太多的随机操作，我们就把染色体基因片段里的相似模板叫做一种模式，这种模式常常因为在某些固定的位置具有某一种对应的特征而在生物性状上表现出一种趋同性，我们在后文中的交叉操作中可以详细的看到并且加以认知，在此处不做详细说明。

相比于传统的优化，在求取符合运行要求的全局最优解时候，遗传算法作为搜索算法之一，已经成熟且具有良好的收敛性、极高鲁棒性和广泛适用性。作为启发式算法的一种基础算法，遗传算法在最初的领域就是组合优化领域，而里面最经典且应用最稳广泛的有三个：作业调度问题，背包问题，巡回旅行商问题，而巡回旅行商问题就是我们熟知的TSP问题。

遗传算法因结合了计算机科学和生物进化遗传学而具有广泛的应用领域，有良好的实际生活背景。本文通过遗传算法，先是为了加深对遗传算法的认识，采用Java简单模拟了全国34个省级行政区的基于基本单一遗传算法的巡回旅行商问题，之后创新的加入逆转进化机制，借助matlab软件进一步模拟生成全国34个省级行政区的TSP可视化图像，以期待对遗传算法下的组合优化问题获得更深一步的研究，以巡回旅行商问题为例，较好的借助基本遗传算法完成实现并模拟了TSP的整个流程，并且对遗传算法的缺陷进行了细致的分析与研究，最后对遗传算法的各种重要参数（如变异概率，交叉概率）进行了控制变量下的灵敏度分析，提出了基本遗传算法下的TSP算法的合理优化模型，对未来个人对遗传算法的深入研究起到了借鉴和积淀作用。

1.2 国内外研究现状

作为一种全局收敛优化的基础启发式算法之一，从90年代以来，遗传算法由于其作为最为成熟实用、高效率、好鲁棒性的算法之一，受到了越来越多的国内外学者的广泛关注。

遗传算法的提出起源于美国，由于年(美国知名学者教授，自然学算法大师)在他的专著《自然界和人工系统的适应性》中首先提出根据自然遗传仿生特性提出遗传算法，后来科学界普遍对这种借鉴生物界自然选择和自然遗传机制的随机化搜索算法表示认同。

遗传算法的特性即优中选优在迭代过程中不断更新着自己的最优值。初始对种群个数，迭代次数进行初始化，拥有三大参数（选择概率、交叉概率、变异概率）对遗传算法进行迭代进化与完善，本文中还加入了逆转进化机制，对这些父代个体进行交叉移植等一系列变化产生新一代的个体集合，不断更新此过程直到满足全局收敛为止。

早在20世纪40年代，生物的演化繁殖过程就成为许多生物学家研究的焦点问题，达尔文之后，孟德尔等许多生物学家展开了对生物遗传学的探究；1946年，第一台计算机的问世，也让生物遗传学的研究走向了智能化，50年以后，逐步实现了对生物遗传在计算机上的大致模拟；1963年，德国柏林技术大学的I.Rechenberg和H.PSchwefel在进行风洞试验时，生物进化策略思想初步产生；60年代，在设计有限态自动机的过程中，I.J,Fogel产生进化规划的伟大构想；随后由美国密歇根大学的J.H.Holland教授和他的学生J.D.Bagley相继提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究，开启了编码时代，同时也是编码技术兴盛的开端，同时他们还提出了 “遗传算法（Genetic Algorithms）”的概念，也是首次在公开学术论坛上遗传算法的出现，标志着遗传算法正式进入“科学技术舞台”； 70年代初，Holland在科学界提出了举足轻重的“模式定理”，如今这个定理被科学界普遍认为是“遗传算法的基本定理”，同时也是遗传算法研究的奠基之作；70年代中期，Holland出版了著名的“Adaptation in Natural and Artificial Systems” （《自然和人工系统下的适应度》），标志遗传算法的诞生。

80年代起，遗传算法被整个科学界重视起来，相继在美国召开了第一届遗传算法国际会议并成立国际遗传算法学会（ISGA）；80年代末，由Holland的学生D.J.Goldberg出版的“Genetic Algorithms in Search,Optimization,and Machine Learning”（在日常研究、组合优化和机器学习中遗传算法的应用）在Holland基础上进一步对遗传算法及其应用作了全面的系统的论述；几乎同时，由I.Davis编辑出版了《遗传算法手册》问世，通过遗传算法在工程技术和社会生活中大量的应用实例对人们在日常生产生活中使用遗传算法起到了积极的指导作用。

剩余内容已隐藏，请支付后下载全文，论文总字数：22395字