The roles of local search, model building and optimal mixing in evolutionary algorithms from a bbo perspective

ABSTRACT

The inclusion of local search (LS) techniques in evolutionary algorithms (EAs) is known to be very important in order to obtain competitive results on combinatorial and real-world optimization problems. Often however, an important source of the added value of LS is an understanding of the problem that allows performing a partial evaluation to compute the change in quality after only small changes were made to a solution. This is not possible in a Black-Box Optimization (BBO) setting. Here we take a closer look at the added value of LS when combined with EAs in a BBO setting. Moreover, we consider the interplay with model building, a technique commonly used in Estimation-of-Distribution Algorithms (EDAs) in order to increase robustness by statistically detecting and exploiting regularities in the optimization problem. We find, using two standardized hard BBO problems from EA literature, that LS can play an important role, especially in the interplay with model building in the form of what has become known as substructural LS. However, we also find that optimal mixing (OM), which indicates that operations in a variation operator are directly checked whether they lead to an improvement, is a superior combination of LS and EA.

References

1. E. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. John Wiley & Sons Inc., New York, New York, 1997.
2. K. Deb and D. E. Goldberg. Sufficient conditions for arbitrary binary functions. Annals of Mathematics and Artificial Intelligence, 10(4):385--408, 1994.
3. F. Glover and M. Laguna. Tabu Search. Kluwer, Norwell, Massachusetts, 1997.
4. D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learing. Addison Wesley, Reading, Massachusetts, 1989.
5. G. R. Harik, F. G. Lobo, and K. Sastry. Linkage learning via probabilistic modeling in the extended compact genetic algorithm (ecga). In M. Pelikan et al., editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 39--61. Springer-Verlag, Berlin, 2006.
6. H. H. Hoos and T. Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco, California, 2005.
7. A. Juels and M. Wattenberg. Stochastic hillclimbing as a baseline method for evaluating genetic algorithms. UC Berkeley technical report CSD-94-834, 1994.
8. C. F. Lima, M. Pelikan, F. G. Lobo, and D. E. Goldberg. Loopy substructural local search for the Bayesian optimization algorithm. In T. Stützle et al., editors, Proceedings of the Second International Workshop on Engineering Stochastic Local Search Algorithms - SLS-2009, pages 61--75, Berlin, 2009. Springer-Verlag.
9. C. F. Lima, M. Pelikan, K. Sastry, M. Butz, D. E. Goldberg, and F. G. Lobo. Substructural neighborhoods for local search in the Bayesian optimization algorithm. In T. P. Runarsson et al., editors, Parallel Problem Solving from Nature - PPSN IX, pages 232--241, Berlin, 2006. Springer-Verlag.
10. J. A. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea. Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithms. Springer-Verlag, Berlin, 2006.
11. P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report Caltech Concurrent Computation Program, Report 826, California Institute of Technology, Pasadena, California, 1989.
12. M. Pelikan, K. Sastry, and E. Cantú-Paz. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer-Verlag, Berlin, 2006.
13. M. Pelikan, K. Sastry, D. E. Goldberg, M. V. Butz, and M. Hauschild. Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap. In G. Raidl et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO-2009, pages 851--858, New York, New York, 2009. ACM Press.
14. E. Radetic and M. Pelikan. Spurious dependencies and eda scalability. In J. Branke et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO-2010, pages 303--310, New York, New York, 2010. ACM Press.
15. E. Radetic, M. Pelikan, and D. E. Goldberg. Effects of a deterministic hill climber on hBOA. In G. Raidl et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO-2009, pages 437--444, New York, New York, 2009. ACM Press.
16. S. Russell and P. Norvig. Artificial Intelligence - A Modern Approach. Prentice-Hall Int. Limited, London, 1995.
17. D. Thierens. Scalability problems of simple genetic algorithms. Evolutionary Computation, 7(4):331--352, 1999.
18. D. Thierens. The linkage tree genetic algorithm. In R. Schaefer et al., editors, Parallel Problem Solving from Nature - PPSN XI, pages 264--273, Berlin, 2010. Springer-Verlag.
19. D. Thierens and P. A. N. Bosman. Optimal mixing evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference - GECCO-2011, New York, New York, 2011. ACM Press.
20. D. Thierens and D. E. Goldberg. Mixing in genetic algorithms. In Proceedings of the 5th International Conference on Genetic Algorithms, pages 38--45, San Francisco, California, 1993. Morgan Kaufmann.
21. N. L. J. Ulder, E. H. L. Aarts, H.-J. Bandelt, P. J. M. van Laarhoven, and E. Pesch. Genetic local search algorithms for the traveling salesman problem. In H.-P. Schwefel and R. Männer, editors, Parallel Problem Solving from Nature - PPSN, pages 109--116, Berlin, 1991. Springer-Verlag.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming