多启发式信息蚁群优化算法求解取样送检路径规划问题

Ant Colony Optimization with Multi-Heuristic Information for Sampling Inspection Path Planning Problem

蚁群优化算法是一种求解组合优化问题的通用算法框架.取样送检路径规划问题是一种带约束的组合优化问题,本文给出了一种求解该问题的数学模型.为求解该问题提出了一种多启发式信息蚁群优化算法(MACO),在选择下一访问节点的概率计算公式中增加了一项启发式信息——起点到被选择点之间距离的倒数,并从理论上分析了该算法的收敛性.在9个算例上进行了仿真实验和分析,说明了新增启发式信息的有效性和适用性,验证了MACO算法可以有效求解该问题,并能获得质量更好的解.

Ant colony optimization （ACO） is a general framework for the combinational optimization problem. The sampling inspection path planning problem is a constrained combinatorial optimization problem. The paper gives a mathematical model of the problem and proposes a multi-heuristic information ant colony optimization algorithm （MACO） to solve it. The reciprocal of the distance between the source node and the feasible node is joined in the probabilistic formula for choosing the next feasible node as a new heuristic information. Then the convergence property of MACO is analyzed. The simulation experiments are done on nine cases. The results demonstrate the availability of the new heuristic information for the problem and good performance of MACO in terms of the solution accuracy.