An Introduction to Genetic Algorithms
By Sam Hsiung and James Matthews
After scientists became disillusioned with classical and neo-classical attempts at modelling intelligence, they looked in other directions. Two prominent fields arose, connectionism (neural networking, parallel processing) and evolutionary computing. It is the latter that this essay deals with - genetic algorithms and genetic programming.
Symbolic AI vs Genetic AlgorithmsMost symbolic AI systems are very static. Most of them can usually only solve one given specific problem, since their architecture was designed for whatever that specific problem was in the first place. Thus, if the given problem were somehow to be changed, these systems could have a hard time adapting to them, since the algorithm that would originally arrive to the solution may be either incorrect or less efficient. Genetic algorithms (or GA) were created to combat these problems. They are basically algorithms based on natural biological evolution. The architecture of systems that implement genetic algorithms (or GA) are more able to adapt to a wide range of problems. A GA functions by generating a large set of possible solutions to a given problem. It then evaluates each of those solutions, and decides on a "fitness level" (you may recall the phrase: "survival of the fittest") for each solution set. These solutions then breed new solutions. The parent solutions that were more "fit" are more likely to reproduce, while those that were less "fit" are more unlikely to do so. In essence, solutions are evolved over time. This way you evolve your search space scope to a point where you can find the solution. Genetic algorithms can be incredibly efficient if programmed correctly.
General Algorithm for Genetic AlgorithmsGenetic algorithms are not too hard to program or understand, since they are biological based. Thinking in terms of real-life evolution may help you understand. Here is the general algorithm for a GA:
Create a Random Initial State
Reproduce (& Children Mutate)
Applications of GAsThe possible applications of genetic algorithms are immense. Any problem that has a large search domain could be suitable tackled by GAs. A popular growing field is genetic programming (GP).
Genetic ProgrammingIn programming languages such as LISP and Scheme, the mathematical notation is not written in standard notation, but in prefix notation. Some examples of this:
+ 2 1 : 2 + 1 * + 2 1 2 : 2 * (2+1) * + - 2 1 4 9 : 9 * ((2 - 1) + 4)Notice the difference between the left-hand side to the right? Apart from the order being different, no parenthesis! The prefix method makes life a lot easier for programmers and compilers alike, because order precedence is not an issue. You can build expression trees out of these strings that then can be easily evaluated, for example, here are the trees for the above three expressions.
Evolving Neural Networks
Evolving the architecture of neural network is slightly more complicated, and there have been several ways of doing it. For small nets, a simple matrix represents which neuron connection which, and then this matrix is, in turn, converted into the necessary 'genes', and various combinations of these are evolved.
Many would think that a learning function could be evolved via genetic programming. Unfortunately, genetic programming combined with neural networks could be incredibly slow, thus impractical. As with many problems, you have to constrain what you are attempting to create. For example, in 1990, David Chalmers attempted to evolve a function as good as the delta rule. He did this by creating a general equation based upon the delta rule with 8 unknowns, which the genetic algorithm then evolved.
Other AreasGenetic Algorithms can be applied to virtually any problem that has a large search space. Al Biles uses genetic algorithms to filter out 'good' and 'bad' riffs for jazz improvisation, the military uses GAs to evolve equations to differentiate between different radar returns, stock companies use GA-powered programs to predict the stock market.
Last Updated: 31/03/2000
Article content copyright © Sam Hsiung and James Matthews, 2000.
All content copyright © 1998-2007, Generation5 unless otherwise noted.