Poniendo las Cosas en Práctica - Algoritmos Genéticos: Búsqueda y Optimización por Selección Natural

Blog sobre Optimizacion Avanzado y Algoritmos Genéticos: Búsqueda y Optimización por Selección Natural en Argentina

El ejemplo que veremos puede ser considerado el “Hello World” de AG. Este ejemplo fue presentado inicialmente por J. Freeman en Simulating Neural Networks with Mathematica. Yo lo tomé de Genetic Algorithms and Engineering Design por Mitsuo Gen y Runwei Cheng.

El problema simulador del mundo intenta evolucionar una expresión con un algoritmo genético. Inicialmente, el algoritmo debe “adivinar” la frase “ser o no ser” de listas de letras generadas al azar.

“Ya que hay 26 letras posibles para cada una de las 13 locaciones [excluyendo espacios en blanco] en la lista, la posibilidad de que obtengamos la frase correcta puramente al azar es (1/26)^13=4.03038×10-19, lo cual es aproximadamente dos chances en un [trillón]” (Gen & Chong, 1997).

Vamos a definir el problema un poco más aquí al hacer la solución aún más difícil. Asumamos que no estamos limitados a la lengua inglesa, o una frase específica. Podemos terminar lidiando con cualquier alfabeto, o hasta cualquier set de símbolos. No tenemos conocimiento de la lengua. Ni siquiera sabemos si hay algún idioma.

Digamos que nuestro oponente pensó en una frase arbitraria, incluyendo espacios en blanco. Sabemos el largo de la frase y la cantidad de símbolos en el alfabeto. Ese es el único conocimiento que tenemos. Después de cada suposición, nuestro oponente nos dice cuántas letras se encuentran en su lugar.

Cada cromosoma es una secuencia de índices de los símbolos en el alfabeto. Si hablamos del alfabeto inglés, entonces ‘a’ será representada por 0, ‘b’ por 1, ‘c’ por 2, y así sucesivamente. Entonces, por ejemplo, la palabra “ser” será representada como [4, 1].

Vamos a demostrar todos los pasos a través de trozos de código Java, pero el conocimiento en Java no es un requerimiento para entender cada paso.

El Centro del Algoritmo Genético

Podemos empezar con la implementación general del algoritmo genético:

public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); }}

Este es un set de pasos simples que todo AG debería tener. En el paso inicial, generamos una población inicial de frases. El tamaño de la población está determinada por populationSize. Y como se genera esta frase depende de la implementación del supplier.

Dentro del paso de iteración, evolucionamos la población hasta que se dan las condiciones de término, dentro de la prueba de nudo while. Las condiciones de término pueden incluir el número de generaciones y la pareja perfecta de una de las frases en la población. El termination encapsula una implementación exacta.

Dentro de cada iteración, hacemos los típicos pasos de AG:

  1. Lleva a cabo una selección sobre la población en adecuación de cromosomas.
  2. Produce una nueva “generación” vía la operación de entrecruzamiento.
  3. Lleva a cabo una recombinación de algunas letras en algunas frases.

El centro del algoritmo es muy simple y de dominio agnóstico. Sería el mismo para todo los problemas. Lo que debes ajustar es la implementación de operadores genéticos. Luego, miraremos más de cerca a cada uno de los ya mencionados operadores AG.

Visitar articulo completo sobre Algoritmos Genéticos: Búsqueda y Optimización por Selección Natural

Comparte tu opinion o comenta

Cuenta tu opinion o amplia el contenido del articulo