Fundamentos del aprendizaje automático: algoritmos genéticos y su aplicación

Algoritmos Genéticos

Conceptos previos

Algunas ideas de Charles Darwing (1809-1882):

• Formuló la teoría de la selección natural de las especies: "On the Origin of Species by Means of Natural Selection, or The Preservation of Favoured Races in the Struggle for Life", 1859. La idea principal: existe una población de individuos compitiendo en un entorno por una serie de recursos para sobrevivir.
• También existen mecanismos de adaptación al entorno: reproducción, mutaciones, etc.

Los individuos que no se adaptan convenientemente al entorno desaparecen, y lo que sí permanecen en la población.

Libros interesantes:

David E. Goldberg "Genetic algorithms in search, optimization and machine learning" (capítulos 1 y 2).

"Introduction to genetic algorithms" Melanie Mitchell.

Iglesias Otero, María Teresa. "Algoritmos genéticos generalizados: variaciones sobre un tema

Axelrod, Robert. The Complexity Of Cooperation. Princeton, NJ: Princeton University Press: 1997

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Conceptos previos de algoritmos genéticos

De los primeros trabajos de algoritmos genéticos son:

• Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
• Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. By John H. Holland. The MIT Press.

Los algoritmos genéticos utilizan estas ideas expuestas anteriormente para resolver problemas de optimización en el ordenador:

Problema => Entorno

• Función de fitness => Mide la adaptación al entorno de los individuos
• Cada individuo codifica una solución => material genético
• Existe un conjunto de soluciones => Población (conjunto de individuos).
• Existen mecanismos aleatorios relacionados con la adaptación de los individuos al entorno (Problema).
• Los individuos más adaptados al entorno (i.e. mejor función de fitness) tendrán más probabilidad de reproducirse.
• Los individuos se pueden recombinar y sus vastagos heredan parte del material genético.
• También pueden existir mutaciones del material genético en los individuos.

Así sobreviven los individuos con mejor fitness, y aquellos que su funcion fitness es peor son desechados.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Esquema general de un Algoritmo Genético (AG)

• El objetivo del AG es mejorar la Función Fitness (F).
• AG(Función Fitness (F), parámetros de evaluación)

1. Inicialización de la población P (primera generación)
2. Mientras no se cumpla el criterio de terminación (hay varias posibilidades), entonces realizar:
   1. S = Selección de progenitores (P) //seleccionar progenitores para crear la descendencia
   2. S = Recombinación (S) //recombinar para generar la descendencia
   3. S = Mutación (S) //mutar para generar la descendencia
   4. P= Selección de supervivientes (P, S) // seleccionar la nueva generación P, de acuerdo a F
3. End // vamos a la siguiente generación
4. Return best (P)

Los criterios de terminación pueden ser varios pero generalmente hay dos:

Un máximo número de generaciones O un máximo número de generaciones sin mejorar nada la Función Fiteness.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): consideraciones prácticas

• Hay que codificar los datos en genes. Es decir tenemos que codificar la solución en cromosomas. Un cromosoma es una cadena de genes. Se pueden considerar que los valores que toman los genes de denominan alelos.
• Por ejemplo si la solución es número entero de 0 a 31, entonces podemos codificarla como un cadena de 5 bits (genes), donde cada gen puede valer 0 o 1 (alelos): b5 b4 b3 b2 b1 Ejemplo codificar 5: 00101. Esto es un ejemplo de codificación binaria.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): consideraciones prácticas sobre la población

• Tamaño inicial de la población [P ], es mayor cuanto mayor complicación tiene el problema a resolver.
• Función de ajuste o Fitness Function (FF), te da una idea de lo bueno o malo que es una solución o generación. Cuando mayor sea el valor de FF de los individuos, la solución es mejor (ya que el individuo esta mejor adaptado a la solución del problema). Hay que determinar cuales son algunos de los operadores de evolución que vamos a utilizar para hacer evolucionar la población. Selección de progenitores: se seleccionan aleatoriamente tantos progenitores como individuos queramos evolucionar.
• Supongamos un problema de maximización. Normalmente la selección se hace proporcional a la FF. Imaginar que tenemos cuatro elementos con un fitness de 80, 40, 20 y 10, así en términos de probabilidad tenemos: 0.53 (1), 0.27 (12), 0.13 (13), y 0.067 (14) . Ahora tiramos un número aleatorio entre 0 y 1 y sale 0.83, entonces seleccionamos el individuo i3. Recombinación o cruce: generalmente se sacan dos vastagos del cruce de dos progenitores con una cierta probabilidad de recombinación pc.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): consideraciones prácticas de recombinación

Recombinación o cruce: generalmente se obtienen 2 descendientes del cruce de dos progenitores. Como hemos dicho, el cruce se realiza con una probabilidad Pc y con una probabilidad (1 - Pc) los progenitores pasan a la siguiente iteración sin modificarse (Importante: los vastagos deben seguir siendo soluciones al problema)

Algunas posibles formas de cruce:

Por ejemplo se pueden cruzar en un punto aleatorio:

a5 a4 a3 a2 a1 b5 b4 b3 a2 a1 b5 b4 b3 b2 b1 a5 a4 a3 b2 b1

O puede haber varios puntos de cruce que son aleatorios.

• También puede haber un cruce uniforme, i.e. un cruce por gen: se seleccionan uno por uno los genes y se ve si el gen se intercambia o no con una cierta probabilidad. Mutación: se realiza una pequeña modificación para explorar nuevas soluciones (por ejemplo un flip aleatorio de un bit).

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): consideraciones prácticas de selección de parejas

Como se hace la selección de las parejas para realizar el operador crossover, existen muchas variantes pero las habituales pueden ser:

Se hace una permutación aleatoria de la generación de individuos (N) y se seleccionan de dos en dos para obtener las parejas de dos progenitores (N/2).

En estas parejas se aplica el operador crossover.

• Se puede aplicar el operador crossover solo a una parte de las parejas de la generación:
• La selección puede realizarse de manera aleatoria, aunque normalmente suele ser una gran parte de las parejas.
• La selección se puede realizar con un criterio más depurado: Se realiza una selección proporcional al fitness de la pareja ( | fitness progenitor 1 - fitness progenitor 2 | ). Así si se quiere hacer un crossover sobre sobre el 85% de las parejas, se ordenan por el fitness de la pareja y se selecciona el 85% con mejor fitness.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): consideraciones prácticas de selección de supervivientes

Como se hace la selección de supervivientes después de la ejecución de los operadores genéticos.

• Recordar que P es la población original y S es la población de descendientes mediante los operadores genéticos comentados: operadores de recombinación y de mutación.
• De acuerdo con esto existen varias posibilidades:
• Renovación completa: normalmente se copia la generación obtenida en la siguiente (P = S).
• Renovación parcial: Los elementos de P y S compiten para formar la nueva P.
• Elitismo: también se suelen mantener las n mejores soluciones en la nueva población (pocas soluciones, tal vez las 2 mejores, sino hay convergencia prematura).

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): Ejemplo de codificación binaria

• Tamaño inicial de la población |P|, es mayor cuanto mayor complicación tiene el problema a resolver.
• Lo parámetros del AG, suelen depender del problema a resolver.
• La longitud L del cromosoma depende del problema en cuestión para codificar esos datos como cromosomas.
• En general no hay que poner ni muchos ni pocos individuos en la población (un valor entre 20 y 100, pero depende del problema).
• La probabilidad de mutación se suele escoger como 1 para cada L*N' individuo, y no más de una mutación por individuo.
• La probabilidad de recombinación entre 0.75 y 0.95.
• Estos valores son orientativos y dependen del problema en sí.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): Ejemplo de codificación binaria para maximizar f(x) = x^2

• Ejemplo: maximizar f (x) = x2
• Queremos encontrar el valor que la maximiza, pero restringiendo la variable a números enteros entre 0 y 31.
• Vamos a suponer una resolución para codificar de 5 bits, así la solución es sencilla, ya que el valor máximo de x = 31, siendo f(x) = 312 = 961.
• Es un ejemplo muy sencillo pero muy ilustrativo para AGs.
• Así vamos a codificar cada elemento por un número binario de 5 posiciones: b5 b4 b3 b2 b1
• Supongamos un ejemplo con 4 individuos elegidos al azar.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): Ejemplo de codificación binaria y selección

Cadena Población Inicial x Fitness f(x) = x2 Probabilidad fi f Número de selecciones esperadas 4 * * Numero de selecciones aleatorias 1 01101 13 169 0.14 0.58 1 2 11000 24 576 0.49 1.97 2 3 01000 8 64 0.06 0.22 0 4 10011 19 361 0.31 1.23 1

Supongamos que la cadena 1 se selecciona una vez, la 2 dos veces, la 3 no se selecciona y la 4 una vez.

• Esto de acuerdo al fitness de cada cadena, como habíamos comentado anteriormente.
• Démonos cuenta que la suma del fitness de todas las cadenas es 1170 con una media por cadena de 293.

FUNDAMENTOS DE APRENDIZAJE AUTOMÁTICO

Algoritmo Genético (AG): Selección por ruleta

La selección se puede ver como una ruleta de los casinos:

• se asigna una proporción de la rueda a cada una de las posibles selecciones de los individuos en función de su valor de probabilidad: fi ƒ

Luego se realiza una selección aleatoria de manera similar a cómo se hace girar la ruleta (roulette wheel selection).

Así para el ejemplo anterior de las 4 cadenas tenemos una selección aleatoria de esta forma.

0.14 % Individuo 1 0.49 % Individuo 2 0.31 % Individuo 4 0.06 % Individuo 3