Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems. (English) Zbl 1255.90105
Summary: This paper proposes a framework named multi-objective ant colony optimization based on decomposition (MoACO/D) to solve bi-objective traveling salesman problems (bTSPs). In the framework, a bTSP is first decomposed into a number of scalar optimization subproblems using Tchebycheff approach. To suit for decomposition, an ant colony is divided into many subcolonies in an overlapped manner, each of which is for one subproblem. Then each subcolony independently optimizes its corresponding subproblem using single-objective ant colony optimization algorithm and all subcolonies simultaneously work. During the iteration, each subproblem maintains an aggregated pheromone trail and an aggregated heuristic matrix. Each subcolony uses the information to solve its corresponding subproblem. After an iteration, a pheromone trail share procedure is evoked to realize the information share of those subproblems solved by common ants. Three MoACO algorithms designed by, respectively, combining MoACO/D with AS, MMAS and ACS are presented. Extensive experiments conducted on ten bTSPs with various complexities manifest that MoACO/D is both efficient and effective for solving bTSPs and the ACS version of MoACO/D outperforms three well-known MoACO algorithms on large bTSPs according to several performance measures and median attainment surfaces.
MSC:
| 90C27 | Combinatorial optimization |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
decomposition; multi-objective; ant colony optimization; bi-objective traveling salesman problemsReferences:
| [1] | Angus D, Woodward C (2009) Multiple objective ant colony optimisation. Swarm Intell 3(1):69–85 · doi:10.1007/s11721-008-0022-4 |
| [2] | Barán B, Schaerer M (2003) A multiobjective ant colony system for vehicle routing problem with time windows. In: Proceedings of the twenty first IASTED international conference on applied informatics, pp 97–102 |
| [3] | Bullnheimer B, Hartl R, Strauss C (1999) An improved ant system algorithm for the vehicle routing problem. Ann Oper Res 89:319–328 · Zbl 0937.90125 · doi:10.1023/A:1018940026670 |
| [4] | Cardoso P, Jesus M, Márquez A (2011) {\(\epsilon\)}-DANTE: an ant colony oriented depth search procedure. Soft Comput 15:149–182 · doi:10.1007/s00500-010-0543-9 |
| [5] | Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197 · doi:10.1109/4235.996017 |
| [6] | Doerner K, Gutjahr W, Hartl R, Strauss C, Stummer C (2006) Pareto ant colony optimization with ILP preprocessing in multiobjective project portfolio selection. Eur J Oper Res 171(3):830–841 · Zbl 1116.90087 · doi:10.1016/j.ejor.2004.09.009 |
| [7] | Dorigo M, Gambardella L (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66 · doi:10.1109/4235.585892 |
| [8] | Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge · Zbl 1092.90066 |
| [9] | Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Tran Syst Man Cybern Part B 26(1):29–41 · doi:10.1109/3477.484436 |
| [10] | Fonseca C, Fleming P (1996) On the performance assessment and comparison of stochastic multiobjective optimizers. In: Vogit H-M, Ebeling W, Rechenberg I, Schwefel HS (eds) Proceedings of PPSN-IV, fourth international conference on parallel problem solving from nature. Lecture notes in computer science, vol 1141. Springer, Berlin, pp 584–593 |
| [11] | Gambardella L, Taillard E, Agazzi G (1999) MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, pp 63–76 |
| [12] | García-Martínez C, Cordón O, Herrera F (2007) 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 · Zbl 1114.90103 · doi:10.1016/j.ejor.2006.03.041 |
| [13] | Hansen M (1998) Metaheuristics for multiple objective combinatorial optimization. PhD thesis |
| [14] | Hansen M, Jaszkiewicz A (1998) Evaluating the quality of approximations to the non-dominated set. Tech. rep. Technical report IMM-REP-1998-7, Technical University of Denmark |
| [15] | Iredi S, Merkle D, Middendorf M (2001) Bi-criterion optimization with multi colony ant algorithms. In: Zitzler E, Deb K, Thiele L, Coello C, Corne D (eds) First International Conference on evolutionary multi-criterion optimization. Lecture notes in computer science, vol 1993. Springer, Berlin, pp 359–372 |
| [16] | Ishibuchi H, Murata T (1998) 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 · doi:10.1109/5326.704576 |
| [17] | Jaszkiewicz A (2002) On the performance of multiple-objective genetic local search on the 0/1 knapsack problem–a comparative experiment. IEEE Trans Evol Comput 6(4):402–412 · doi:10.1109/TEVC.2002.802873 |
| [18] | Jaszkiewicz A, Zielniewicz P (2009) Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem. Eur J Oper Res 193:885–890 · Zbl 1151.90043 · doi:10.1016/j.ejor.2007.10.054 |
| [19] | Knowles J (2005) A summary-attainment-surface plotting method for visualizing the performance of stochastic multiobjective optimizers. In: Proceedings of the 5th international conference on intelligent systems design and applications. IEEE, Washington, DC, USA, pp 552–557 |
| [20] | López-Ibáñez M, Stützle T (2010a) Automatic configuration of multi-objective ant colony optimization algorithms. In: Dorigo M, Birattari M, Di Caro G, Doursat R, Engelbrecht A, Floreano D, Gambardella L, Grob R, Sahin E, Stützle T, Sayama H (eds) ANTS 2010. Lecture notes in computer science, vol 6234, Springer, Berlin, pp 95–106 |
| [21] | López-Ibáñez M, Stützle T (2010b) The impact of design choices of multiobjective ant colony optimization algorithms on performance: an experimental study on the biobjective TSP. In: Proceedings of the 12th annual conference on genetic and evolutionary computation, ACM, Portland, Oregon, USA, pp 71–78 |
| [22] | López-Ibáñez M, Paquete L, Stützle T (2004) On the design of ACO for the biobjective quadratic assignment problem. In: Dorigo M (ed) Proceedings of ANTS. Lecture notes in computer science, vol 3172, Springer, Heidelberg, pp 224–225 |
| [23] | López-Ibáñez M, Paquete L, Stützle T (2010) Empirical methods for the analysis of optimization algorithms. In: Dorigo M, Birattari M, Di Caro G, Doursat R, Engelbrecht A, Floreano D, Gambardella L, Grob R, Sahin E, Stützle T, Sayama H (eds) Exploratory analysis of stochastic local search algorithms in biobjective optimization. Springer, Berlin, pp 209–222 |
| [24] | Mariano C, Morales E (1999) A multiple Ant-Q algorithm for the design of water distribution irrigation network. Tech. rep. Technical report HC-9904, Instituto Mexicano de Tecnología del Agua |
| [25] | Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Boston · Zbl 0949.90082 |
| [26] | Peng W, Zhang Q, Li H (2009) Comparison between MOEA/D and NSGA-II on the multi-objective travelling salesman problem. In: Goh C, Ong Y, Tan K (eds) Multi-objective memetic algorithms. Studies in computational intelligence, vol 171. Springer, Berlin, pp 309–324 · Zbl 1160.90679 |
| [27] | Stützle T, Hoos H (2000) MAX–MIN ant system. Future Gener Comput Syst 16(8):889–914 · doi:10.1016/S0167-739X(00)00043-1 |
| [28] | T’kindt V, Monmarché N, Tercinet F, Laügt D (2002) An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. Eur J Oper Res 142(2):250–257 · Zbl 1082.90592 · doi:10.1016/S0377-2217(02)00265-5 |
| [29] | Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731 · doi:10.1109/TEVC.2007.892759 |
| [30] | Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms–a comparative case study. In: Eiben A, Bäck T, Schaerer M, Schwefel H (eds) Parallel problem solving from nature V. Springer, Berlin, pp 292–301 |
| [31] | Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271 · doi:10.1109/4235.797969 |
| [32] | Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. Tech. rep. Switzerland, Tech. rep. TIK-Rep, 103 |
| [33] | Zitzler E, Thiele L, Laumanns M, Fonseca C, Fonseca V (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132 · doi:10.1109/TEVC.2003.810758 |
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.
