倪郁东，赵　群，沈吟东，张玉洁（.合肥工业大学数学学院，安徽合肥　30009；.华中科技大学自动化学院，湖北武汉　430074）



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

倪郁东1，赵群1，沈吟东2，张玉洁1
（1.合肥工业大学数学学院，安徽合肥230009；2.华中科技大学自动化学院，湖北武汉430074）

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

关键词：最小比率旅行商问题；蚁群算法；混合行为；优化

沈吟东（1965-），女，安徽合肥人，博士，华中科技大学教授，博士生导师.

旅行商问题（traveling salesman problem，TSP）是一类典型的组合优化问题，同时也是NP-Hard问题。通常可简单描述为：有一旅行商欲前往n个城市推销商品，从某一城市出发，经过各个城市一次后返回出发城市，问该旅行商应如何选择出行路线，使得总路程最短。最小比率旅行商问题（MRTSP）是从经典TSP中引申出来的一个变形问题，它在原TSP的基础上增加了收益假定，即旅行商从城市i走到城市j能获得一定收益pij，现在的问题变成：确定一条路线，使得总路程与总收益的比最小。这种思想类似于经济学中的费用效益，既考虑到了成本同时又考虑到了收益。相比于TSP中只考虑路程，研究MRTSP往往更具实际意义。……