Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T16:28:30.522Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  21 February 2008

Thibaut Lust  and
Jacques Teghem
Thibaut Lust
Affiliation:
Laboratory of Mathematics & Operational Research, Faculté Polytechnique de Mons, 9, rue de Houdain, 7000 Mons, Belgium; [email protected]
Jacques Teghem
Affiliation:
Laboratory of Mathematics & Operational Research, Faculté Polytechnique de Mons, 9, rue de Houdain, 7000 Mons, Belgium; [email protected]
Get access

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.

Keywords

Combinatorial multiobjective optimizationhybrid metaheuristicmemetic algorithmTabu SearchKnapsack
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 1: Cooperative methods for multiobjective optimization , January 2008 , pp. 3 - 33
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barichard, V. and Hao, J-K., Genetic tabu search for the multi-objective knapsack problem. J. Tsinghua Sci. Technology 8 (2003) 8–13.
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.
Y. Collette and P. Siarry, Optimisation multiobjectif. Eyrolles (2002).
Czyzak, P. and Jaszkiewicz, A., Pareto simulated annealing – a metaheuristic technique for multiple-objective combinatorial optimization. J. Multi-Crit. Decis. Anal. 7 (1998) 34–47. 3.0.CO;2-6>CrossRef
P. Dagnelie, Statistique théorique et appliquée. De Boeck-Université, Bruxelles (1998).
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. CrossRef
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.
M. Ehrgott and X. Gandibleux, Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers, Boston (2002).
Elaoud, S., Loukil, T. and Teghem, J., Pareto fitness genetic algorithm. Eur. J. Oper. Res. 177 (2007) 1703–1719. CrossRef
X. Gandibleux, M. Sevaux, K. Sörensen and V. T'Kindt, Metaheuristics for Multiobjective Optimisation. Springer (2004).
F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Dordrecht, The Netherlands (1998).
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.
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.
Ishibuchi, H. and Narukawa, K., 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. CrossRef
A. Jaszkiewicz, Genetic Local Search for Multiple Objective Combinatorial Optimization. Technical Report RA-014/98, Institute of Computing Science, Poznan University of Technology (1998).
A. Jaszkiewicz, Experiments done with the momhlib: http://www-idss.cs.put.poznan.pl/jaszkiewicz/momhlib/. Technical report (2000).
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).
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).
Jaszkiewicz, A., Genetic Local Search for Multiple Objective Combinatorial 0ptimization. Eur. J. Oper. Res. 137 (2002) 50–71. CrossRef
Jaszkiewicz, A., 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. CrossRef
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.
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.
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.
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.
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.
P. Moscato, On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Technical Report C3P 826, Caltech Concurrent Computation Program (1989).
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).
Srinivas, N. and Deb, K., Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evol. Comput. 2 (1994) 221–248. CrossRef
R. Steuer, Multiple Criteria Optimization: Theory, Computation and Applications. John Wiley & Sons, New-York (1985).
E-G. Talbi, A taxonomy of hybrid metaheuristics. J. Heuristics 8 (2002) 541–564. CrossRef
Ulungu, E.L., Teghem, J., Fortemps, Ph. and Tuyttens, D., Method, MOSA: A Tool for Solving Multiobjective Combinatorial Optimization Problems. J. Multi-Criteria Decision Analysis 8 (1999) 221–236. 3.0.CO;2-O>CrossRef
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).
E. Zitzler, http://www.tik.ee.ethz.ch/~zitzler/testdata.html.
E. Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, November (1999).
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.
Zitzler, E. and Thiele, L., Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans. Evol. Comput. 3 (1999) 257–271. CrossRef