A study of hybridisation techniques and their application to the design of evolutionary algorithms
Carlos Cotta dash, Porras · 1998
Evolutionary algorithms are heuristic optimisation techniques based on the principles of natural evolution, namely adaptation and survival of the fittest. The simplicity and wide applicability of these techniques has motivated that even canonical models of evolutionary algorithms were considered as robust and effective optimisation techniques, globally better than other specialised algorithms. However, recent theoretical results (the so-called No Free Lunch Theorem) have shown that any optimisation algorithm is inherently limited if it is applied to an unknown problem (i.e., if no problem-specific knowledge is used). Thus, augmenting the basic model with problem–knowledge is a requirement for ensuring good performance of the algorithm. In its broadest sense, such addition of knowledge is termed hybridisation. Due to their highly parameterisable nature (problem representation, operators, evolution mode, . . .), evolutionary algorithms are specifically adequate for hybridisation. This thesis studies different mechanisms for carrying out hybridisation in this context, striving to produce a set of useful tools and design guidelines for constructing effective optimisation algorithms within the framework of evolutionary algorithms. After analysing the applicability of the No Free Lunch Theorem to evolutionary algorithms, the first part of the thesis presents a global approach to hybridisation. More precisely, two major hybridisation models are distinguished: including problem–knowledge in the core of the algorithm (strong hybridisation) or combining different optimisation algorithms (weak hybridisation). The former model is formalised using the classical concept of adaptive system. This concept is used as a structural unit for developing grained adaptive systems, a formalisation of the latter model. A study of the computational power of both models shows that they two have Turing-capabilities. This implies that an arbitrary computation (and hence an arbitrary search) can be performed by these systems, provided that enough problem knowledge is available. Furthermore, both models are shown to be equally powerful and hence the same results can be, in principle, achieved by using any of them. Subsequently, strong hybridisation is studied. Designing an optimal strong hybrid evolutionary algorithm is characterised as a combinatorial optimisation problem whose resolution is shown to be NPhard. Thus, two methodological heuristics are studied, focusing in the addition of knowledge to operators and representations respectively. Firstly, the analysis of the fitness variance of formae (generalised schemata) is investigated in two ways: for selecting an operator from a set of preexisting operators (inverse analysis) and for designing new operators (direct analysis). The efectiveness of both versions of the analysis is confirmed on a real-world problem, the optimisation of a flowshop system. Secondly, the utilisation of non-homogeneous representations (representations in which certain solutions which are known to be nonoptimal are excluded, and promising solutions are represented more than once) is considered. These representations are theoretically studied and empirically evaluated on instances of the binary multidimensional knapsack problem. The next part of the thesis concentrates on weak hybridisation. As for strong hybridisation, two method-