《遗传_模拟退火_蚁群三个算法求解TSP的对比》由会员分享，可在线阅读，更多相关《遗传_模拟退火_蚁群三个算法求解TSP的对比（25页珍藏版）》请在金锄头文库上搜索。
1、 数学与统计学院智能计算及应用课程设计设计题目：智能计算解决旅行商问题摘要本文以遗传算法、模拟退火、蚁群算法三个算法解决旅行商问题，将三个算法进展比拟分析。目前这三个算法广泛应用于各个领域中，本文以31个城市为例，运用遗传算法、模拟退火、蚁群算法分别进展了计算，将他们的计算结果进展了比拟分析。关键词: 遗传算法 模拟退火 蚁群算法 旅行商问题背景：遗传算法：20世纪60年代初，美国Michigan大学的John Holland教授开场研究自然和人工系统的自适应行为，在从事如何建立能学习的机器的研究过程中，受达尔文进化论的启发，逐渐意识到为获得一个好的算法仅靠单个策略建立和改良是不够的，还要依赖
2、于一个包含许多候选策略的群体的繁殖，从而提出了遗传算法的根本思想。 20世纪60年代中期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然进化思想的模拟进化算法那么遭到疑心与反对，但Holland及其指导的博士仍坚持这一领域的研究。Bagley发表了第一篇有关遗传算法应用的论文，并首先提出“遗传算法这一术语，在其博士论文中采用双倍体编码，开展了复制、穿插、变异、显性、倒位等基因操作算子，并敏锐地发觉到防止早熟的机理，开展了自组织遗传算法的概念。与此同时，Rosenberg在其博士论文中进展了单细胞生物群体的计算机仿真研究，对以后函数优化颇有启发，并开展了自适应交换策略，在遗传操作方
3、面提出了许多独特的设想。Hollistien在其1971年发表的计算机控制系统的人工遗传自适应方法论文中首次将遗传算法应用于函数优化，并对优势基因控制、穿插、变异以及编码技术进展了深入的研究。人们经过长期的研究，在20世纪o年代初形成了遗传算法的根本框架。1975年Holland出版了经典著作“Adaptation in Nature and Artificial System,该书详细阐述了遗传算法的根本理论和方法，提出了著名的模式理论，为遗传算法奠定了数学根底。同年，DeJong发表了重要论文“An Analysis of the Behav-nor of a Class of Genet
4、ie Adaptive System，在论文中，他将Holland的模式理论与计算实验结合起来，并通过函数优化的应用深人研究，将选择、穿插、变异操作进一步完善和系统化，并提出了代沟等新的操作技术，所得出的许多结论至今仍具有普遍的指导意义。 进入20世纪80年代末期，随着计算机技术的开展，遗传算法的研究再次兴起。遗传算法以其较强的解决问题的能力和广泛的适应性，深受众多领域研究人员的重视，遗传算法的理论研究和应用研究已成为十分热门的课题。自1985年起，遗传算法及其应用的国际会议每两年召开一次，并且在相关的人工智能会议和刊物上大多设有遗传算法的专题。模拟退火：模拟退火算法来源于固体退火原理，是一种
5、基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体部粒子随温升变为无序状，能增大，而徐徐冷却时粒子渐趋有序，在每个温度都到达平衡态，最后在常温时到达基态，能减为最小。模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis1等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中
6、随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效防止陷入局部极小并最终趋于全局最优的串行结构的优化算法。蚁群算法：蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物
7、过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究说明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进展了比拟，数值仿真结果说明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。算法原理：遗传算法：遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题遗传过程的解，一代又一代地优化，并逼近最优解。遗传操作包括以下三个根本遗传算子(genetic operator
8、):选择(selection)；穿插(crossover)；变异(mutation)。这三个遗传算子有如下特点：个体遗传算子的操作都是在随机扰动情况下进展的。因此，群体中个体向最优解迁移的规那么是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进展的高效有向的搜索而不是如一般随机搜索方法所进展的无向搜索。遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接
9、遗传到下一代或通过配对穿插产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估根底上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。其中轮盘赌选择法 roulette wheel selection是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，那么i 被选择的概率，为遗传算法显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进展多轮选择。每一轮产生一个0，1
10、之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的穿插操作。在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的穿插算子。所谓穿插是指把两个父代个体的局部结构加以替换重组而生成新个体的操作。通过穿插，遗传算法的搜索能力得以飞跃提高。穿插算子根据穿插率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：实值重组离散重组,中间重组,线性重组,扩展线性重组。二进制穿插单点穿插,多点穿插,均匀穿插,洗牌穿插,缩小代理穿插。最常
11、用的穿插算子为单点穿插。具体操作是:在个体串中随机设定一个穿插点，实行穿插时，该点前或后的两个个体的局部结构进展互换，并生成两个新个体。下面给出了单点穿插的一个例子：个体A：1 0 0 1 1 1 1 1 0 0 1 0 0 0 新个体个体B：0 0 1 1 0 0 0 0 0 1 1 1 1 1 新个体变异算子的根本容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：a)实值变异b)二进制变异。一般来说，变异算子操作的根本步骤如下：a)对群中所有个体以事先设定的变异概率判断是否进展变异b)对进展变异的个体随机选择变异位进展变异。遗传算法引入变异的目
12、的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过穿插算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否那么接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。遗传算法中，穿插算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过穿插和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠穿插不能摆脱时，通过变异操作可有助于这种摆脱。
13、所谓相互竞争，是指当通过穿插已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用穿插和变异操作，是目前遗传算法的一个重要研究容。模拟退火：模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体部粒子随温升变为无序状，能增大，而徐徐冷却时粒子渐趋有序，在每个温度都到达平衡态，最后在常温时到达基态，能减为最小。根据Metropolis准那么，粒子在温度T时趋于平衡的概率为e(-E/(kT)，其中E为温度T时的能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的
14、模拟退火算法：由初始解i和控制参数初值t开场，对当前解重复“产生新解计算目标函数差承受或舍弃的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。模拟退火算法可以分解为解空间、目标函数和初始解三局部。模拟退火的根本思想:(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2) 对k=1，L做第(3)至第6步：(3) 产生新解S(4) 计算增量t=C(S)-C(S
15、)，其中C(S)为评价函数，(5) 假设t0，然后转第2步。模拟退火算法新解的产生和承受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和承受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或局部元素进展置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换局部产生，所以目标函数差的计算最好按增量计算。事实说明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被承受,判断的依据是一个承受准那么，最常用的承受准那么是Metropolis准那么: 假设t0那么承受S作为新的当前解S，否那么以概率exp(-t/T)承受S作为新的当前解S。第四步是当新解被确定承受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换局部予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此根底上开场下
