×

Perturbed decomposition algorithm applied to the multi-objective traveling salesman problem. (English) Zbl 1391.90510

Summary: Dealing with multi-objective combinatorial optimization, this article proposes a new multi-objective set-based meta-heuristic named perturbed decomposition algorithm (PDA). Combining ideas from decomposition methods, local search and data perturbation, PDA provides a 2-phase modular framework for finding an approximation of the Pareto front. The first phase decomposes the search into a number of linearly aggregated problems of the original multi-objective problem. The second phase conducts an iterative process: aggregated problems are first perturbed then selected and optimized by an efficient single-objective local search solver. Resulting solutions will serve as a starting point of a multi-objective local search procedure, called Pareto local search. After presenting a literature review of meta-heuristics on the multi-objective symmetric traveling salesman problem (TSP), we conduct experiments on several instances of the bi-objective and tri-objective TSP. The experiments show that our proposed algorithm outperforms the best current methods on this problem.

MSC:

90C27 Combinatorial optimization
90C29 Multi-objective and goal programming
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ehrgott, M., Multicriteria optimization, (2005), Springer Berlin, Heidelberg · Zbl 1132.90001
[2] Zhang, Q.; Li, H., MOEA/da multiobjective evolutionary algorithm based on decomposition, IEEE Trans Evol Comput, 11, 6, 712-731, (2007)
[3] Codenotti, B.; Manzini, G.; Margara, L.; Resta, G., Perturbationan efficient technique for the solution of very large instances of the Euclidean TSP, INFORMS J Comput, 8, 2, 125-133, (1996) · Zbl 0866.90130
[4] Steuer, R. E., Multiple criteria optimization: theory, computation, and applications, (1986), Wiley New York · Zbl 0663.90085
[5] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search, (2003), Springer New York · Zbl 1116.90412
[6] Stützle, T., Iterated local search for the quadratic assignment problem, Eur J Oper Res, 174, 3, 1519-1539, (2006) · Zbl 1103.90066
[7] Talbi E-G, Rahoual M, Mabed MH, Dhaenens C. A hybrid evolutionary approach for multicriteria optimization problems: application to the flow shop. In: EMO, vol. 1. Zurich: Springer; 2001. p. 416-28.
[8] Angel, E.; Bampis, E.; Gourves, L., A dynasearch neighborhood for the bicriteria traveling salesman problem, (Metaheuristics for multiobjective optimisation, (2004), Springer Berlin, Heidelberg), 153-176 · Zbl 1162.90537
[9] Paquete, L.; Chiarandini, M.; Stützle, T., Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study, (Metaheuristics for multiobjective optimisation, (2004), Springer Berlin, Heidelberg), 177-199 · Zbl 1070.90102
[10] Liefooghe, A.; Humeau, J.; Mesmoudi, S.; Jourdan, L.; Talbi, E.-G., On dominance-based multiobjective local searchdesign, implementation and experimental analysis on scheduling and traveling salesman problems, J Heuristics, 18, 2, 317-352, (2012) · Zbl 1358.90046
[11] Lust, T.; Teghem, J., Two-phase Pareto local search for the biobjective traveling salesman problem, J Heuristics, 16, 3, 475-510, (2010) · Zbl 1189.90145
[12] Ehrgott, M.; Gandibleux, X., Hybrid metaheuristics for multi-objective combinatorial optimization, (Hybrid metaheuristics, (2008), Springer Berlin, Heidelberg), 221-259
[13] Drugan, M. M.; Thierens, D., Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies, J Heuristics, 18, 5, 727-766, (2012)
[14] Drugan, M.; Thierens, D., Path-guided mutation for stochastic Pareto local search algorithms, (Parallel problem solving from nature XI, (2010), Springer Berlin, Heidelberg), 485-495
[15] Merz, P., Advanced fitness landscape analysis and the performance of memetic algorithms, Evol. Comput., 12, 3, 303-325, (2004)
[16] Jaszkiewicz, A., Genetic local search for multi-objective combinatorial optimization, Eur J Oper Res, 137, 1, 50-71, (2002) · Zbl 1002.90051
[17] Ishibuchi, H.; Murata, T., Multi-objective genetic local search algorithm, (Proceedings of IEEE international conference on evolutionary computation, (1996), IEEE Nagoya), 119-124
[18] Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Trans Syst Man Cybern Part C: Appl Rev, 28, 3, 392-403, (1998)
[19] Paquete, L.; Stützle, T., A two-phase local search for the biobjective traveling salesman problem, ((2003), Springer Berlin, Heidelberg), 479-493 · Zbl 1036.90561
[20] Dubois-Lacoste, J.; López-Ibáñez, M.; Stützle, T., Improving the anytime behavior of two-phase local search, Ann Math Artif Intell, 61, 2, 125-154, (2011) · Zbl 1234.68362
[21] Jaszkiewicz A, Zielniewicz P. Efficient adaptation of the pareto memetic algorithm to the multiple objective travelling salesperson problem. In: Proceedings of the 7th international conference devoted to multi-objective programming and goal programming; 2006.
[22] Kumar R, Singh P. Pareto evolutionary algorithm hybridized with local search for biobjective TSP; 2007. p. 361-98.
[23] Paquete, L.; Stützle, T., Design and analysis of stochastic local search for the multiobjective traveling salesman problem, Comput Oper Res, 36, 9, 2619-2631, (2009) · Zbl 1179.90302
[24] Lust, T.; Jaszkiewicz, A., Speed-up techniques for solving large-scale biobjective TSP, Comput Oper Res, 37, 3, 521-533, (2010) · Zbl 1173.90534
[25] Paquete, L., Stochastic local search algorithms for multiobjective combinatorial optimizationmethods and analysis, IOS Press, 295, (2005)
[26] Aneja, Y. P.; Nair, K. P.K., Bicriteria transportation problem, Manag Sci, 25, 1, 73-78, (1979) · Zbl 0442.90056
[27] Cohon, J. L., Multiobjective programming and planning, (1978), Academic Press New York · Zbl 0462.90054
[28] Li, H.; Landa-Silva, D., An adaptive evolutionary multi-objective approach based on simulated annealing, Evol Comput, 19, 4, 561-595, (2011)
[29] Johnson, D. S.; McGeoch, L. A., The traveling salesman problema case study in local optimization, Local search in combinatorial optimization, 1, 215-310, (1997) · Zbl 0947.90612
[30] Bentley, J. J., Fast algorithms for geometric traveling salesman problems, ORSA J Comput, 4, 4, 387-411, (1992) · Zbl 0758.90071
[31] Cheng, J.; Zhang, G.; Li, Z.; Li, Y., Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems, Soft Comput, 16, 4, 597-614, (2012) · Zbl 1255.90105
[32] García-Martínez, C.; Cordón, O.; Herrera, F., A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP, Eur J Oper Res, 180, 1, 116-148, (2007) · Zbl 1114.90103
[33] López-Ibáñez, M.; Stützle, T., The automatic design of multiobjective ant colony optimization algorithms, IEEE Trans Evol Comput, 16, 6, 861-875, (2012)
[34] Murata T, Ishibuchi H, Gen M. Specification of genetic search directions in cellular multi-objective genetic algorithms. In: Evolutionary multi-criterion optimization. Berlin, Heidelberg: Springer; 2001. p. 82-95.
[35] Ke, L.; Zhang, Q.; Battiti, R., A simple yet efficient multiobjective combinatorial optimization method using decompostion and Pareto local search, IEEE Trans Cybern, 44, 10, 1808-1820, (2014)
[36] Ke, L.; Zhang, Q.; Battiti, R., Moea/d-acoa multiobjective evolutionary algorithm using decomposition and antcolony, IEEE Trans Cybern, 43, 6, 1845-1859, (2013)
[37] Charon, I.; Hudry, O., The noising methoda new method for combinatorial optimization, Oper Res Lett, 14, 3, 133-137, (1993) · Zbl 0798.90118
[38] Charon I, Hudry O. The noising methods: a survey. In: Essays and surveys in metaheuristics. New York: Springer; 2002. p. 245-261. · Zbl 1005.90051
[39] Reinelt, G., TSPLIB - a traveling salesman problem library, ORSA J Comput, 3, 4, 376-384, (1991) · Zbl 0775.90293
[40] Zitzler, E., Evolutionary algorithms for multiobjective optimization: methods and applications, (1999), Shaker Verlag Ithaca
[41] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Da Fonseca, V. G., Performance assessment of multiobjective optimizersan analysis and review, IEEE Trans Evol Comput, 7, 2, 117-132, (2003)
[42] Hansen, M. P.; Jaszkiewicz, A., Evaluating the quality of approximations to the non-dominated set, IMM, Department of Mathematical Modelling, Technical University of Denmark, (1998)
[43] C.M. Fonseca, L. Paquete, M. López-Ibánez. An improved dimension-sweep algorithm for the hypervolume indicator. In: Congress on evolutionary computation. Vancouver: IEEE; 2006. p. 1157-1163.
[44] Beume, N.; Fonseca, C. M.; López-Ibáñez, M.; Paquete, L.; Vahrenhold, J., On the complexity of computing the hypervolume indicator, IEEE Trans Evol Comput, 13, 5, 1075-1082, (2009)
[45] Fonseca CM, Knowles JD, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. In: Third international conference on evolutionary multi-criterion optimization (EMO 2005), vol. 216; 2005. p. 240.
[46] Mann, H. B.; Whitney, D. R., On a test of whether one of two random variables is stochastically larger than the other, Ann Math Stat, 50-60, (1947) · Zbl 0041.26103
[47] Holm, S., A simple sequentially rejective multiple test procedure, Scand J Stat, 65-70, (1979) · Zbl 0402.62058
[48] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Oper Res, 21, 2, 498-516, (1973) · Zbl 0256.90038
[49] Applegate, D.; Cook, W.; Rohe, A., Chained lin-kernighan for large traveling salesman problems, INFORMS J Comput, 15, 1, 82-92, (2003) · Zbl 1238.90125
[50] Borges PC, Hansen MP. A basis for future successes in multiobjective combinatorial optimization. Technical report. Department of Mathematical Modelling, Technical University of Denmark; 1998.
[51] Laumanns, M.; Thiele, L.; Deb, K.; Zitzler, E., Combining convergence and diversity in evolutionary multiobjective optimization, Evol Comput, 10, 3, 263-282, (2002)
[52] Paquete L, Stützle T. Clusters of non-dominated solutions in multiobjective combinatorial optimization: an experimental analysis. In: Multiobjective programming and goal programming. Berlin, Heidelberg: Springer; 2009. p. 69-77. · Zbl 1176.90512
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.