Genetic Algorithms

Technologies

Genetic Algorithms

Genetic algorithms are general-purpose search algorithms based upon the principles of evolution observed in nature. Genetic algorithms combine selection, crossover, and mutation operators with the goal of finding the best solution to a problem. Genetic algorithms search for this optimal solution until a specified termination criterion is met.

The solution to a problem is called a chromosome. A chromosome is made up of a collection of genes which are simply the parameters to be optimized. A genetic algorithm creates an initial population (a collection of chromosomes), evaluates this population, then evolves the population through multiple generations (using the genetic operators discussed above) in the search for a good solution for the problem at hand.

Genetic algorithms can be applied to a wide variety of optimization problems such as scheduling, computer games, stock market trading, medical, adaptive control, transportation, the traveling salesmen problem, etc.

Evolutionary Computing

Despite their superficial differences, the four main approaches to evolutionary computing share the same basic template. Whether you favor genetic algorithms, evolutionary programming, evolution strategies or genetic programming, you will have to start with a random or semi random population of candidate solutions and you will have to devise a ‘fitness function’.

The fitness function is a feedback system to measure how well each individual within the population performs in terms of the designated task or problem. Individuals that do well have a greater probability of passing their genetic information onto the next generation. The rules governing how offspring are generated from parents are encoded in the genetic operators. These cover:

  • reproduction (how exactly candidates are selected for breeding)
  • mutation (whether, and at what rate, random changes will occur in genetic information)
  • recombination (when this operator is used, successful individuals exchange genetic information with other successful individuals to form offspring).
  • What chiefly distinguishes one evolutionary approach from another is choice of representation and choice of genetic operator.

Consider the problem of maximizing the function f(x) = x2, for x between 0 and 31.

  1. The decision variable must be encoded : since x may take any value between 0 and 31, it will be coded as a five-bit, binary unsigned integer.
  2. The initial population is generated at random.
  3. Fitness values are calculated for each string in the initial population, merely by calculating f(x) for each decoded value of x. e.g. ‘01000’ decodes to ‘8’, fitness is calculated as x2, which is 82 = 64.
  4. The next generation of the genetic algorithm begins with reproduction. This is a simple copying operation, subject to weightings derived from the fitness values. Candidates with high fitness will have a greater probability of being reproduced in the succeeding generation and those with worst fitness will tend to die off.
  5. The crossover procedure has two steps.
    1. Strings are mated randomly.
    2. Mated string couples cross over, using randomly selected crossing sites
  6. The last operator, mutation, is performed on a bit-by-bit basis. Assuming arbitrarily that the probability of mutation is 0.001, with 20 transferred bit positions, we should expect 20×0.001 = 0.02 bits to undergo mutation during a given generation.
  7. The new population is now ready to be assigned fitness values, and tested.

Evolutionary computing harnesses the power of natural selection to turn computers into automatic optimization and design tools. The three mechanisms that drive evolution forward are reproduction, mutation and the Darwinian principle of survival of the fittest. In the biological world these mechanisms enable life forms to adapt to a particular environment over successive generations. The camel’s hump, the eagle’s eye, the dolphin’s sonar, the crafty human brain itself; all these solutions to environmental problems were generated by evolution. All bear witness to its power as a universal optimizer. Like evolution in nature, evolutionary computing also breeds progressively better solutions to a wide variety of complex problems.

White papers on our products and technologies are available upon request. E-mail us at innovation@bluetronix.net or call 440.247.3434.