Genetic Algorithms

Genetic algorithms are stochastic search algorithms, which act on a population of possible solutions. They are loosely based on the mechanics of population genetics and selection. The potential solutions are encoded as `genes' | strings of characters from some alphabet. New solutions can be produced by `mutating' members of the current population, and by `mating' two solutions together to form a new solution. The better solutions are selected to breed and mutate and the worse ones are discarded. They are probabilistic search methods; this means that the states, which they explore, are not determined solely by the properties of the problems. A random process helps to guide the search. Genetic algorithms are used in artificial intelligence like other search algorithms are used in artificial intelligence to search a space of potential solutions to one which solves the problem.

In machine learning we are trying to create solutions to some problem by using data or examples. There are essentially two ways to do this. Either the solution is constructed from the data, or some search method is used to search over a class of candidate solutions to find an effective one.

Genetic algorithms are important in machine learning for three reasons. First, they act on discrete spaces, where gradient-based methods cannot be used. Second, they are essentially reinforcement learning algorithms. The performance of a learning system is determined by a single number, the fitness. Finally, genetic algorithms involve a population and sometimes what one desires is not a single entity but a group.