改进混合蚁群算法求解关联旅行商问题

An improving hybrid ant colony optimization for solving incident traveling salesman problem

由于蚁群算法搜索初期信息匮乏,导致信息素累积时间长,求解速度慢,所以结合具有快速全局搜索能力的遗传算法,同时引入混沌搜索和平滑机制,采用混沌搜索产生初始种群可以克服生成大量非可行解的缺陷,加速染色体向最优解收敛,平滑机制有助于对搜索空间进行更有效的搜索,构成IHACO。针对50个城市的关联旅行商问题,建立数学模型,应用IHACO与PSOGA、ACO、GA和TS求解ITSP和TSP,算例证明IHACO优于其他4种算法,能收敛到最优解,提高了进化效率,而由于关联因素的制约,解也发生了变化。通过应用IHACO和ACO求解TSPlib的3个算例,进一步证明了IHACO优于ACO,能搜索到近优解。

Due to lack of information when ant colony optimization （ACO） started to search at the early period, the accumulation time of pheromone is long, the speed of solving is slow, so combining genetic algorithm （GA） with rapid global search ability, at the same time, chaos search and smooth mechanism are introduced, initial population is generated by chaotic search can overcome the defect of generating a large number of infeasible solution, accelerating chromosome convergence to the optimal solution, moreover, a smooth mechanism helps to search for more effective search space, thus constituting an IHACO. Aiming at 50 cities incident traveling salesman problem （ITSP）, to establish mathematical model, using IHACO, PSOGA, ACO, GA and TS to solve TSP and ITSP. The results of numerical examples prove that IHACO is better than the other four kinds of algorithms, it can also converge to the optimal solution and improve the efficiency of the evolution, because of the incident factor, solution have also changed. By applying IHACO and ACO to solve three examples of TSPlib, further prove IHACO is better than ACO, and it can search the near optimal solution.