一种基于启发式演化算法的最优-最差蚂蚁系统

An improved best-worst ant system based on heuristic evolutionary algorithm

针对传统最优-最差蚂蚁系统(BWAS)存在搜索效率低、收敛速度慢的缺点,提出一种基于启发式演化算法的最优-最差蚂蚁系统(IEABWAS)算法。该算法通过加入启发式演化算子,在算法的每次迭代中将最优蚂蚁与次优蚂蚁执行启发式的演化算子操作,并将这种演化操作产生的较好个体替代系统中最差的个体,以达到快速收敛的目的。同时,为使搜索更加集中于最优解附近,对最优-最差蚂蚁的信息素更新方式进行适应性调整,以提高算法的全局搜索能力。使用该算法求解复杂旅行商问题(TSP),结果表明:与传统的最优-最差蚂蚁系统相比,该算法不但具有更强的全局搜索能力,而且能提高算法的收敛速度,算法性能得到明显改善。

In order to overcome the shortcomings of slow convergent speed and low searching efficiency existing in traditional best-worst ant system, an improved best-worst ant system algorithm （IEABWAS） was presented based on heuristic evolutionary algorithm. The principle of the algorithm is as follows： Firstly, a heuristic crossover operator was imported; In iteration of the algorithm, the heuristic evolving operators were used to crossover between the best ant and the second-best ant for generating superior ant to replace the worst ant. Meanwhile, the searching ability of the algorithm was improved by adjusting the updating method of the pheromone of best-worst ant system. The experiment results show that, compared with the traditional best-worst ant system algorithm, this new algorithm to solve complex traveling salesman problem （TSP） has not only stronger searching ability but also can accelerate convergent speed, and the algorithm performance is improved greatly in the end.