### GA based Sorting (Bogosort?) using pyevolve

#### by Amit

*If Monkeys can compose Shakespeare, they can sort numbers too*

I love the awful simplicity of the Infinite Monkey Theorem. Bogosort is a sorting algorithm in that spirit. I had posted a Scheme implementation a while ago.

pyevolve currently contains an example of the Infinite Monkey theorem in the *pyevolve_ex22_monkey.py* file. If Monkeys can compose Shakespeare, they can sort numbers too. Here is my GA based sorting implementation using *pyevolve *(Note that this source code will be a part of the *pyevolve* examples and the licensing applies ) :

# Bogosort using GAs- Random sort using GA # Another PoC of Infinite Monkey Theorem # Amit Saha import math import random import logging from pyevolve import pyevolve from pyevolve import G1DList from pyevolve import GSimpleGA from pyevolve import Selectors from pyevolve import Crossovers from pyevolve import Statistics from pyevolve import Consts from pyevolve import Initializators # numbers to sort numbers = [10,5,-99,7,8,9,4,3,1,0] def eval_func(genome): score = 0 for i in range(0,len(genome)-1): if numbers[genome[i]] > numbers[genome[i+1]]: score = score + 1 return score def G1DListBogoInitializator(genome, **args): """ The initializator for Bogo sorrt""" lst = [i for i in xrange(genome.getListSize())] random.shuffle(lst) genome.genomeList = lst def run_main(): # Genome instance, 1D List of 2 elements (2 variable problem) genome = G1DList.G1DList(len(numbers)) # Sets the range max and min of the 1D List genome.setParams(bestrawscore=0) # Set the Initializator genome.initializator.set(G1DListBogoInitializator); # The evaluator function (evaluation function) genome.evaluator.set(eval_func) # Set the crossover algorithm genome.crossover.set(Crossovers.G1DListCrossoverEdge) # Genetic Algorithm Instance ga = GSimpleGA.GSimpleGA(genome, random.random()) ga.setCrossoverRate(1.0) ga.setMutationRate(0.05) ga.setPopulationSize(100) #Set raw score = 0.0 as termination criteria ga.terminationCriteria.set(GSimpleGA.RawScoreCriteria) # Minimize the function ga.setMinimax(Consts.minimaxType["minimize"]) # Do the evolution, with stats dump # frequency of 10 generations ga.evolve(freq_stats=10) # Best individual print ga.bestIndividual() print "Sorted Numbers" for i in ga.bestIndividual(): print numbers[i], if __name__ == "__main__": run_main()

Some notes on the code above:

- In GA, we need a measure of the
**fitness**of a solution. Here I have used the number of elements*out of order*as a measure of fitness. In a sorted array of numbers, all the elements are in order, i.e a score of 0.0 - The crossover operator used here is the
*Edge Recombination Operator* - The termination criteria is the raw score of 0.0 (explained in the first point)

**Is this Bogo sort?**

Strictly No. Bogo sort is supposedly purely random. GAs give a direction to the sorting algorithm here. So, may be this is pseudo-bogosort!