《应用蚁群算法静态组合优化问题教学文案.doc》由会员分享，可在线阅读，更多相关《应用蚁群算法静态组合优化问题教学文案.doc（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Good is good, but better carries it.精益求精，善益求善。应用蚁群算法静态组合优化问题-应用蚁群算法静态组合优化问题添加时间:2011-9-1010:13:37来源:作者:点击数:94应用蚁群元启发式的静态组合优化问题是相对简单，一旦确定了映射的问题，让增量建设一个解决方案，社区结构，和一个随机状态转换模块将当地用来引导建设性的程序。1程序元启发式蚁群（）2当（终止标准不满意）3日程活动4蚂蚁代和活动（）;5素蒸发（）;6daemon在行动（）;自选7结束日程活动8结束，当9结束程序10程序蚂蚁代和活动（）11当（可用资源）12日程设立一个新的蚂蚁（）;13新
2、的积极的蚂蚁（）;14结束当15结束程序16程序新的积极蚂蚁（）蚂蚁生命周期17初始化蚂蚁（）;18M=更新蚂蚁内存（）;19当（目前的状态目标状态）20A=读当地蚂蚁路由表（）;21P=计算转移概率（A;M;问题的限制）;22下一状态=适用蚂蚁决定政策（P;问题的限制）;23转移到下一状态（下一状态）;24如果（在线步信息素更新）25存款信息素的访问弧（）;26更新蚂蚁路由表（）;27结束如果28M=更新内部状态（）;29结束当30如果（在线延误信息素更新）31评价的解决方案（）;32存款信息素的所有访问弧（）;33更新蚂蚁路由表（）;34结束如果35模具（）;36结束程序图3该蚁群元启发式
3、的伪代码。评论包含在括号内。所有程序在第一级压痕在声明中同时并行的执行。守护进程的程序的行动（）在第六行是可选的，并指集中行动执行了守护拥有全球知识。目标国（第19）是指一个完整的解决方案建造的蚂蚁。在一步一步和延迟信息素更新程序行24-27和30-34往往是相互排他性。当他们两人都缺席的信息素是所存放的守护进程。表1名单中的应用蚁群算法静态组合优化问题。应用及分类按时间顺序排列。问题名称作者年份主要参照算法名称旅行商Dorigo,Maniezzo&Colorni199133,40,41ASGambardella&Dorigo199549Ant-QDorigo&Gambardella19963
4、7,38,50ACS&ACS-3-optManiezzo&Colorni199797,98MMASManiezzo199712ASrank二次分配Maniezzo,Colorni&origo199477AS-QAPGambardella,Taillard&Dorigo199753,54HAS-QAPaStutzle&Hoos199899MMAS-QAPManiezzo&Colorni199876AS-QAPbManiezzo199875ANTS-QAPJob-shop调度Colorni,Dorigo&aniezzo199420AS-JSP车辆路径Bullnheimer,Hartl&Straus
5、s199615,11,13AS-VRPGambardella,Taillard&Agazzi199952HAS-VRP顺序排序Gambardella&Dorigo199751HAS-SOP图着色Costa&Hertz199722ANTCOL最短的共同超序列Michel&Middendorf199878,79AS-SCSaHAS-QAP是一种蚂蚁算法不遵循所有方面的蚁群元启发式b这是一个变异的原始AS-QAP.表2名单中的应用蚁群算法，动态组合优化问题。分类的申请，并排列顺序。问题名称作者年份主要参照算法名称面向连接的网络路由Schoonderwoerd,Holland,Bruten&Rothk
6、rantz199690,89ABCWhite,Pagurek&Oppacher1998105ASGADiCaro&Dorigo199831AntNet-FSBonabeau,Henaux,Guerin,Snyers,Kuntz&Theraulaz19986ABC-smartants连接不到网络路由DiCaro&Dorigo199726,28,32AntNet&AntNet-FASubramanian,Druschel&Chen1997100RegularantsHeusse,Guerin,Snyers&Kuntz199864CAFvanderPut&Rothkrantz1998102,103A
7、BC-backward严格执行依赖方面的蚁群元启发式关于时间的信息素更新（系24-27和30-34的算法在图3）。在蚁群静态算法的组合优化的方式更新信息素的蚂蚁步道变化的算法：任意组合在线步信息素更新和在线延迟信息素更新是可能的。另一个重要方面涉及执行依赖的daemon行动（）部分蚁群元启发式（6线的算法在图3）。守护进程行动实施行动需要某种形式的全球性知识的问题。例子是离线信息素更新和局部优化的解决方案，内置的蚂蚁。大多数蚁群算法中提出的本款强烈鼓舞蚂蚁系统（因为），第一工作蚁群优化33，40。许多连续应用的最初构想是相对简单的应用向具体问题正在审议之中。因此，我们开始的描述蚁群算法rith
8、ms与AS。以下为每个蚁群算法中列出的表1给出了短描述了该算法的主要特点和所取得的成果。3.1.1旅行商问题第一次申请的蚁群优化算法是利用旅游推销员问题（TSP问题）作为测试的问题。主要原因TSP问题，其中一个研究得最多的NP-hard71，86问题的组合优化，选择是这是一个最短路径问题的蚁群比喻很容易适应和这是一个教学问题（即它是非常容易理解和解释的算法行为不掩盖太多的技术性问题）。一般定义旅行商问题是下面的。考虑集合N的节点，代表城市，以及集合E弧线全连接节点N，让是弧（）E的长度，这是城市和间的距离，且、。TSP的问题是在图G=（N，E）中找到一个最小长度的哈密顿回路，而图G的哈密顿回路
9、是一个封闭的参观访问，只有当所有的N=|n|节点的G，它的长度是由所给予的总和，长度所有的弧线组成。在下面我们将简要地概述了蚁群算法，提出了为总悬浮颗粒物，从蚂蚁系统。更全面观点可在96找到。3.1.1.1蚂蚁系统（AS）蚂蚁系统（AS）是第一个（1991）33，40蚁群算法。其重要性所在主要是在目前的原型一些蚂蚁算法已发现了许多有趣的和成功的应用。在蚂蚁系统中人工蚂蚁在建立解决方案（旅游）的TSP移动的问题图从一个城市到另一个。该算法执行在以下目录次迭代，。在每次迭代蚂蚁建立一个巡回执行概率决策规则适用（状态转移）步。在实践中，蚂蚁选择节点移动到节点，弧被加上正在建设旅游。这一步是反复进行，
10、直至蚂蚁已经完成了访问。三个蚂蚁系统算法在19,33,40,41定义，这些同的方式更新信息素步道。这算法叫做蚂蚁密度、蚂蚁数量、蚂蚁周期。当建立一个解决方案时，蚂蚁密度和蚂蚁蚂蚁数量存信息素。而蚂蚁周期蚂蚁存款信息素后，他们建立了一个完整的游览。初步实验运行了一套基准问题33,40,41表明，蚂蚁周期的表现明显优于其他两种算法。因此，研究蚂蚁系统更好地了解特点，这是目前已知的蚂蚁系统，而其他两个算法被遗弃。正如我们所说，在以后的蚂蚁已经建立了自己的旅行，每个蚂蚁存款信息素的素变数相关线索的访问弧线，使访问弧线变得更加可取的未来蚂蚁(也就是说，线上延迟信息素更新工作)。然后蚂蚁死掉。在没有履行守
11、护活动，而信息素蒸发程序之前发生的蚂蚁开始存款信息素，是交叉的蚂蚁活动。数额信息素踪迹联系弧的目的是代表教训可取的选择，当在城市城时（这也相当于是可取的弧属于蚂蚁游览建造的）。线索信息的信息素是变化问题的解决方案，以反映所取得的经验在解决问题的蚂蚁。蚂蚁存款的数额成正比信息素的质量，解决他们生产：短游览蚂蚁所产生的更大数额的存款素它的弧它用来产生游览。这一选择可以直接搜索实现良好的解决办法。主要作用是信息素蒸发，以避免停滞，也就是在这种情况最终所有蚂蚁做同样的访问。每个蚂蚁的内存（内部状态）包含已访问了城市，并称为所谓禁忌名单。以下我们将继续利用长期禁忌列表说明蚂蚁的记忆。内存是用来确定，每个
12、蚂蚁的一套城市蚂蚁位于城市我仍然要访问的。利用内存蚂蚁k，因此可以建立可行的解决办法的一个隐含的状态空间图代（在TSP，这相当于一个城市完全访问一次）。此外，内存允许蚂蚁支付相同的路径存入在线延迟性信息素的访问弧线。蚂蚁决策表的节点i得到组成的当地信息素径值与当地启发式值如下：（2）而是信息素在弧时间的数额径，是启发式价值从节点i到节点j，是的一套邻居节点，和是两个参数，用于控制的相对比重和启发式信息素踪迹价值。当建设参观的T-次迭代算法，蚂蚁选择从城市到城市的概率如下，当建设参观的T-次迭代算法（3）而是蚂蚁还没有访问一套节点附近的节点（通过运用私人记忆，中节点从中选择）参数和的作用如下：如
13、果，最近的城市更有可能被选择，这相当于一个经典随机贪心算法（有多起点，因为蚂蚁的最初随机分布的节点）。相反的，如果，只有信息素在起作用：这种方法将导致迅速出现了停滞不前的状况与相应的一代旅游（一般，坚决次优）。之间的权衡启发式价值和开拓者强度似乎是必要的。在所有的蚂蚁已经遍历完后，信息素的所有弧蒸发触发，然后每一个蚂蚁存储一定量的信息素在每一已经用的弧：（4）而是蚂蚁在迭代所有的遍历，是他的长度。请注意，在对称TSP，弧被认为是双向的，以便于弧和弧临时更新（实际上，它们是同样的弧）。不同的是的对称性，而弧有方向性，该信息素踪迹弧和弧可以不同。在这种情况下，因此当一蚂蚁从节点到节点，仅弧而不是弧
14、更新。很显然方在程中，的值取决与蚂蚁如何运动，遍历越短，信息素存储就越多。在实践中，增加新的信息素的蚂蚁和信息素蒸发执行下列规则适用于所有的弧线：（）而，是每次迭代（保持不变）的数量，是衰变的信息素径系数。最初的数额信息素被设置为相同的小积极常数的所有弧，总的蚂蚁数被设置成，而相应设成1.5、0.5；这些值是被Dorigo33试验发现的。还介绍了精英蚂蚁，也就是守护进程的行动，其中所使用的弧线蚂蚁产生的最佳旅游从一开始就得到了审判额外信息素。蚂蚁系统是相对于其他一般用途的一些相对启发式小的TSP问题(这些问题，涉及30到75个城市)一时间，结果40,41非常有趣和令人失望。蚂蚁系统是能够找到和
15、改善最好的解决办法发现了遗传算法的Oliver30106,一个30城市问题，与它比较，它有一个类似的或更好的性能通用的启发式。不幸的是，越来越多的问题，体积，蚂蚁系统没有达到最有名的解决方案，在允许3000次迭代，但它展示快速收敛，以良好的解决办法。这些令人鼓舞的，虽然不是期待的，结果刺激了一些研究人员进一步研究蚁群优化方法。这些努力已导致许多成功的应用，在以下各节中列出。3.1.1.2其他近似的蚂蚁系统Stutzle和Hoos（1997）97，98曾经介绍过同样的蚂蚁系统最大最小的蚂蚁系统，但是（1）信息素径只有更新离线的守护（其中的弧线所用最好的蚂蚁在当前迭代得到更多的信息素），（2）信息
16、素踪迹值限制在区间，（3）信息素踪迹初始值到它的最大值。根据方程3，把明确的限制线索强度限制了各种可能的值的概率选择一个特定的弧。这有助于避免停滞，这是其中一个原因蚂蚁系统表现不佳时，作为一个精英战略被采用，像只允许最好的蚂蚁来更新信息素的小径。为了避免停滞，这可能会发生一些信息素的情况下径接近，而其他大多数接近。Stutzle和Hoos增加了他们所说的“开拓者平滑机制：也就是说，信息素更新步道使用比例机制：。通过这样的方式，相对差异开拓者的优势得到更小，这显然有利于探索新的途径。他们发现，当运用到，比蚂蚁系统发现显著好的路径，虽然相比这些从ACS获得的（ACS是蚂蚁系统在3.1.1.3节讨论
17、中的扩展）。Bullnheimer、Hartl和Strauss12又一次提出蚂蚁系统的修正，叫做。在中，像在MMAS情况一样，唯一的信息素更新是由守护进程，实现了下列活动：（1）蚂蚁被用路径长度来排序，其中的弧线所访问的第一个-1蚂蚁在排名收到的数额信息素成正比访问蚂蚁排名；（2）所用的弧线蚂蚁产生最佳游览从开始试验还得到更多的信息素（这相当于为的精英蚂蚁信息素更新）。这是两种形式的离线信息素更新。在执行过程中的贡献，最好的游览迄今为止乘以。动态的数额信息素是由给出：（6）而，是从路径开始最佳的解决长度，如果蚂蚁排列已经用弧在他的踪迹，并且。是蚂蚁在排列、迭代的踪迹长度。式子6应用所有的弧和，
18、因此，实施两个素蒸发和离线信息素更新。他们发现这个新程序的质量显着改善，应用蚂蚁系统。3.1.1.3蚁群系统（ACS），ACS-3-opt,和Ant-Q蚁群系统算法已经被Dorigo和Gambardella（1996）37，38，50介绍来改进蚂蚁系统。能够找到良好的解决方案在合理的时间内为解决小问题。蚁群系统是基于蚂蚁系统，但提出了一些重要的区别。首先，守护进程更新信息素的步道离线：在算法的每一次迭代结束，一旦所有的蚂蚁已经建立一个解决方案，信息素踪迹添加到弧用蚂蚁发现最好的旅游从一开始的路径。在SCS-3-opt,而守护进程首次激活本地搜索程序，基于的一个变种3-opt本地搜索程序73以便
19、与完善蚂蚁产生解决方案，然后进行离线更新信息素踪迹。离线信息素更新规则是：（7）而是一个参数管理信息素衰变，是最好的路径自开始的长度。式子7仅应用到弧属于。其次，蚂蚁用不同的决策规则，叫做伪随机比例规则，在这规则中，城市中的蚂蚁选择城市按照以下规则移动。让成为蚂蚁决策表：（8）让是一个在0,1分布均匀的随机变量，是一个可调参数。被蚂蚁位于节点选择下一个节点用的伪随机比例规则是以下：如果那么（9）相反，当（10）这个决策规则有一双重功能：当，规则决定利用规则知识的问题，也就是说，启发式知识的距离城市之间的知识和经验教训的以信息素步道形式存储。而当，它经营有偏见的探索（相当于蚂蚁系统中的式子3）.
20、调谐可以调节程度的探索和选择是否集中活动的系统的最佳解决方案，或探讨搜索空间。第三，在蚁群系统只执行线一步一步信息素更新。这些更新有利于执行的出现是迄今比其他最佳解决方案。那个信息素的更新是由适用规则：（11）而。式子11说明一个蚂蚁从城市到城市在弧上更新信息素在弧。值是一样的初始值素步道，试验得出：得出很好的结果，而是城市的数目，是旅游所产生的近邻启发式的长度56。当一蚂蚁从城市到城市，当地更新规则的应用提出了相应的信息素踪迹减少。信息素踪迹在道路上减少的理由正在使用的蚂蚁建立一个以下解决方案是。考虑蚂蚁在城2开始和转移到城市3，4，等等，蚂蚁在城市1开始和选择城市2作为第一个城市迁移到。然
21、后，有一个好的机会，蚂蚁将追寻蚂蚁一步延迟。地方更新规则的运用，减少影响的开拓者降低了这种情况的风险。换句话说，蚁群系统的地方更新规则有使访问弧吸引力越来越少的效果，正如他们被蚂蚁所访问，间接有利于探索尚未访问的弧线。因此，蚂蚁往往不收敛到一个共同的道路。这一事实，被实验38观察，是一种可取的财产，因为蚂蚁探索不同的路径，那里有一个更高的概率，其中一个将找到一个改进解决方案，跟他们都汇集到同一路径相比（这将使得使用蚂蚁无意义）。最后，蚁群系统利用一个数据结构叫做候选人名单，以提供当地额外启发式信息。候选人名单是的首选城市要访问某一城市。在蚁群系统，当一蚂蚁在城市，而不是检查所有没有访问的邻居，
22、它从那些候选名单中选择的城市来移动;仅当有候选城市能访问，然后其他城市进行检查。候选城市名单中包含增加城市距离的城市（是一个参数），名单扫描顺序，并根据蚂蚁禁忌名单，以避免已经访问城市。蚁群系统在标准问题上测试过（在37,38上看详细结果），两个对称和非对称，大小不同，并与许多其他中继启发式相比。在所有情况下，其业绩，无论是质量的解决方案，以及产生他们所需CPU的时间，是最好的之一。ACS-3-opt的表现被拿来与遗传算法（当地优化）47,48相比，赢得了第一届国际竞赛进化优化2。这两个算法在行为对称问题，ACS-3-opt非对称表现出相似性。总的来讲，我们说过蚁群系统是Ant-Q的直接继承（
23、1996）36,49一个算法，试图合并蚂蚁系统和Q-learning104属性。实际上Ant-Q仅在值被蚂蚁进行在线步信息素更新时与蚁群系统不同。想法是用下一步状态预测价值来更新信息素步道。在Ant-Q，通过下列方程取代方程11，蚂蚁实现在线步信息素更新：（12）不幸的是，后来发现设置复杂预测长期的一个小恒定值，正如在蚁群系统做的那样，导致大致相同表现。因此，尽管具有良好的表现，因为蚁群系统同样不错，但更简单，Ant-Q被遗弃。同样的，与上面描述的其他蚁群系统版本被研究，是因为（1）它采用一步一步的在线更新方法（在38实验运行停用，或通过设置更新项在方程11值，（2）采用决策规则（在49，伪随
24、机比例规则，式子9和10跟蚂蚁系统中的随即比例对比，伪随机规则不同于伪随机比例规则，是因为随机项是均匀随机），（3）解决方案的类型，用后来程序来更新信息素步道（在38在目前的迭代，使用最好的解决办法与从开始路径最好解决方案的蚁群系统比较）。蚁群系统正如所上面所描述的，是表现最好的所有算法的组合获得了上面说道的机会。3.1.2二次分配问题二次分配问题（QAP）是分配个设施到个地点，这样的费用转让，尽量减少的问题。这是一个设施被指定分配到地点的函数。二次分配问题是继旅行商问题后，第一个被类似蚂蚁系统算法吸引的问题。这是一个合理的选择，因为二次分配是一个泛化的TSP问题。Maniezzo,Color
25、ni和Dorigo（1994）77采用完全相同的算法,正如蚂蚁系统用特定二次分配最大最小启发式来计算值，在式子3.算法结果蚂蚁系统二次分配测试了一套标准的问题，并导致具有相同的质量元启发式方法像模拟退火和进化计算。最近，Maniezzo、Colorni76和Maniezzo75开发了蚂蚁系统二次分配问题的两个变种，并且给他们添加一个局部最优值，由此产生的算法与一些有非常好的结果的启发式二次分配问题进行了比较。蚂蚁系统二次分配问题给了测试问题最好的结果。Stutzle和Hoos(1998)用他们MMAS-QAP算法99（MMAS-QAP和HAS-QAP是MMAS的简单应用，在3.1.1.2二次分
26、配问题章节可以查看）得出了同样的结果。Gambardella和TaillardDorigo(1997)用HAS-QAP算法也得出同样的结果。MMMASQAP和HAS进行比较的一些用于在两个类别的问题最佳启发式：随机和结构二次分配问题，而结构二次分配问题是来源于真是世界应用的实例问题。这些蚂蚁算法被证明在结构化问题上变现最佳，。详细的蚁群算法算法应用到二次分配问题的观点可以在查到。.Job-shop调度问题Colorni,Dorigo和Maniezzo(1994)应用蚂蚁系统到Job-shop调度问题，这一问题可以从下面计算：给定一个和由一个命令序列的行动被处决组成的集。Job-shop调度问题
27、是分配任务、时间给机器运行，以便在最高的完成时间最小化所有行动，也没有同时在同一台机器上，处理两件任务。JSP是hard。他们的基本算法的应用是完全一样的，因为在启发式价值计算使用时间最长的剩余处理时间启发式。由于不同性质的制约因素对TSP，他们还确定了新的建设蚂蚁的禁忌名单的方式。AS-JSP技术应用方面的问题多达15台和15个就业机会一直在寻找解决办法10的最优值20，41。这些结果，但也不例外，是令人鼓舞的，并提出进一步的工作可能会导致一种可行的制度。另外，相对于其他的办法是必要的。3.1.4车辆路径问题这里有很多车辆路径问题类型的问题（VRPs）。Bullnheimer,Hartl和S
28、trauss11,13,15应用一个类似蚂蚁系统算法于以下实例。让是一个完整的带权有向图，其中是集合的节点，是弧的集合，且每一弧有一相关权重代表和的距离。节点代表一车库，其中车辆M停在那里。要求和服务时间关联到每个客户（和）。我们的目标是找到最低的车辆路线成本，使（1）每一位客户的只被一车辆访问；（2）每辆车辆的总需求不超过欧它的容量D；（3）每辆车辆总的路径长度不超过一个界限L；（4）每辆车的起点和末点都在车库。算法蚂蚁系统-车辆路径问题，是Bullnheimer,Hartl和Strauss为了上面的问题而定义的，是基于在3.1.1.2章节讨论的蚂蚁系统排算法的蚂蚁系统的直接扩展。为车辆路径
29、问题，他们用各种标准的启发式，增加了一基于2-opt启发式的简单局部最优值。他们还调整了建立在考虑采取限制路径最大总长度L的车辆和其最大容量D的禁忌清单的方式。同一系列标准问题的比较显示出了蚂蚁系统-车辆路径问题至少是有趣的。它优于模拟退火算法和神经网络，而它的性能略比禁忌搜索有所下降。Gambardella,Taillard和Agazzi(1999)52同样也涉及了车辆路径问题，通过蚁群算法。他们首先改写这个问题，增加了城市，设定M-1仓库，其中m是车辆的数目。用这个改写，车辆路径问题变成一个代约束的禁忌搜索问题。因此，他们定义了一算法，称之为HAS-VRP，被ACS所鼓励：每一蚂蚁建立一完
30、全的路径而没有违反车辆容量限制（每一车辆有一个相关的最大运输权重）。一个完整的游览包括许多subtours接驳站，每个分赛相当于一个路径相关的车辆。信息素踪迹更新是在ACS离线。此外，局部的优化程序，边交流的基础上适用的服务。结果这种做法与那些具有竞争力的最有名的算法和新上界已为众所周知的计算问题的实例。他们还研究了车辆路径问题有时间窗（VRPTW），扩展了车辆路径问题，通过引入时间窗，期间客户必须被服务。因此，在时间前，访问客户的车辆将会不得不等待。在文献中，有时间窗的车辆路径问题解决考虑两个目标函数：一是最大限度地减少车辆的数目，第二个是减少总的旅行时间。一个解决较低的车辆数目办法，总是喜
31、欢的解决方案较高的车辆数目，但较低的旅行时间。为了优化这两个目标同时，两集蚁群算法已被设计出来。第一个群尝试尽量减少车辆的数目，而另一人使用V辆车辆，其中V是第一群计算出的车辆数，以减少旅行时间。这两个群用不同的信息素的小径工作，但最好的蚂蚁被允许更新其他群的信息素踪迹。在文学上，这种做法已被证明是著名而有竞争力的。3.1.5最短的共同超序列问题给定一个包含字母的集合L，找到一最小长度的串，它是每一L中的串的超级序列。而串S是一串A的超级序列，如果S能从A通过插入A零或者更多的字符。这个问题就是被称为最短共同超级序列问题（SCS），Michel和Middendorf(1998)78,79通过蚂
32、蚁系统-最短共同超级序列抨击它。蚂蚁系统-最短共同超级序列不同于蚂蚁系统在于：它使用的前进函数，函数考虑到选择下一个符号附加在下次迭代的影响。前进函数返回的值取代启发式值，在概率决策规则（式子3）。同样的，在蚂蚁系统-最短共同超级序列，从一简单的启发式返回，成为LM的值在信息素踪迹任期分解。Michel和Middendorf进一步改善他们的算法，通过使用一个岛屿模型计算（即不同的蚂蚁群工作相同的问题，利用私人信息素径分布;每一个固定数量的迭代他们交流的最好解决办法找到）AS-SCS-LM(AS-SCS带启发式，前进，岛屿模型计算)被拿来同MM46、LM启发式比较，以及与最近拟议的，专门为SCS
33、的问题的遗传算法。对绝大多数测试的问题，SCS是表现最好的算法。.图着色问题Costa和Hertz（1997）22为分配类型的问题，提出了ASATP算法。他们定义的ATP算法基本和蚂蚁系统一样，除了蚂蚁必须做出两种选择：首先，他们选择项目，然后他们选择资源分配给先前选择的项目，这两种选择都是通过两个概率规则函数的两个不同的信息素步道和和两个合适的启发式价值1和2。事实上，使用两个素步道是主要介绍了新颖的AS-ATP。他们证明了他们的方法，通过图着色问题（）的申请。给定一个图，中的着色，是的映射，这样如果。图着色问题是找到一种着色的图G，使总数q采用的色彩是最低。他们提出的算法，称为ANTCOL
34、，利用著名的图着色启发式，像递归第一（RLF）72和DSATUR。Costa和Hertz，在一套随机图表中测试ANTCOL和一些现有的最佳启发式比较。结果结果表明，ANTCOL性能媲美其他启发式获得的：在20个随机产生的100个节点的图上任何两个节点与概率0.5的平均数目颜色使用ANTCOL是.，而最好的已知的结果23，44是14.95。更多的研究将是必要的，以确定是否建议使用两个素步道可以成为一个有用加入到蚁群算法。.顺序排序问题顺序排序问题（）42由寻找最低权重Hamil-tonian路径上的加权有向图的弧和节点组成，优先约束节点之间。这是非常类似的非对称TSP，在其中结束城市都不是直接连
35、接到启动城市。顺序排列问题是的，模型现实世界的问题，如单车辆路径问题的回升和交付的制约，生产规划，交通等问题，柔性制造系统，因此，从应用的角度来看是一个重要问题。Gambardella和Dorigo(1997)51通过一个蚁群算法的扩展，抨击了顺序排列问题。实际上，跟蚁群算法一样，除了可行节点集，这是建立在考虑采取额外的优先制约因素，并为局部最优值，一个专门设计著名的的变种。获得的结果是优秀的。试验运行大量的标准问题，并与现有最好的启发式方法进行了比较。在所有情况下，在解决质量和计算时间，是表现最好的方法。此外，对一系列问题进行测试改，进许多最有名的结果。关于研友|诚聘英才|联系我们|友情链接版权所有：2007-2009中山研友工作室电话：0760-86388801QQ：741287446地址：广东中山市石岐区学院路1号邮编:528402技术支持：安徽三户网络皖ICP备10002124号-