echo \$RANDOM

## Category: pyevolve

### 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!