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.

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.

DOI : 10.1051/ro:2008003
Classification : 90C29, 90C59
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] V. Barichard and J-K. Hao, Genetic tabu search for the multi-objective knapsack problem. J. Tsinghua Sci. Technology 8 (2003) 8-13. | Zbl

[2] V. Barichard and J.K. Hao, 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] Y. Collette and P. Siarry, Optimisation multiobjectif. Eyrolles (2002).

[4] P. Czyzak and A. Jaszkiewicz, Pareto simulated annealing - a metaheuristic technique for multiple-objective combinatorial optimization. J. Multi-Crit. Decis. Anal. 7 (1998) 34-47. | MR | Zbl

[5] P. Dagnelie, Statistique théorique et appliquée. De Boeck-Université, Bruxelles (1998).

[6] K. Deb, S. Agrawal, A. Pratab and T. Meyarivan, 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] K. Deb and D.E. Goldberg, 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] M. Ehrgott and X. Gandibleux, Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers, Boston (2002). | MR | Zbl

[9] S. Elaoud, T. Loukil and J. Teghem, Pareto fitness genetic algorithm. Eur. J. Oper. Res. 177 (2007) 1703-1719. | MR | Zbl

[10] X. Gandibleux, M. Sevaux, K. Sörensen and V. T'Kindt, Metaheuristics for Multiobjective Optimisation. Springer (2004). | MR | Zbl

[11] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998). | MR | Zbl

[12] H. Ishibuchi and S. Kaige, 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] H. Ishibuchi and T. Murata, 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] H. Ishibuchi and K. Narukawa, 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] A. Jaszkiewicz, Genetic Local Search for Multiple Objective Combinatorial Optimization. Technical Report RA-014/98, Institute of Computing Science, Poznan University of Technology (1998).

[16] A. Jaszkiewicz, Experiments done with the momhlib: http://www-idss.cs.put.poznan.pl/jaszkiewicz/momhlib/. Technical report (2000).

[17] A. Jaszkiewicz 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. Jaszkiewicz, 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] A. Jaszkiewicz, Genetic Local Search for Multiple Objective Combinatorial 0ptimization. Eur. J. Oper. Res. 137 (2002) 50-71. | MR | Zbl

[20] A. Jaszkiewicz, 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] J. Knowles and D. Corne, 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] J. Knowles and D. Corne, 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] J. Knowles and D. Corne, 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] T. Lust and J. Teghem, 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] Z. Michalewicz and J. Arabas, 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] P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Technical Report C3P 826, Caltech Concurrent Computation Program (1989).

[27] J.R. Schott, Fault tolerant design using single and multicriteria genetic algorithm optimization. Ph.D. thesis, Institute of Technology, Department of Aeronautics and Astronautics, Massachusetts (1995).

[28] N. Srinivas and K. Deb, Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evol. Comput. 2 (1994) 221-248.

[29] R. Steuer, Multiple Criteria Optimization: Theory, Computation and Applications. John Wiley & Sons, New-York (1985). | MR | Zbl

[30] E-G. Talbi, A taxonomy of hybrid metaheuristics. J. Heuristics 8 (2002) 541-564.

[31] E.L. Ulungu, J. Teghem, Ph. Fortemps and D. Tuyttens, MOSA Method: A Tool for Solving Multiobjective Combinatorial Optimization Problems. J. Multi-Criteria Decision Analysis 8 (1999) 221-236. | Zbl

[32] L. While, L. Bradstreet, L. Barone and P. Hingston, 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] E. Zitzler, http://www.tik.ee.ethz.ch/zitzler/testdata.html.

[34] E. Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, November (1999).

[35] E. Zitzler, M. Laumanns, L. Thiele, C. M. Fonseca and V. Grunert Da Fonseca, 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] E. Zitzler and L. Thiele, Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans. Evol. Comput. 3 (1999) 257-271.

Cité par Sources :