《（人工智能）群智能是近年来人工智能研究的一个热点话题蚁群算法作.》由会员分享，可在线阅读，更多相关《（人工智能）群智能是近年来人工智能研究的一个热点话题蚁群算法作.（29页珍藏版）》请在金锄头文库上搜索。
1、（人工智能）群智能是近 年来人工智能研究的一个 热点话题蚁群算法作 摘要 群智能是近年来人工智能研究的一个热点话题。蚁群算法作为群智能算法 的一个热点，是意大利学者 M.Dorigo 通过模拟蚁群觅食行为提出的。本文首 先介绍了群智能，然后详细介绍蚁群算法原理及其优缺点。接着依据大量实验 对参数 m、Q 的选择进行研究，得出其选择规律，并在以前学者 “三步走”的基础上提出了一种“四步走”的有效方法来选择蚁群算法最优组 合参数，然后对蚁群改进算法进行分析，同时以实验的方式对这几种算法各自 求解 TSP 问题的性能进行了对比分析，得出性能结果排名，并发现当 TSP 问题 最优解相同时还可以依据其他
2、性能（迭代次数、迭代时间等）得出最优结果， 最后还对陈烨的“蚁群算法实验室”的可视化编程进行了优化和改进，使之能 够更方便的用于几种算法性能比较和同种算法不同参数的比较。 【关键词】群智能；蚁群算法；参数选择；TSP；可视化 ExperimentalAnalysisandParameterSelectionforthe AntColonyOptimizationAlgorithm XuHui Abstract： Swarmintelligencehasbeenahotspotinthefieldofartificialintelligencein recentyears.Amongthealg
3、orithmsofswarmintelligence,antcolonyalgorith mwaspresentedbyanItalyscholarM.Dorigolearningfromthebehaviorsimula tingantcolonyforaging.Firstly,thispaperhasintroducedthegroupintelligenc eandpromotedtheantcolonyalgorithm,obtainedthechoiceregularof“m, ,Q”basingontheexperiment,andproposedaneffectivemetho
4、dnamed“ foursteps”inthefundationofothersscholars “threesteps”tochoosethem ostsuperiorcombinationparameterofantgroupalgorithm,thenanaliedthesi xkindsimprovedalgorithmofantcolonyantcolonyalgorithm,atthesametime explainedtheabilityofseveralkindsofantalgorithmtosolvetheTSPquestiona ccordingtotheexperime
5、nts;obtainedthemostsuperiorresultaccordingtoot herperformance(iterativenumberoftimes,iterativetimeandsoon)whenthe mostsuperiorresultofTSPquestionoptimalsolutionissame.Finally,thispaper alsohascarriedontheoptimizationandtheimprovementtothevisibleprogra mmingofChenYes“antcolonyalgorithmlaboratory”toen
6、ableitmoreco nvenienttouseinseveralalgorithmsperformancecomparisonandthecompar isonofdifferentparameterandhomogeneousalgorithm. Keywords： Swarmintelligence;Antcolonyalgorithm;ParameterSelection;TSP;Visua lization 目录 1 绪论 1 1.1 引言 1 1.2 群智能 1 1.3 蚁群算法的提出 2 1.4 本文研究工作 2 2 蚁群算法概述 4 2.1 蚁群算法基本原理 4 2.2 蚁
7、群算法的优点与不足 5 2.3 本章小结 6 3 蚁群算法的参数设置研究 7 3.1 硬件/软件环境平台 7 3.2 蚂蚁数目对基本蚁群算法的影响 7 3.3 信息启发式因子和期望值启发式因子 9 3.4 信息素残留系数 10 3.5 总信息量 11 3.6 本章小结 12 4 蚁群算法实验分析 13 4.1 改进的蚁群优化算法 13 4.1.1 最优解保留策略蚂蚁系统 13 4.1.2 蚁群系统 13 4.1.3 最大-最小蚂蚁系统 13 4.1.4 基于排序的蚂蚁系统 14 4.1.5 The Best-Worst Ant System14 4. 2 实验仿真及算法性能比较分析 15 4.
8、2.1 硬件/软件环境平台 15 4.2.2 重要参数设置 15 4.2.3 实验结果 15 4.3 本章小结 17 5 可视化编程 18 5.1 “蚁群算法实验室”的优点与不足 18 5.2 最大最小蚁群算法的图形化演示的改进 18 5.3 本章小结 22 6 结论与展望 23 参考文献 24 致 谢 25 附 录 26 1 绪论 自蚁群算法提出以来,就引起了国内外学者的广泛关注，提出了很多改进算 法。参数的设置直接影响到算法的性能，所以对参数设置的研究越来越重要， 而目前对它的研究大多还处于实验分析阶段。 1.1 引言 随着人们对生命本质的不断了解，生命科学也以前所未有的速度迅猛发展， 使
9、人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算 途径。在这种背景下，社会性动物的自组织行为引起了人们的广泛关注，许多 学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的 “群智能” 。 受蚂蚁总能找到一条从蚁巢到食物源的最短路径的启发，意大利学者 M.Dorigo 与 20 世纪 90 年代提出了一种新型的智能优化算法蚁群优化算法 （AntColonyOptimization，ACO）1。在不长的时间里，蚁群算法得到了不 断发展和完善，而且被用于解决大多数优化问题或者能够转化为优化求解的问 题，现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、
10、 电信 QoS 管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持 以及仿真和系统辩识等方面。 1.2 群智能 群智能指的是“无智能的主体通过合作表现出智能行为的特性”2，是一种 基于生物群体行为规律的计算技术。它受社会昆虫，例如蚂蚁、蜜蜂和群居脊 椎动物，又如鸟群、鱼群和兽群等的启发，解决分布式问题。它在没有集中控 制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了 一种新的思路。 有些专家在研究自然界的生物群体系统时，惊奇地发现社会昆虫和群居的 脊椎动物能发现新的食物源、在群体内部产生劳动分工，建筑庞大复杂的巢穴、 跨越几千公里迁徙到指定地区和在狭窄的空间内协调
11、调度等。这些社会性动物 的自组织行为引起了人们广泛的关注，许多学者对这种行为进行数学建模并用 计算机对其进行仿真，发现群智能有如下特点和优点2： (1)群体中相互合作的个体是分布的(Distributed)，这样更能够适应当前网 络环境下的工作状态。 (2)没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于 某一个或者某几个个体的故障而影响整个问题的求解。 (3)可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的 系统具有更好的可扩充性(Scalability)。 (4)由于系统中个体的增加而增加的系统通信开销在这里是十分小的，系统 中每个个体的能力十分简单，这
12、样每个个体的执行时间比较短，并且实现也比 较简单，具有简单性(Simplicity)。 1.3 蚁群算法的提出 目前，群智能理论研究领域包括两种主要算法：蚁群算法 (AntColonyOptimization，简记 ACO)和粒子群算法 (ParticleSwarmOptimization，简记 PSO)。而以蚁群算法为代表的群体智能已 成为当今分布式人工智能研究的一个热点，它是由意大利学者 M.Dorigo、V.Maniez-zo、A.Colorini3,4,5等人从生物进化机制中受到启发， 通过模拟自然界蚂蚁搜索路径的行为后，于 1991 年首先提出的，也叫蚂蚁系统 （AntSystem，
13、AS） 。M.Dorigo 等人充分利用蚁群搜索食物的过程与著名的旅 行商问题（TravelingSalesmanProblem）之间的相似性，吸收了蚂蚁的行为 特征，设计虚拟的“蚂蚁”摸索不同的路线，并留下会随时间逐渐消失的虚拟 “信息量”2。虚拟的“信息量”会挥发，当蚂蚁每次随机选择要走的路径时， 倾向于选择信息量比较浓的路径。根据“信息量浓度更近”的原则，既可选择 出最佳路线。 虽然蚁群算法的研究时间不长，但初步研究已显示它在求解复杂优化问题 方面具有很大优势，特别是 1998 年在比利时布鲁塞尔专门召开了第一届蚂蚁优 化国际研讨会后，现在每两年召开一次这样的蚂蚁优化国际研讨会。这标志着
14、 蚁群算法的研究已经得到国际上的广泛支持，使得这种新兴的智能进化仿生算 法展现出了勃勃生机6。 1.4 本文研究工作 本文围绕蚁群算法的原理、改进及其应用展开研究，全文共分六章，各章 内容安排如下： 第一章：绪论 本章首先对群智能进行介绍，然后阐述蚁群算法产生的背景。 第二章：蚁群算法概述 本章详细介绍蚁群算法原理及其优缺点。 第三章：蚁群算法的参数设置研究 本章针对参数设置进行大量实验，并对实验结果做出研究分析，得出参数 m，Q 的选择规律，在此基础上，提出新的有效方法对蚁群算法最优 组合参数进行选择。 第四章：蚁群算法实验分析 本章分析几种改进的蚁群算法，并采用国际上通用的测试问题库 TS
15、PLIB 中 的对称 TSP 问题作为测试对象，通过仿真试验对六种算法各自求解 TSP 问题的 性能进行比较，得出当 TSP 问题最优解相同时，可依据其他性能（迭代次数、 迭代时间等）得出 TSP 问题的最优结果。 第五章：可视化编程 针对陈烨的“蚁群算法实验室”进行优化和改进。 第六章：结论与展望 总结本文工作，提出展望。 2 蚁群算法概述 下面详细介绍蚁群算法原理及其优缺点。 2.1 蚁群算法基本原理 现实生活中单个蚂蚁的能力和智力非常简单，但他们能通过相互协调、分 工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其以蚂蚁总能找 到一条从蚁巢到食物源的最短路径而令人惊叹。 根据仿生学
16、家的长期研究发现：蚂蚁虽没有知觉，但运动时会通过在路径 上释放出一种特殊的分泌物-信息素来寻找路径。蚂蚁个体之间就是利用信息素 作为介质来相互交流、合作的。某条路上经过的蚂蚁越多，信息素的强度就会 越大，而蚂蚁能感知路上信息素的存在和强度，它们倾向于选择外激素强度大 的方向，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过 这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强， 这样就会有更多的蚂蚁选择此路径，这条路径上的外激素就会越来越强，选择 此路径的蚂蚁也越来越多。直到最后，几乎所有的蚂蚁都选择这条最短的路径。 蚁群算法可以表述如下：在算法的初始时刻，将 m 只蚂蚁随机地放到 n 座 城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此 时各路径上的信息素量相等，设 ij(0)=C（C 为一较小的常数） ，接下来，每只 蚂蚁根据路径上残留的信息素量和启发式信息（两城市间的距离）独立地选择 下一座城市，在时刻 t，蚂蚁 k 从城市 i 转移
