Problem Definition

Many problems in the world that we wish to solve are intractable, that is, it will take more than polynomial time to find the optimal solution. In most situations a sub-optimal solution can be used instead and a range of techniques have been developed to provide a near optimal solution in minimal time.

Genetic algorithms are one such technique. They begin by generating a population of potential solutions to the problem, encoded on genes. Over a number of generations new solutions are bred by crossing and mutating. Solutions compete for space within the population and those who cannot compete, die out. The process of selection, similar to natural selection, will find a near optimal solution after a number of generations.

There are five characteristic components in every genetic algorithm:

  • a genetic representation for solutions to the problem
  • a way to create an initial population of potential solutions
  • an evaluation function that plays the role of the environment, rating solutions in terms of their fitness
  • genetic operators that alter the composition of children during reproduction
  • values for various parameters that the genetic algorithm uses (population size, probability of applying genetic operators)

Each component can be represented in a number of different ways and used in many algorithms. MUTANTS will provide a library of these genetic algorithm components. Reuse of components speeds the creation of an algorithm giving the chance for experimentation to produce faster or better algorithms.