Does a Genetic Algorithm Always Have To Be Population Based??

Genetic algorithm (GA) is a computational method of problem solving which draws inspirations from the mechanisms of evolution. It is a population based algorithm in which the population consist of potential solutions, called genotypes. The first step is the encoding process which simply creates a ‘template’ to represent a solution. Note that these potential solutions are not the real solution to the problem; they are just a random instance of a potential solution. A simple analogy for this process in computer programming would be to define what data type to be used and then randomly generating values of that data type. The algorithm will then ‘evolve’ the population over a number of generations using a fitness function which gives guidelines to evaluate the genotypes and thereby a way to produce better genotypes.

Recombination and mutation are the techniques which are used to evolve the solution of the algorithm. Both of these methods are modelled on their biological counterparts. Recombination involves taking two genotypes and creating a new genotype by combining these two genotypes in some fashion. Mutation involves altering the values of the genotype to any other values permitted by the encoding ‘template’. Over the generations, the older genotypes ‘dies’ off and are replaced by better genotypes. Hence, we get a population with higher average fitness value which will move towards the correct or optimal solution.

In the classical view of genetic algorithm, the evolutionary landscape was thought to be rugged as shown in the figure above and the algorithm was seen as performing a ‘hill climbing’ function on this landscape. In such scenario, there is a chance of not finding the global optima. Neutral networks are like ridges connecting two terrains with same fitness value. Thus, the search can jump from one terrain to another by mutation. If such networks exist abundantly throughout the landscape, the search will never get stuck in local optima and hence the evolutionary dynamics changes considerably. The term ‘neutral network’ has been conceived by Schuster while doing research on RNA evolution. Thus the landscape can now be viewed as layers of neutral networks connected by mutations where each neutral network has a unique fitness value.

In the presence of such networks, a new algorithm has been proposed which is very different from the traditional genetic algorithm. This algorithm doesn’t use recombination method and have a population of only one genotype. A mutated genotype is created and the fitness values of the mutated genotype and the original genotype are compared. If the fitness value of the mutated genotype is smaller than the original genotype, the original genotype is selected for further mutation; otherwise the mutated genotype is selected for further mutation. These steps are repeated a number of times till we get an optimal solution. And it has been shown that this algorithm performs much better than the population based GA which shows that a GA doesn’t need to be population based all the time, at least not when there are neutral networks.