首页|期刊导航|哈尔滨工业大学学报（英文版）|A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem
哈尔滨工业大学学报（英文版）2005，Vol.12Issue(6)：721-726,6.
A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem
A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem
摘要
Abstract
Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the multi-objective shortest path problem (MSPP) has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algorithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this paper. The encoding of the solution and the operators such as crossover, mutation and selection are developed.The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.关键词
shortest path/multi-objective optimization/tournament selection/pareto optimum/genetic algorithmKey words
shortest path/multi-objective optimization/tournament selection/pareto optimum/genetic algorithm分类
信息技术与安全科学引用本文复制引用
HU Shi-cheng,XU Xiao-fei,ZHAN De-chen..A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem[J].哈尔滨工业大学学报（英文版）,2005,12(6):721-726,6.基金项目
Sponsored by the National High Technology Development 863 Program of China( Grant No. 2001AA414010) and the Key Science-Technology Project of the National ‘ Tenth Five-Year-Plan' of China( Grant No. 2001BA201A03 ). （ Grant No. 2001AA414010）
