Introduction to Evolutionary Algorithms

3. Implementation Building Blocks

We can condense the contents of the previous section into a more formal and terse form by saying that...

• We have a population of individuals (for example, a colony of rabbits)
• The population exists in a defined environment (a field somewhere in Yorkshire)
• We have a well understood and defined set of environmental factors which effect the success of individuals, over which we have no control (Food supply, predators etc)
• Individuals survival is dependant upon their ability to exploit the environment (find food, evade predators etc)
• Individuals traits are passed to their offspring
• Offspring also undergo some mutation at conception which can alter their own traits in a positive or negative way

We can use this list as a basis for a computer based model of evolution which we can use to breed solutions to other problems. To do this we need the following four building blocks. I have used the school timetabling example from section 1 to help illustrate their purpose...

• The individual: A representation of the solution (a structure telling us when and where lessons take place)
• The population: A means of maintaining a list of these structures
• The environment: A function which gives us a measure of an individual's level of success. This is generally known as the fitness function (based on the number of timetable clashes, missed lessons etc)
• Natural selection: A scheme for managing the deaths of unfit individuals and the breeding of new individuals

Once we have this simple set of building blocks we will be ready to implement the evolutionary algorithm, which is essentially the loop illustrated in figure 4.

fig. 4: Evolutionary Algorithm

The next section gives an introduction to the Travelling Salesman Problem (TSP), which we will use to help illustrate the application of EAs to simple problems. Then, the following few sections give details of how we can implement the above algorithm and the associated building blocks in Delphi, to solve the TSP. Since Delphi is a pretty complete object oriented language it should be fairly simple to translate the code as you see fit (into C++ for example...).

	Back
	Contents
	Next