遗传,模拟退火,蚁群三个算法求解TSP地对比.doc

《遗传,模拟退火,蚁群三个算法求解TSP地对比.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与统计学院智能计算及应用课程设计设计题目：智能计算解决旅行商问题摘要本文以遗传算法、模拟退火、蚁群算法三个算法解决旅行商问题，将三个算法进行比较分析。目前这三个算法广泛应用于各个领域中，本文以31个城市为例，运用遗传算法、模拟退火、蚁群算法分别进行了计算，将他们的计算结果进行了比较分析。关键词:遗传算法模拟退火蚁群算法旅行商问题背景：遗传算法：20世纪60年代初，美国Michigan大学的JohnHolland教授开始研究自然和人工系统的自适应行为，在从事如何建立能学习的机器的研究过程中，受达尔文进化论的启发，逐渐

2、意识到为获得一个好的算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策略的群体的繁殖，从而提出了遗传算法的基本思想。  20世纪60年代中期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然进化思想的模拟进化算法则遭到怀疑与反对，但Holland及其指导的博士仍坚持这一领域的研究。Bagley发表了第一篇有关遗传算法应用的论文，并首先提出“遗传算法”这一术语，在其博士论文中采用双倍体编码，发展了复制、交叉、变异、显性、倒位等基因操作算子，并敏锐地察觉到防止早熟的机理，发展了自组织遗传算法的概念

3、。与此同时，Rosenberg在其博士论文中进行了单细胞生物群体的计算机仿真研究，对以后函数优化颇有启发，并发展了自适应交换策略，在遗传操作方面提出了许多独特的设想。Hollistien在其1971年发表的《计算机控制系统的人工遗传自适应方法》论文中首次将遗传算法应用于函数优化，并对优势基因控制、交叉、变异以及编码技术进行了深入的研究。  人们经过长期的研究，在20世纪}o年代初形成了遗传算法的基本框架。1975年Holland出版了经典著作“AdaptationinNatureandArtificialSystem"

4、,该书详细阐述了遗传算法的基本理论和方法，提出了著名的模式理论，为遗传算法奠定了数学基础。同年，DeJong发表了重要论文“AnAnalysisoftheBehav-norofaClassofGenetieAdaptiveSystem"，在论文中，他将Holland的模式理论与计算实验结合起来，并通过函数优化的应用深人研究，将选择、交叉、变异操作进一步完善和系统化，并提出了代沟等新的操作技术，所得出的许多结论至今仍具有普遍的指导意义。  进入20世纪80年代末期，随着计算机技术的发展，遗传算法的研究再次兴起。遗传算法以

5、其较强的解决问题的能力和广泛的适应性，深受众多领域研究人员的重视，遗传算法的理论研究和应用研究已成为十分热门的课题。自1985年起，遗传算法及其应用的国际会议每两年召开一次，并且在相关的人工智能会议和刊物上大多设有遗传算法的专题。模拟退火：模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体部粒子随温升变为无序状，能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，能减为最小。模拟退火算法(SimulatedAnnealing，SA)最早的思

6、想是由N.Metropolis[1]  等人于1953年提出。1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应

7、用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。蚁群算法：蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制

8、器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。算法原理：遗传算法：遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣