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!

Advertisement

pyevolve: SBX implementation

pyevolve is an evolving (no pun intended) pure Python GA/GP framework. I have been playing with it during my spare time and I am happy to blog that I have done my first contribution to it by providing support for the widely used Simulated Binary Crossover (SBX) crossover method in Real coded Genetic Algorithms. This is the changeset.

This will be available in the upcoming 0.6 release, but why wait, when you can now pull it from the SVN repository.