Summary
Introduction to Evolutionary Computing - Book Summary
- Course
- Institution
- Book
Complete book summary for Introduction to Evolutionary Computing by A.E. Eiben and J.E. Smith.
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
Summary Evolutionary Computing (X_400111)
-
Summary Evolutionary Computing (MSc AI VU)
-
Evolutionary Computing - Exam questions 2019 and 2021
Seller
Follow
tararoopram
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tararoopram. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $18.71. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now