L2 - Evolutionary Algorithms 1

Question 1

Give a high level explanation of Evolutionary Algorithms…

Answer 1

EA’s are based on the natural process of evolution, in which we see the survival of the fittest. In computational context, this is an iterable process to generate optimal solutions.

Question 2

What are the 3 iteratable steps in the Evolutionary Process?

Answer 2

Selection : Select solutions to apply variations too.
Variation : Apply a small variation.
Population Update : Update the solution population with the most optimal solutions.

Question 2

Should we implement a small or large variation at the variations state?

Answer 2

Small, because it’s harder to identify the cause-effect relationship when larger variations have been made.

Question 3

Give an overview of the steps in involves in EA’s…

Answer 3

1. Generate a set of random solutions ( parents ).
2. Selection : Select solutions that the variation will be applied to.
3. Variation → Apply the variation to the solutions ( children ).
4. Population Update → Create a set of the most optimal solutions. This will be the parent set for the next iteration.
5. Back to step 2.

Question 4

What scenarios are EA’s ideal for?

Answer 4

When we need an optimal solution, but not necessarily an exact solution. This is usually when we are dealing with huge search spaces where it’s infeasible to identify all solutions.

Question 5

Give 3 real life examples where EA’s could be leveraged?

Answer 5

• Most well distributed water distribution system.
• Most efficient orbit.
• Most efficient telephone wire mapping.

Question 6

Define Search and Optimisation…

Answer 6

Searching for the best solution within a certain amount of time.

Question 7

What complexities do Search Spaces usually fall in to?

Answer 7

Polynomial or exponential.

Question 8

Define what a fitness function is, and give an example…

Answer 8

A function that analyses a solution to determine it’s fitness score.
Fitness Score is how effectively the solution solves the problem.

Question 9

If the search space is small, what search method should we use to find the optimal solution?

Answer 9

Exhaustive Search ( Enumeration ), where we find all possible solutions, and choose the most efficient one.

Question 10

Define what the ‘too-big’ problem category is…

Answer 10

A Too Big problem is a problem that has a search space to large for Exhaustive Search. These can either be easy or hard.
Easy : Polynomial
Hard: Exponential

Question 11

Which Search Space category do most import problems fall in to?

Answer 11

Hard

Question 12

What does it mean if we have an exact problem?

Answer 12

An exact problem is a problem where we know we can find the most optimised solution.

Question 13

What does problem complexity mean? What are the 2 key types?

Answer 13

Problem Complexity refers to the size of the problem in terms of the search space. These are either Easy or Hard.
Easy : Polynomial Time
Hard : Exponential Time.

Question 14

Define Tractable problems…

Answer 14

An Easy problem:
- Polynomial Time.
- Algorithms are known that can generate optimal solutions within time.

Question 15

Define Intractable problems…

Answer 15

A Hard problem:
- Exponential Time.
- Fastest known algorithm to solve the problem has a similar time to exhaustive search, thus is infeasible.

Question 16

Using a MST, explain how a MST problem can be either easy or hard based on the scenario…

Answer 16

An easy MST problem would be to simply find the MST of a weighted graph.

A Hard MST problem would be constraints added to the problem. For example, find the MST of a piping network in which there are 16 nodes, each of which has 21 pipes stemming from it.

Question 17

What type of algorithm category do EA’s fall in to?

Answer 17

Approximation Algorithms. These are algorithms that are used to find the most optimal solution since the problems are usually too big to find an exact solution.

Question 18

Describe the relationship between speed and quality when using EA’s as opposed to other algorithms…

Answer 18

EA’s may be slower than other algorithms, but the generate higher quality solutions over time. Just as evolution is slow, but has developed the current most optimal solution at each iteration.

Question 19

What are the 3 general properties of EA algorithms?

Answer 19

• Find close to optimal solutions.
• Can’t guarantee to have the optimal solution.
• Take reasonable time.