Algoritmos Genéticos

Los algoritmos genéticos son un método para resolver problemas de optimización con restricciones y sin restricciones que se basa en la selección natural, tratan de incorporar las ideas de la evolución natural. Los algoritmos genéticos modifican repetidamente una población de soluciones individuales; en cada paso, los algoritmos genéticos seleccionan individuos al azar de la población actual para ser padres y los utiliza para producir los hijos para la próxima generación. En generaciones sucesivas, la población «evoluciona» hacia una solución óptima. Se utilizan para resolver una variedad de problemas de optimización que no son muy adecuadas para los algoritmos de optimización estándar, incluyendo problemas en los que la función objetivo es discontinua, no diferenciables, estocástica, o altamente no lineal. (The MathWorks Inc., 2016)

El proceso básico para un algoritmo genético sigue los siguientes pasos:

Población Inicial: Crear una población inicial. Esta población suele ser generada de forma aleatoria y puede ser de cualquier tamaño.

1. Evaluación: Cada miembro de la población es luego evaluado y se calcula un nivel de ajuste para ese individuo. El nivel de ajuste se calcula basado respecto a la satisfacción de los requisitos deseados.
2. Selección: Constantemente se desea incrementar el nivel de ajuste de la población. La selección, por tanto, ayuda a incrementar el nivel de ajuste descartando los malos diseños y manteniendo solo los mejores individuos de la población. Existen algunos métodos de selección, pero la idea fundamental es la misma, hacer que sea más probable que los individuos más aptos sean los seleccionados para la próxima generación.
3. Cruce: Consiste en crear nuevos individuos mediante la combinación de los aspectos de los individuos seleccionados. El objetivo es que mediante la combinación de ciertos rasgos a partir de dos o más individuos se genere una descendencia con mayor nivel de ajuste, que heredarán las mejores características de cada uno de los padres de ella.
4. Mutación: La mutación se considera un operador básico, que proporciona un pequeño elemento de aleatoriedad en los individuos de la población. Si bien se admite que el operador de cruce es el responsable de efectuar la búsqueda a lo largo del espacio de posibles soluciones, el operador de mutación es el responsable del aumento o reducción del espacio de búsqueda dentro del algoritmo genético y del fomento de la variabilidad genética de los individuos de la población.
5. Repetición: Una vez obtenida la nueva generación, se puede empezar de nuevo desde el paso dos hasta llegar a una condición de terminación.

Terminación: cuando el algoritmo ha encontrado la selección más probable o el nivel de ajuste es el deseado, se presume que la solución que es lo suficientemente buena y cumple con un criterio de mínimos predefinidos. (Jacobson, 2012)

Aunque los algoritmos genéticos son fáciles de describir y programar, su comportamiento puede ser complicado, y varias preguntas abiertas existen acerca de cómo funcionan y para qué tipo de problemas que son los más adecuados.

La teoría tradicional de los algoritmos genéticos (formulada por primera vez en Holanda, 1975) asume que, en un nivel muy general de descripción, los algoritmos genéticos trabajan mediante el descubrimiento, enfatizando, y recombinando los buenos «individuos» de soluciones en una manera altamente paralela. La idea aquí es que las buenas soluciones tienden a estar formadas por bloques de combinaciones de valores de un alto nivel de ajuste de las cadenas en las que están presentes. (Mitchel, 1999)

Bibliografía

Agudelo, L., López-Lezama, J. M., & Muñoz, N. (11 de Febrero de 2014). Scielo – Scientific Electronic Library Online. Obtenido de Análisis de Vulnerabilidad de Sistemas de Potencia Mediante Programación Binivel: http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0718-07642014000300013

Jacobson, L. (12 de Febrero de 2012). The Project Spot. Obtenido de Creating a genetic algorithm for beginners: http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3

Mitchel, M. (1999). An Introduction to Genetic Algorithms. Cambridge, Massachusetts: Massachusetts Institute of Technology.

The MathWorks Inc. (2016). The MathWorks – Documentation. Obtenido de What Is the Genetic Algorithm?: http://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html?requestedDomain=www.mathworks.com