论文部分内容阅读
最小比率旅行商问题是经典旅行商问题的扩展,不仅考虑路程,而且考虑收益,以路程和收益之比为目标函数.为求解该问题,给出了一种确定性的现代启发式算法——中心引力优化算法.针对算法依赖初始点敏感的问题,采用佳点集构造初始群体,使初始群体尽可能分布均匀;采用加速度和位置的计算模型,并给出基于随机键的编码方法,实现算法的搜索空间到问题解空间的转换.结合典型算例进行仿真和比较,实验结果表明本算法具有计算精度高和鲁棒性强等优点,为最小比率旅行商问题的求解提供了可行有效的方法.“,”The minimum ratio traveling salesmah problem is the extension of the classical traveling salesman problem,which problem considers not only distance,but also the benefits.The objective function is the ratio between the distance and benefits.To solve this problem,central force optimization algorithm is proposed,which is a deterministic meta-heuristic algorithm.Considering the algorithm is sensitive to the initial points,good point set is used to construct the initial population,which makes the initial population distribute as uniformly as possibly.The calculation model based on acceleration and position is adopted.The encoding method based on random key is presented,which implements the transformation from the searching space of the algorithm to the solution space of the problem.The typical examples are used for simulation and comparison.The experimental results show that the method has advantages such as high computing precision and strong robustness.The presented algorithm provides a feasible and effective method for solving the minimum ratio traveling salesman problem.