Opportunistic evolution: efficient evolutionary computation on large-scale computational grids

ABSTRACT

We examine opportunistic evolution, a variation of master-slave distributed evaluation designed for deployment of evolutionary computation to very large grid computing architectures with limited communications, severe evaluation overhead, and wide variance in evaluation node speed. In opportunistic evolution, slaves receive some N individuals at a time, evaluate them, and then run those individuals through their own mini evolutionary loop until some fixed wall clock time has been exceeded. Our implementation of opportunistic evolution may be used in conjunction with either a generational or, for maximum throughput, an asynchronous steady-state evolutionary model in the master. Opportunistic evolution is strongly exploitative. We perform initial experiments comparing the technique with a traditional master/slave model, and suggest possible classes of problems for which it might be apropos.

REFERENCES

• 1: Ricardo Bianchini , Christopher M. Brown, Parallel Genetic Algorithms on Distributed-Memory Architectures, University of Rochester, Rochester, NY, 1993
• 2: R. Bradwell and K. Brown. Parallel asynchronous memetic algorithms. In E. Canú-Paz and B. Punch, editors, Evolutionary Computation and Parallel Processing, pages 157---159, 1999.
• 3: Adora E. Calaor , Augusto Y. Hermosilla , Bobby O. Corpus, Jr., Parallel Hybrid Adventures with Simulated Annealing and Genetic Algorithms, Proceedings of the 2002 International Symposium on Parallel Architectures, Algorithms and Networks, p.39, May 22-24, 2002
• 4: E. Cantú-Paz. A survey of parallel genetic algorithms. Technical Report 97003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 117 Transportation Building, 104 S. Mathews Ave., Urbana, IL 61801, 1997.
• 5: E. Cantú-Paz. Designing Efficient and Accurate Parallel Genetic Algorithms. PhD thesis, University of Illinois, 1999.
• 6: J. Digilakis and K. Margaritis. Performance comparison of memetic algorithms. Journal of Applied Mathematics and Computation, 158:237--252, October 2004.
• 7: J. Grefenstette. Parallel adaptive algorithms for function optimization. Technical Report CS-81-19, Computer Science Department, Vanderbilt Univesity, P.o. Box 1679, Station B, Nashville, TN 37235, 1981.
• 8: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 9: S. Luke, L. Panait, G. Balan, S. Paus, Z. Skolicki, E. Popovici, J. Harrison, J. Bassett, R. Hubley, and A. Chircop. ECJ: A Java-based evolutionary computation research system. http://cs.gmu.edu/$\sim$eclab/projects/ecj/, 2007.
• 10: M. Mitchell, S. Forest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Proceedings of the First European Conference on Artifical Life, 1992.
• 11: M. Nowostawski and R. Poli. Parallel genetic algorithm taxonomy. In Knowledge-Based Intelligent Information Engineering Systems, pages 88--92, 1999.
• 12: ORIGIN: Evolutionary SDK. http://www.parabon.com/developers/origin.jsp, 2008.
• 13: Zbigniew Maciej Skolicki , Kenneth A. Jong, An analysis of island models in evolutionary computation, George Mason University, Fairfax, VA, 2007
• 14: J. Tang, M. H. Lim, Y. S. Ong, and M. J. Er. Parallel memetic algoithm with selective local search for large scale quadratic assignment problems. International Journal of Innovative Computing, Information and Control, 2(6):1399--1416, 2006.
• 15: Richard A. Watson , Jordan B. Pollack, Compositional evolution: interdisciplinary investigations in evolvability, modularity, and symbiosis, Brandeis University, Waltham, MA, 2002
• 16: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms

Keywords:
distributed evolutionary computation