The Lonely Planet guide to Artificial Intelligence
(Part 2)
22-54-2003
By: Shane Dempsey
Genetic Algorithms made easy (ish)
Genetic Algorithms (GA) are modeled after the process of natural selection in living organisms. In the real world organisms adapt to their environment over time through mutation and natural selection. Genetic Algorithms attempt to mimic this process by evolving a solution to a predefined problem. Problems where GA is applied tend to be difficult to solve using more conventional methods. They tend to involve multiple variables where the optimum solution is difficult to determine. Examples include finding the shortest path from city to city.
In the same way, possible solutions (guesses) are adapted to problems over time in genetic algorithms. Genetic algorithms are usually implemented to search for answers to certain problems.
An effective GA will generate a large set of random possible solutions sets to a given problem. These possible solutions represent the problems chromosomes. Each solution is analysed to determine its fitness or how best it matches the ideal solution to the problem. This ideal may represent a solution to the problem that is optimum in all cases, which may not be achievable due to the difficulty of the problem.
Some problems are just very hard!
Just like in nature, the fitter a solution chromosome is the more likely it is to reproduce and pass on its traits to the next evolution of the system. Pairs of fit chromosomes are mated to produce offspring that are hopefully fitter and closer to the ideal. These chromosomes come from designated mother and father solution sets, categorized based on the traits they exhibit in solving the problem.
Generation after generation is evolved until a chromosome is found that has the desired solution set, corresponding to an ideal or acceptable solution to the difficult problem.
Some of the areas that Genetic Algorithms have been applied to include:
* Artificially generated music
Timetabling and scheduling problems
* Navigation systems
* Financial market trend analysis and prediction
* Aeronautical design
For those who like to do a bit of maths I've included a concrete example below, involving a basic equation and some tricky steps that I'll try to signpost along the way.
To solve the equation a + 2b + 3c = 10 where a,b & c are positive integers [e.g. 0,1,2,3] Let's start with the following solution set for (a,b,c). I'm reducing the scope of the solution set by saying that a,b & c <= 10
Solution No. (a,b,c) Fitness assessment (0 is ideal) Fitness %
1 (1, 4, 2) 15 - 10 = 5 19.75
2 (8,6,2) 26 - 10 = 16 6.17
3 (1,2,3) 14 - 10 = 4 24.69
4 (3, 1, 1) 10 - 8 = 2 49.3
To calculate the fitness percentage I use basic probability theory. The higher my fitness assessment number the less fit the value is. Therefore I calculate the percentage for solution 1 as (1/5) / [ 1/5 + 1/16 + 1/4 + 1/2] all multiplied by 100 = 20 / 1.0125 = 19.75
I then match pairs based on these probabilities to produce another 4 solutions. A combination of solutions 3 & 4 is most likely. These could produce offspring similar to (1,1,1) & (3,2,3).
Solutions taken from 4 are underlined. And so we continue until we evolve the correct answer. Maybe something like (3,2,1) as 3 + 4 + 3 = 10. It's worth noting that this is very similar to solution number 4, which had the highest fitness %.
This is tricky stuff initially but has great potential for a wide range of applications in engineering, science and economics. If you're interested then have a look at the following web page [1]
[1] The Genetic Algorithms Archive, http://www.aic.nrl.navy.mil/galist/
| 
