Combining Drift Analysis and Generalized Schema Theory to Design Efficient Hybrid and/or Mixed Strategy EAs
This provides theoretical guidance for designing efficient hybrid/mixed strategy EAs, addressing a gap for researchers and practitioners in optimization.
The paper tackles the lack of theoretical foundations for designing efficient hybrid and mixed strategy evolutionary algorithms (EAs) by developing a rigorous mathematical framework based on generalized schema theory, fitness levels, and drift analysis, and demonstrates its application on the NP-hard single-machine scheduling problem.
Hybrid and mixed strategy EAs have become rather popular for tackling various complex and NP-hard optimization problems. While empirical evidence suggests that such algorithms are successful in practice, rather little theoretical support for their success is available, not mentioning a solid mathematical foundation that would provide guidance towards an efficient design of this type of EAs. In the current paper we develop a rigorous mathematical framework that suggests such designs based on generalized schema theory, fitness levels and drift analysis. An example-application for tackling one of the classical NP-hard problems, the "single-machine scheduling problem" is presented.