基于任务分发模式的并行蚁群算法

本文提出并实现了一种新的并行蚁群优化(ACO:Ant Colony Optimization)策略:基于任务分发模式的并行蚁群算法。该策略适合于MIMD的并行系统,采用集中式的管理模型,由管理者(主线程)负责程序的IO操作并且维护一个任务列表,工人(人工蚂蚁)负责路径的搜索。算法运行过程中,管理者节点动态地向工人节点分发任务,从而尽量达到负载的均衡。在具体的搜索过程中,为了防止假收敛,每只蚂蚁都带有不同的启发式信息。最后利用该策略实现了一种MMAS的ACO,对TSP问题的测试实验数据表明,相对于串行算法和一些并行ACO,该算法具有一定的优势。