La idea de Algoritmos Genéticos, se basa en la teoría de la evolución de las especies, de Charles Darwin (1859). La idea principal es que las variaciones o mutaciones, ocurren en la reproducción y serán conservadas en base a la idoneidad reproductiva.
Los Algoritmos Genéticos se basan en la búsqueda paralela de soluciones, hasta dar con una suficientemente válida o se aborta el programa si no se encuentra dicha solución y el tiempo transcurrido de cómputo no es aceptable.
Inicialmente se genera una población (soluciones posibles en un array), que van regenerándose en base a un cruce de 2 individuos (cadenas de genes o ADN) de dicha población, sucesivamente y aleatoriamente, se mutan genes del individuo en cuestión.
Existe una función de idoneidad que evalúa cada individuo de la población y determinará si un individuo es suficientemente válido como para ser considerado la solución al problema que abordamos.
La probabilidad de elección de dos individuos para cruce (crossover) y mutación, debería ser directamente proporcional a su idoneidad como solución. En mi desarrollo no implementé dicha mejora, pero queda como ejercicio a quien quiera desarrollarla. Probablemente yo lo haga en un futuro.
El problema que nos ocupa, (8 reinas) consiste en un tablero de 8x8, con 8 reinas que se presuponen oponentes y debemos situarlas de forma que ninguna de jaque a las demás, ni horizontal, vertical o diagonalmente.
El pseudocódigo principal está en el método “algoritmo”, de la clase Agenetico en el código. Voy a comentar dicho código, ya que es la clave del desarrollo.
def algoritmo(self, poblacion):
while True:
npobla=[]
for i in range(len(poblacion)):
x=self.seleccion(poblacion)
y=self.seleccion(poblacion)
hijo=self.reproducir(x, y)
if rnd.randint(1, 20)<3:
hijo=self.mutar(hijo)
npobla.append(hijo)
if npobla[i].fitness>=(self.casillas*self.casillas-self.casillas):
return npobla[i]
poblacion=npobla
Como dije anteriormente, inicialmente creamos una población aleatoria y vamos modificandola en base a la funcion reproducir y aleatoriamente mutamos un gen del individuo hijo.
De esta forma, generamos npobla (otro array) donde almacenamos la nueva población, evaluamos la idoneidad (fitness) del individuo actual y devolvemos el individuo idóneo (solución válida) para posteriormente finalizar el proceso al mostrar la solución.
Las soluciones que encontramos al problema de las 8 reinas pueden variar, pero en nuestra ejecución son las siguientes:
. . R .
R . . .
. . . R
. R . .
fitness: 12 0.020
. . R . .
R . . . .
. . . R .
. R . . .
. . . . R
fitness: 20 0.028
. . R . . .
. . . . . R
. R . . . .
. . . . R .
R . . . . .
. . . R . .
fitness: 30 2.270
. . . R . . .
R . . . . . .
. . . . R . .
. R . . . . .
. . . . . R .
. . R . . . .
. . . . . . R
fitness: 42 0.059
. . R . . . . .
. . . . . R . .
. . . . . . . R
R . . . . . . .
. . . R . . . .
. . . . . . R .
. . . . R . . .
. R . . . . . .
fitness: 56 0.069
. . . . . . . . R
. . . R . . . . .
. . . . . R . . .
. . . . . . . R .
. R . . . . . . .
. . . . . . R . .
R . . . . . . . .
. . R . . . . . .
. . . . R . . . .
fitness: 72 862.279
Hice la prueba, desde 4 hasta 9 casillas. Como vereis, la ejecución con 9 casillas muestra la necesidad de mayor optimización del código, ya que se dispara en tiempo de proceso.
El código completo es el siguiente: Descargar
Espero que os haya despertado la curiosidad, como mínimo sobre los algoritmos genéticos, y que os haya gustado el artículo.
Gracias por la lectura.
Un saludo y hasta la próxima!
blog comments powered by