Evolutionary Computation

Due: Tuesday, 12 September 2017 at the beginning of class

• Follow the general homework directions.
• Make sure you cite all your references and contacts.
• Read
• Syllabus
• Chapters 1, 2, and 3 in textbook.
• Problems
1. 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.
• Formalise this problem as a free optimization problem.
• Formalise this problem as a constraint satisfaction problem.
• Formalise this problem as a constrained optimisation problem.
2. 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.
• Predicting where the ball will bounce.
• Planning how to move the bat to the predicted position of the ball at some future time.
• Learning opponent's behaviour.
• Deciding where to hit ball next so that the opponent has the smallest chance of returning it.
3. Find out when hominids are first thought to have appeared, and estimate how many generations it has taken for you to evolve.
4. Find out for how long have humans have used the following as tools: Evolution, The wheel, Fire.