El AG es una búsqueda meta-heurística al igual que una técnica de optimización basada en principios presentes en la evolución natural. Pertenece a una clase más larga de algoritmos evolutivas.
El AG mantiene una población de cromosomas—un set de soluciones posibles para el problema. La idea es que la “evolución” encuentre una solución óptima para el problema después de un número de generaciones sucesivas—similar a una selección natural.
El AG imita tres procesos evolutivos: selección, entrecruzamiento cromosómico y mutación.
Tal como la selección natural, el concepto central de la selección AG es la adaptación. Los cromosomas que se adaptan mejor tienen una mayor oportunidad de sobrevivir. La adaptación es una función que mide la calidad de la solución representada por el cromosoma. En esencia, cada cromosoma dentro de la población representa los parámetros de entrada, como el volumen y precio de cambio, cada cromosoma, lógicamente, consistirá de dos elementos. Como los elementos están codificados dentro del cromosoma es otro tema.
Durante la selección, los cromosomas forman parejas de padres para la reproducción. Cada niño toma características de sus padres. Básicamente, el niño representa una recombinación de características de sus padres: Algunas de las características son tomadas de un padre y otras del otro padre. Adicionalmente a la recombinación, algunas de las características pueden mutar.
Ya que los cromosomas más adecuados producen más niños, cada generación subsecuente será más adecuada. En algún punto, una generación contendrá un cromosoma que representará una solución lo suficientemente buena para nuestro problema.
El AG es poderoso y ampliamente aplicable a problemas complejos. Hay una clase extensa de problemas de optimización que son un tanto difícil de resolver usando técnicas convencionales de optimización. Los algoritmos genéticos son algoritmos eficientes que poseen soluciones aproximadamente óptimas. Las ya bien conocidas aplicaciones incluyen programación, transporte, planificación de ruta, tecnologías de grupo, diseño de plano, entrenamiento de red neural y muchos otros.
Poniendo las Cosas en Práctica
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() {
List<T> population = Stream.generate(supplier)
.limit(populationSize)
.collect(toList());
while (!termination.test(population)) {
population = selection(population);
crossover(population);
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:
- Lleva a cabo una selección sobre la población en adecuación de cromosomas.
- Produce una nueva “generación” vía la operación de entrecruzamiento.
- 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.
Selección
Como ya sabemos, la selección es un proceso hecho para encontrar sucesores para los cromosomas actuales—los cromosomas que sean más adecuados para nuestro problema. Durante la selección, necesitamos asegurar que los cromosomas con mejor adecuación tienen más chance de sobrevivir.
private List<T> selection(List<T> population) {
final double[] fitnesses = population.stream()
.mapToDouble(fitness)
.toArray();
final double totalFitness = DoubleStream.of(fitnesses).sum();
double sum = 0;
final double[] probabilities = new double[fitnesses.length];
for (int i = 0; i < fitnesses.length; i++) {
sum += fitnesses[i] / totalFitness;
probabilities[i] = sum;
}
probabilities[probabilities.length - 1] = 1;
return range(0, probabilities.length).mapToObj(i -> {
int index = binarySearch(probabilities, random());
if (index < 0) {
index = -(index + 1);
}
return population.get(index);
}).collect(toList());
}
La idea de esta implementación es la siguiente: La población es representada como rasgos consecuentes en el eje numérico. La población completa está entre 0 y 1.
El trozo de la serie que toma un cromosoma es proporcional a su adecuación. Esto da como resultado un cromosoma mucho más adecuado el cual toma un trozo más grande. Luego escogemos un número al azar entre 0 y 1 y encontramos una serie que incluye este número. Obviamente, las series más grandes tienen mejor oportunidad de ser seleccionados, por ende, los cromosomas más adecuados tienen mejor oportunidad de sobrevivir..
Ya que no conocemos detalles sobre la función de la adecuación, necesitamos normalizar los valores de adecuación. La función de adecuación es representada por fitness, la cual convierte a un cromosoma en un doble arbitrario que representa la adecuación del cromosoma.
En el código, encontramos una tarifa de adecuación para todos los cromosomas en la población y también encontramos la adecuación total. Dentro del nudo for, ejecutamos una suma acumulativa sobre probabilidades disminuidas por adecuación total. Matemáticamente, esto debería resultar en la variable final teniendo un valor de 1. Debido a la imprecisión del punto flotante, no podemos garantizar eso, así que lo ajustamos a 1 para estar seguros.
Finalmente, por una cantidad de tiempo igual al número de cromosomas entrantes, generamos un número al azar, encontramos una serie que incluya el número y luego seleccionamos el cromosoma correspondiente. Como debes haber notado, el mismo cromosoma puede ser seleccionado muchas veces.
Entrecruzamiento
Ahora necesitamos que los cromosomas se “reproduzcan.”
private void crossover(List<T> population) {
final int[] indexes = range(0, population.size())
.filter(i-> random() < crossoverProbability)
.toArray();
for (int i = 0; i < indexes.length / 2; i++) {
shuffle(Arrays.asList(indexes));
final int index1 = indexes[2 * i];
final int index2 = indexes[2 * i + 1];
final T value1 = population.get(index1);
final T value2 = population.get(index2);
population.set(index1, crossover.apply(value1, value2));
population.set(index2, crossover.apply(value2, value1));
}
}
Con la probabilidad predefinida como crossoverProbability, seleccionamos padres para la reproducción. Los padres que sean seleccionados son mezclados, permitiendo así que se de cualquier combinación. Tomamos parejas de padres y aplicamos el operador crossover. Aplicamos el operador dos veces para cada pareja porque necesitamos mantener el mismo tamaño de la población. Los niños reemplazan a los padres en la población.
Mutación
Finalmente, llevamos a cabo la recombinación de las características.
private void mutation(List<T> population) {
for (int i = 0; i < population.size(); i++) {
if (random() < mutationProbability) {
population.set(i, mutation.apply(population.get(i)));
}
}
}
Con la probabilidad mutationProbability predefinida, llevamos a cabo la “mutación” en los cromosomas. La mutación como tal es definida como mutation.
Configuración de Algoritmo de Problema-Específico
Ahora echemos un vistazo a qué tipo de parámetros de problema específico necesitamos proveer para nuestra implementación genérica.
private BiFunction<T, T, T> crossover;
private double crossoverProbability;
private ToDoubleFunction<T> fitness;
private Function<T, T> mutation;
private double mutationProbability;
private int populationSize = 100;
private Supplier<T> supplier;
private Predicate<Collection<T>> termination;
Los parámetros, respectivamente, son: 1. Operador de entrecruzamiento 2. Probabilidad de entrecruzamiento 3. Función de adecuación 4. Operador de mutación 5. Probabilidad de mutación 6. Tamaño de la población 7. Proveedor de cromosomas para la población inicial 8. Función de término
Aquí está la configuración de nuestro problema:
new GeneticAlgorithm<char[]>()
.setCrossover(this::crossover)
.setCrossoverProbability(0.25)
.setFitness(this::fitness)
.setMutation(this::mutation)
.setMutationProbability(0.05)
.setPopulationSize(100)
.setSupplier(() -> supplier(expected.length))
.setTermination(this::termination)
.find()
Operador de Entrecruzamiento y Probabilidad
private char[] crossover(char[] value1, char[] value2) {
final int i = (int) round(random() * value1.length);
final char[] result = new char(value1.length);
System.arraycopy(value1, 0, result, 0, i);
System.arraycopy(value2, i, result, i, value2.length - i);
return result;
}
La probabilidad de entrecruzamiento es 0.25, así que esperamos que en promedio, 25 por ciento de los cromosomas sean seleccionados para el entrecruzamiento. Llevamos a cabo un simple procedimiento, para el entrecruzamiento de un par de cromosomas. Generamos un número al azar n para la selección [0..length], dónde length es el largo del cromosoma. Ahora unimos la pareja seleccionada tomando el primer símbolo n de uno de los cromosomas y el resto de los símbolos después del segundo.
Función Adecuada
private double fitness(char[] value) {
return range(0, value.length)
.filter(i -> value[i] == expected[i])
.count();
}
La función adecuada simplemente cuenta el número de combinaciones entre la frase clave y el cromosoma dado.
Operador de Mutación y Probabilidad
private char[] mutation(char[] value) {
final char[] result = Arrays.copyOf(value, value.length);
for (int i = 0; i < 2; i++) {
int letter = (int) round(random() * (ALPHABET.length - 1));
int location = (int) round(random() * (value.length - 1));
result[location] = ALPHABET[letter];
}
return result;
}
La operación de mutación se ejecuta independientemente en cada cromosoma. La probabilidad de mutación es de 0.05, así que esperamos que, en promedio cinco por ciento de la población sea mutada. Mutamos al escoger una posición de letra al azar y reemplazar su valor con una letra al azar del alfabeto. Lo hacemos dos veces por cada cromosoma mutado.
Proveedor
private char[] supplier(int length) {
final char[] result = new char(length);
for (int i = 0; i < length; i++) {
int letter = (int) round(random() * (ALPHABET.length - 1));
result[i] = ALPHABET[letter];
}
return result;
}
El proveedor genera frases al azar tomando letras del alfabeto igualmente al azar. Cada frase tiene un largo constante predefinido.
Función de Término
private boolean termination(Collection<char[]> chars) {
count++;
final Optional<char[]> result = chars.stream()
.filter(value -> round(fitness(value)) == expected.length)
.findAny();
if (result.isPresent()) {
System.out.println("Count: " + count);
System.out.println(result.get());
return true;
}
final boolean terminated = count == 3000;
if (terminated) {
chars.forEach(System.out::println);
}
return terminated;
}
La función término cuenta el número de llamadas y regresos true, si hay ya una pareja exacta, o si la cuenta de la generación llega a 3,000.
Ejecución
Ahora estamos listos para probar nuestro algoritmo. Si lo ejecutas varias veces, notarás que no todas las ejecuciones son exitosas. En cada oportunidad, el número de iteraciones será diferente. Esto se debe a una naturaleza de probabilidad del algoritmo. El algoritmo tiene varios puntos donde se puede mejorar. Puedes jugar con entrecruzamiento y probabilidades de mutación.
Bajar el número a una solución estable pero lenta. Un número más pequeño de cromosomas se verá afectado por operadores genéticos, por tanto, más iteraciones serán requeridas para la solución.
Aumentar los números acelerará el algoritmo, pero también hará que la solución sea inestable. Los cromosomas adecuados no solo serán preservados, pero también se verán afectados por los operadores genéticos. Por este motivo, perderán sus “buenos” genes.
Es importante encontrar un buen balance. Aumentar el número de iteraciones le dará al algoritmo más oportunidades para encontrar una solución pero, por otra parte, tomará más tiempo. También aplicar métodos diferentes de entrecruzamiento y mutación. Una buena selección de estos operadores mejorará drásticamente la calidad de la solución.
¿Qué sigue?
Hemos cubierto solo la punta del iceberg. Tomamos un ejemplo que tiene solo una entrada y ésta puede ser presentada, fácilmente, como un cromosoma. Los operadores genéticos son simples.
Es muy interesante tomar un problema de la vida real y aplicar el algoritmo genético a éste. Descubrirás diferentes acercamientos al codificar entradas de data reales, al igual que diferentes implementaciones de entrecruzamiento y mutación.
Si un problema puede ser expresado a través de un set de parámetros que tenemos que adivinar para optimizar una métrica, podemos establecer rápidamente un AG que podemos usar para resolverlo.
Uno de los problemas más interesantes es enseñar redes neuronales artificiales. Podemos establecer los parámetros optimizados para ser fuerzas sinapsis y para que la métrica adecuada sea el porcentaje de entradas por el cual nuestras redes neurales hayan dado la respuesta correcta. Después de eso, nos podemos relajar y dejar que nuestras redes neurales evolucionen en la solución ideal que deseamos. O al menos hasta que tengamos algo lo suficientemente bueno, porque la evolución toma tiempo.
Si aun no te has registrado en el servicio de UBER y quieres llevarte un viaje gratis, esta es tu oportunidad, lo único que debes hacer es registrarte a través del siguiente vínculo: https://www.uber.com/invite/b2rc48pmue y luego colocar el código promocional b2rc48pmue .
