The thesis presents Evolutionary Algorithms as stochastic methods for the optimization of systems.
Evolutionary Algorithms can be developed by transfer and abstraction of processes observed in nature. These algorithms allow the solution of technical problems in as simple and effective a way as in natural evolution.
A survey of the historical development of Evolutionary Algorithms and the early publications is given. The three main schools of Evolutionary Algorithms are presented: Evolutionary Programming, Evolutionary Strategies and Genetic Algorithms. However, instead of describing the differences between these schools the similarities are accentuated. The use of procedures and operators for solving different classes of problems is emphasized. This thought is fundamental to the work.
Based on a simple structure, procedures and operators of Evolutionary Algorithms are presented and explained. This description doesn't accentuate singular algorithms or operators. Instead, the interrelations and dependencies between them are explained. Thus, a hierarchical structure is developed using a homogenous description. This hierarchical structure is itemized with more special cases. Thus, not only a common description is used but the understanding of isolated components as part of a larger system and the interactions between these parts is facilitated and enhanced.
The partition of the population of Evolutionary Algorithms, necessary for the parallel calculation of a large number of variants, develops into the description of population models. The dissertation gives an overview of previous classifications of population models. The partition of the population based on the range of selection is chosen as most appropriate: global, regional and local model. A description of the different population models is given.
For the first time a universal description of neighborhood topologies is given. This description can be used for the regional and the local model. The neighborhood topologies can be extended into arbitrary dimensions. All topologies discussed are special cases of the universal description. The advantage of the universal topology definition is most apparent when comparing the utility of different topologies.
New extensions of the regional model are presented: the use of multiple strategies and the use of competing subpopulations.
The use of multiple strategies opens the possibility for using different parameter combinations for each subpopulation concurrently. This provides multiple enhancements to the Evolutionary Algorithm. The use of different strategies is quicker and more simple compared to multiple runs using different parameter combinations. The results can be presented in a compact and clearly arranged way providing a direct and straightforward evaluation and interpretation of the success of each and all strategies. Additionally, the strategies can supplement each other during a run. This produces better results than using the strategies separately. Besides calculation methods of the success of strategies by the order of subpopulations, methods for the visual comparison of strategies and for the interpretation of the success of the strategies are presented.
By using competing subpopulations not only multiple strategies are employed. In addition, a distribution of the available resources according the success of the subpopulations is achieved. Successful strategies receive more resources than fruitless strategies. Thus, a dynamic distribution of resources preferring successful strategies is attained. For the methods of distribution of resources analogies to the methods of fitness assignment are drawn. By the distribution of resources the strategy parameters are adjusted during a run. This adaptation is not given by the user beforehand or drawn from external knowledge. Instead, the distribution follows the state of the run. Thus, not only multiple strategies are used at the same time. Successful strategies receive a large amount of resources. Fruitless strategies consume only a small percentage of the resources. An "extinction" of temporarily fruitless strategies is prevented. The use of competing subpopulations supplements multiple strategies by efficient distribution of resources simultaneously.
The use of multiple strategies and the use of competing subpopulations provide a further step for the development of efficient and enhanced Evolutionary Algorithms necessary for the solution of large and difficult problems. The advantage of these enhancements of the regional population model are most apparent in the solution of real world problems. These problems gain most from the rapid test of multiple strategies by efficiently distributing available resources.
For the first time extensive methods for the visual analysis of Evolutionary Algorithms are described. The data produced by the Evolutionary Algorithm have a relatively simple structure. Because of the large amount of data produced these data must be processed to make them comprehensible and usable. The presented methods and algorithms enable the visualization of the state and the course of the Evolutionary Algorithm. The visualization can be utilized for different time ranges, different amounts of data, directly available data and derived data. Additionally, methods for visualizing properties of the objective function are presented. These methods are useful when analyzing a system. By using the described visualization methods deeper insight into the work of the Evolutionary Algorithm is gained. This is not available using other methods or buried inside the large amount of data. The extensive examples present the use of the methods on real world and test problems. The information derivable is pointed out.
All presented algorithms, operators and methods are implemented in the Genetic and Evolutionary Algorithm Toolbox for use with Matlab. This toolbox comprises the most complete implementation of Evolutionary Algorithms under the programming environment MATLAB. All examples, graphics and applications presented were calculated and produced using this toolbox. The platform-independent implementation and documentation enables the direct use on all Matlab-enabled computer systems.
Two real world applications are described and solved: optimization of the climate in a greenhouse and optimization of a chopper controller (locomotive). Both applications constitute complex problems. Attention was paid to the incorporation of problem specific knowledge into the optimization process. Using Evolutionary Algorithms the inclusion of problem specific knowledge is possible at different levels. The incorporation of problem specific knowledge accelerates the search for solutions and improves the quality of the solutions.
By employing appropriately tailored tools Evolutionary Algorithms constitute enhanced optimization methods with various properties useful for the practical application. Evolutionary Algorithms can be employed to a broad class of problems. In many applications using Evolutionary Algorithms produced superior results compared to classical optimization methods.
The conclusions discuss future development of Evolutionary Algorithms. Two aspects will be discussed in depth: the coding of the genetic information and aspects of diploidy and polyploidy.
The method of coding the genetic information is a problem specific question. By employing coding customized to a special problem additional knowledge is input into the search process. Often this results in a more focused and more effective search. On the other side, a simple coding employing simple and universal operators has the possibility to create a larger variability. However, the larger universality often leads to a slower and longer search.
In nature the genetic information of most (lower) organisms is coded in a singular (haploid) kind. But nearly all higher organisms posses diploid or polyploid chromosomes. The more complex the organisms get, the more complex is the underlying genetic structure. An overview of earlier publications on the use of diploid information in Evolutionary Algorithms is given. The employment of diploidy can bring the following enhancements to Evolutionary Algorithms: maintenance of the genetic diversity of the population and quicker adaptation regarding changes of the objective function.
The artificial worlds of today's Evolutionary Algorithms using constraint populations, stationary objective functions and a small number of generations do not recognise an advantage of a diploid or polyploid system compared to a sensible designed haploid system. The future development of Evolutionary Algorithms will advance into solving much larger problems, employing multiple objective functions simultaneously and using larger populations. Then the use of diploid systems should be reconsidered as the advantages of diploid systems compared to haploid systems may be significant.
The thesis contains an extensive reference section covering all aspects dealt with. A glossary explains important terms from biology, genetics and Evolutionary Algorithms in their respective context.