Optimización inspirada en la naturaleza
ARTÍCULO ESCRITO POR
Algoritmos genéticos
En un artículo previo del blog titulado “Algoritmos heurísticos, metaheurísticos y exactos” se explicaban las diferencias entre los tres principales grupos en los que se pueden clasificar los algoritmos de optimización.
Los algoritmos genéticos son algoritmos de optimización pertenecientes al grupo de las metaheurísticas.
Se pueden aplicar a un amplio abanico de problemas a los que se enfrentan las empresas diariamente: problemas de optimización de rutas, problemas de clasificación y clustering, planificación de tareas, problemas industriales (por ejemplo, problemas de corte o empaquetado o de optimización del rendimiento de reguladores automáticos)) o problemas financieros (por ejemplo, previsión de riesgo de quiebra u optimización de carteras).
La característica principal de los algoritmos genéticos es que imitan la evolución de las especies según las leyes de la Naturaleza.
La evolución natural
En el proceso de evolución natural cada especie busca mejorar su adaptación a un medio siempre cambiante. Una parte de los organismos evolucionan mediante dos procesos básicos: la selección natural y la reproducción sexual.
La selección natural determina qué individuos de una especie sobreviven para reproducirse, lo que se ha venido a llamar la supervivencia del más fuerte. Donde se considera que un individuo es más o menos fuerte según su grado de adaptación al medio. Es decir, según los rasgos que lo caracterizan será más o menos capaz de sobrevivir a la interacción con el medio ambiente y con otros individuos. El que esté más adaptado sobrevivirá más tiempo y tendrá más descendencia, a la que transmitirá su carga genética.
El segundo mecanismo que da lugar al proceso de evolución es, como ya se ha dicho, la reproducción sexual, que asegura la mezcla y recombinación de los genes que constituyen el material genético heredado por los descendientes. Gracias a esta recombinación, los individuos evolucionan mucho más rápidamente de lo que lo harían si se limitasen a heredar una copia de los genes de uno sólo de sus progenitores modificada ocasionalmente por mutación.
Por lo tanto, en el proceso de evolución hay tres operadores principales: selección, cruce y mutación.
La selección determina qué individuos son elegidos para la reproducción y cuánta descendencia tiene cada individuo. El cruce permite la mejora de la especie debido a la aparición de individuos con características que favorecen su adaptación, y la mutación crea características totalmente nuevas.
Si la selección y el cruce fuesen los únicos mecanismos implicados en la evolución, los rasgos de los individuos estarían limitados a rasgos que ya han aparecido previamente alguna vez en la población. En la Naturaleza, la mutación es el proceso que sirve para reintroducir características que se han podido perder a lo largo de los procesos de selección y cruce o, incluso, que nunca han existido antes.
Cómo aplicar la evolución natural a la optimización
Los algoritmos genéticos utilizan estos principios básicos, que tan buenos resultados han proporcionado en el medio natural, para resolver problemas de optimización.
Al principio del algoritmo un grupo de individuos (puntos del espacio de soluciones posibles) que se llama población, se inicializa aleatoriamente.
Estos individuos o posibles soluciones se codifican como una cadena de dígitos, cada uno de los cuales se llama gen. En los algoritmos genéticos tradicionales las posibles soluciones se representaban como cadenas de dígitos binarios.
El siguiente paso del proceso de optimización es evaluar el grado de adaptación del individuo y asignarle un valor que corresponda a dicho grado de adaptación. Se calcula el valor de la función a optimizar para cada individuo y se considerará que un individuo está mejor adaptado que otro si al evaluar la función en el punto que representa el individuo en cuestión se obtiene un valor mejor.
Después empieza la creación de una nueva generación por medio de los mecanismos de selección, cruce y mutación:
-
- Se seleccionan los individuos mejor adaptados, los que resuelven mejor el problema de optimización, para tener descendencia
- Los genes de los padres se recombinan para generar los de la descendencia por uno o varios puntos. Al crear nuevas soluciones a partir de soluciones que resuelven bien el problema, se explora el espacio de posibles soluciones en las áreas más prometedoras.
- Los genes de la descendencia se mutarán con una cierta probabilidad. La mutación se usa para asegurar que todas las áreas del espacio de posibles soluciones permanecen al alcance del algoritmo. Si no, aquellos rasgos que no aparezcan en la población inicial de soluciones, nunca se podrían explorar.
Una vez creada, la descendencia sustituye a los padres y se produce una nueva generación de soluciones cada vez mejores.
Ventajas de los algoritmos genéticos sobre otras técnicas de optimización
Los algoritmos genéticos, en vez de usar un único punto para explorar el espacio de posibles soluciones empezando por un punto inicial aleatorio y continuando en la dirección que optimiza la solución (hill climbing), tienden una red sobre el espacio.
La multitud de individuos que constituyen una población en evolución muestrean ese espacio en muchas regiones simultáneamente, es decir, son intrínsicamente paralelos.
Además, el número de individuos que buscan en una región es directamente proporcional a la probabilidad de encontrar una buena solución en ella. Esto ocurre así porque sucesivas generaciones de reproducción y cruce producen un mayor número de individuos en esas regiones.
El algoritmo favorece que los individuos mejor adaptados se reproduzcan, así los individuos cuyo nivel de adaptación está sobre la media (y que resultan estar en las regiones con mayor probabilidad de contener buenas soluciones) tendrán más descendencia en la siguiente generación.
Estas características minimizan la posibilidad de caer en óptimos locales y permiten resolver de forma cuasi-óptima problemas cuya combinatoria hace que el espacio de búsqueda sea muy grande. Gracias a esto, los algoritmos genéticos son más robustos que otros métodos tradicionales de optimización.
