Solution Spaces

The Bogosort algorithm is a (highly inefficient) sorting algorithm. It uses the trial and test technique. The step-by-step procedure of this algorithm is as follows :

  1. Are the array elements sorted? If yes, return the array.
  2. Randomly shuffle the array. Return to step 1.

The larger the size of the array, the more time it is going to take for this algorithm to run since the algorithm has to exhaustively search all possible permutations. But we can guarantee that the program will terminate because we have bound the algorithm to a solution space where we are certain our (most optimum) solution exists. In the case of the bogosort program, our solution space is the permutations of the initialised array and we know that the ordered array is also a permutation of the initialised array.

There is no way for this algorithm to figure out how good the solution it guessed was. To make an algorithm that is purely based on randomization reach a solution more efficiently, we need to give it the ability to recognize and grade solutions that are better than the others.

“Survival of the Fittest” — Natural Selection and Evolution

The traits of all animals were a product of evolution. Animals that needed to fly further adapted their wings to do so. Animals that needed to reach higher leaves grew longer necks.

More importantly, animals with traits that made them more likely to survive in their environment and produce offspring were preferred in nature over those that couldn’t. Favourable attributes produced in a generation of parents are propagated to their descendants, ensuring the survivability of the offspring.

The Genetic Algorithm

The genetic algorithm falls under the family of evolutionary computation. In these types of algorithms, an initial batch of solutions is iterated on until we reach an optimized solution. We reach this solution by selecting the solutions from the batch which are preferred more than the others and giving them a higher probability of propagating them to the next generation. To generate more variation between generations of solutions, operations such as cross-breeding and mutation are used.

Scroll to Top