| Introduction | A step by step guide | |
Genetic Algorithms (GA) are techniques for solving optimization problems inspired by the theory of evolution and biogenetics. These algorithms are excellent at exploring large search spaces for optimal or near optimal solutions. The basics of a genetic algorithm are:
1.Representing possible solutions to problems as a string of parameters (numbers). This string is called a chromosome and the parameters within it are called genes.
2.Randomly creating a number (generation) of these chromosomes.
3.Calculating the effectiveness of each chromosome as a solution to the problem then ranking the chromosomes in order of effectiveness (fitness to survive).
4.Creating a new generation of chromosomes by randomly selecting pairs of chromosomes (parents) and mixing their genes to form child chromosomes. This process is called 'crossover' and the selection of the parents is biased to more effective (fit) parents.
5.Repeating steps 3 to 4 for a number of cycles (generations).
The randomness of the above process allows the effective exploration of the space of solutions. While the selection of effective solutions (chromosomes) and the mixing of their genes allows the accumulation of good features from partially good solutions. As a result, genetic algorithms can explore large domains and converge on good solutions relatively quickly. GA's also give a powerful trade off between the time taken to reach a solution and the quality of the solution. Typically it is desirable to achieve a "good" solution in a short time as opposed to an optimal solution that may require infinite time.
The two basic steps in developing solutions using GA's are an appropriate representation of the problem and a method of assessing the effectiveness (cost) of a solution. The easiest representation of a problem for GA implementation is as a string of numbers. Each number is represented by a gene that can be constrained by the minimum and maximum values it can take. A cost function is defined which derives a value for the cost of the solution from a given set of gene values. In such a representation, each gene represents a different numeric parameter of the solution. Alternatively, a chromosome can be used to represent a sequence of jobs which requires optimization. In such a case the number of genes will equal the number of jobs to be sequenced and the value of each gene will be unique and range from 1 to the number of tasks.
As an alternative to using Knowledge Builder @Commands for the main cost function (procedure), you can use VBScript syntax commands. These are recommended when large sequences of commands are needed in one procedure and the maximum execution speed at run time is required - typically the case with optimization applications.
There may be instances when you need to ensure that the random generation starts off at the same point. If so, the RandSeed command can be used to seed the random number generator.