We present in this paper a new multiobjective memetic algorithm scheme called MEMOX. In current multiobjective memetic algorithms, the parents used for recombination are randomly selected. We improve this approach by using a dynamic hypergrid which allows to select a parent located in a region of minimal density. The second parent selected is a solution close, in the objective space, to the first parent. A local search is then applied to the offspring. We experiment this scheme with a new multiobjective tabu search called PRTS, which leads to the memetic algorithm MEMOTS. We show on the multidimensional multiobjective knapsack problem that if the number of objectives increase, it is preferable to have a diversified research rather using an advanced local search. We compare the memetic algorithm MEMOTS to other multiobjective memetic algorithms by using different quality indicators and show that the performances of the method are very interesting.
Mots-clés : combinatorial multiobjective optimization, hybrid metaheuristic, memetic algorithm, Tabu search, knapsack
@article{RO_2008__42_1_3_0,
author = {Lust, Thibaut and Teghem, Jacques},
title = {MEMOTS : a memetic algorithm integrating tabu search for combinatorial multiobjective optimization},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {3--33},
publisher = {EDP-Sciences},
volume = {42},
number = {1},
year = {2008},
doi = {10.1051/ro:2008003},
mrnumber = {2400273},
zbl = {1170.90479},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2008003/}
}
TY - JOUR AU - Lust, Thibaut AU - Teghem, Jacques TI - MEMOTS : a memetic algorithm integrating tabu search for combinatorial multiobjective optimization JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 3 EP - 33 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2008003/ DO - 10.1051/ro:2008003 LA - en ID - RO_2008__42_1_3_0 ER -
%0 Journal Article %A Lust, Thibaut %A Teghem, Jacques %T MEMOTS : a memetic algorithm integrating tabu search for combinatorial multiobjective optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 3-33 %V 42 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2008003/ %R 10.1051/ro:2008003 %G en %F RO_2008__42_1_3_0
Lust, Thibaut; Teghem, Jacques. MEMOTS : a memetic algorithm integrating tabu search for combinatorial multiobjective optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 1, pp. 3-33. doi : 10.1051/ro:2008003. http://www.numdam.org/articles/10.1051/ro:2008003/
[1] and , Genetic tabu search for the multi-objective knapsack problem. J. Tsinghua Sci. Technology 8 (2003) 8-13. | Zbl
[2] and , An empirical study of tabu search for the mokp, in Series of Information & Management Sciences, editor, in Proc. of the First International Workshop on Heuristics, China (2002) Vol. 4, 47-56.
[3] and , Optimisation multiobjectif. Eyrolles (2002).
[4] and , Pareto simulated annealing - a metaheuristic technique for multiple-objective combinatorial optimization. J. Multi-Crit. Decis. Anal. 7 (1998) 34-47. | MR | Zbl
[5] , Statistique théorique et appliquée. De Boeck-Université, Bruxelles (1998).
[6] , , and , A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, in Proc. of the Parallel Problem Solving from Nature VI Conference, Paris, France (2000). Springer Lect. Notes Comput. Sci. 1917 (2000) 849-858.
[7] and , An investigation of niche and species formation in genetic function optimization, in Proc. of the 3rd International Conference on Genetic Algorithms edited by J.D. Schaffer, Washington. Morgan Kaufmann Publishers, San Francisco, CA, USA (1989) 42-50.
[8] and , Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers, Boston (2002). | MR | Zbl
[9] , and , Pareto fitness genetic algorithm. Eur. J. Oper. Res. 177 (2007) 1703-1719. | MR | Zbl
[10] , , and , Metaheuristics for Multiobjective Optimisation. Springer (2004). | MR | Zbl
[11] and , Tabu Search. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). | MR | Zbl
[12] and , Comparison of Multiobjective Memetic Algorithms on 0/1 Knapsack Problems, in 2003 Genetic and Evolutionary Computation Conference. Workshop Program, edited by Alwyn Barry, Chicago, Illinois, USA. AAAI (2003) 222-227.
[13] and , Multi-Objective Genetic Local Search Algorithm. in Proc. of the 1996 International Conference on Evolutionary Computation, edited by Nagoya, Japan Toshio Fukuda and Takeshi Furuhashi. IEEE (1996) 119-124.
[14] and , Recombination of Similar Parents in EMO Algorithms, In Evolutionary Multi-Criterion Optimization. edited by C.A. Coello Coello, A. Hernández Aguirre, and E. Zitzler Third International Conference, EMO 2005, Guanajuato, México. Springer. Lect. Notes Comput. Sci. 3410 (2005) 265-279. | Zbl
[15] , Genetic Local Search for Multiple Objective Combinatorial Optimization. Technical Report RA-014/98, Institute of Computing Science, Poznan University of Technology (1998).
[16] , Experiments done with the momhlib: http://www-idss.cs.put.poznan.pl/jaszkiewicz/momhlib/. Technical report (2000).
[17] On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem - A Comparative Experiment. Technical Report RA-002/2000, Institute of Computing Science, Poznan University of Technology, Poznań, Poland, July (2000).
[18] , A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm. Technical Report RA-003/01, Institute of Computing Science, Poznan University of Technology, Poznan, Poland (2001).
[19] , Genetic Local Search for Multiple Objective Combinatorial 0ptimization. Eur. J. Oper. Res. 137 (2002) 50-71. | MR | Zbl
[20] , On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem - A Comparative Experiment. IEEE Trans. Evol. Comput. 6 (2002) 402-412.
[21] and , The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Multiobjective Optimisation, in 1999 Congress on Evolutionary Computation, Washington, D.C., July 1999. IEEE Service Center (1999) vol. 1, 98-105.
[22] and , M-PAES: A Memetic Algorithm for Multiobjective Optimization. In 2000 Congress on Evolutionary Computation, Piscataway, New Jersey, July 2000. IEEE Service Center (2000) vol. 1, 325-332.
[23] and , Memetic algorithms for multiobjective optimization: issues, methods and prospects, in Recent Advances in Memetic Algorithms, edited by N. Krasnogor, J.E. Smith, and W.E. Hart, Springer (2004) 313-352. | MR
[24] and , PRTS+D et MEMOTS : Nouvelles Métaheuristiques pour l'Optimisation Combinatoire Multicritère. In Actes des articles longs sélectionnés lors du 7ème congrès de la roadef, Lille, February 2006. Presses Universitaires de Valenciennes, (2006) 137-151.
[25] and , Genetic algorithms for the 0/1 knapsack problem. In Methodologies for Intelligent Systems Conference (ISMIS), edited by Z.W Ras and M. Zemankova. Berlin (1994) 134-143.
[26] , On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Technical Report C3P 826, Caltech Concurrent Computation Program (1989).
[27] , Fault tolerant design using single and multicriteria genetic algorithm optimization. Ph.D. thesis, Institute of Technology, Department of Aeronautics and Astronautics, Massachusetts (1995).
[28] and , Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evol. Comput. 2 (1994) 221-248.
[29] , Multiple Criteria Optimization: Theory, Computation and Applications. John Wiley & Sons, New-York (1985). | MR | Zbl
[30] , A taxonomy of hybrid metaheuristics. J. Heuristics 8 (2002) 541-564.
[31] , , and , MOSA Method: A Tool for Solving Multiobjective Combinatorial Optimization Problems. J. Multi-Criteria Decision Analysis 8 (1999) 221-236. | Zbl
[32] , , and , Heuristics for optimising the calculation of hypervolume for multi-objective optimisation problems. In Proc. of the 2005 IEEE Congress on Evolutionary Computation, Edinburgh, UK (2005).
[33] , http://www.tik.ee.ethz.ch/zitzler/testdata.html.
[34] , Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, November (1999).
[35] , , , and , Why Quality Assessment of Multiobjective Optimizers Is Difficult. in Proc. of the Genetic and Evolutionary Computation Conference (GECCO'2002), edited by W.B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller, E. Burke, and N. Jonoska, July 2002. Morgan Kaufmann Publishers, San Francisco, CA, USA (2002) 666-673.
[36] and , Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans. Evol. Comput. 3 (1999) 257-271.
Cité par Sources :
