En este caso, me cruce con un articulo sobre algoritmos genéticos, y se me dio por investigar, y como siempre en Internet hay cosas maravillosas, si uno sabe como buscar.
A continuación viene un resumen de lo que descubrí esta tarde:
A grandes rasgos los algoritmos genéticos constan de 2 partes: mutación y evaluación.
La idea general es: se tiene una población, en la cual los individuos van mutando, y los menos adaptados(los que distan mas de mi objetivo) se van descartando.
En este ejemplo nuestro objetivo va a ser llegar a una cadena de finalizacion por ej. "holamundo", partiendo de cadenas completamente aleatorias, del mismo tamaño (esta ultima restricción para limitar la complejidad).
Si quieren hacer algún paralelismo con la biología, imagínense estas cadenas como el código genético.
En nuestro caso, no estamos buscando que genes son responsables de alguna enfermedad, o como ser inmortales, sino que estamos buscando a partir de un código genético cualquiera llegar a uno que deseemos (nuestro objetivo es un código genético, no lo que este produce).
Esta es nuestra condición de terminación para este ejemplo, y esta muy relacionada con la evaluación que vamos a hacer con nuestros "individuos"
Dijimos antes, que los algoritmos genéticos constan de 2 partes principales. Mutación y Evaluación.
En el caso de las cadenas, la forma más sencilla de mutar es cambiar un caracter dentro de la cadena, por un caracter cualquiera.
En la evaluación, la idea es que nos diga cuan bueno es ese individuo. En nuestro caso, cuan cerca esta de nuestra cadena de finalización.
Esa distancia la vamos a calcular como la suma de la distancia entre las letras en las mismas posiciones de la cadena.
Este ejemplo esta armado en python. Los que lo conocen, perfecto! y los que no, no se asusten, que es un lenguaje de muy sencillo y de fácil lectura.
A continuación están las funciones (metodos para que no me critiquen los que saben POO) para mutar y evaluar.
Mutacion:
def clone(self):
result=""
position=getRandomInt(len(self.string))
for i in range(lstr):
if i != position:
result+=self.string[i]
else:
result+=getRandomChar()
return result
Aclaraciones:
getRandomInt(x) devuelve un numero aleatorio menor o igual que x
getRandomChar() devuelve una letra aleatoria
Esta método tomo la cadena de este individuo (self.string) y devuelve una cadena con un caracter cambiado
Evaluacion:
def fitness(self,string):
result=0
for i in range(len(string)):
result+=abs(ord(string[i])-ord(self.string[i]))
return result
Para los que no sepan python:
ord(c) devuelve el codigo ascii de c
abs(n) devuelve el valor absoluto de n
Este metodo compara la cadena de este individuo(self.string) con la cadena que le paso como argumento. En nuestro caso va a ser la cadena de finalizacion ("holamundo").
Nuestro objetivo va a ser que esta evaluacion de el menor valor posible.
Estos metodos pertenecen a la class Schromosome (cromosoma de cadenas) que se inicializa de la siguiente manera
def __init__(self,slen,string=''):
if string!='':
self.string=string
return
self.string=""
for i in range(slen):
self.string+=getRandomChar()
Esta clase tiene 2 inicializaciones posibles, si le pasas el parámetro "string", inicializa la cadena de ese individuo con ese parámetro, sino genera una cadena aleatoria de longitud "slen".
Ya tenemos definido a nuestro individuo.
Como esta definido, los individuos van a empesar con una cadena alatoria y los vamos a ir haciendo mutar para lograr que esa cadena se valla acercando a nuestra cadena de finalizacion.
Vamos con el programa principal:
Definimos y inicializamos nuestra población:
pop=50
population=[]
for i in range(pop):
population.append(Schromosome(len(endString)))
Definimos nuestra cadena de finalizacion:
endString='holamundo'
Ordeno a la poblacion de acuerdo a su evaluación:
population.sort(key=lambda guy: guy.fitness(endString))
Este orden va a ser muy importante porque nos va a permitir definir quienes son los peores individuos dentro de nuestra población para poder descartarlos.
A mutar se a dicho:
Ahora nos queda definir como vamos a hacer mutar a nuestros individuos.
Para este caso la estrategia que elegí fue: agarrar a un individuo cualquiera y mutarlo hasta que sea mejor que si mismo. Con este nuevo individuo ( el original sigue estando en la población como estaba) reemplazo al peor individuo de la
población.
Esta proceso continua hasta que alguno de los individuos llega a la cadena de finalizacion.
iteration=0
while True:
guy=population[getRandomInt(pop)]
prev=guy.fitness(endString)
new=prev
while prev<=new:
newguy=Schromosome(0,guy.clone())
new=newguy.fitness(endString)
population[pop-1]=newguy
population.sort(key=lambda guy: guy.fitness(endString))
print ('iteration:',iteration,'best:',population[0].string)
iteration+=1
if newguy.string==endString:
break
Esta es una primera aproximación a un algoritmo genético. Asi como esta armado tarda entre 300 y 400 iteraciones en terminar.
Faltarían agregar algunas cosas como ser reproducción y selección. Posiblemente quede para un próximo post.
El código completo esta en :
http://pastebin.com/en8MvzZP
