应用蚁群算法静态组合优化问题

《应用蚁群算法静态组合优化问题》由会员分享，可在线阅读，更多相关《应用蚁群算法静态组合优化问题（14页珍藏版）》请在金锄头文库上搜索。

1、应用蚁群算法静态组合优化问题 添加时间: 2011-9-10 10:13:37 来源: 作者: 点击数:94 应用蚁群元启发式的静态组合优化问题是相对简单，一旦确定了映射的问题，让增量建设一个解决方案，社区结构，和一个随机状态转换模块将当地用来引导建设性的程序。1 程序 元启发式蚁群（ ） 2 当（终止标准不满意） 3 日程活动 4 蚂蚁代和活动（ ） ; 5 素蒸发（ ） ; 6 daemon 在行动（ ） ; 自选 7 结束日程活动 8 结束，当 9 结束程序 10 程序 蚂蚁代和活动（ ） 11 当（可用资源） 12 日程设立一个新的蚂蚁（ ） ; 13 新的积极的蚂蚁（ ） ; 14

2、结束当 15 结束程序16 程序 新的积极蚂蚁（ ）蚂蚁生命周期 17 初始化蚂蚁（ ） ; 18 M=更新蚂蚁内存（ ） ; 19 当（目前的状态目标状态） 20 A=读 当地蚂蚁路由表（ ） ; 21 P =计算 转移概率（A;M;问题的限制） ; 22 下一状态=适用蚂蚁决定政策（P;问题的限制） ;23 转移到下一状态（下一状态） ; 24 如果（在线步信息素更新） 25 存款信息素的访问弧（ ） ; 26 更新蚂蚁路由表（ ） ; 27 结束 如果28 M=更新内部状态（ ） ; 29 结束当30 如果（在线延误信息素更新） 31 评价的解决方案（ ） ; 32 存款信息素的所有访问

3、弧（ ） ; 33 更新蚂蚁路由表（ ） ; 34 结束如果35 模具（ ） ; 36 结束 程序图 3 该蚁群元启发式的伪代码。评论包含在括号内。所有程序在第一级压痕在声明中同时并行的执行。守护进程的程序的行动（ ）在第六行是可选的，并指集中行动执行了守护拥有全球知识。目标国（第 19 ）是指一个完整的解决方案建造的蚂蚁。在一步一步和延迟信息素更新程序行 24-27 和 30-34 往往是相互排他性。当他们两人都缺席的信息素是所存放的守护进程。表 1 名单中的应用蚁群算法静态组合优化问题。应用及分类按时间顺序排列。问题名称作者年份主要参照算法名称旅行商Dorigo,Maniezzo&Colo

4、rni199133, 40, 41ASGambardella & Dorigo199549Ant-QDorigo & Gambardella199637, 38, 50ACS& ACS-3-optManiezzo & Colorni199797, 98MMASManiezzo 199712ASrank二次分配Maniezzo,Colorni& origo199477AS-QAPGambardella,Taillard& Dorigo199753, 54HAS-QAPaSt utzle & Hoos199899MMAS-QAPManiezzo & Colorni199876AS-QAPbMani

5、ezzo199875ANTS-QAPJob-shop 调度Colorni,Dorigo& aniezzo199420AS-JSP车辆路径Bullnheimer, Hartl & Strauss199615, 11, 13AS-VRP Gambardella,Taillard&Agazzi199952HAS-VRP顺序排序Gambardella & Dorigo199751HAS-SOP图着色Costa & Hertz199722ANTCOL最短的共同超序列Michel & Middendorf199878, 79AS-SCSa HAS-QAP 是一种蚂蚁算法不遵循所有方面的蚁群元启发式b 这是

6、一个变异的原始 AS-QAP.表 2 名单中的应用蚁群算法，动态组合优化问题。分类的申请，并排列顺序。问题名称作者年份主要参照算法名称面向连接的网络路由 Schoonderwoerd, Holland, Bruten & Rothkrantz199690, 89ABCWhite, Pagurek & Oppacher1998105ASGADi Caro & Dorigo199831AntNet-FSBonabeau, Henaux, Gu erin, Snyers, Kuntz& Th eraulaz19986ABC-smart ants连接不到网络路由Di Caro & Dorigo1997

7、26, 28, 32AntNet & AntNet-FASubramanian, Druschel & Chen1997100Regular antsHeusse, Gu erin, Snyers & Kuntz199864CAFvan der Put & Rothkrantz1998102, 103ABC-backward严格执行依赖方面的蚁群元启发式关于时间的信息素更新（系 24-27 和 30-34 的算法在图 3 ） 。在蚁群静态算法的组合优化的方式更新信息素的蚂蚁步道变化的算法：任意组合在线步信息素更新和在线延迟信息素更新是可能的。另一个重要方面涉及执行依赖的 daemon 行动（

8、）部分蚁群元启发式（ 6 线的算法在图 3 ） 。守护进程行动实施行动需要某种形式的全球性知识的问题。例子是离线信息素更新和局部优化的解决方案，内置的蚂蚁。大多数蚁群算法中提出的本款强烈鼓舞蚂蚁系统（因为） ，第一工作蚁群优化 33 ， 40 。许多连续应用的最初构想是相对简单的应用向具体问题正在审议之中。因此，我们开始的描述蚁群算法 rithms 与 AS 。以下为每个蚁群算法中列出的表 1 给出了短描述了该算法的主要特点和所取得的成果。3.1.1 旅行商问题第一次申请的蚁群优化算法是利用旅游推销员问题（ TSP 问题）作为测试的问题。主要原因 TSP 问题，其中一个研究得最多的 NP-ha

9、rd 71 ， 86 问题的组合优化，选择是这是一个最短路径问题的蚁群比喻很容易适应和这是一个教学问题（即它是非常容易理解和解释的算法行为不掩盖太多的技术性问题） 。一般定义旅行商问题是下面的。考虑集合 N 的节点，代表城市，以及集合 E 弧线全连接节点 N ，让是弧（） E 的长度，这是城市和间的距离，且、 。TSP 的问题是在图 G =（N ， E）中找到一个最小长度的哈密顿回路，而图 G 的哈密顿回路是一个封闭的参观访问， 只有当所有的 N = | n |节点的 G ，它的长度是由所给予的总和，长度所有的弧线组成。在下面我们将简要地概述了蚁群算法，提出了为总悬浮颗粒物，从蚂蚁系统。更全面

10、观点可在 96 找到。3.1.1.1 蚂蚁系统（AS）蚂蚁系统（AS）是第一个（ 1991 ）33，40 蚁群算法。其重要性所在主要是在目前的原型一些蚂蚁算法已发现了许多有趣的和成功的应用。在蚂蚁系统中人工蚂蚁在建立解决方案（旅游）的 TSP 移动的问题图从一个城市到另一个。该算法执行在以下目录次迭代， 。在每次迭代蚂蚁建立一个巡回执行概率决策规则适用（状态转移）步。在实践中，蚂蚁选择节点移动到节点，弧被加上正在建设旅游。这一步是反复进行，直至蚂蚁已经完成了访问。 三个蚂蚁系统算法在19, 33, 40, 41定义，这些同的方式更新信息素步道。这算法叫做蚂蚁密度、蚂蚁数量、蚂蚁周期。当建立一个

11、解决方案时，蚂蚁密度和蚂蚁蚂蚁数量存信息素。而蚂蚁周期蚂蚁存款信息素后，他们建立了一个完整的游览。初步实验运行了一套基准问题33, 40, 41 表明，蚂蚁周期的表现明显优于其他两种算法。因此，研究蚂蚁系统更好地了解特点，这是目前已知的蚂蚁系统，而其他两个算法被遗弃。正如我们所说，在以后的蚂蚁已经建立了自己的旅行，每个蚂蚁存款信息素的素变数相关线索的访问弧线，使访问弧线变得更加可取的未来蚂蚁(也就是说，线上延迟信息素更新工作)。然后蚂蚁死掉。在没有履行守护活动，而信息素蒸发程序之前发生的蚂蚁开始存款信息素，是交叉的蚂蚁活动。数额信息素踪迹联系弧的目的是代表教训可取的选择，当在城市城时（这也相当

12、于是可取的弧属于蚂蚁游览建造的） 。线索信息的信息素是变化问题的解决方案，以反映所取得的经验在解决问题的蚂蚁。蚂蚁存款的数额成正比信息素的质量，解决他们生产：短游览蚂蚁所产生的更大数额的存款素它的弧它用来产生游览。这一选择可以直接搜索实现良好的解决办法。主要作用是信息素蒸发，以避免停滞，也就是在这种情况最终所有蚂蚁做同样的访问。每个蚂蚁的内存（内部状态）包含已访问了城市，并称为所谓禁忌名单。以下我们将继续利用长期禁忌列表说明蚂蚁的记忆。内存是用来确定，每个蚂蚁的一套城市蚂蚁位于城市我仍然要访问的。利用内存蚂蚁 k，因此可以建立可行的解决办法的一个隐含的状态空间图代（在 TSP，这相当于一个城市

13、完全访问一次） 。此外，内存允许蚂蚁支付相同的路径存入在线延迟性信息素的访问弧线。蚂蚁决策表的节点 i 得到组成的当地信息素径值与当地启发式值如下：（2）而是信息素在弧时间的数额径，是启发式价值从节点 i 到节点 j，是的一套邻居节点，和是两个参数，用于控制的相对比重和启发式信息素踪迹价值。当建设参观的 T -次迭代算法，蚂蚁选择从城市到城市的概率如下，当建设参观的 T -次迭代算法（3）而是蚂蚁还没有访问一套节点附近的节点（通过运用私人记忆，中节点从中选择） 参数和的作用如下：如果，最近的城市更有可能被选择，这相当于一个经典随机贪心算法（有多起点，因为蚂蚁的最初随机分布的节点） 。相反的，如

14、果，只有信息素在起作用：这种方法将导致迅速出现了停滞不前的状况与相应的一代旅游（一般，坚决次优） 。之间的权衡启发式价值和开拓者强度似乎是必要的。在所有的蚂蚁已经遍历完后，信息素的所有弧蒸发触发，然后每一个蚂蚁存储一定量的信息素在每一已经用的弧：（4）而是蚂蚁在迭代所有的遍历，是他的长度。请注意，在对称 TSP，弧被认为是双向的，以便于弧和弧临时更新（实际上，它们是同样的弧） 。不同的是的对称性，而弧有方向性，该信息素踪迹弧和弧可以不同。在这种情况下，因此当一蚂蚁从节点到节点，仅弧而不是弧更新。很显然方在程中，的值取决与蚂蚁如何运动，遍历越短，信息素存储就越多。在实践中，增加新的信息素的蚂蚁和

15、信息素蒸发执行下列规则适用于所有的弧线：（）而，是每次迭代（保持不变）的数量，是衰变的信息素径系数。最初的数额信息素被设置为相同的小积极常数的所有弧，总的蚂蚁数被设置成，而相应设成 1.5、0.5；这些值是被Dorigo33试验发现的。还介绍了精英蚂蚁，也就是守护进程的行动，其中所使用的弧线蚂蚁产生的最佳旅游从一开始就得到了审判额外信息素。蚂蚁系统是相对于其他一般用途的一些相对启发式小的 TSP 问题(这些问题，涉及 30 到 75 个城市) 一时间，结果40,41 非常有趣和令人失望。蚂蚁系统是能够找到和改善最好的解决办法发现了遗传算法的Oliver30106,一个 30 城市问题，与它比较，它有一个类似的或更好的性能通用的启发式。不幸的是，越来越多的问题，体积，蚂蚁系统没有达到最有名的解决方案，在允许 3000 次迭代，但它展示快速收敛，以良好的解决办法。这些令人鼓舞的，虽然不是期待的，结果刺激了一些研究人员进一步研究蚁群优化方法。 这些努力已导致许多成功的应用，在以下各节中列出。3.1.1.2 其他近似的蚂蚁系统Stutzle 和 Hoos（1997）97，98曾经介绍过同样的蚂蚁系统最大最小的蚂蚁系统，但是（1）信息素径只有更新离线的守护（其中