Topics about Data Sciences and BI
Foto de Usuario
WalterAcuña

Ranking Troomes
Mensajes: 16
Registrado: 24 Ago 2019, 15:07

Algoritmos genéticos en el machine learning

Mensaje por WalterAcuña » 18 Sep 2020, 19:10

Definición
Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Problemática
Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos . descendientes de los anteriores . los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones.

Funcionamiento General de los AG
De manera general podemos comentar que los AG describen las soluciones posibles del problema como individuos dentro de una población. Cada individuo se representa como una secuencia de caracteres donde cada caracter se llama gen y el conjunto de caracteres se llama cromosoma. Los individuos son evaluados midiendo que tan bien solucionan el problema.
Una vez evaluados, se seleccionan los mejores individuos y pasan a una etapa de recombinación genética en la cual se emplean estrategias de cruce y mutación para producir variedades de individuos diferentes a las de sus antecesores, las cuales se utilizan para poblar la siguiente generación del algoritmo.
Este ciclo se repite iterativamente y en cada generación se obtienen mejores individuos que heredan y modifican ligeramente las características de sus ancestros llegando a soluciones con un buen desempeño en la tarea que deseamos realizar.
Imagen

Representación Genética
Como ya he dicho, los algoritmos genéticos sirven para optimizar. Dado un problema a resolver, un algoritmo genético dará (si está bien programado) soluciones cada vez mejores a este problema.
Por eso es importante definir bien el problema, y crear una representación genética adecuada. ¿Y qué es esto?
En el apartado anterior hacía la comparación de un Algoritmo Genético con una población de gacelas. Cada gacela tiene un material genético determinado, llamado genotipo. Si analizamos dos gacelas, veremos que tienen un genotipo muy parecido, pero diferente.
Si el genotipo es el material genético de un individuo, el fenotipo son las características del individuo producidas por los genes. El genotipo de una mariposa es su material genético, y su fenotipo la coloración, tamaño de las alas… que son consecuencia de las combinaciones de genes.
A la hora de programar un Algoritmo Genético debes pensar cuáles serán los elementos que conformarán el genotipo de los individuos y de qué forma se corresponden a un fenotipo. Por ejemplo, si estás evolucionando un circuito analógico, la representación genética puede ser un alfabeto de caracteres que se corresponda a componentes como Resistencias, Condensadores, Transistores… el genotipo de cualquier solución estará formado por una combinación de estas letras.
1- Inicialización:
La población inicial puede generarse al azar, pero debe ser lo suficientemente grande y diversa para que durante la evaluación los individuos muestren un fitness distinto. Si todos los individuos tienen el mismo fitness, el programa no va a poder seleccionar bien los mejores para su reproducción.

2- Función de Fitness (Evaluación)
La Función de Fitness evalúa cada uno de los individuos de la población y les asigna un valor numérico según su calidad. Este valor numérico se llama fitness.

3- Selección y Reproducción
Hay varias formas de seleccionar los individuos con el fitness más elevado para crear una nueva población. Algunas de las más utilizadas son:
Selección proporcional: cuanto más alto sea el fitness de un individuo, mayor será la probabilidad de que pase a la siguiente generación.
Selección por torneo: se eligen varios individuos al azar de la población y se compara su fitness. El individuo con el fitness más alto pasará a la siguiente generación. ¿Para qué sirve esto? Hay ocasiones en que es interesante escoger soluciones que no son tan buenas para poder mantener una buena variabilidad genética entre los individuos. Así al mezclar el material genético se exploran soluciones muy distintas.
Selección por rango: los individuos se ordenan en función de su fitness, y la probabilidad que tienen de reproducirse va según su posición.
La presión expresa el porcentaje de individuos que serán seleccionados. Cuánto más alta sea la presión, menos individuos serán seleccionados para la siguiente generación.
Imagen
4- Crossover o Mutación
Una vez se han seleccionado los mejores individuos, el Crossover consiste en mezclar el material genético de estos para crear los nuevos individuos.
La forma más sencilla de hacerlo es mediante un One-point Crossover. Consiste en elegir un punto al azar de los dos individuos e intercambiar el material genético a partir de esta posición.
Imagen
Ventajas, desventajas y uso
La ventaja principal del uso de los AG es que suelen llegar a soluciones muy creativas y optimizadas debido a su capacidad de explorar el espacio de búsqueda por caminos que normalmente no lo hacemos los humanos y diseñadores.
Los algoritmos evolutivos tienen la desventaja de ser altos en coste computacional y depender de muchos hiperparámetros: tamaño de cromosoma, probabilidad de cruce, probabilidad de mutación, número de generaciones, entre otros. Lo anterior hace difícil trabajar con ellos ya que son muy dependientes del problema.
Actualmente se siguen utilizando en algunos campos de las ciencias de la computación, que buscan optimización en espacios de búsquedas y combinatorios demasiado grandes como por ejemplo optimización de rutas, optimización de costos, espacios, etc.
Un ejemplo en donde se pueden utilizar los AG consiste en encontrar una buena arquitectura de red neuronal representando la topología de la red como una cadena donde se representan el número de neuronas para cada capa de la red y el número de épocas necesarias para entrenarla.
Una función de evaluación posible para ese problema es la precisión de la red neuronal al correr con los datos del conjunto de prueba. Esta estrategia resulta cara computacionalmente, sin embargo, puede arrojar mejores resultados que el proceso de exploración tradicional, llegando a mejorar las topologías propuestas por los expertos humanos.
Si bien los AG han perdido algo de popularidad ante los increíbles avances obtenidos por las técnicas de Deep Learning, resultan una opción sumamente interesante para explorar problemas complejos que vale la pena conocer y estudiar.

Referencias


Responder