Xiao-Bing Hu^1,2, Ming Wang¹, and Ezequiel Di Paolo^3,4

¹ State Key Laboratory of Earth Surface Processes and AQ2 Resource Ecology, Beijing Normal University, Beijing 100875, China;

² School of Engineering, University of Warwick, Coventry CV4 7AL, AQ3 U.K.;

³ Ikerbasque, Basque Science Foundation, Centre for Research on Life, Mind and Society, University of the Basque Country, 20080 San Sebastian, Spain;

⁴ Centre for Computational Neuroscience and Robotics, Department of Informatics, University of Sussex, Brighton BN1 9RH, U.K..

 

Abstract: Searching the Pareto front for multiobjective optimization problems usually involves the use of a population-based search algorithm or of a deterministic method with a set of different single aggregate objective functions. The results are, in fact, only approximations of the real Pareto front. In this paper, we propose a new deterministic approach capable of fully determining the real Pareto front for those discrete problems for which it is possible to construct optimization algorithms to find the k best solutions to each of the single-objective problems. To this end, two theoretical conditions are given to guarantee the finding of the actual Pareto front rather than its approximation. Then, a general methodology for designing a deterministic search procedure is proposed. In this case study, by following the general methodology, a ripple-spreading algorithm is designed to calculate the complete exact Pareto front for multiobjective route optimization. When compared with traditional Pareto front search methods, the obvious advantage of the proposed approach is its unique capability of finding the complete Pareto front. This is illustrated by the simulation results in terms of both solution quality and computational efficiency.

 

Keywords: Multiobjective optimization; Pareto front; ripple-spreading algorithm; route optimization.

 

Published in IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics. 2012, doi: 10.1109/TSMCB.2012.2223756.