ALGORITMOS GENETICOS. PROBLEMA DE LAS 8 REINAS EN PYTHON

(Comments)

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!

Current rating: 3.4

Comments