Skip to content

Instantly share code, notes, and snippets.

@jogonba2
Created February 22, 2015 03:15
Show Gist options
  • Save jogonba2/bbe046f0edc9a3f1f741 to your computer and use it in GitHub Desktop.
Save jogonba2/bbe046f0edc9a3f1f741 to your computer and use it in GitHub Desktop.
Genetic algorithm to generate a super single hardcoded.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Overxfl0w13 - 2015
from random import randint
# El objetivo es generar el super individuo #
super_single = 0b101010101
# Usaremos como función de evaluación el propio número, tendrá mayor valor cuanto mayor sea el número y por tanto más cerca del super individuo esté #
def genetic_algorithm():
population_size = 6
population,counter,max_iter = get_init_population(population_size),0,10000000
while super_single not in population and counter<max_iter:
best_singles = get_best_singles(population)
num_best_singles = population_size/2
population = {}
for x in xrange(population_size/2):
first_single = randint(0,num_best_singles-1)
second_single = None
# No se permite reproducción asexual #
while second_single != first_single: second_single = randint(0,num_best_singles-1)
descendants = get_descendants(first_single,second_single)
first_descendant,second_descendant = mutate_single(descendants[0]),mutate_single(descendants[1])
population[first_descendant],population[second_descendant] = first_descendant,second_descendant
counter += 1
if counter<max_iter:
print " ! Super single reached at iteration: " + str(counter) + "\n"
pretty_print(population)
else : print " ! Super single not reached, max limit " + str(max_iter) + " exceeded \n"
def get_init_population(num_singles):
first_population = {}
for x in xrange(num_singles):
single = randint(0b00000000,0b01010101)
first_population[single] = single
return first_population
def get_best_singles(population):
return sorted(population, key=population.get,reverse=True)
def get_descendants(first_single,second_single):
# Si se reproducen generan 2 individuos nuevos, si no siguen ellos en la siguiente poblacion #
reproduction = randint(0,1)
if reproduction==1: return make_reproduction(first_single,second_single)
else: return (first_single,second_single)
def make_reproduction(first_single,second_single):
# Punto de cruce aleatorio, permutar al menos un bit y no todos #
crosspoint,first_descendant,second_descendant = randint(1,7),0b00000000,0b00000000
first_mask,second_mask = int("0b"+"1"*crosspoint,2),int("0b"+"1"*(8-crosspoint),2)
# Crear primer descendiente #
first_descendant = ((first_single&first_mask)<<crosspoint)|(second_single&second_mask)
# Crear segundo descendiente #
second_descendant = ((second_single&first_mask)<<crosspoint)|(first_single&second_mask)
return (first_descendant,second_descendant)
def mutate_single(single):
for x in xrange(8):
# P(mutacion) = 0.1 #
if randint(0,100)<10: single ^= 0b000000001<<(8-x)
return single
def pretty_print(population):
print "---- POPULATION ----\n"
for single in population:
print " -> " + bin(single) + " -> " + str(single)
print "\n--------------------\n"
if __name__ == "__main__":
genetic_algorithm()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment