Designing Efficient Genetic and Evolutionary Algorithm Hybrids

Genetic and evolutionary algorithms (GEAs) are being employed to solve a wide range of problems in search and optimization. Most real-world applications use GEAs in combination with domain specific methods to achieve superior performance. Such combinations, often referred to as hybrids, stand to gain much from a system-level framework for efficiently combining global searchers such as GEAs with domain-specific and local searchers. This chapter presents the foundations for such a framework. The theory herein attempts to attain the optimal division of labor between global and local search so that the desired solution quality can be obtained in the minimum time, or given a fixed time budget, the best solution quality can be obtained. It relies on a two-fold decomposition: the hybrid is composed of a global searcher and a local searcher, and the search space is divided into basins of attraction from where the local search can lead to the desired solution quality. The framework allows us to choose between different schedules so as to maximize chances of success. The framework utilizes knowledge of run duration theory and uses the quality of solution at each generation to compute the parameters needed by the theory. The study also looks at characteristics of a class of functions (known as traps) that determine the speedups that can be obtained from using local search.