求解最小比率旅行商问题的混合行为蚁群算法

Mixing behavior ant colony algorithm for solving minimum ratio traveling salesman problem

为了快速并且有效地求解最小比率旅行商问题,文章提出了一种混合行为蚁群算法。通过对蚁群算法中转移概率以及信息素更新策略加以改进,使蚂蚁能够随机性地选择自己的行为规范,将蚁群进一步智能化;为防止陷入局部最优,算法中设计了交换策略与灾变策略。仿真实验结果表明,改进后的算法能够有效求解最小比率旅行商问题。

In order to optimize the minimum ratio traveling salesman problem（MRTSP） quickly and effectively, a kind of mixing behavior ant colony optimization（ACO） is proposed. By improving ACO＇s transition probabilities and strategy of updating pheromone, every ant can select its behavior rules randomly, which makes the ant colony more intelligentialized. Exchange strategy and catastrophe strategy are designed in the algorithm to avoid falling into local optimum. The results of simulation experiment indicate that the modified algorithm can optimize MRTSP effectively.