====== Algoritmos genéticos ======
===== Introducción =====
==== Genética ====
Los organismos contienen celulas, dentro de estas encontramos cadenas en espiral de DNA llamadas cromosomas. Las cadenas de DNA se constituyen por pequeños bloques llamados genes formados por nucleotidos, hay 4 tipos Thymine, Adenine, Cytosine y Guanine (TACG). La información del DNA se llama 'allele' y las características de este 'locus'. El DNA define el organismo y también es conocido como Genoma, el Genotipo será una configuración específica de los alleles. Un genotipo complejo es un Phenotype.
El mundo está lleno de Phenotypes (personas, animales, plantas...), siendo muy distintos organismos... Y un organismo llegará a ser eficiente si este realiza las tareas adecuadas (sobrevivir a depredadores, encontrar comida, reproducirse...), para que un organismo pueda hacer todo esto deberá evolucionar, aún así pueden exister factores que entorpezcan su evolución. La forma de medir la eficiencia de un organismo es llamada fitness.
Cuando dos organismos son agrupados y se reproducen, sus cromosomas son mezclados para crear un nuevo grupo de cromosomas consistente en los genes de ambos padres. Este proceso es llamado recombinación o crossover. El nuevo organismo heredará los genes buenos y los malos, el nuevo organismo repetirá este proceso. Cada generación debería de mostrar una tendencia a ser mejor que la anterior, haciendo perdurar las características más "solicitadas" en las parejas.
Lo que ocurre es parecido al efecto que surge cuando se juega al juego del teléfono, un mensaje inicial va traspasandose de persona a persona y a la vez cambiando. Este proceso de cambio en los organismos es llamado mutación, y puede ser bueno, o malo para el individuo. Aún así hemos de pensar que a la larga perdurarán aquellos que sean beneficiosos para "la raza", ya que con el tiempo sobrvivirán los que tengan más ventajas.
==== Emulando la evolución ====
Los algoritmos genéticos trabajan igual que la evolución de razas, se codifica un problema como un cromosoma digital, se crea una población inicial de cromosomas aleatorios y estos evolucionan añadiendoseles pequeñas mutaciones.
Estos cromosomas digitales son series de 0s y 1s aleatorios, un número binario. Al implementar esta idea es importante hacerlo de forma que pueda ser decodificado para dar una solución. En un principio, el primer grupo de cromosomas representará una solución terrible pero mediante el paso de generaciones (las iteraciones del próximo algoritmo), poco a poco llegaremos a una solución correcta.
=== Algoritmo para encontrar una solución ===
- Se revisa cada cromosoma para ver cuan bueno es resolviendo el problema y se asigna una puntuación adecuada a su calidad (fitness).
- Se seleccionan 2 miembros de la población actual. La probabilidad de ser seleccionados vendrá dada por su fitness. A más fitness más probabilidad de ser seleccionados (método usado: La selección mediante la ruleta de la fortuna).
- Dependiendo del índice de cruzados (crossover rate), se cruzarán bits aleatorios de cada cromosoma.
- Se escogen los bits de los cromosomas y se modificarn según el índice de mutación.
- Se repetirán los pasos 2, 3, 4 hasta que se cree la población con el tamaño adecuado.
Este algoritmo se realiza dentro de un bucle, cada iteración representa una generación.
La realización del bucle completo es una época.
=== Selección mediante la ruleta de la fortuna ===
Este es un método de escoger miembros de la población de forma proporcional a su fitness. El cromosoma más preparado tendrá un tanto por ciento mayor de ser seleccionado, aunque esto no garantice que ese cromosoma sea seleccionado para la próxima generación sí que tendrá más posivilidades. Es algo así como imaginar un gráfico de sectores, donde el tamaño del sector es proporcional al fitness del miembro, luego se escoge el cromosoma de forma parecida a como se hace en una ruleta de la fortuna.
=== Índice de cruzado (crossover rate) ===
Es la probabilidad de que dos cromosomas escogidos junten sus bits para producir nueva descendencia. Este valor debería de ser sobre el 0.7, según el autor. Cada vez que se escogen dos cromosomas de la población se eligirá como cruzarlos mediante la generación de un número entre 0 y 1, si el número es menor que el crossover rate (0.7), entonces se escoge una posición aleatoria y se intercambian todos sus bits a partir de ese punto...
Ejemplo, dos cromosomas: \\
10001001110010010
01010001001000011 \\
se escoge la posción aleatoria, pongamos 10, pues intercambiaremos sus bits a partir de esa posición: \\
10001001101000011
01010001010010010
=== Índice de mutación (mutation rate) ===
Es la probabilidad que un bit dentro de un cromosoma sea cambiado (que un 0 pase a ser 1 y viceversa). Entonces... Cuando se escoge un cromosoma de la población, primero se chequeará el cruce, y entonces se moverán cada bit de los cromosomas de la descencencia según cuan necesario sea cruzarlos.
==== Una primera aproximación ====
=== Problema ===
El problema a tratar va a ser el de encontrar la salida de un pequeño laberinto. Para ello vamos a necesitar dos clases principales, una que represente al laberinto y otra a Bob, correspondiente a la IA y por tanto quien tendrá que encontrar la salida. \\
La clase correspondiente al laberinto no tiene gran dificultad, una matriz de enteros con tantas filas y columnas como el laberinto indique correspondiendo a una cuadrícula donde los 0 representa los lugares por donde se puede pasar, los 1 por donde no, el 2 la entrada y el 3 la salida. Realmente la dificultad del problema está en la clase Bob.
=== El genoma ===
La clase genoma es la base para resolver un problema mediante algoritmos genéticos. A parte de otros elementos, contiene un vector de cromosomas (valores 0 o 1) y un valor de fitness. Un objeto genoma representa un camino que Bob puede tomar para salir del laberinto.
double fitness;
std::vector chromosomas;
Genoma (int nCromo) {
fitness = 0;
for (int i=0; i
Para mover a Bob por el laberinto necesitaremos encontrar las direcciones que deberá seguir y los cromosomas son quienes las representan, para ello los cogeremos de dos en dos, ya que necesitamos cuatro valores, y según su valor binario resultante de su combinación corresponderá a una dirección concreta:
* 00 -> 0 -> abajo
* 01 -> 1 -> arriba
* 10 -> 2 -> izquierda
* 11 -> 3 -> derecha
El valor de fitness corresponde a lo cerca que está esta solución de la solución final. \\
Un objeto genoma al crearse se le indica el número de cromosomas que ha de tener, es necesario que sea un número suficiente de pasos para alcanzar la salida del laberinto (en este caso hemos de pensar que el número de cromosomas ha de ser, al menos, el doble al de pasos necesarios para salir del laberinto ya que para un paso se necesitan dos cromosomas). Los cromosomas se generan aleatoriamente y luego, tras convertirlos en coordenadas dentro del laberinto, tenemos una solución con un valor de fitness concreto. El mejor genoma será aquel que tenga el valor de fitness más alto. \\
=== El algoritmo ===
- Lo primero que se ha de hacer es crear la primera generación de genomas, tantos genomas como se desee que tenga una generación, pero a mayor número menos generaciones serán necesarias para resolver el problema.
- Calculamos de cada genoma su fitness.
- Buscamos el genoma de mayor fitness y nos quedamos con él.
- Si el fitness de este genoma es el mayor valor posible, en nuestro caso 1, ya hemos encontrado la solución.
- Empezamos a crear la siguiente generación de genomas, para ello se escogen dos genomas padres (de la generación actual) utilizando la selección por ruleta de la fortuna.
- Estos dos padres se han de cruzar creando así dos nuevos genomas hijos que luego deberán de ser mutados.
- Se volverán a escoger dos padres que generarán dos hijos que luego mutarán, así hasta llegar al número de genomas que ha de tener una generación.
- La nueva generación reemplazará a la anterior.
- Una vez tenemos la siguiente generación nos vamos al paso 2.
Aquí el {{ai:bobsmaze.zip|código fuente de la solución}} (más o menos) conseguida, requiere Qt y está compilado en Suse Linux 10.3
=== Cómo calcular el valor de fitness? ===
Para este ejemplo, y sin matarnos mucho, lo que haremos será ver cuan lejos está la última coordenada del genoma (una vez calculado todo el recorrido, convirtiendo los cromosomas a pasos y esos pasos en un camino) de la salida del laberinto.
int DiffX = abs(pos.rx() - this->maze->getGoal()->rx());
int DiffY = abs(pos.ry() - this->maze->getGoal()->ry());
g->fitness = 1/(double)(DiffX+DiffY+1);
=== Cómo se reliza la selección utilizando la ruleta? ===
La idea consiste en definir un tope, para ello se coge un número aleatorio entre 0 y la suma de todos los fitness de la población actual actual. Se van pasando todos los genomas hasta llegar a uno que supere el tope. A mayor fitness mayor probabilidad de ser escogido.
int Bob::rouleteSelection () {
double tope = this->getTotalFitness() * randFloat();
double tmp = 0;
int idx = 0;
while (tmp <= tope) {
tmp += this->populations[idx].fitness;
idx++;
}
return idx - 1;
}
=== Cómo se realiza el cruce de dos genomas? ===
El cruce de dos genomas es influido por dos elementos, el //crossover rate// que indica si los dos genomas serán o no cruzados y el punto donde se cruzan los cromosomas de estos dos genomas.
void Genoma::crossover (Genoma* secondParent, double crossover_rate, Genoma* firstSon, Genoma* secondSon) {
if (randFloat() > crossover_rate) {
firstSon->chromosomas = this->chromosomas;
secondSon->chromosomas = secondParent->chromosomas;
return;
}
int corte = randInt(0, this->chromosomas.size() - 1);
for (int i=0; ichromosomas.push_back(this->chromosomas[i]);
secondSon->chromosomas.push_back(secondParent->chromosomas[i]);
}
for (int i=corte; ichromosomas.size(); i++) {
firstSon->chromosomas.push_back(secondParent->chromosomas[i]);
secondSon->chromosomas.push_back(firstSon->chromosomas[i]);
}
}
Por cada cruce a realizar se crea un número aleatorio entre 0 y 1, si este está dentro del crossover rate los dos genomas se cruzarán, si no los genomas hijos tendrán los mismos cromosomas que los padres. \\
Una vez se ha decidido que definitivamente se realizará el cruce se elige un punto de corte, entre el 0 y el número de cromosomas, los cromosomas hijos tendrán una combinación de los cromosomas de los padres definida por ese punto.
=== Cómo implementar la mutación? ===
La mutación se basa en cambiar un genoma (de 0 a 1 y viceversa) según la //mutation rate//. Por cada cromosoma se crea un decimal aleatorio entre 0.0 y 1.0, si este supera a la tasa de mutación (que también estaría en este rango) el cromosoma no cambia, pero si está en dicho rango sí.
void Genoma::mutate (double mutation_rate) {
for (int i=0; i< this->chromosomas.size(); i++)
if (randFloat() < mutation_rate)
this->chromosomas[i] = !this->chromosomas[i];
}