Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications (Numerical Insights)
Format: PDF / Kindle (mobi) / ePub
Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications discusses algorithmic developments in the context of genetic algorithms (GAs) and genetic programming (GP). It applies the algorithms to significant combinatorial optimization problems and describes structure identification using HeuristicLab as a platform for algorithm development.
The book focuses on both theoretical and empirical aspects. The theoretical sections explore the important and characteristic properties of the basic GA as well as main characteristics of the selected algorithmic extensions developed by the authors. In the empirical parts of the text, the authors apply GAs to two combinatorial optimization problems: the traveling salesman and capacitated vehicle routing problems. To highlight the properties of the algorithmic measures in the field of GP, they analyze GP-based nonlinear structure identification applied to time series and classification problems.
Written by core members of the HeuristicLab team, this book provides a better understanding of the basic workflow of GAs and GP, encouraging readers to establish new bionic, problem-independent theoretical concepts. By comparing the results of standard GA and GP implementation with several algorithmic extensions, it also shows how to substantially increase achievable solution quality.
in Section 2.6, • summarize this chapter on GP in Section 2.7, and ﬁnally • refer to a range of outstanding literature in the ﬁeld of theory and praxis of GP in Section 2.8. 2.1 Introduction: Main Ideas and Historical Background As has already been mentioned, one of the central tasks in artiﬁcial intelligence is to make computers do what needs to be done without telling them exactly how to do it. This does not seem to be unnatural since it demands of computers to mimic the human reasoning
operators have been proposed which are designed so that they combat bloating, see for example [Ang98], [PL97b], or [Lan00]. Often we see another tendency of GP that does not fulﬁll Occam’s law, namely that it is prone to producing programs that are overspeciﬁed. This means that programs that are too complex for the problem at hand and that much simpler programs could fulﬁll the given task as well; especially in databased modeling this phenomenon is also known as “overﬁtting.” We shall come back
newly generated chromosomes per generation (no matter if these have been accepted or not). • The question, whether or not an oﬀspring is better than its parents, is answered in the same way as in the context of oﬀspring selection. Figure 4.4 shows the typical development of the actual population size during an exemplary run of RAPGA applied to the ch130 benchmark instance of © 2009 by Taylor & Francis Group, LLC 76 Genetic Algorithms and Genetic Programming FIGURE 4.4: Typical development of
the special case of a cellular model is shown here. . . . . . . . . . . . . Exemplary programs given as rooted, labeled structure trees. Exemplary evaluation of program (a). . . . . . . . . . . . . Exemplary evaluation of program (b). . . . . . . . . . . . . Exemplary crossover of programs (1) and (2) labeled as parent1 and parent2, respectively. Child1 and child2 are possible new oﬀspring programs formed out of the genetic material of their parents. . . . . . . . . . . . . . . . . . . . . . . .
preferred as they can be used in other applications easier. It is, of course, not easy to ﬁnd models that ignore unimportant details and capture the behavior of the system that is analyzed; due to this challenging character of the task of system identiﬁcation, modeling has been considered as “an art” [Mor91]. In the following section we are going to explain the problems of noise and overﬁtting using a simple example. 9.1.2 220.127.116.11 An Example Learning Polynomial Models Let us consider the