## Stochastic Optimisation

An approach to finding a solution to a problem is to try many alternatives before choosing the best one. There are various optimisation techniques for finding good solutions for problems that are to complex to systematically examine each possible alternative. Stochastic approaches include a random element - i.e. they are not deterministic.

The "Travelling Salesman Problem" will be used to demonstrate various stochastic optimisation techniques.

### The Travelling Salesman Problem

The travelling salesman problem (TSP) is a classic AI problem. The task is to find the shortest possible route that visits each of a set of cities exactly once.

### Test Data

For this example we are going to use the cities and distances (in miles) shown in the table below.

Manchester | Exeter | Newcastle | London | Derby | Wolverhampton | |
---|---|---|---|---|---|---|

Bristol | ||||||

Manchester | ||||||

Exeter | ||||||

Newcastle | ||||||

London | ||||||

Derby |

To make it easy to represent a solution in a concise way, we will combine the initial of each city in the order they are visited. For example, `DENLWBM`

represents a journey from **D**erby to **E**xeter (211 miles) to **N**ewcastle (371) to **L**ondon (276) to **W**olverhampton (130) to **B**ristol (93) to **M**anchester (168). The total distance for this journey is 211 + 371 + 276 + 130 + 93 + 168 = **1249** miles.

### Random Search

Random search involves producing a set number of randomly generated journeys. The journey with the shortest total distance is the one that is chosen.

### Hill Climbing

Hill climbing is an iterative algorithm that starts with a randomly generated solution. All "neighbouring" solutions are generated. In the case of TSP, "neighbouring" solutions could be generated by switching the order of adjacent cities. If a better solution is found, the process is repeated (generating "neighbouring" solutions of the new best solution) until no further improvements can be found.

### Genetic Algorithms

Genetic algorithms are a type of evolutionary algorithm (EA), inspired by natural evolution. The process starts with a set of randomly generated solutions and happens in generations. Each new generation is based on (i.e. *evolves from*) the solutions contained in the previous generation. Four common approaches which are combined to produce new generations are:

*Selection*- keeping the best solutions from the previous generation.*Mutation*- altering a solution from the previous generation to produce a new solution.*Crossover*- combining two solutions from the previous generation to produce one new solution. When using crossover to produce new TSP solutions it is important to ensure the new solution is valid (i.e. it contains every city exactly once). A naive approach to combining`EMBNLWD`

and`EWNDBLM`

would be to join the start of the first (`EMBN`

) with the end of the second (`BLM`

) but the result (`EMBNBLM`

) is invalid as it does not contain`W`

or`D`

.*Randomness*- producing a new randomly generated solution.