EvoComp 2021
Course notes [Lectures, papers and book]
Name: Tim de Boer VUnetID: wbr950
1 Chapter 0: Evolutionary Problem Solving
Some problems, like chess puzzles, can be solved with numerous approaches:
• Dumb approaches, like backtracking
• A bit smarter versions of above
• Or Evolutionary approaches: build a population of candidate solutions (individual) for the problem (en-
vironment), only keep the best ones based on a fitness function (quality), and combine the good things of
these best ones into a ’child’
Of course, evolutionary computing is not the same as natural evolution, see fig 1.
Figure 1: Differences between natural evolution and evolutionary algorithms
2 Chapter 1: Types of problems
There are different types of problems to be solved in which Evolutionary Computing might be the right approach.
We have:
• Black box model; provide input, let it flow through a model and achieve some output. In general, we have
3 problem types depending on which component is missing:
– Optimisation: Model and desired output is known, find input
∗ timetable University: with big search space and lots of criteria, must be feasible as well.
∗ Satellite structure: with fitness function such as vibration resistance; this can lead to creative
structures.
1
,wbr950 – Course notes [Lectures, papers and book] 2
∗ This problem can be captured by a computational system where an input is a certain configura-
tion of all eight queens, the model calculates whether the queens in a given configuration check
each other or not, and the output is the number of queens not being checked
– Modelling: find the model, e.g. evolutionary machine learning.
∗ Let us take the stock exchange as an example, where some economic and societal indices (e.g.,
the unemployment rate, gold price, euro–dollar exchange rate, etc.) form the input, and the Dow
Jones index is seen as output. The task is now to find a formula that links the known inputs to
the known outputs, thereby representing a model of this economic system.
∗ Also the voice control system for smart homes includes a modelling problem. The set of all
phrases pronounced by the user (inputs) must be correctly mapped onto the set of all control
commands in the repertoire of the smart home.
– Simulation: we have a model and change input to see effects on output (weather, climate, economics).
∗ In this case, the inputs are the meteorological data regarding, temperature, wind, humidity,
rainfall, etc., and the outputs are actually the same: temperature, wind, humidity, rainfall, etc.,
but at a different time. The model here is a temporal one to predict meteorological data.
• Search Problems define search spaces and problems solvers move through search space to find solution.
Search space: collection of all objects of interest including desired solution.
• Optimisation vs constraint satisfactions: we make a distinction between objective functions (maximize x)
and constraints (binary evaluation whether constraint holds), such as: are there queens that check each
other? See figure 2 for the combinations.
Figure 2: The names for combinations of objective functions and constraints
• NP problems: classification scheme by looking at properties of the problem solver, e.g. this stone is 100kg
(property of problem) vs. this stone is heavy to lift (property of problem solver).
– We define by problem size (search space), running-time.
– Class P: polynomial time to solve
– NP: solution itself can be verified in polynomial time. P is subset of NP
– NP-complete: subset of NP; any other problem can be reduced to this problem in polynomial time
– NP-hard: solution cannot be verified in polynomial time but as least as hard as NP-complete
Questions from book:
• Consider the well-known graph k-colouring problem. Here we are given a set of points (vertices) and a
list of connections between them (edges). The task is to assign one of k colours to each vertex, so that no
two vertices which are connected by an edge share the same colour.
, wbr950 – Course notes [Lectures, papers and book] 3
– Formalise this problem as a free optimisation problem.
∗ Maximize the number of non-shared-coloured vertexes.
– Formalise this problem as a constraint satisfaction problem.
∗ Find a configuration of coloured vertices such that no two vertices which are connected by an
edge share the same colour.
– Formalise this problem as a constrained optimisation problem.
∗ Maximize the number of coloured vertices such that no two vertices which are connected by an
edge share the same colour.
– A group of students are tasked with building a robotic system to play table tennis. For each of the
following capabilities that the system should exhibit, state whether it is an optimisation, modelling,
or simulation problem.
∗ Identifying the ball in a video feed.
· Modelling
∗ Predicting where the ball will bounce.
· Modelling
∗ Planning how to move the bat to the predicted position of the ball at some future time.
· Optimization
∗ Learning opponent’s behaviour.
· Simulation
∗ Deciding where to hit ball next so that the opponent has the smallest chance of returning it.
· Optimization
– A company decides to produce a robotic system that can guide groups of potential students and
their parents around a university campus on an open day. There are considerable regional differences
in dialects across its target markets. For each of the following capabilities that the system should
exhibit, state whether they are an optimisation, modelling, or simulation problem.
∗ Learning to recognize speech.
· Optimization
∗ Recognizing a question.
· Modelling
∗ Planning a route to the next room on the tour.
· Optimization
∗ Recognizing an obstacle in a corridor (it gives a bad impression to run people over).
· Modelling
∗ Moving to avoid an obstacle.
· Simulation
• There is much current research in producing autonomous vehicles that can be used on real roads. For each
of the following capabilities that such a system should exhibit, state whether they are an optimisation,
modelling, or simulation problem.
– Learning to recognize traffic signs.
∗ Modelling
– Recognizing a traffic sign in a video feed as the vehicle drives along.
∗ Modelling
– Planning shortest, or quickest, route between two places.
∗ Optimization
– Avoiding a child that runs into the road.
∗ Simulation
– Steering in the middle of the road.
∗ Simulation
