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

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

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

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

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

4、nt-QDorigo & Gambardella199637, 38, 50ACS& ACS-3-optManiezzo & Colorni199797, 98MMASManiezzo199712ASrank二次分配Maniezzo,Colorni& origo199477AS-QAPGambardella,Taillard& Dorigo199753, 54HAS-QAPaSt utzle & Hoos199899MMAS-QAPManiezzo & Colorni199876AS-QAPbManiezzo199875ANTS-QAPJob-shop 调度Colorni,Dorigo& an

5、iezzo199420AS-JSP车辆路径Bullnheimer, Hartl & Strauss199615, 11, 13AS-VRPGambardella,Taillard&Agazzi199952HAS-VRP顺序排序Gambardella & Dorigo199751HAS-SOP图着色Costa & Hertz199722ANTCOL最短的共同超序列Michel & Middendorf199878, 79AS-SCSa HAS-QAP 是一种蚂蚁算法不遵循所有方面的蚁群元启发式b 这是一个变异的原始 AS-QAP.表 2 名单中的使用蚁群算法，动态组合优化问题。分类的申请，并排列

6、顺序 问题名称作者年份主要参照算法名称面向连接的网络路由Schoonderwoerd, Holland, Bruten & Rothkrantz199690, 89ABCWhite, Pagurek & Oppacher1998105ASGADi Caro & Dorigo199831AntNet-FSBonabeau, Henaux, Gu erin, Snyers, Kuntz & Th eraulaz19986ABC-smart ants 连接不到网络路由Di Caro & Dorigo199726, 28, 32AntNet & AntNet-FASubramanian, Drusch

7、el & Chen1997100Regular antsHeusse, Gu erin, Snyers & Kuntz199864CAFvan der Put & Rothkrantz1998102, 103ABC-backward 严格执行依赖方面的蚁群元启发式关于时间的信息素更新（系 24-27 和 30-34 的算法在图 3 ） 。在蚁群静态算法的组合优化的方式更新信息素的蚂蚁步道变化的算法：任意组合在 线步信息素更新和在线延迟信息素更新是可能的。另一个重要方面涉及执行依赖的daemon行动（）部分蚁群元启发式（6线的算法在图3 ） 。守护进程行动实施行动需要某种形式的全球性知识的问题。

8、例子是离线信息素更新 和局部优化的解决方案，内置的蚂蚁。大多数蚁群算法中提出的本款强烈鼓舞蚂蚁系统（因为） ，第一工作蚁群优化 33 ，40 。 许多连续使用的最初构想是相对简单的使用向具体问题正在审议之中。因此，我们开始的描 述蚁群算法 rithms 和 AS 。以下为每个蚁群算法中列出的表1 给出了短描述了该算法的主 要特点和所取得的成果。3.1.1 旅行商问题第一次申请的蚁群优化算法是利用旅游推销员问题（ TSP 问题）作为测试的问题。主要原因TSP问题，其中一个研究得最多的NP-hard 71 ,86 问题的组合优化，选择是这是一个最短路径问题的蚁群比喻很容易适应和这是一个教学问题（即

9、它是非常容易理解和解释 的算法行为不掩盖太多的技术性问题）。一般定义旅行商问题是下面的。考虑集合N的节点，代表城市，以及集合E弧线全连接节 点N，让是弧（）WE的长度，这是城市和间的距离，且、TSP的问题是在图G = （N，E） 中找到一个最小长度的哈密顿回路，而图G的哈密顿回路是一个封闭的参观访问，只有当 所有的N = In I节点的G，它的长度是由所给予的总和，长度所有的弧线组成。在下面我们将简要地概述了蚁群算法，提出了为总悬浮颗粒物，从蚂蚁系统。更全面观点可 在 96 找到。3.1.1.1蚂蚁系统（AS）蚂蚁系统（AS）是第一个（1991 ） 33, 40蚁群算法。其重要性所在主要是在目

10、前的原型 一些蚂蚁算法已发现了许多有趣的和成功的使用。在蚂蚁系统中人工蚂蚁在建立解决方案（旅游）的TSP移动的问题图从一个城市到另一个。 该算法执行在以下目录次迭代，。在每次迭代蚂蚁建立一个巡回执行概率决策规则适用（状 态转移）步。在实践中，蚂蚁选择节点移动到节点，弧被加上正在建设旅游。这一步是反复 进行，直至蚂蚁已经完成了访问。三个蚂蚁系统算法在19, 33, 40, 41定义，这些同的方式更新信息素步道。这算法叫做蚂 蚁密度、蚂蚁数量、蚂蚁周期。当建立一个解决方案时，蚂蚁密度和蚂蚁蚂蚁数量存信息素。 而蚂蚁周期蚂蚁存款信息素后，他们建立了一个完整的游览。初步实验运行了一套基准问题33, 4

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

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

13、素径值和当地启发式值如下：（2）而是信息素在弧时间的数额径，是启发式价值从节点i到节点j,是的一套邻居节点，和是 两个参数，用于控制的相对比重和启发式信息素踪迹价值。当建设参观的T -次迭代算法，蚂蚁选择从城市到城市的概率如下，当建设参观的T -次 迭代算法（3）而是蚂蚁还没有访问一套节点附近的节点（通过运用私人记忆，中节点从中选择） 参数和的作用如下：如果，最近的城市更有可能被选择，这相当于一个经典随机贪心算 法（有多起点，因为蚂蚁的最初随机分布的节点）。相反的，如果，只有信息素在起作用： 这种方法将导致迅速出现了停滞不前的状况和相应的一代旅游（一般，坚决次优）。之间的 权衡启发式价值和开拓

14、者强度似乎是必要的。在所有的蚂蚁已经遍历完后，信息素的所有弧蒸发触发，然后每一个蚂蚁存储一定量的 信息素在每一已经用的弧：（4）而是蚂蚁在迭代所有的遍历，是他的长度。请注意，在对称TSP，弧被认为是双向的， 以便于弧和弧临时更新（实际上，它们是同样的弧）。不同的是TSP的对称性，而弧有方 向性，该信息素踪迹弧和弧可以不同。在这种情况下，因此当一蚂蚁从节点到节点，仅弧而 不是弧更新。很显然方在程4中，的值取决和蚂蚁如何运动，遍历越短，信息素存储就越多。 在实践中，增加新的信息素的蚂蚁和信息素蒸发执行下列规则适用于所有的弧线：（5） 而，是每次迭代（保持不变）的数量，是衰变的信息素径系数。最初的数

15、额信息素被设置为 相同的小积极常数的所有弧，总的蚂蚁数被设置成，而相应设成 1.5、0.5；这些值是被 Dorigo33试验发现的。还介绍了精英蚂蚁，也就是守护进程的行动，其中所使用的弧线蚂 蚁产生的最佳旅游从一开始就得到了审判额外信息素。蚂蚁系统是相对于其他一般用途的一 些相对启发式小的TSP问题（这些问题，涉及30到75个城市）一时间，结果40,41非常有 趣和令人失望。蚂蚁系统是能够找到和改善最好的解决办法发现了遗传算法的Oliver30106, 一个30城市问题，和它比较，它有一个类似的或更好的性能通用的启发式。不幸的是，越 来越多的问题，体积，蚂蚁系统没有达到最有名的解决方案，在允许3000次迭代，但它展 示快速收敛，以良好的解决办法。这些令人鼓舞的，虽然不是期待的，结果刺激了一些研究 人员进一