Embedding Branch and Bound within Evolutionary Algorithms
|
C. Cotta, J.M. Troya Applied Intelligence 18(2):137-153, 2003 © Kluwer Academic Publishers 2003. All rights reserved. |
|
Abstract
|
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. |
|
|
 |
|
Download BibTEX entry | |
||||
|
 |
|
Electronic version available from Kluwer | |
|
|
Preprint version (265K) | |
[Back to publications page].