基于超顶点交流策略的并行蚁群算法

通过分析影响并行蚁群算法性能的诸多因素,以提高算法效率减少通信量为主旨,提出了1种基于超顶点交流策略的并行蚁群算法.在该算法中,处理机之间交流的内容不再是最优解或信息素矩阵,而是由若干个顶点组合成的超顶点,从而改变了计算粒度;其次,又提出了1种更忠实于真实蚁群信息系统的基于信息素递减的信息素更新方法,减少了最优解对蚂蚁后选择路径上信息素的影响.通过对TSP进行的实验表明,与其他交流策略的并行蚁群算法相比,该算法有较强的全局收敛性和更快的寻优速度.

Parallel Ant Colony Algorithm with the Information Exchange Based on Super Vertexes

In order to improve the performance of parallel ant colony algorithms,an adaptive parallel ant colony algorithm with the information exchange based on super vertexes of a certain characteristic is proposed.The content of information exchange is the super vertexs composed of several vertexes,no longer being the best solutions or the matrix of pheromone.A new formula updating pheromone based on pheromone descending is introduced,which can reduce the influence of pheromone on subsequent ants.The algorithm is applied to the TSP on the massive parallel processors Shengteng 1800.The comparison between traditional ACO and other parallel ant colony algorithm demonstrates that the algorithm brings higher global convergence and speed of optimization.