Samenvatting
Introduction to Evolutionary Computing - Book Summary
- Instelling
- Vrije Universiteit Amsterdam (VU)
Complete book summary for Introduction to Evolutionary Computing by A.E. Eiben and J.E. Smith.
[Meer zien]Voorbeeld 4 van de 89 pagina's
Voorbeeld 4 van de 89 pagina's
In winkelwagengesponsord bericht van onze partner
Gekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Verkoper
Volgen
Voorbeeld van de inhoud
Introduction to Evolutionary Computing - Book Summary1 Problems to Be Solved
In this chapter we discuss problems to be solved, as encountered frequently by engineers, computer
scientists, etc. The field of evolutionary computing is primarily concerned with problem solvers. There
are various classes of problems to solve, and in fact, these problems can be classified in different ways.
1.1 Optimisation, Modelling, and Simulation Problems
The classification of problems used in this section is based on a “black box” model of computer systems.
Informally, we can think of any computer-based system as follows. A computer system is composed of
three elements; inputs, model, outputs.
The system initially sits, awaiting some input from either a person, a sensor, or another computer. When
input is provided, the system processes that input through some computational model, whose details are
not specified in general (hence the name black box). The purpose of this model is to represent some
aspects of the world relevant to the particular application.
Examples of a model
● a formula that calculates the total route length from a list of consecutive locations
● a statistical tool estimating the likelihood of rain given some meteorological input data
● a mapping from real time data regarding a car’s speed to the level of acceleration necessary to
approach some prespecified target speed
● a complex series of rules that transform a series of keystrokes into an on screen version of the
page you are reading now
After processing the input the system provides some outputs.
Examples of outputs
● messages on screen
● values written to a file
● commands sent to an actuator such as an engine
Depending on the application, there might be one or more inputs of different types, and the computational
model might be simple, or very complex. Importantly, knowing the model means that we can compute the
output for any input
1.1.1 Optimisation
In an optimisation problem the model is known, together with the desired output (or a description of the
desired output), and the task is to find the input(s) leading to this output.
1
,Introduction to Evolutionary Computing - Book Summary
Examples
● Travelling salesman problem
● Eight-queens problem
1.1.2 Modelling
In a modelling or system identification problem, corresponding sets of inputs and outputs are known, and
a model of the system is sought that delivers the correct output for each known input. In terms of human
learning this corresponds to finding a model of the world that matches our previous experience, and can
hopefully generalize to as-yet unseen examples.
It is important to note that modelling problems can be transformed into optimisation problems by
designating the error rate of a model as the quantity to be minimised or its hit rate to be maximised.
Examples
● Stock exchange
● Task of identifying traffic signs in images - perhaps from video feeds in a smart car
1.1.3 Simulation
In a simulation problem we know the system model and some inputs, and need to compute the outputs
corresponding to these inputs.
Advantages of simulators:
● Simulation can be more economical than studying the real-world effects. The real-world
alternative may not be feasible at all.
● Simulation can be the tool that allows us to look into the future
Examples
● Electronic circuit, say, a filter cutting out low frequencies in a signal
● Weather forecast system
1.2 Search Problems
A deeply rooted assumption behind the black box view of systems is that a computational model is
directional: it computes from the inputs towards the outputs and it cannot simply be inverted. The process
of problem-solving can be viewed as a search through a potentially huge set of possibilities to find the
desired solution. Consequently, the problems that are to be solved this way can be seen as search
problems. Optimisation and modelling problems can be naturally perceived as search problems, while this
does not hold for simulation problems.
2
,Introduction to Evolutionary Computing - Book Summary
This view naturally leads to the concept of a search space, being the collection of all objects of interest
including the solution we are seeking. Depending on the task at hand, the search space consists of all
possible inputs to a model (optimisation problems), or all possible computational models that describe the
phenomenon we study (modelling problems).
The specification of the search space is the first step in defining a search problem. The second step is the
definition of a solution. For optimisation problems such a definition can be explicit, e.g. board
configuration where the number of checked queens is zero, or implicit, e.g. a tour that is the shortest of all
tours. For modelling problems a solution is defined by the property that it produces the correct output for
every input. This notion of problem solving as search gives us an immediate benefit: we can draw a
distinction between (search) problems - which define search spaces - and problem solvers - which are
methods that tell us how to move through search spaces.
1.3 Optimisation Versus Constraint Satisfaction
In general, we can consider an objective function to be some way of assigning a value to a possible
solution that reflects its quality on a scale, whereas a constraint represents a binary evaluation telling us
whether a given requirement holds or not. Solutions to a problem can be identified in terms of optimality
with respect to some objective function. Additionally, solutions can be subject to constraints phrased as
criteria that must be satisfied.
Examples of objection functions
1. the number of checked queens on a chess board (to be maximised)
2. the length of a tour visiting each city in a given set exactly once (to be minimised)
3. the number of images in a collection that are labelled correctly by a given model m(to be
maximised)
Examples of solutions subject to constraints
1. Find a configuration of eight queens on a chess board such that no two queens check each other
2. Find a tour with minimal length for a travelling salesman such that city X is visited after city Y
Four categories of problem types distinguished by the presence or absence of an objective function and
constraint are shown below.
In these terms, the travelling salesman problem (item 2 above) is a free optimisation problem (FOP), the
eight-queens problem (item 4 above) is a constraint satisfaction problem (CSP), and the problem shown in
item 5 is a constrained optimisation problem (COP). Comparing item 1 and 4 we can see that constraint
satisfaction problems can be transformed into optimisation problems.
3
, Introduction to Evolutionary Computing - Book Summary
1.4 The Famous NP Problems
In this section we discuss a classification scheme where it is not possible to classify a problem according
to one of the previous schemes because the problem categories are defined through the properties of
problem-solving algorithms. The motivation behind this approach is the intention to talk about problems
in terms of their difficulty (e.g. being hard or easy to solve). The basic idea is to call a problem easy if
there exists a fast solver for it, and hard otherwise. This notion of problem hardness leads to the study of
computational complexity.
If the search space S is defined by continuous variables (i.e., real numbers), then we have a numerical
optimisation problem. If S is defined by discrete variables (e.g., Booleans or integers), then we have a
combinatorial optimisation problem. Note that the discrete search spaces are always finite or, in the worst
case, countably finite.
The first key notion in computational complexity is that of problem size, which is grounded in the
dimensionality of the problem at hand (i.e., the number of variables) and the number of different values
for the problem variables.
The second notion concerns algorithms. The running-time of an algorithm is the number of elementary
steps, or operations, it takes to terminate: polynomial (n2), super-polynominal (no(log log n)), exponential (2n).
The best-known definitions of problem hardness relate the size of a problem to the (worst-case)
running-time of an algorithm to solve it. The final notion is that of problem reduction, which is the idea
that we can transform one problem into another via a suitable mapping.
● A problem is said to belong to class P if there exists an algorithm that can solve it in polynomial
time (easily solved).
● A problem is said to belong to class NP if it can be solved by some algorithm (with no claims
about its runtime) and any solution can be verified within polynomial time by some other
algorithm. Note: P is a subset of NP.
● A problem is said to belong to class NP-complete if it belongs to the class NP and any other
problem in NP can be reduced to this problem by an algorithm which runs in polynomial time.
● A problem is said to belong to class NP-hard if it is at least as hard as any problem in
NP-complete, but where the solution cannot necessarily be verified within polynomial time (e.g.,
Halting problem).
4
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper tararoopram. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €17,48. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen