how2examples.com
Home - Introduction to Artificial Intelligence

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.

 ManchesterExeterNewcastleLondonDerbyWolverhampton
Bristol
168
79
295
118
135
93
Manchester
-
241
142
199
60
75
Exeter
-
-
371
187
211
169
Newcastle
-
-
-
276
162
204
London
-
-
-
-
129
130
Derby
-
-
-
-
-
42

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 Derby to Exeter (211 miles) to Newcastle (371) to London (276) to Wolverhampton (130) to Bristol (93) to Manchester (168). The total distance for this journey is 211 + 371 + 276 + 130 + 93 + 168 = 1249 miles.

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:

The process continues for a set number of generations or until a good enough solution is found.

Examples of Stochastic Optimisation