Skip to content

Instantly share code, notes, and snippets.

@jiunbae
Created July 19, 2017 09:20
Show Gist options
  • Save jiunbae/7dbe86a5c5360a3c9b1e18f262af1c46 to your computer and use it in GitHub Desktop.
Save jiunbae/7dbe86a5c5360a3c9b1e18f262af1c46 to your computer and use it in GitHub Desktop.
Optimizing bogosort genetic algorithm
from random import sample, uniform, randrange, shuffle
from time import sleep
def breed(mother, father):
fetus = mother[:randrange(len(mother))]
sperm = list(filter(lambda x: x not in fetus, father))
return fetus + sperm
def fitness(array):
return len(list(filter(lambda x: x[0]==x[1],
zip(array, sorted(array))))) / float(len(array))
def wheel_choice(items):
p = uniform(0.0, sum(map(fitness, items)))
for item in items:
p -= fitness(item)
if p < 0: return item
return item
def gen_shuffle(array):
childs = [sample(array, len(array)) for _ in range(8)]
mother, father = wheel_choice(childs), wheel_choice(childs)
return breed(mother, father)
def bogo_shuffle(x):
shuffle(x)
return x
def bogo(x, func):
cnt = 0
while x != sorted(x):
x = func(x)
cnt += 1
return cnt
def test(array, epoch, func):
total = 0
for _ in range(epoch):
total += bogo(array[:], func)
print ("""FUNCTION: {}
epoch: {}
array: {}
total: {}
average: {}""".format(func, epoch, array, total, total / float(epoch)))
epoch = 32
size = 8
array = sample(range(size), size)
test(array, epoch, bogo_shuffle)
test(array, epoch, gen_shuffle)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment