Las matemáticas de los algoritmos genéticos
MetaQuotes | 4 febrero, 2016
Los algoritmos genéticos se aplican en tareas de optimización. Por ejemplo en el aprendizaje neuronet, esto es, para seleccionar los valores de peso que permiten obtener el mínimo error. El algoritmo genético se basa en el método de búsqueda aleatoria. El principal problema de la búsqueda aleatoria es que no podemos saber cuánto tiempo se tarda en resolver el problema. Para evitar perder un tiempo importante se aplican métodos desarrollados en biología, en concreto métodos relacionados con el origen de las especies y la evolución. Los animales que mejor se adaptan son los que sobreviven. Como resultado, la adecuación de la población aumenta, lo que permite adaptar el entorno dinámico.
John H. Holland, de la Universidad de Michigan, en Estados Unidos, propuso este algoritmo por primera vez en 1975. Este algoritmo se llama plan reproductivo de Holland y es la base de la inmensa mayoría de algoritmos genéticos. Sin embargo, antes de echar un vistazo detallado a este plan, vamos a discutir cómo puede codificarse la realidad y encapsularse en los algoritmos genéticos.
Presentación
En el campo de la biología todos los organismos se pueden representar con un fenotipo que determina qué cosa es tal o cual objeto del mundo real; y también con un genotipo que contiene información completa sobre el objeto en cuestión y su conjunto de cromosomas. Todos los genes, o dicho de otra manera, los elementos de información del genotipo, se reflejan en el fenotipo. En consecuencia, para solucionar nuestro problema debemos presentar los caracteres del objeto de esa forma; esto se puede utilizar en el algoritmo genético. Los mecanismos del algoritmo genético funcionan a nivel del genotipo sin necesidad de conocer el patrón interno del objeto, lo que permite utilizarlo en muchas tareas variadas, muy diferentes entre sí.
Las cadenas de bits representan el genotipo del objeto en la variación más amplia del algoritmo genético. Un gen del genotipo del objeto se corresponde con un atributo del objeto en su fenotipo. Un gen es una cadena de bits de longitud fija que representa el valor de dicha característica.
Codificación de los atributos enteros
La manera más sencilla de codificar los atributos es mediante los valores de sus bits. Entonces es bastante sencillo tomar un gen de una determinada longitud suficiente para representar todos los valores posibles de un atributo. Pero desafortunadamente esta codificación tiene sus inconvenientes. El inconveniente fundamental es que los números vecinos difieren entre sí en varios bits. De este modo, el 7 y el 8 representados en binario difieren en 4 posiciones, lo que dificulta el funcionamiento del algoritmo genético, e incrementa el tiempo necesario para que converjan. Para evitar esto es mejor utilizar la codificación allá donde los números vecinos difieren entre sí en menos posiciones, idealmente en un bit. Tal codificación se representa con el código Gray, que se recomienda utilizar en la implementación del algoritmo genético. Los valores del código Gray se presentan en la siguiente tabla:
| Codificación binaria | Código Gray | ||||
|---|---|---|---|---|---|
| Código decimal | Código binario |
Código hexadecimal | Código decimal | Código binario | Código hexadecimal |
| 0 | 0000 | 0h | 0 | 0000 | 0h |
| 1 | 0001 | 1h | 1 | 0001 | 1h |
| 2 | 0010 | 2h | 3 | 0011 | 3h |
| 3 | 0011 | 3h | 2 | 0010 | 2h |
| 4 | 0100 | 4h | 6 | 0110 | 6h |
| 5 | 0101 | 5h | 7 | 0111 | 7h |
| 6 | 0110 | 6h | 5 | 0101 | 5h |
| 7 | 0111 | 7h | 4 | 0100 | 4h |
| 8 | 1000 | 8h | 12 | 1100 | Ch |
| 9 | 1001 | 9h | 13 | 1101 | Dh |
| 10 | 1010 | Ah | 15 | 1111 | Fh |
| 11 | 1011 | Bh | 14 | 1110 | Eh |
| 12 | 1100 | Ch | 10 | 1010 | Ah |
| 13 | 1101 | Dh | 11 | 1011 | Bh |
| 14 | 1110 | Eh | 9 | 1001 | 9h |
| 15 | 1111 | Fh | 8 | 1000 | 8h |
En consecuencia, cuando codificamos un atributo entero, lo dividimos en cuatro partes y transformamos cada una de ellas según las reglas de la codificación Gray.
En las implementaciones prácticas de los algoritmos genéticos no suele hacer falta transformar los valores de los atributos en valores de gen. En la práctica, el problema inverso ocurre cuando hay que encontrar el valor del atributo por el valor del gen correspondiente.
Así, la tarea de descifrar los valores de los genes, cuyos atributos son enteros, es trivial.
Codificación de atributos de coma flotante
Parece que lo más fácil para codificar es utilizar el bit de representación. Aunque así seguimos teniendo los mismos inconvenientes que con los enteros. Por esta razón aplicaremos la siguiente secuencia de operaciones en la práctica:
- El intervalo completo de valores permitidos del atributo se divide en partes, con la precisión deseada.
- El valor del gen es un número entero que numera el intervalo (utilizando el código Gray).
- Se toma como valor del parámetro el número que está en la mitad de este intervalo.
Echemos otro vistazo a la secuencia de operaciones anterior con este ejemplo:
Supongamos que los valores del atributo están en el rango [0,1]. El rango se ha partido en 256 intervalos para la codificación. Para codificar el número necesitamos 8 bits. El valor del gen es, por ejemplo, 00100101bG (la letra mayúscula G significa que es el código Gray). En primer lugar, pues, utilizando el código Gray, encontramos el número del intervalo correspondiente: 25hG->36h->54d. Y comprobamos qué intervalo se corresponde con el mismo. Con unos sencillos cálculos obtenemos el intervalo [0,20703125, 0,2109375]. Es decir, el valor del parámetro será (0,20703125+0,2109375)/2=0,208984375.
Codificación de datos no numéricos
Los datos no numéricos se tienen que transformar en números antes de codificarse. Esto se describe detalladamente en los artículos de nuestro website que describen el funcionamiento de las redes neuronales.
Cómo determinar el fenotipo de un objeto por su genotipo
Para determinar el fenotipo de un objeto, esto es, los valores de los atributos del objeto, tan solo tenemos que saber los valores de los genes que se corresponden con dichos atributos, es decir, el genotipo del objeto. La integridad de los genes que describen el genotipo del objeto representa un cromosoma. En algunas implementaciones también se llama espécimen. De este modo, en la implementación del algoritmo genético, el cromosoma representa una cadena de bits de longitud fija. Cada intervalo de la cadena se corresponde con un gen. La longitud de los genes de un cromosoma puede ser igual o diferente. Los genes de la misma longitud se utilizan más frecuentemente. Consideremos un ejemplo de cromosoma e interpretemos su valor. El objeto tiene 5 atributos, cada uno de los cuales se codifica en un gen de 4 elementos. Por lo tanto la longitud del cromosoma es de 5*4=20 bits:
| 0010 | 1010 | 1001 | 0100 | 1101 |
Ahora podemos determinar los valores de los atributos
| Atributo | Valor del gen | Valor binario del atributo | Valor decimal del atributo | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Atributo 1 | 0010 | 0011 | 3 | ||||||||
| Atributo 2 | 1010 | 1100 | 12 | ||||||||
| Atributo 3 | 1001 | 1110 | 14 | ||||||||
| Atributo 4 | 0100 | 0111 | 7 | ||||||||
| Atributo 5 | 1101 | 1001 | 9 |
Operadores genéticos básicos
Como es sabido en la teoría de la evolución, es muy importante la forma en que los individuos transmiten sus características a sus descendientes. En los algoritmos genéticos, el cruce (crossover, en inglés) es un operador genético que permite variar la programación de un cromosoma o cromosomas de una generación a la siguiente. Este operador funciona de la siguiente manera:
- se seleccionan dos unidades padre/madre de una población;
- se determina el punto de ruptura (como norma, de forma aleatoria);
- la descendencia queda determinada por la concatenación de las partes del padre y de la madre.
Veamos cómo funciona este operador:
| Cromosoma_1: | 0000000000 | ||||
| Cromosoma_2: | 1111111111 |
Suponemos que el punto de ruptura ocurre después del 3er bit del cromosoma, por lo que:
| Cromosoma_1: | 0000000000 | >> | 000 | 1111111 | Cromosoma_resultante_1 | ||||||||||||
| Cromosoma_2: | 1111111111 | >> | 111 | 0000000 | Cromosoma_resultante_2 |
Entonces uno de los cromosomas resultantes queda determinado como descendiente con una probabilidad de 0.5.
El otro operador genético sirve para mantener la diversidad de la población. Se trata del así llamado operador mutación. Este operador altera el valor inicial de uno o más genes de un cromosoma. Por consiguiente, cada bit del cromosoma se invierte con una probabilidad determinada.
También se utiliza un operador más, llamado inversión. Este operador divide el cromosoma en dos partes, y cambia las posiciones. Esto se puede representar esquemáticamente así:
| 000 | 1111111 | >> | 1111111 | 000 |
En teoría estos dos operadores genéticos son suficientes para hacer funcionar el algoritmo genético. Sin embargo, en la práctica se utilizan operadores adicionales y se modifican los mismos. Por ejemplo, es posible que además del cruce de un solo punto (el descrito anteriormente) existan más puntos. En este último caso se crean varios puntos de ruptura, generalmente dos. Además, el operador de mutación realiza la inversión de un solo bit seleccionado al azar de un cromosoma en algunas implementaciones del algoritmo.
Diagrama de flujo del algoritmo genético
Ahora que ya sabemos interpretar los valores del gen, podemos explicar cómo funcionan las funciones del algoritmo genético. Echemos un vistazo detallado a la representación clásica del diagrama de flujo del algoritmo genético.
- Inicializar la hora de inicio, t=0. Crear aleatoriamente la población inicial, que consiste de k unidades. B0 = {A1,A2,…,Ak)
- Calcular la adecuación de cada unidad, FAi = fit(Ai) , i=1…k, y la adecuación de la población entera, Ft = fit(Bt). El valor de esta función determina en qué medida la unidad descrita por este cromosoma se adapta para resolver el problema.
- Seleccionar la unidad Ac de la población. Ac = Get(Bt)
- Seleccionar la segunda unidad de la población con una probabilidad determinada (la probabilidad de cruce Pc), Аc1 = Get(Bt), e implementar el operador de cruce, Ac = Crossing(Ac,Ac1).
- Implementar el operador de mutación con una probabilidad determinada (la probabilidad de mutación Pm), Ac = mutation(Ac).
- Implementar el operador de inversión con una probabilidad determinada (la probabilidad de inversión Pi), Ac = inversion(Ac).
- Poner el nuevo cromosoma obtenido en la nueva población, insert(Bt+1,Ac).
- Los pasos 3 y 7 se tienen que repetir k veces.
- Incrementar el número de época actual, t=t+1.
- Si se satisface la condición de parada, terminamos el bucle. En caso contrario volvemos al paso 2.
Algunas etapas del algoritmo requieren un análisis más exhaustivo.
Los pasos 3 y 4, la fase de selección de los cromosomas padre, desempeñan el papel más importante para el correcto funcionamiento del algoritmo. Existen varias alternativas, sin embargo. El método de selección utilizado con más frecuencia se llama ruleta. Al utilizar este método, la probabilidad de seleccionar tal o cual cromosoma se determina por su adecuación, esto es, PGet(Ai) ~ Fit(Ai)/Fit(Bt). Este método aumenta la probabilidad de que los atributos pertenecientes a las unidades más adaptadas se transmitan a los descendientes. Otro método utilizado a menudo es la selección por torneo. Consiste en que se seleccionan aleatoriamente varias unidades (2, como norma general) entre la población. La unidad más apta se selecciona como ganadora. Por otro lado, algunas implementaciones del algoritmo aplican la así llamadaestrategia elitista, que significa que las unidades más adaptadas tienen garantizado incorporarse a la nueva población. Generalmente, esta aproximación permite acelerar la convergencia del algoritmo genético. El inconveniente de esta estrategia es la probabilidad incrementada del algoritmo que entra en el mínimo local.
Otro punto importante es determinar el criterio de parada del algoritmo. Se utilizan como criterios tanto las épocas de funcionamiento del algoritmo como la determinación de la convergencia (normalmente se compara la adecuación de la población en varias épocas y la parada, cuando este parámetro está estabilizado).