题目：并行蚁群算法研究及其应用

利用蚁群算法的潜在并行性构造并行蚁算法是提高蚁群算法效率的重要途径。为提高蚁群算法在大规模实际路网中的路径寻优问题求解效率，以及缓解蚁群算法在求解大规模问题时易早熟等现象的发生，针对实际道路路网的一类路径寻优问题，提出了带回退机制的蚁群搜索算法，求解在实际道路路网中完成遍历所有规定节点的一条较优路径。
为解决大规模实际道路路网数据量大，蚁群算法收敛速度慢的问题，归纳了六种并行蚁群算法模型和两种新的信息交流策略，对六种并行模型进行了实验分析。分别在单机多核环境下构造了基于MPI、OpenMP、TBB、Cilk++及Winapi函数的并行蚁群算法模型，在多核集群机下构造了基于MPI、MPI+OpenMP 及MPI+TBB混合编程的并行蚁群计算模型,并以西安市实际道路交通路网的路径寻优问题为求解对象，对上述计算模型进行了实验和对比。
实验结果表明，在单机多核下把基于MPI和OpenMP的并行蚁群算法相比，前者运行时间短，加速比高；在多核集群机下把基于MPI和MPI+OpenMP的混合模型对比,混合并行模型在进程数较多时仍具有较高的加速比。采用Threading Building Blocks和Cilk++并行编程模型实现了并行蚁群搜索，与基于Winapi函数的多线程蚁群算法相比，这两种模型均避免了手动启动线程及识别临界区资源等复杂操作，开发难度降低；在运行效率方面，基于TBB的并行蚁群算法和基于Winapi的并行蚁群算法效率接近，而基于Cilk++的蚁群算法在双核环境下，运行效率和加速比均超过了基于Winapi的并行蚁群算法。
目前大多数高性能计算系统采用分层硬件设计：即通过网络设施连接起来的几个多核CPU共享存储结点，并行程序设计必须结合结点间的分布式存储并行和每个结点内的共享存储并行。因此要为高性能系统设计有效的并行软件必将面临高度分层的系统设计，很自然地构造一种混合编程模型，结点内部使用OpenMP并行，结点间使用MPI消息传递。
传统的并行蚁群算法策略在一定程度上加速了算法收敛速度，提高了运行效率，但确存在着通信过于频繁及忽略了种群多样性，如果把每次迭代中最优的蚂蚁信息广播给其它所有的蚁群，容易陷入局部最优，及产生过大的通信开销。最差蚂蚁可能是局部最差，但若忽略这些最差蚂蚁走过的路径，最优蚂蚁极易使局部最优路径信息素过度加强，不利于最终最优路径生成。最差蚂蚁也应该以一定的概率广播给其它种群，提高种群多样性及得出全局最优解，由此提出来动态蚁群择优策略及分段周期交流策略。