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: 5
  • Share

Comments

There are currently no comments

New Comment

* Please fill all required form field, thanks!