This documents gives an overview over the complete field of Evolutionary Computing, as given by the Evolutionary Computing course at Vrije Universiteit Amsterdam.
Evolutionary Computing - Exam questions 2019 and 2021
All for this textbook (6)
Written for
Vrije Universiteit Amsterdam (VU)
MSc Artificial Intelligence
Evolutionary Computing (X_400111)
All documents for this subject (2)
1
review
By: michielvandenengel • 2 year ago
Seller
Follow
timdeboer
Reviews received
Content preview
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
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 timdeboer. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.54. You're not tied to anything after your purchase.
