Empecemos por el principio… ¿qué son los algoritmos genéticos y por qué utilizarlos en nuestro negocio?
Los Algoritmos Genéticos (Genetic Algorithm, GA en inglés) son una técnica de optimización basada en búsquedas heurísticas. Los GAs pertenecen a una rama mucho más amplia de algoritmos llamados Evolutionary Algorithm (Algoritmos Evolutivos). Estos algoritmos están basados en el concepto de la evolución natural de las especies presente en la naturaleza.
El proceso de optimización es el siguiente: para un determinado problema, partimos de la base de un conjunto de población de posibles soluciones . Estas soluciones se someten a un proceso de recombinación (Crossover) y mutación (Mutation), produciendo nuevos “hijos” (exactamente como pasa en la Naturaleza con la genética).
Este proceso se repite durante varias generaciones. A cada nueva solución obtenida, se le asigna una puntuación. Cuanto más cerca esté esa posible solución de la función objetivo (es decir, cuando más cerca esté esa solución de resolver el problema planteado) mayor será la puntuación. Los individuos con mayor puntuación, tienen mayor probabilidad de sobrevivir a la siguiente permutación, exactamente como pasa en la Teoría de Evolución Natural de Charles Darwin.
Lo que se consigue con este proceso es que las posibles soluciones vayan “evolucionando” a lo largo de las generaciones, hasta que se alcanza la solución más óptima (es decir, más ajustada a la función objetivo)
Funcionamiento de los Algoritmos Genéticos
Un Algoritmo Genético consta de 6 pasos:
1. Definición de la Población inicial
Se genera una población inicial (normalmente de forma aleatoria), donde cada individuo es una posible solución al problema a resolver. Un individuo está formado por parámetros con un valor. En los GAs, a los individuos se les llama cromosoma, y a los parámetros, genes. Normalmente, los genes son binarios (1s y 0s), por lo que un cromosoma (o individuo) es una cadena de 1s y 0s.
2. Evaluación
A cada una de los cromosomas de la población se le aplica una función de aptitud que determina cómo de buena es esa solución. Esta calificación determina la probabilidad que ese individuo sea escogido para “reproducirse”.
3. Selección
En esta fase seleccionamos a los individuos más aptos para que sus genes pasen a la siguiente generación (individuos con mayor puntuación de acuerdo con la función de aptitud). Se escogen pues pares de cromosomas para ser cruzados en el siguiente paso (Recombinación).
4. Recombinación
Es el equivalente de la reproducción sexual en la naturaleza, y es la parte más significativa de los algoritmos genéticos. Por cada par de cromosomas elegidos en la fase de Selección, se define un punto de cruce y a partir de este se crea un par de descendientes con la información recombinada (“Crossover” en inglés).
5.Mutación
Consiste en modificar al azar algunos cromosomas (cambiando el valor de alguno de sus genes). La mutación es esencial para evitar convergencias prematuras y para añadir nuevas soluciones de forma random que ayuden en el proceso de optimización.
6. Finalización
Hay distintos criterios para la finalización del algoritmo. Debido a que la solución óptima se desconoce (es lo que estamos buscando precisamente), no podemos utilizarla como criterio de finalización. En vez de eso, se suelen utilizar dos criterios:
- Cuando el algoritmo converja en una solución (no se producen nuevas descendencias mejores que las anteriores durante un periodo de tiempo)
- Correr el Algoritmo genético un número máximo de iteraciones
Finalmente, comentar que cada nuevo individuo (cromosoma) sustituye a uno con menor aptitud (llamado “reemplazo”), de forma que el tamaño de la población (número de cromosomas) se mantiene fijo a lo largo de todo el proceso.
Ventajas de los Algoritmos Genéticos
- Es mucho más rápido y más eficiente que muchos métodos tradicionales
- El proceso se puede paralelizar, por lo cual se pueden usar múltiples procesadores a la vez para hacer converger la solución más rápidamente
- Sirve tanto para funciones continuas como discretas.
- Son también de aplicabilidad para los problemas multiobjetivo (multi-objective optimization, MOO, de los cuales hablaremos en otra entrada)
Desventajas de los Algoritmos Genéticos
- La función de evaluación se debe computar en cada iteración. Si ésta es costosa, el tiempo de cálculo puede incrementarse de forma substancial.
- Son poco escalables: un pequeño aumento en el número de parámetros puede hacer crecer su complejidad de forma exponencial, hasta hacerlo de hecho inviable por tiempo y recursos necesarios.
- Pueden converger en óptimos locales. Esto significa que puede hallar una solución que, siendo mejor que las calculadas hasta el momento, no es la mejor solución.
- Los hyperparámetros del modelo (probabilidad de mutación, punto de recombinación, población inicial, número de iteraciones antes de detenerse…) requieren un análisis profundo del problema, por lo que no se adaptan bien a ”un solo algoritmo para todos los problemas”.
Aplicaciones reales de los Algoritmos Genéticos
Algunos ejemplos de soluciones basadas en algoritmos genéticos:
- Optimización de Scheduling: Asignación óptima de recursos (empleados) en tiendas físicas para optimizar las ventas, aplicando restricciones de número mínimo de empleados en cada hora, horas trabajadas anualmente, vacaciones, tráfico esperado en tienda, etc.
- Optimización de proveedores: Determinar el proveedor óptimo para cada uno de los productos del catálogo que minimicen el coste de adquisición, teniendo en cuenta las restricciones de máximo número de proveedores distintos, mínimo ahorro respecto al año anterior, número máximo de proveedores nuevos para el año actual, etc.
- Optimización del famoso problema de rutas en logística (Travelling salesman problem – TSP) planteado ya en 1930 y estudiado ampliamente en el campo de las ciencias de la computación: Dado un número de ciudades, ¿cuál es la ruta más corta que las une a todas exactamente una vez y que vuelve al punto de origen?
Como puedes imaginar sus aplicaciones son casi infinitas, y sus ventajas muy tangibles, si quieres saber cómo pueden ayudar a tu empresa a mejorar procesos y conseguir resultados, no dudes en contactar con nosotros, como Consultora Analítica con más de 20 años de experiencia en el equipo podremos ayudarte a ello 😉
