蚁群算法用于TSP的并行策略及模型_图文

1、 蚁群算法用于TSP的并行策略及模型作者:刘乃文, 刘方爱, LIU Nai-wen, LIU Fang-ai作者单位:山东师范大学,信息科学与工程学院,济南,250014刊名: 计算机应用研究英文刊名:APPLICATION RESEARCH OF COMPUTERS年,卷(期:2007,24(12被引用次数:1次参考文献(15条1.COLORNI A.DORIGO M.MANIEZZO V Distributed optimization by ant colonies 19912.DOGIGO M Optimization,learning and natural algorithms

2、19923.DORIGO M.MANIEZZO V.COLORNI A Ant system:optimization by a colony of cooperating agents 1996(014.GUTJAHR W J A generalized convergence result for the graph based ant system 2003(045.GUTJAHR W J A graph-based ant system and its convergence 2000(086.BLUM C.ROLI A Metaheuristics in combinatorial

3、optimization:overview and conceptual comparison 2003(038.CARO G D Swarm intelligence 20059.BULLNHEIMER B.KOTSIS G.STRAU C Parallelization strategies for the ant systemTR DOM 9-97 199710.DORIGO M.STUTZLE T Ant colony optimization 200311.段海滨蚁群算法及其在高性能电动仿真转台参数优化中的应用研究 200512.秦玲蚁群算法的改进与应用学位论文 200413.CHU

4、 S C.RODDICK J F.PAN J S Parallel ant colony systems 200314.段海滨蚁群算法原理及其应用 200515.GENDRON B Parallel computing in combinatorial optimization 2005相似文献(10条1.学位论文肇勇改进蚁群算法的理论及方法研究2004本文总结了国内外蚁群算法的研究成果,并提出了新的改进蚁群算法.蚁群算法在组合优化问题的成功应用,使得人们开始将焦点又集中在其在连续优化问题上的应用.目前国内外对于蚁群算法在连续优化问题的应用研究成果还很少,但初步研究已显示出蚁群算法较好的性能.

5、多极值全局优化问题是本文研究的重点,通过使用一种新的蚁群算法基于网格法的蚁群算法进行多个算例的测试,证明了该算法的性能较好.可以预见随着蚁群算法理论的不断完善,蚁群算法将越来越成功地用于连续优化问题.本文的主要研究内容及成果如下:(1对全局优化方法的基本框架和研究进展进行了系统的综述,分别从全局优化问题的特点,全局优化方法的构造原理和分类,以及现有全局优化方法的不足等几个方面进行了系统的阐述.(2针对近几年来发展较快的启发式搜索算法的理论和方法进行了系统的研究.详细研究了启发式搜索算法的产生、构造方法、基本类型等几个方面.并概述了几种元启发式算法:蚁群算法、模拟退火法、遗传算法、禁忌搜索法、混

6、沌优化算法等.(3详细系统的研究了蚁群算法的发展现状,对于各种改进蚁群算法的特点进行了分析和对比,在此基础之上提出了新的改进蚁群算法,并经过程序调试,其结果显示新的改进蚁群算法的有较好的性能.在研究用于组合优化问题的蚁群算法的基础上,详细地阐述了一种用于连续优化问题的蚁群算法基于网格的改进蚁群算法,通过测试多个算例发现该方法能够较好地解决一些多极值函数的优化问题.(4对广义邻域搜索算法及其统一结构进行了详细的阐述和分析,并提出了一种新的混合优化算法-ACOSA,即基于蚁群算法和模拟退火法的混合算法.对于ACOSA混合算法的结构和性能进行了分析,经过测试证明ACOSA混合算法优于单纯蚁群算法和模

7、拟退火法等元启发式算法.2.学位论文于沛欣一种混合蚁群算法在JSP问题中的应用研究2008随着市场竞争的日趋激烈,每个企业都在寻求更好的生产与运作管理方案,以提高企业的生产、经营和管理效率,从而提高企业的核心竞争优势。生产与运作管理的核心是车间调度问题能否高效地获得优化解,研究车间调度问题具有很大的理论意义和现实价值。车间调度问题是解决如何按时间的先后分配资源来完成不同的生产任务,使预定目标最优化的问题。作业车间调度-(JSP问题是许多实际车间调度问题的简化模型,是一个典型的NP一难问题。该问题具有约束性、非线性、不确定性、大规模性等复杂性,已被证明在多项式时间内得不到最优值。近年来,对于Jo

8、b-shop调度问题求解方式主要有启发式算法和元启发式算法,但各有其不足之处:元启发式方法的运行时间长,可获得较好的解,但其解不稳定;启发式方法可在较短的时间内得到鲁棒性较强的解,但是极少获得较优的解。为了更好地解决作业车间调度问题,将一些解决此类问题较好的算法组合起来。蚁群算法是通过信息素的累积和更新收敛于最优路径上,具有分布式并行全局搜索能力,但初期信息素匾乏,求解速度慢。禁忌搜索法(TabuSearch是一种通过邻域搜索以获取最优解的方法,能有效地加快解的收敛速度。本文根据蚁群算法的特点,对蚁群算法进行改进,并将禁忌搜索算法熔入到蚁群算法中,以改善蚁群算法的收敛速度。算法动态融合的思想是

9、首先应用改进的蚁群算法找到JSP问题的可行解,然后应用禁忌搜索在可行解的邻域找到更优的解。最后,本文对JSP问题应用实验仿真计算。结果表明,改进的蚁群算法与禁忌搜索结合后的混合蚁群算法的收敛速度更高,具有更好的全局收敛性能,能在更少的迭代次数达到全局最优解,具有更高的收敛速度。3.学位论文 王珊珊 基于混合蚁群算法的车辆可重复利用VRPTW问题的研究 2006 车辆路径问题(VRP是近年来交通运输、管理科学、运筹学、图论、网络分析等学科研究的热点问题之一，在现实中有着广泛的应用，例如公交线路 、物流配送、网络路由等等。研究此类问题具有很强的现实意义。本文着重研究带时间窗的车辆路径问题(VRPT

10、W。VRPTW是在基本VRP上添加时间窗约束 条件后的一种变化形式，是更为复杂和特殊的问题。VRPTW已被证明是NP-hard组合优化问题，当问题规模较大时，很难得到问题的精确解。如何设计有 效的算法，从而在较短的计算时间快速获得较好的解，成为现阶段研究的重点。 蚁群算法是受自然界中蚂蚁觅食行为的启发而发展起来的一种元启发式优化算法，是一种本质并行的算法，全局搜索能力强。蚂蚁之间通过信息交 流加速了进化过程，利用了正反馈原理和学习机制，具有较强的搜索较优解的能力。在基本蚁群算法的基础上，又逐渐发展出来许多新的改进算法，并 在二次分配(QAP、网络路由、车间调度(JSP、车辆路径(VRP等组合优

11、化问题的求解中取得了很好的效果。 本文基于蚁群算法对VRPTW问题进行系统研究。主要工作如下： 首先，介绍VRP问题的各种约束条件和分类标准。分析VRPTW问题的特性以及构造VRPTW问题的模型时须考虑的各种因素如目标函数、约束条件、变量 等等，给出VRPTW问题的数学模型。对求解VRPTW问题的精确算法、传统启发式算法和元启发式算法进行介绍。接下来介绍蚁群算法的基本原理、发展变 化以及在VRP领域的应用。 然后，基于对VRPTW问题的研究，结合物流配送中的实际情况，提出车辆可重复利用的VRPTW问题(VRPTWRV，建立相应的多目标数学规划模型。并在 蚁群系统(Ant ColonySyste

12、m的基础上，按照优先访问服务开始时间较早、服务所需时间较短以及关窗时间较早的客户的原则，设计相应的启发式因子 和蚂蚁的状态转移规则；结合最大最小蚂蚁系统(MMAS、基于排序的蚂蚁系统(ASRank的优点，并引入自适应机制，动态调整信息素的挥发系数，设计 相应的信息素更新策略，既加强对每次迭代最优解的利用，又避免过早陷入局优，从而兼顾算法的收敛速度和全局性。根据客户服务结束时间较早优先 的原则构造较好的初始解。使用候选表来加快搜索速度。在算法中加入局部搜索阶段，在所有蚂蚁都构造完解之后信息素全局更新之前，使用在求解 VRPTW问题上非常有效的几种局部搜索方法如2-opt*、or-opt、CROS

13、S-exchange等，并在or-opt中结合GENI-exchange算子的思想，来对蚂蚁构造的解进 行改进，将元启发式算法和局部搜索方法的优点结合起来，设计出求解VRPTWRV问题的混合蚁群算法(HACO-VRPTWRV。最后，进行大量的数据仿真实验。 研究在不同的参数组合下HACO-VRPTWRV算法性能的变化，确定较好的参数组合和取值范围。比较不同的初始解生成策略对算法性能的影响。研究解的多 样性。对比加入局部搜索过程前后算法的收敛速度和求得的解的质量，以及车辆可重复利用和不可重复利用下使用的车辆数和总运行时间、等待时间、 行驶时间等等。实验结果表明，本文所设计的算法是有效的，具有较快

14、的收敛速度，解的全局性也较好。 4.学位论文 罗旭辉 应用于TSP问题的蚁群优化算法参数研究 2007 基于自然的元启发式算法一直是人工智能领域中一个非常重要的研究课题，在以往的研究工作中，学者们提出了神经网络，模拟退火，遗传算法等 许多优秀的元启发式算法，并在解决各类问题时取得了良好的效果。而作为一种较新颖的启发式算法，蚁群算法自上个世纪九十年代初诞生以来，一直 受到研究人员的关注。蚁群算法在优化求解许多问题时都能够取得很好的效果，特别是在对一些离散问题求解时的表现尤其突出。 然而，时至今日蚁群算法还是存在一些内在的问题有待解决。和许多其他的启发式算法一样，蚁群算法的一个缺点在于，算法的优化

15、性能往往取决 于对于算法控制参数的取值，这些取值在以往的工作中往往是非常机械的，各个参数的取值也是独立的，如果取值不当，蚁群算法将容易陷入局部最优 ，并且优化性能也不理想。 本文对以TSP问题为优化对象的蚁群优化算法ACS进行参数研究，分析各个控制参数在优化过程中对算法的影响，以及某些参数之间的关系。从而制 定一种有效的参数预设规则，在保持算法优化性能的前提下，降低算法参数设置的复杂度。本文的工作主要可以分为四个部分，第一部分，回顾了一些 的经典的蚁群算法的优化性能及其应用领域，同时研究了它们参数设置的规则。第二部分，描述ACS算法，研究收敛状态变化对优化性能的影响。第三部 分，通过分析算法优

16、化原理，研究算法各个参数在迭代过程中对路径构建的作用，选取具体的预设参数。第四部分，进行ACS算法的仿真试验，研究参数 对优化过程的影响，以及参数之间的关系，制定一种有效的参数预设规则。本文的研究工作表明，参数预设规则应用于不同的TSP问题实例时都能取得较 好的效果，并且对蚁群算法的参数研究具有很高的发展价值。 5.学位论文 孙海鹰 蚁群算法的理论与性能研究 2009 蚁群优化算法是一种新型的求解复杂优化问题的元启发式算法，它是由意大利学者M.Dorigo等人受到自然界中真实蚁群集体行为的灵感而首先提出 来的，并用来解决离散优化问题。由于蚁群算法具有稳健性、全局性、普遍性、分布式计算等优点，其

17、理论研究不断深入，应用领域不断扩大。大量实 验结果表明，它在解决许多组合优化问题时都能表现出较好的求解能力，经过了众多国内外学者不断地对其进行扩展和改进，蚁群算法正经历着一个不 断发展和完善的过程。 虽然通过对大量应用问题的求解，已经显示出蚁群优化算法的高效性，但它的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够 成功地解决这些问题。它能否保证所得到的解一定是全局最优解，还有什么问题利用蚁群算法不能解决，对于能够解决的问题，它的时间复杂性到底有 多大。因此有必要研究蚁群优化算法的欺骗性问题。由于蚁群算法具有本质上的并行特性，我们需要研究如何高效率地对它进行并行化，如何平衡通信 开

18、销与加速比之间的关系。蚁群算法的一个主要缺点是不能直接解决连续优化问题。以往解决此类问题的方案，大部分改变了蚁群优化算法的基本结构 ，不能充分发挥蚁群优化算法的正反馈机制的优势。因此有必要研究在解决连续优化问题时该如何保持本质模型的不变，如何充分利用信息素和启发式 信息，保证解的精确性的同时能加速收敛速度。 本文针对蚁群算法的上述问题，作了下面的研究。 (1研究蚁群算法求解欺骗性问题时的收敛性和时间复杂度。以n-bit陷阱问题为例，证明了蚁群算法一阶欺骗性问题在一定的信息素初始值条件下 ，不满足解的收敛性，但满足值的收敛性。我们证明了，使用信息素带限的蚁群算法MMAS求解n-bit陷阱问题达到

19、最优解的时间复杂度为 O(n2m.logn，这里n为问题的规模，m为蚂蚁的个数。同时，我们的实验结果也验证了上述结论的正确性。 (2提出了一种MPP上的自适应的并行蚁群算法PACO。该算法在两个方面进行了重要改进来加强算法的性能。一方面，我们提出一种处理机之间的信 息交流策略，使得每个处理机可自适应地选择另外一个处理机来交流信息并更新信息素。另一方面，我们还提出一种根据解的多样性来自适应地调节信 息交流周期的方法，以在加强优化能力的同时避免早熟收敛，以增加解的多样性。我们对并行蚁群算法PACO值的收敛性进行了分析与证明。我们用标准 的旅行商问题在大规模并行机上做了测试，实验结果表明，我们算法在

20、收敛速度，加速比，稳定性和准确性各方面都要优于别的并行蚁群算法。 (3提出了一种用蚁群算法求解连续空间优化问题的方法。该方法保持了基本蚁群算法的基本框架，将传统蚁群算法中蚂蚁由解分量的信息素和启发 式的乘积值按比例来决定取值概率的方式，改为根据连续的概率分布函数来取值。我们还将函数在各个维上的极值点方向作为蚂蚁搜索的启发式信息。 在标准测试函数上的试验结果显示，我们的算法与其他类似的算法相比，不但具有较快的收敛速度，而且能够有效地提高解的精确性，增强了算法的稳 定性。 6.学位论文 陈佑健 蚁群算法的研究及在网络路由优化上的应用 2005 蚁群算法是一种新型的用于求解组合优化或函数优化问题的元

21、启发式算法,其基本思想是借用生物界的蚂蚁群体觅食机理,将每个蚂蚁看作一个智能 体,作为智能群体的蚁群,其觅食过程显现出高度的并行性、正反馈性和鲁棒性,以此为基础的蚁群算法也具有这样一些特点.因此,蚁群算法的研究无论从 理论上还是实用上,都具有较高的价值.本文首先分析了蚁群算法的原理与模型,介绍了算法的特点和研究现状,通过实验分析了算法中几个关键参数的选 择.针对基本蚁群算法的主要缺陷,如收敛速度慢和易于陷入局部最优等问题,将用于求解组合优化问题的基本蚁群算法进行了改进.首先,在概率选择上采 用了确定性与随机性相结合的选择原则;其次,由于基本蚁群算法初期时各条路径上的信息素数量相同,导致算法的初

22、期求解速度缓慢,因此提出了分区搜 索的思想,使各条路径上的信息素在初期有所差别,加速算法的收敛;第三,结合局部与全局信息素调整策略对路径上的信息素进行动态更新;第四,对与信 息素相关的一些参数进行了自适应改变;最后,引入遗传算法中的变异思想,以扩大解的搜索空间.针对蚁群算法在求解连续优化问题上相对较弱的特点,提 出了基于网格划分的蚁群算法,将传统的用于求解离散空间优化问题的蚁群算法进行了扩展.在应用研究上,分析了网络路由优化问题,研究了基于蚁群算 法的IP网络QoS单播路由;讨论了基于蚁群算法的一些其它应用.通过算例对所提出的改进的蚁群算法进行了仿真验证,实验结果表明,本文提出的改进算法 是有

23、效和可行的;在连续函数优化上和基于蚁群算法的网络路由优化等应用上也进行了实验仿真.本课题旨在为推进蚁群算法的理论研究和应用研究起到 一定的作用. 7.学位论文 高磊 基于蚁群算法的带能力约束的车辆路径问题研究 2007 车辆路径问题(Vehicle Routing Problem，VRP是近年来交通运输、管理科学、运筹学、图论、网络分析等学科研究的热点问题之一，在现实中有 着广泛的应用，例如公交线路、物流配送、网络路由等等。研究此类问题具有很强的现实意义。本文着重研究带能力约束的车辆路径问题 (Capabilityconstrained Vehicle Routing Problem，CVRP

24、，CVRP是在基本VRP上添加能力约束条件后的一种变化形式，是更为复杂和特殊的问题。 VRP已被证明是NPhard组合优化问题，当问题规模较大时，很难得到问题的精确解。如何设计有效的算法，从而在较短的计算时间快速获得较好的解 ，成为现阶段研究的重点。 蚁群算法是受自然界中蚂蚁觅食行为的启发而发展起来的一种元启发式优化算法，是一种本质并行的算法，全局搜索能力强。蚂蚁之间通过信息交 流加速了进化过程，利用了正反馈原理和学习机制，具有较强的搜索能力，近年来改进蚁群算法在在二次分配(QAP、网络路由、车间调度(JSP、车辆 路径(VRP等组合优化问题得到广泛应用。 本文基于蚁群算法对车辆路径问题进行系

25、统研究，主要工作如下： 首先，介绍VRP问题国内外研究现状，在对VRP问题从构成要素、分类和界定几个方面做概述的基础上，深入探讨了VRP问题的理论框架：包括从 TSP问题到VRP问题的描述及模型建立，并对求解VRP问题的精确算法、传统启发式算法和元启发式算法进行分析和总结。 然后，介绍蚁群算法的基本原理，分析归纳蚁群算法的主要特点，并对蚁群算法近年来的发展变化做简要总结，最后对蚁群算法在组合优化领域的 应用情况，尤其在VRP问题上的应用情况进行概述。 最后，基于对VRP问题的研究，结合物流配送中的实际情况，建立带能力约束车辆路径问题(CVRP数学规划模型。并在基本蚁群算法(Ant Algori

26、thm的基础上，设计出求解CVRP问题的简易蚁群算法(BA和三个逐步改进的蚁群算法(AA1，AA2，AA3，经过编程调试和反复实验仿真，上述算法 在求解中小规模CVRP问题上效果令人满意，在较大规模的CVRP问题的快速求解上获得成功，实验结果表明，本文所设计的算法是有效的，具有较快的收 敛速度，解的全局性也较好。 8.学位论文 吴圣宁 嵌入式处理器编译器关键技术研究 2007 嵌入式系统通常对性能、实时性、功耗等有着严格的要求，需要非常高效的机器代码。因此，嵌入式软件开发常采用汇编语言。但汇编语言编程费 时、调试困难，而且代码难以移植。嵌入式系统的广泛应用和嵌入式软件规模的不断扩大，决定了用高

27、级语言代替汇编语言进行嵌入式软件开发是必然 趋势。但使用高级语言编译器生成代码的质量和手工编写的汇编代码相比还有很大差距，不能满足嵌入式系统的要求。因此，嵌入式处理器编译技术研 究有着非常重要的现实意义。 传统编译技术通常不能直接适用于嵌入式领域，需要进行扩展或者设计全新的算法。传统的编译技术一般基于规则的机器模型，并采用简单启发式 方法以达到较快的编译速度。嵌入式处理器一般具有不规则的体系结构特征，且在嵌入式环境中，编译器生成高质量代码的重要性高于编译时间。 本文主要研究了嵌入式处理器编译技术的三个问题：嵌入式处理器寄存器分配、多媒体扩展指令集的代码生成、双指令集处理器多目标代码选择。 在传

28、统图着色寄存器分配方法中，假设机器模型具有简单的寄存器文件。这些算法采用“degreek”测试冲突图结点是否局部可着色，并通过特殊 的技巧对此扩展，以适用于不规则的寄存器文件特征。经过多年研究，此问题取得了很大进展。但是，传统图着色寄存器分配算法在进行冲突图结点局 部可着色测试时，无法知道邻居结点所分配的颜色，只能采取保守的估算，因而降低了编译生成的代码质量。这是它们难以克服的困难。 传统树模式匹配和动态规划技术不能有效利用多媒体处理器的指令集并行，基于传统并行编译技术的扩展一般局限于循环级并行，且没有全局优化 标量指令和SIMD指令的使用。 传统编译技术一般仅优化单一的目标，例如性能、功耗。

29、嵌入式系统常需同时优化多个目标。单一目标的优化对其它目标有何影响，如何在多个目 标间权衡，需要进一步研究。 嵌入式系统的复杂性决定了需要采用新的方法学来研究嵌入式编译技术。从元启发式算法以及编译器前后端有机结合这两个角度来研究嵌入式编译 技术是本文工作的重要思想。 近二十年来，元启发式(Meta-heuristics算法得到广泛研究。这些算法来自于人们从自然界得到的启发，通过模拟物理过程、生物进化等自然现象 ，能够克服经典优化算法的局限性，系统地搜索问题的解空间，较好地解决多种优化问题。编译技术中同样存在各种优化问题，尤其在嵌入式环境中 ，这些问题更加复杂，常使得传统编译技术不能简单地适用。元

30、启发式算法为求解复杂的编译优化问题提供了广阔空间。 程序分析是编译优化的基础。可以把编译器前端程序分析的优势和编译器后端的机器相关信息结合起来，以适应复杂的嵌入式环境下编译技术研究 的需要。 本文主要研究成果和创新包括以下几个方面： 1.针对嵌入式处理器不规则寄存器文件体系结构特征，本文提出了一种新的图着色寄存器分配混合演化算法HMAGRA，突破了传统图着色寄存器分 配算法在寄存器冲突图结点局部可着色测试问题上难以克服的障碍，为实现嵌入式处理器寄存器分配器提供了新途径。本文的HMA-GRA算法主要由遗传算 法和禁忌搜索算法构成，利用Chaitin算法作为前端对冲突图进行预处理，对剩余冲突图中各

31、结点按照其类型随机分配颜色，计算结点间的冲突数量，通 过演化过程逐渐减少图的总体冲突，最终实现图成功着色。此算法不仅可以精确计算冲突图结点是否局部可着色，而且能够用规范的寄存器分配模型代 替传统算法中的特殊技巧，以适应嵌入式处理器寄存器文件不规则特征带来的复杂性。 2.面向多媒体指令集，本文提出了一种新的SIMD代码生成算法ICGME。ICG-ME算法扩展了传统的树模式匹配和动态规划技术，通过修改代码生成器 的产生器iburg工具为数据流树结点的每个目标非终结符保留多个匹配规则，以识别构造SIMD指令的并行操作；在编译器前端对存储操作相对于向量寄存 器的对齐状况进行数据流分析，并把分析结果传递

32、给编译器后端，以辅助构造SIMD和数据重组指令；最终生成多媒体向量指令和非多媒体标量指令混合 的汇编代码。通过结合编译器前端程序分析的优势和编译器后端的机器信息，ICGME算法不仅简化了SIMD代码的生成，而且能够同时利用SIMD指令和非 SIMD指令，以生成高质量的机器代码。 3.以ARMThumb双指令集处理器为例，本文提出了用元启发式算法求解编译技术中多目标优化问题的方法学。本文把双指令集处理器代码选择问题 表示为权衡程序代码大小和运行时间的多目标优化问题，利用程序profiling技术为其建立数学模型，通过一种多目标蚁群算法结合子集选择的方法求解 此问题。 4.基于SuIFMachineSUIF编译器研究框架，我们进一步完善了代码选择、寄存器分