Genetic Algorithms - Description:Applications which use genetic algorithms to solve problems are surfacing in a wide range of areas. Over 500 research articles were published in 1994 alone on genetic algorithms, and widespread interest in these computer programs is increasing. Genetic algorithms are essentially a software version of the evolutionary process. The main difference is the computer process can be greatly accelerated by fine-tuning and manipulating the evolutionary principles, where members of the population are born, mate, and die in a few microseconds. This allows for enormous change to occur rapidly.
Genetic algorithms require a set of population members, usually numbering between 20 to 100. Each population member represents a trial solution to a given problem. The trial solution - where numbers are used for the input variables - is tested by an evaluation function, which calculates the quality of the trial solution. The output is commonly called the Fitness, since it describes how "fit" the trial solution is.
The inputs for the fitness function are often called genes, chromosomes, or genomes. For Generator, we refer to them as "genes". The fitness function typically has a number of different inputs. For instance, if the fitness function for a factory calculates the factory's profit, the input variables, or genes, may consist of worker overtime, supply costs, productivity, QA efforts, process variables, etc. Each population member will therefore have an identical number of genes, or input variables.
Genetic Algorithms work by starting with relatively poor trial solutions, that is, population members with poor fitness. Three basic processes are then allowed to occur: mating, mutation, and selection ("survival of the fittest"). The first process, mating, involves an exchange of information between population members, something which is referred to as crossover. When population members mate, they cross gene values over to their partner, resulting in an exchange of gene values. This rearranges the information in the gene values of the population members, creating new and diverse "offspring" that combine potentially beneficial features of their parents.
Once the crossover has taken place, the offspring undergo mutation. In mutation, the values of the individual genes of population members can be changed, or mutated. Mutation is important in evolution because unlike crossover (which merely trades genes), new gene values are introduced. This further increases the diversity of the population members.
"Survival of the fittest" principles complete the evolutionary cycle. Once crossover and mutation have occurred, the new population members will replace the old ones if they are better. In this fashion, population members can have improved fitness with each new cycle (or generation) of crossover, mutation, and natural selection. Program users typically want to maximize or minimize the fitness, so the survival of the fittest action is governed by whether the new fitness is better or worse than the previous generation's fitness. The resulting process yields a steadily improving solution to the problem, often identifying the optimum solution in a surprisingly short time.
9715 West Sunset Highway Spokane, WA 99224 Phone: 509-456-8321 FAX: 509-456-8351