Genetic algorithm to generate a super single hardcoded.

geneticpoc

#!/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()