蚁群算法(Ant Colony Algorithm,ACA)最早被成功用于解决旅行商问题(Traveling Salesman Problem,TSP),后来因为鲁棒性强、易于与其他方法结合、天然并行性的特点,被广泛应用于解决作业调度问题、航迹规划问题、车辆路径问题等,同时也在机器人领域、数据挖掘与分类等其他实用领域取得了一定的成果。蚁群算法中每次迭代循环结束后,都需要对路径中的信息素浓度进行更新,但是基本蚁群算法执行完更新过程后会导致其易陷入局部最优解进入停滞状态,同时伴随着收敛速度慢等问题,如何优化解决存在的问题,并提高算法在数据规模不断增大时的执行速度和可扩展性,成为本领域的热点问题。针对上述基本蚁群算法易陷入局部最优解和收敛速度慢的问题,在现有研究的基础上,本文采用强化信息素更新机制,通过对其解集信息矩阵进行处理,判断算法是否接近停滞状态;若算法接近停滞状态,再采用新型信息素平滑机制处理信息矩阵,减少或消除算法停滞,提出了一种基于信息素优化机制的算法——蚁群优化提升算法(Ant Colony Optimization Improvement,简称ACOI)。该算法使得基本蚁群算法继续沿着求解全局最优解的目标执行搜索过程。对ACOI算法进行可并行化分析,结合目前常用的并行性框架,针对串行ACOI算法在单机上执行时间长的问题,提出了基于OpenMP的ACOI算法并行化方法,缩短了算法执行时间;针对ACOI算法数据规模增大时在高性能集群上的扩展性问题,利用MPI节点间可并行性的特点,提出了基于MPI的ACOI算法并行化方法,有效解决了扩展性问题;针对纯MPI并行方法在集群上出现的通信代价过高、利用率过低的问题,在OpenMP+MPI混合模型的基础上提出了基于混合编程模型的ACOI算法并行化方法。实验证明,改进后的ACOI算法有效减少了其陷入局部最优解导致算法停滞的概率,同时加快了算法的收敛速度、稳定性增强;基于ACOI算法的并行化方法能够更加充分地利用高性能集群的现有资源,减少了算法的执行时间。