GA based Sorting (Bogosort?) using pyevolve
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!