MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization

Thibaut Lust; Jacques Teghem

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 1, page 3-33
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Lust, Thibaut, and Teghem, Jacques. "MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization." RAIRO - Operations Research 42.1 (2008): 3-33. <http://eudml.org/doc/250424>.

@article{Lust2008,
abstract = { 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. },
author = {Lust, Thibaut, Teghem, Jacques},
journal = {RAIRO - Operations Research},
keywords = {Combinatorial multiobjective optimization; hybrid metaheuristic; memetic algorithm; Tabu Search; Knapsack; combinatorial multiobjective optimization; tabu search},
language = {eng},
month = {2},
number = {1},
pages = {3-33},
publisher = {EDP Sciences},
title = {MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization},
url = {http://eudml.org/doc/250424},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Lust, Thibaut
AU - Teghem, Jacques
TI - MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization
JO - RAIRO - Operations Research
DA - 2008/2//
PB - EDP Sciences
VL - 42
IS - 1
SP - 3
EP - 33
AB - 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.
LA - eng
KW - Combinatorial multiobjective optimization; hybrid metaheuristic; memetic algorithm; Tabu Search; Knapsack; combinatorial multiobjective optimization; tabu search
UR - http://eudml.org/doc/250424
ER -

References

top
  1. V. Barichard and J-K. Hao, Genetic tabu search for the multi-objective knapsack problem. J. Tsinghua Sci. Technology8 (2003) 8–13.  
  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.  
  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).  
  9. S. Elaoud, T. Loukil and J. Teghem, Pareto fitness genetic algorithm. Eur. J. Oper. Res.177 (2007) 1703–1719.  
  10. X. Gandibleux, M. Sevaux, K. Sörensen and V. T'Kindt, Metaheuristics for Multiobjective Optimisation. Springer (2004).  
  11. F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998).  
  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.  
  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.  
  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.  
  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).  
  30. E-G. Talbi, A taxonomy of hybrid metaheuristics. J. Heuristics8 (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 Analysis8 (1999) 221–236.  
  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, .  URIhttp://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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.