L3 - Search Landscapes and Hillclimbing Flashcards
Give key umbrella terms of Evolutionary Computation…
Algorithm Type
Recombination ( Crossover )
Selection
Replacer
Mutation
Parameters
Give 2 non evolutionary algorithms, that are flawed and less optimal, but are simpler…
Hillclimbing
Local Search
Why are Hillclimbing and Local Search less optimal that EA’s?
Because they are prone to getting stuck at local optima. This is because they’re always looking for the next more optimised solution. Thus, if they reach a local optimum, they will stay at that solution since both the previous and next solution will be less optimum.
Define the Hillclimbing algorithm…
A search optimisation algorithm that finds the local optimal solution. It does this by making small mutations to the current solution, and assessing the fitness of each mutation. The algorithm only considers solutions that are no worse than the current locally optimal solution. In this sense, the algorithm can only climb up hill.
Explain the 4 steps of the Hillclimbing algorithm…
- Initialise a current solution c, and get the fitness of c.
- Mutate c to get some m
- Evaluate the fitness of m, compared to c, if m is no less optimal than c, assign m to c such that c = m.
- Repeat until termination criteria.
What is a Landscape Graph in Hillclimbing? Define what is on the Y-axis and X-axis…
A graph that shows the fitness of an initial solution and it’s mutations.
Y-Axis is the fitness score.
X-Axis is the initial solution and it’s mutations.
Describe how we can use Hillclimbing to solve the Travelling Salesman Problem for a graph with nodes A,B,C,D,E
Take the initial solution of A,B,C,D,E and iteratively apply a Mutation function of swapping 2 adjacent nodes. Whenever a mutation is no worse that the current solution, we assign it to the current solution.
Define a Landscape…
The graph we get when imposing F(s) on all s within a search space of solutions S.
Solutions are along the X-axis and fitness scores are along the Y-axis.
Define a Neighbourhood…
Given a mutation factor M, the neighbourhood of a solution is the set of all mutations of the solution.
Find the neighbourhood of the solution ‘1100101’ when M = flip a random bit.
If the initial solution s = 1100101
For every mutation, we need to choose a random bit from s, and flip it.
When mutating a solution, do we always mutate from the initial solution s?
Yes.
Why do Landscapes tend to be smooth?
Because solutions and their neighbourhood only have small mutations applied, thus their fitness values are likely to be similar. These small increments / decrements in fitness result in a smooth local area in the landscape.
What would happen if the applies big mutations?
The landscape would be lively to have more drastic fluctuations.
What are the 4 types of landscapes?
Unimodal
Plateau
Multimodal
Deceptive
Explain the landscapes we usually see in real world problems…
We typically see landscapes that are not smooth and have more drastic fluctuations. This is because the search space for real problems is huge and varied, and only a small area of the search space contains solutions with high fitness. Thus, we typically end up with large, fluctuating landscapes that have only a small area of solutions with relevant fitness.
