Distributed hyper-heuristics for real parameter optimization

ABSTRACT

Hyper-heuristics (HHs) are heuristics that work with an arbitrary set of search operators or algorithms and combine these algorithms adaptively to achieve a better performance than any of the original heuristics. While HHs lend themselves naturally for distributed deployment, relatively little attention has been paid so far on the design and evaluation of distributed HHs. To our knowledge, our work is the first to present a detailed evaluation and comparison of distributed HHs for real parameter optimization in an island model. Our set of test functions includes well-known benchmark functions and two realistic space-probe trajectory optimization problems. The set of algorithms available to the HHs include several variants of differential evolution, and uniform random search. Our main conclusion is that some of the simplest HHs are surprisingly successful in a distributed environment, and the best HHs we tested provide a robust and stable good performance over a wide range of scenarios and parameters.

REFERENCES

• 1: B. Addis, A. Cassioli, M. Locatelli, and F. Schoen. Global optimization for the design of space trajectories, 2008. Optimization Online eprint archive http://www.optimization-online.org/DB_HTML/2008/11/2150.html.
• 2: Enrique Alba, Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, 2005
• 3: Maribel García Arenas , Pierre Collet , A. E. Eiben , Márk Jelasity , Juan J. Merelo Guervós , Ben Paechter , Mike Preuß , Marc Schoenauer, A Framework for Distributed Evolutionary Algorithms, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.665-675, September 07-11, 2002
• 4: M. Biazzini, A. Montresor, and M. Brunato. Towards a decentralized architecture for optimization. In Proc. of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS'08), Miami, FL, USA, April 2008.
• 5: E. Burke, G. Kendall, J. Newall, E. Hart, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In Handbook of Metaheuristics, pages 457--474. 2003.
• 6: E. K. Burke , G. Kendall , E. Soubeiga, A Tabu-Search Hyperheuristic for Timetabling and Rostering, Journal of Heuristics, v.9 n.6, p.451-470, December 2003 [doi>10.1023/B:HEUR.0000012446.94732.b6]
• 7: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 8: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 9: E. Hand. Head in the clouds. Nature, 449:963, 2007.
• 10: M. Hollander and D.A. Wolfe. Nonparametric Statistical Methods. Wiley, 2nd edition, 1999.
• 11: M. Jelasity and O. Babaoglu. T-Man: Gossip-based overlay topology management. In S.A. Brueckner, G. Di Marzo Serugendo, D. Hales, and F. Zambonelli, editors, Engineering Self-Organising Systems, volume 3910 of LNCS, pages 1--15. Springer, 2006.
• 12: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 13: Márk Jelasity , Spyros Voulgaris , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.8-es, August 2007 [doi>10.1145/1275517.1275520]
• 14: Joshy Joseph , Craig Fellenstein, Grid Computing, Prentice Hall PTR, Upper Saddle River, NJ, 2003
• 15: D. Ouelhadj and S. Petrovic. A cooperative distributed hyper-heuristic framework for scheduling. In Proc. of the IEEE Int conference on Systems, Man and Cybernetics (SMC 2008), Singapore, 2008.
• 16: Ender Özcan , Burak Bilgin , Emin Erkan Korkmaz, A comprehensive analysis of hyper-heuristics, Intelligent Data Analysis, v.12 n.1, p.3-23, January 2008
• 17: PeerSim. http://peersim.sourceforge.net/.
• 18: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 19: P. Rattadilok, A. Gaw, and R.S. Kwan. Distributed choice function hyper-heuristics for timetabling and scheduling. In Practice and Theory of Automated Timetabling PATAT V, number 3616 in LNCS, pages 51--67. Springer, 2005.
• 20: Rainer Storn , Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, v.11 n.4, p.341-359, December 1997 [doi>10.1023/A:1008202821328]
• 21: Marco Tomassini, Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 22: T. Vinko and D. Izzo. Learning the best combination of solvers in a distributed global optimization environment. In Proceedings of AGO 2007, pages 13--17, Mykonos, Greece, 2007. Gossip-based aggregation in large dynamic networks.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
differential evolution, distributed computing, hyper-heuristics