Embedding branch and bound within evolutionary algorithms

摘要

A framework for hybridizing evolutionary algorithms with the branch-and-bound algorithm (B&B) is presented in this paper. This framework is based on using B&B as an operator embedded in the evolutionary algorithm. The resulting hybrid operator will intelligently explore the dynastic potential (possible children) of the solutions being recombined, providing the best combination of formae (generalized schemata) that can be constructed without introducing implicit mutation. As a basis for studying this operator, the general functioning of transmitting recombination is considered. Two important concepts are introduced, compatibility sets, and granularity of the representation. These concepts are studied in the context of different kinds of representation: orthogonal, non-orthogonal separable, and non-separable. The results of an extensive experimental evaluation are reported. It is shown that this model can be useful when problem knowledge is available in the form of an optimistic evaluation function. Scalability issues are also considered. A control mechanism is proposed to alleviate the increasing computational cost of the algorithm for highly multidimensional problems. [References: 36]