On the hybridization of SMS-EMOA and local search for continuous multiobjective optimization

ABSTRACT

In the recent past, hybrid metaheuristics became famous as successful optimization methods. The motivation for the hybridization is a notion of combining the best of two worlds: evolutionary black box optimization and local search. Successful hybridizations in large combinatorial solution spaces motivate to transfer the idea of combining the two worlds to continuous domains as well. The question arises: Can local search also improve the convergence to the Pareto front in continuous multiobjective solutions spaces? We introduce a relay and a concurrent hybridization of the successful multiobjective optimizer SMS-EMOA and local optimization methods like Hooke & Jeeves and the Newton method. The concurrent approach is based on a parameterized probability function to control the local search. Experimental analyses on academic test functions show increased convergence speed as well as improved accuracy of the solution set of the new hybridizations.

REFERENCES

• 1: N. Beume, B. Naujoks, and M. Emmerich. SMS-EMOA: Multiobjective Selection based on Dominated hypervolume. European Journal of Operational Research, 181(3):1653--1669, 2007.
• 2: M. Box, D. Davies, and W. Swann. Nonlinear Optimization Technique, volume 5. Oliver and Boyd Ltd., 1969.
• 3: Kalyanmoy Deb , Tushar Goel, A Hybrid Multi-objective Evolutionary Approach to Engineering Shape Design, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.385-399, March 07-09, 2001
• 4: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. Evolutionary Computation, IEEE Transactions on, 6(2):182--197, 2002.
• 5: M. Ehrgott and X. Gandibleux. Hybrid metaheuristics for multi-objective combinatorial optimization. In F. Almeida, M. J. B. Aguilera, and C. Blum, editors, Hybrid Metaheuristics, volume 4030 of Lecture Notes in Computer Science, pages 221--259. Springer, 2006.
• 6: M. T. M. Emmerich, A. H. Deutz, and N. Beume. Gradient-based/evolutionary relay hybrid for computing pareto front approximations maximizing the s-metric. In Hybrid Metaheuristics, pages 140--156, 2007.
• 7: J. Fliege, L. M. G. Drummond, and B. Svaiter. Newton's method for multiobjective optimization. Optimization Online, 2008.
• 8: J. Fliege and B. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479--494, 2000.
• 9: Robert Hooke , T. A. Jeeves, `` Direct Search'' Solution of Numerical and Statistical Problems, Journal of the ACM (JACM), v.8 n.2, p.212-229, April 1961 [doi>10.1145/321062.321069]
• 10: H. Ishibuchi and T. Murata. Multi-objective genetic local search algorithm. In International Conference on Evolutionary Computation, pages 119--124, 1996.
• 11: H. Ishibuchi and K. Narukawa. Some issues on the implementation of local search in evolutionary multiobjective optimization. In Genetic and Evolutionary Computation - GECCO 2004, pages 1246--1258, 2004.
• 12: H. Ishibuchi and T. Yoshida. Implementation of local search in hybrid multi-objective genetic algorithms: A case study on owshop scheduling. In Proc. of fourth Asia-Pacific Conference on Simulated Evolution And Learning, pages 193--197, 2002.
• 13: H. Ishibuchi, T. Yoshida, and T. Murata. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. on Evolutionary Computation, 7:204--223, 2003.
• 14: A. Jaszkiewicz. Genetic local search for multiple objective combinatorial optimization. Technical report, 1998.
• 15: Saúl Zapotecas Martínez , Carlos A. Coello Coello, A Proposal to Hybridize Multi-Objective Evolutionary Algorithms with Non-gradient Mathematical Programming Techniques, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_83]
• 16: G. R. Raidl. A unified view on hybrid metaheuristics. In F. Almeida, M. J. B. Aguilera, and C. Blum, editors, Hybrid Metaheuristics, volume 4030 of Lecture Notes in Computer Science, pages 1--12. Springer, 2006.
• 17: Oliver Schuetze , Gustavo Sanchez , Carlos A. Coello Coello, A new memetic strategy for the numerical treatment of multi-objective optimization problems, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389232]
• 18: H. Schwefel. John Wiley&Sons, Inc., 1995.
• 19: Pradyumn Kumar Shukla, Gradient Based Stochastic Mutation Operators in Evolutionary Multi-objective Optimization, Proceedings of the 8th international conference on Adaptive and Natural Computing Algorithms, Part I, April 11-14, 2007, Warsaw, Poland [doi>10.1007/978-3-540-71618-1_7]
• 20: Karthik Sindhya , Kalyanmoy Deb , Kaisa Miettinen, A Local Search Based Evolutionary Multi-objective Optimization Approach for Fast and Accurate Convergence, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_81]
• 21: R. Steuer. Multiple Criteria Optimization: Theory, Computation and Application. John Wiley&Sons, New York, NY, 1985.
• 22: D. Sudholt. Computational Complexity of Evolutionary Algorithms, Hybridizations, and Swarm Intelligence. PhD thesis, Technische Universtät Dortmund, Dortmund, 2008.
• 23: E.-G. Talbi, A Taxonomy of Hybrid Metaheuristics, Journal of Heuristics, v.8 n.5, p.541-564, September 2002 [doi>10.1023/A:1016540724870]
• 24: Eckart Zitzler , Kalyanmoy Deb , Lothar Thiele, Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation, v.8 n.2, p.173-195, June 2000 [doi>10.1162/106365600568202]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms

Keywords:
hybrid evolutionary multiobjective algorithm, hybrid metaheuristics, local search, memetic algorithms