Loading...
Please wait, while we are loading the content...
Similar Documents
Fitness Landscapes and Memetic Algorithm Design 3.1 Introduction 3.2 Fitness Landscapes of Combinatorial Problems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Merz, Peter Freisleben, Bernd |
| Copyright Year | 1999 |
| Abstract | The notion of tness landscapes has been introduced to describe the dynamics of evolutionary adaptation in nature 40] and has become a powerful concept in evolutionary theory. Fitness landscapes are equally well suited to describe the behavior of heuristic search methods in optimization, since the process of evolution can be thought of as searching a collection of genotypes in order to nd the genotype of an organism with highest tness and thus highest chance of survival. Thinking of a heuristic search method as a strategy to \navigate" in the tness landscape of a given optimization problem may help in predicting the performance of a heuristic search algorithm if the structure of the landscape is known in advance. Furthermore, the analysis of tness landscapes may help in designing highly eeective search algorithms. In the following we show how the analysis of tness landscapes of combinatorial optimization problems can aid in designing the components of memetic algorithms. However, some of the presented concepts can also be utilized for the development of other search algorithms , including genetic algorithms and neighborhood search algorithms (e.g. simulated annealing and tabu search). In combinatorial optimization, the number of (candidate) solutions of a given problem is nite. Due to the fact that the complete enumeration of the search space is in many cases impractical (many combinatorial optimization problems are known to be NP-hard 12]), only a small fraction of all solutions can be evaluated and thus the structure of the problem must be exploited to nd optimum or near optimum solutions. To identify the structure of a given problem, the idea of tness landscape analysis appears to be a promising approach. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
