基于蚁群算法的多Agent任务分配方法

《基于蚁群算法的多Agent任务分配方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第26卷第4期湖南工业大学学报Vol.26No.42012年7月JournalofHunanUniversityofTechnologyJuly2012doi:10.3969/j.issn.1673-9833.2012.04.021基于蚁群算法的多Agent任务分配方法文志强，何宇晨（湖南工业大学计算机与通信学院，湖南株洲412007）摘要：针对多Agent任务分配问题，结合蚁群算法的思想，设计了基于图的任务分配数学模型，提出了基于蚁群算法的多Agent任务分配方法，并通过实验与3个经典方法进行比较和分析，探讨了蚂蚁

2、数对求解结果的影响。实验结果表明，所提出的算法是有效的。关键词：多Agent；任务分配；蚁群算法；信息素中图分类号：TP391文献标志码：A文章编号：1673-9833(2012)04-0092-05Multi-AgentTaskAllocationBasedonAntColonyAlgorithmWenZhiqiang，HeYuchen（SchoolofComputer&Communication，HunanUniversityofTechnology，ZhuzhouHunan412007，China）Abstra

3、ct：Inviewofmulti-agenttaskallocationproblems,ataskallocationmodelbasedongraphispresented,andbasedonantcolonyalgorithmamulti-agenttaskallocationmethodisproposed.Throughexperiments,itiscomparedwiththreeclassicmethods,andtheinfluenceofantsnumberonthesolutionisdisc

4、ussed.Theexperimentalresultshowsthattheproposedmethodiseffective.Keywords：multi-Agent；taskallocation；antcolonyalgorithm；pheromone种方法易实现且能找到最优分配方法，但该方法的0引言时间复杂度高，不适合于实时处理。贪心算法，就在计算机应用中，待处理任务的复杂程度越来是使每次所做的选择看起来都是当前最佳的，期望越高，而由单个Agent难以快速处理一个大而复杂通过所做的局部最优选择产生出一个全局最

5、优解。的任务，因而，由多个Agent共同合作去完成某项对大多数优化问题，该算法能产生最优解，但也不[1-2]复杂任务是必然的趋势。这就需要将一个任务分一定总是最优。Kuhn-Munkres算法，是通过给每一解为多个子任务，然后分配给不同的Agent协同处个顶点一个标号，将求最大权匹配的问题转换为求理，因此，合理的任务分配方案成为高效处理任务完全匹配的问题，该方法只适合于任务数和Agent的前提。任务分配是将合适的任务分配给合适的数相等的情形。上述方法都是非智能化方法，不能Agent以实现整体执行效果最优，这是一个NP

6、难问完全解决任务分配的最优化问题。另一类方法是智题。多Agent任务分配求解方法主要有：穷举搜索能化任务分配求解方法，利用智能化算法如遗传算[3][4][5]法，就是通过穷举所有的分配方案来求解问题。这法、蚁群算法、粒子群算法等来搜索最优任务收稿日期：2012-06-08基金项目：国家自然科学基金资助项目（61170102），湖南省自然科学基金资助项目（11JJ3070，10JJ3002，11JJ4050）作者简介：文志强（1973-），男，湖南湘乡人，湖南工业大学副教授，博士，主要研究方向为图像处理和视觉跟踪，E-

7、mail：zhqwen20001@163.com第4期文志强，等基于蚁群算法的多Agent任务分配方法93分配方案。这些方法利用了求解过程中的一些启发率算法，其灵感来源于蚂蚁在寻找食物过程中发现式信息，求解效果比非智能化方法好。如针对蚁群路径的行为。蚁群算法模拟多只蚂蚁的蚁群协作过算法求解分配任务问题时易陷入局部最优解的缺陷，程，每只蚂蚁在候选解的空间中独立地搜索解，并文献[6]提出了一个分组多态蚁群算法。为了高效获在所找到的解上留下一定量的信息。解的性能越好取最优解，文献[4]使用改进的蚁群优化算法来解决蚂蚁留在其

8、上的信息量越大，信息量越大的解被选多目标资源分配问题。文献[7]将蚁群算法应用于自择的可能性也越大。在算法的最初阶段所有解上的主车辆的任务分配和路径规划，以提高任务规划的信息量是相同的，随着算法的推进较优解上的信息性能。量增加，算法渐渐收敛。蚁群算法已成功解决了一任务分配的目的是求多个任务与多个Agent之间系列问题，如TSP问题、Job-Sh