Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2015 | Buch

Problems to Be Solved Kapitel lesen Erstes Kapitel lesen

Introduction to Evolutionary Computing

verfasst von: A.E. Eiben, J.E. Smith

Verlag: Springer Berlin Heidelberg

Buchreihe : Natural Computing Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The overall structure of this new edition is three-tier: Part I presents the basics, Part II is concerned with methodological issues, and Part III discusses advanced topics. In the second edition the authors have reorganized the material to focus on problems, how to represent them, and then how to choose and design algorithms for different representations. They also added a chapter on problems, reflecting the overall book focus on problem-solvers, a chapter on parameter tuning, which they combined with the parameter control and "how-to" chapters into a methodological part, and finally a chapter on evolutionary robotics with an outlook on possible exciting developments in this field.

The book is suitable for undergraduate and graduate courses in artificial intelligence and computational intelligence, and for self-study by practitioners and researchers engaged with all aspects of bioinspired design and optimization.

Inhaltsverzeichnis

Frontmatter

The Basics

Frontmatter
1. Problems to Be Solved
Abstract
In this chapter we discuss problems to be solved, as encountered frequently by engineers, computer scientists, etc. We argue that problems and problem solvers can, and should, be distinguished, and observe that the field of evolutionary computing is primarily concerned with problem solvers. However, to characterise any problem solver it is useful to identify the kind of problems to which it can be applied. Therefore we start this book by discussing various classes of problems, and, in fact, even different ways of classifying problems.
A. E. Eiben, J. E. Smith
2. Evolutionary Computing: The Origins
Abstract
This chapter provides the reader with the basics for studying evolutionary computing (EC) through this book. We begin with a brief history of the field of evolutionary computing, followed by an introduction to some of the biological processes that have served as inspiration and that have provided a rich source of ideas and metaphors to researchers.We then discuss motivations for working with, and studying, evolutionary computing methods. We end with examples of applications where EC was successfully applied.
A. E. Eiben, J. E. Smith
3. What Is an Evolutionary Algorithm?
Abstract
The most important aim of this chapter is to describe what an evolutionary algorithm (EA) is. In order to give a unifying view we present a general scheme that forms the common basis for all the different variants of evolutionary algorithms. The main components of EAs are discussed, explaining their role and related issues of terminology. This is immediately followed by two example applications to make things more concrete. We then go on to discuss general issues concerning the operation of EAs, to place them in a broader context and explain their relationship with other global optimisation techniques.
A. E. Eiben, J. E. Smith
4. Representation, Mutation, and Recombination
Abstract
As explained in Chapt. 3, there are two fundamental forces that form the basis of evolutionary systems: variation and selection. In this chapter we discuss the EA components behind the first one. Since variation operators work at the equivalent of the genetic level, that is to say they work on the representation of solutions, rather than on solutions themselves, this chapter is subdivided into sections that deal with different ways in which solutions can be represented and varied within the overall search algorithm.
A. E. Eiben, J. E. Smith
5. Fitness, Selection, and Population Management
Abstract
As explained in Chap. 3, there are two fundamental forces that form the basis of evolutionary systems: variation and selection. In this chapter we discuss the EA components behind the second one. Having discussed some typical population management models, and selection operators, we then go on to explicitly look at some situations where diversity is needed, such as multimodal problems, and some approaches to population management, and altering selection, that have been proposed to increase useful diversity.
A. E. Eiben, J. E. Smith
6. Popular Evolutionary Algorithm Variants
Abstract
In this chapter we describe the most widely known evolutionary algorithm variants. This overview serves a twofold purpose: On the one hand, it introduces those historical EA variants without which no EC textbook would be complete together with some more recent versions that deserve their own place in the family tableau. On the other hand, it demonstrates the diversity of realisations of the same basic evolutionary algorithm concept.
A. E. Eiben, J. E. Smith

Methodological Issues

Frontmatter
7. Parameters and Parameter Tuning
Abstract
Chapter 3 presented an algorithmic framework that forms the common basis for all evolutionary algorithms. A decision to use an evolutionary algorithm implies that the user adopts the main design decisions behind this framework. Thus, the main algorithm setup follows automatically: the algorithm is based on a population of candidate solutions that is manipulated by selection, recombination, and mutation operators. To obtain a concrete, executable EA, the user only needs to specify a few details. In this chapter we have a closer look at these details, named parameters. We discuss the notion of EA parameters and explain why the task of designing an evolutionary algorithm can be seen as the problem of finding appropriate parameter values. Furthermore, we elaborate on the problem of tuning EA parameters and provide an overview of different algorithms that can tune EAs with limited user effort.
A. E. Eiben, J. E. Smith
8. Parameter Control
Abstract
The issue of setting the values of evolutionary algorithm parameters before running an EA was treated in the previous chapter. In this chapter we discuss how to do this during a run of an EA, in other words, we elaborate on controlling EA parameters on-the-fly. This has the potential of adjusting the algorithm to the problem while solving the problem. We provide a classification of different approaches based on a number of complementary features and present examples of control mechanisms for every major EA component. Thus we hope to both clarify the points we wish to raise and also to give the reader a feel for some of the many possibilities available for controlling different parameters.
A. E. Eiben, J. E. Smith
9. Working with Evolutionary Algorithms
Abstract
In this chapter we discuss the practical aspects of using EAs. Working with EAs often means comparing different versions experimentally, and we provide guidelines for doing this, including the issues of algorithm performance measures, statistics, and benchmark test suites. The example application (Sect. 9.4) is also adjusted to the special topics here; it illustrates the application of different experimental practices, rather than EA design.
A. E. Eiben, J. E. Smith

Advanced Topics

Frontmatter
10. Hybridisation with Other Techniques: Memetic Algorithms
Abstract
In the preceding chapters we described the main varieties of evolutionary algorithms and described various examples of how they might be suitably implemented for different applications. In this chapter we turn our attention to systems in which, rather than existing as stand-alone algorithms, EA-based approaches are either incorporated within larger systems, or alternatively have other methods or data structures incorporated within them. This category of algorithms is very successful in practice and forms a rapidly growing research area with great potential. This area and the algorithms that form its subject of study are named memetic algorithms (MA). In this chapter we explain the rationale behind MAs, outline a number of possibilities for combining EAs with other techniques, and give some guidelines for designing successful hybrid algorithms.
A. E. Eiben, J. E. Smith
11. Nonstationary and Noisy Function Optimisation
Abstract
Unlike most of the examples we have used so far, real-world environments typically contain sources of uncertainty. This means that if we measure the fitness of a solution more than once, we will not always get the same result. Of course, biological evolution happens in just such a dynamic environment, but there are also many EA applications in environments featuring change or noise when solutions are evaluated. In these nonstationary situations the search algorithm has to be designed so that it can compensate for the unpredictable environment by monitoring its performance and altering some aspects of its behaviour. An objective of the resulting adaptation is not to find a single optimum, but rather to select a sequence of values over time that maximise or minimise some measure of the evaluations, such as the average or worst. This chapter discusses the various sources of unpredictability, and describes the principal adaptations to the basic EA in response to them.
A. E. Eiben, J. E. Smith
12. Multiobjective Evolutionary Algorithms
Abstract
In this chapter we describe the application of evolutionary techniques to a particular class of problems, namely multiobjective optimisation. We begin by introducing this class of problems and the particularly important notion of Pareto optimality. We then look at some of the current state-of-the-art multiobjective EAs (MOEAs) for this class of problems and examine the ways in which they make use of concepts of different evolutionary spaces and techniques for promoting and preserving diversity within the population.
A. E. Eiben, J. E. Smith
13. Constraint Handling
Abstract
In this chapter we return to an issue first introduced in Sect. 1.3, namely that some problems have constraints associated with them. This means that not all possible combinations of variable values represent valid solutions to the problem at hand, and we examine how this impacts on the design of an evolutionary algorithm. This issue has great practical relevance because many real-world problems are constrained. It is also theoretically challenging, since many intractable problems (NP-hard, NP-complete, etc.) are constrained. Unfortunately, constraint handling is not straightforward in an EA, because the variation operators (mutation and recombination) are typically ‘blind’ to constraints. This means that even if the parents satisfy some constraints, there is no guarantee their offspring will. This chapter reviews the most commonly used techniques for constraint handling, identifies a number of common features, and provides some guidance for the algorithm designer.
A. E. Eiben, J. E. Smith
14. Interactive Evolutionary Algorithms
Abstract
This chapter discusses the topic of interactive evolution, where the measure of a solution’s fitness is provided by a human’s subjective judgement, rather than by some predefined model of a problem. Of course, the world around us is full of examples of human intervention in biological evolution, in the form of pets, garden flowers, food crops and farm animals. Applications of Interactive Evolutionary Algorithms (IEAs) range from capturing aesthetics in art and design, to the personalisation of artefacts such as medical devices. When including humans ‘in the loop’ we must consider their peculiar characteristics. On one hand, they can provide insight and guidance beyond simply selecting parents for breeding. On the other, they can be inconsistent, and are prone to fatigue and loss of attention. These factors make it inappropriate to use the ‘traditional’ model of an EA generating possibly thousands of candidate solutions. This chapter describes and explains some of the major algorithmic changes that have been proposed to cope with these issues.
A. E. Eiben, J. E. Smith
15. Coevolutionary Systems
Abstract
In most of this book we have been concerned with problems where the quality of a proposed solution can be relatively easily measured in isolation by some externally provided fitness function. Evaluating a solution may involve an element of random noise, but does not particularly depend on the context in which it is done. However, there are two obvious scenarios in which this set-up does not really hold. The first occurs when a solution represents some strategy or design that works in opposition to some competitor that is itself adapting. The most obvious example here would be adversarial game-playing such as chess. The second comes about when a solution being evolved does not represent a complete solution to a problem, but instead can only be evaluated as part of a greater whole, that together accomplishes some task. An example might be the evolution of a set of traffic-light controllers, each to be sited on a different junction, with fitness reflecting their joint performance in reducing congestion over a day’s simulated traffic. Both of these are examples of coevolution. This chapter gives an overview of the types of scenarios where coevolution might be usefully applied, and of some of the issues involved in designing a successful application.
A. E. Eiben, J. E. Smith
16. Theory
Abstract
In this chapter we present a brief overview of some of the approaches taken to analysing and modelling the behaviour of evolutionary algorithms. The Holy Grail of these efforts is the formulation of predictive models describing the behaviour of an EA on arbitrary problems, and permitting the specification of the most efficient form of optimiser for any given problem. However, (at least in the authors’ opinions) this is unlikely ever to be realised, and most researchers will currently happily settle for techniques that provide any verifiable insights into EA behaviour, even on simple test problems. The reason for what might seem like limited ambition lies in one simple fact: evolutionary algorithms are hugely complex systems, involving many random factors. Moreover, while the field of EAs is fairly young, it is worth noting that the field of population genetics and evolutionary theory has a head start of more than a hundred years, and is still battling against the barrier of complexity.
A. E. Eiben, J. E. Smith
17. Evolutionary Robotics
Abstract
In this chapter we discuss evolutionary robotics (ER), where evolutionary algorithms are employed to design robots. Our emphasis lies on the evolutionary aspects, not on robotics per se. Therefore, we only briefly discuss the ER approaches that work with conventional evolutionary algorithms to optimize some robotic features and pay more attention to systems that can give rise to a new kind of evolutionary algorithms. In particular, we consider groups of mobile robots whose features evolve in real-time, for example, a swarm of Mars explorers or ‘robot moles’ mining ore deep under the surface. In such settings the group of robots is a population itself, which leads to interesting interactions between the robotic and the evolutionary components of the whole system. For robotics, this new kind of ER offers the ability to evolve controllers as well as morphology in partially unknown and changing environments on the fly. For evolutionary computing, autonomous mobile robots provide a special substrate for implementing and studying artificial evolutionary processes in physical entities going beyond the digital systems of today’s evolutionary computing.
A. E. Eiben, J. E. Smith
Backmatter
Metadaten
Titel
Introduction to Evolutionary Computing
verfasst von
A.E. Eiben
J.E. Smith
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-44874-8
Print ISBN
978-3-662-44873-1
DOI
https://doi.org/10.1007/978-3-662-44874-8

Premium Partner

    Bildnachweise