Genetic algorithm: Hypothesis space search

As already understood from our illustrative example, it is clear that genetic algorithms employ a randomized beam search method to seek maximally fit hypotheses. In the hypothesis space search method, we can see that the gradient descent search in backpropagation moves smoothly from one hypothesis to another. On the other hand, the genetic algorithm search can move much more abruptly. It replaces the parent hypotheses with an offspring that can be very different from the parent. Due to this reason, genetic algorithm search has lower chances of it falling into the same kind of local minima that plaques the gradient descent methods.

There is one practical difficulty that is often encountered in genetic algorithms, it is crowding. Crowding can be defined as the phenomenon in which some individuals that are more fit in comparison to others, reproduce quickly, therefore the copies of this individual take over a larger fraction of the population. Most of the strategies used in the genetic algorithms are inspired by biological evolution. One such other strategy used is fitness sharing, in which the measured fitness of an individual is decreased by the presence of another individual of a similar kind. The third method is to restrict all the individuals to combine to form offspring. To better understand we can say that by allowing individuals of the same kind to recombine, clusters of similar individuals are formed, forming multiple subspecies in the population.

Another method would be to spatially distribute individuals and allow only nearby individuals to combine.

Population evolution and schema theorem.

The schema theorem of Holland is used to mathematically characterize the evolution over time of the population with respect to time. It is based on the concept of schema. So, what is schema? Schema is any string composed of 0s, and 1s, and *s, where * represents null, so a schema 0*10, is the same as 0010 and 0110. The schema theorem characterizes the evolution within a genetic algorithm on the basis of the number of instances representing each schema. Let us assume the m(s, t) to denote the number of instances of schema denoted by ‘s’, in the population at the time ‘t’, the expected value in the schema theorem is described as m(s, t+1), in terms of m(s, t), and the other parameters of the population, schema, and GA.

In a genetic algorithm, the evolution of the population depends on the selection step, the recombination step, and the mutation step. The schema theorem is one of the most widely used theorems in the characterization of population evolution within a genetic algorithm. If it fails to consider the positive effects of crossover and mutation, it is in a way incomplete. There are many other recent theoretical analyses that have been proposed, many of these analogies are based on models such as Markov chain models and the statistical mechanical model.

Reference

Genetic algorithm: Hypothesis space search