多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性.%The multi-objective traveling salesman problems (MOTSP) are a generalization of the well-known traveling salesman problem where multiple conflicting objectives include optimizing distance, cost, profit, risk of the tour, etc. This paper proposes a preference-based Pareto evolutionary algorithm, named p-PEA, to model and solve this NP-hard problem. The algorithm is built on framework of agent-based simulation model, where MOTSP is represented as an agent model. In this way, various factors of practical MOTSP are easier involved in the model, than the mathematics approaches. Based on agent simulation, multi-objective data of feasible solutions are collected from simulation output. Furthermore, an evolutionary algorithm is adopted to search Pareto-optimal solutions. In the p-PEA algorithm, preference information of decision-maker is introduced to search preferred Pareto-optimal solutions. Finally, the proposed p-PEA algorithm is applied to a bi-objective TSP instance with 130 cities to demonstrate its validity and effectiveness.
展开▼
