artificial life

Chapter 5: Genetic Algorithms

5.7 Conclusion

Genetic Algorithms can be applied to a variety of problems. It makes a good heuristic for NP-hard problems such as the Traveling Salesman problem. Biologist Richard Dawkins used Genetic Algorithms with human aesthetic taste as the fitness function to create “biomorphs” - creature like line drawings [Dawkins, 1996]. Genetic Algorithms can also be combined with L-Systems to create L-Systems that adhere to certain natural rules such as symmetry.

In general, GA’s are useful for solving any sort of problem that can be represented in a bit vector of predetermined size. The hardest part is creating a fitness function that will place the individuals on some spectrum of fitness that reflects the actual fitness of the genotype. Usually these representation can be created using the definition of the problem, such as using the value of the knapsack, or the amount a sack is overweight in the 0-1 Knapsack Problem.

Genetic Algorithms find good or even optimal solutions to the 0-1 knapsack problem in a fraction of the time it would otherwise take. Genetic Algorithms are a powerful tool for finding good solutions to very hard problems. They are also very interesting because they emulate the natural phenomena of genetic regeneration to gain their power.