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.
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:
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.