Solving Cool Problems with Genetic Algorithms

representable as strings (hence the name Genetic Algorithm - the programming model is based on DNA). In terms of practical value, genetic algorithms are useful for solving problems in which the solutions are difficult to find by following a specific algorithm designed to solve the problem (using genetic algorithms in place of predesigned algorithms such as Djikstra's algorithm for path finding just wouldn't make sense). It functions as a sort of systematized brute force approach. Problems genetic algorithms are valuable for solving include scheduling problems, constraint satisfaction problems, and other problems that require searching a large number of possibilities. Genetic algorithms can be applied to protein folding or even tuning Linux kernel performance.
A simpler example just to get the point across is finding a five digit number that acts as the best solution to an expression; for example, if you wish to find the number that makes the expression x^2+2x-11 equal to 0, you could of course use brute force to solve the equation, but a genetic algorithm can also be used, and if you have a very complex expression, it may be of great value to use a genetic algorithm, especially when one considers the time saved over brute force. In a sense, all genetic algorithm problems boil down to solving complex expressions or sets of expressions, as all problems are representable in that fashion. Genetic algorithms work from the same basis as evolutionary theory. A genetic algorithm has several components: a pool of solutions, a method of evaluating the effectiveness of each solution, a breeding function that combines the best solutions into new solutions, and a mutation function. The pool of solutions do not compete for resources; rather, each solution is tested by an evaluation function (called the "fitness" function), which then gives it a ranking based on its effectiveness at solving the problem compared to the other solutions. The best solution strings are the ones that are ranked highest (that are the most "fit"); the breeding function takes two of the better performing solutions and combines them together into a new solution. The breeding function should repeat the process of randomly selecting two solutions and breeding them; the better performing functions should be given the higher percentage chance of being selected. The breeding function generally works by taking slices of each solution and splicing them together into a new one. Solutions are often represented as strings, so generally, a breeding function will take fragments of random lengths from each string and concatenate them together to form a new string. Each fragment should be placed into the location in the new string that corresponds to its location in the old string. For example, if a string fragment is from positions 5 to 8 in the first string being bred, it should be placed into positions 5 through 8 in the new child solution. After the strings have been bred, and the set of potential solutions has been refilled, it is important to have the mutation function. The mutation function is important because it introduces an element of randomness that allows variation in the solution sets, which otherwise would stagnate and have no advantage over a hand-crafted solution. Mutations may diminish the strength of some solutions, but in general it will increase the overall value of the solution set; by including a very small mutation rate, you introduce new traits that might never have otherwise existed within the pool. This allows you to explore a larger group of possibilities and avoid stagnation. In fact, many other AI techniques forgo the idea of breeding solutions and work simply by making small "mutations" or changes to a potential solution to a problem. Genetic algorithms can do some amazing things and solve very complex problems. Nevertheless, this techniques will require having way of evaluating possible solutions -- this is one of the most difficult problems with genetic algorithms. The second challenge is finding a good way to represent solutions to the problem as strings. Once these are sorted out, a genetic algorithm may be a good approach to your problem.