Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos, Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular.
Los algoritmos genéticos pertenecen a la computación evolutiva, son considerados también una técnica de inteligencia artificial. A través de millones de años, los organismos han evolucionado biológicamente para sobrevivir y crecer en un mundo cambiante. Los materiales genéticos de todos los organismos vivos consisten de cromosomas que están divididos en genes; su codificación y desarrollo son considerados un proceso clave en la continuación de las especies.
Funcionamiento de un algoritmo genético básico
Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:
Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema.
Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.
Condición de término: El AG se deberá detener cuando se alcance la solución óptima, pero generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:
Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
Cruzamiento: La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
Mutación: Modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
Reemplazo: Una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.
Ventajas y Desventajas
-
No necesitan conocimientos específicos sobre el problema que intentan resolver.
-
Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.
-
Cuando se usan para problemas de optimización maximizar una función objetivo- resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.
-
Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.
-
Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.
-
Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.
-
Pueden converger prematuramente debido a una serie de problemas de diversa índole
Aplicaciones
-
Infraestructura de redes de comunicación móviles.
-
Optimización de estructuras moleculares.
-
Planificación de producción multicriteria.
-
Predicción.
-
Selección óptima de modelos matemáticos para la descripción de sistemas biológicos.
-
Manejo de residuos sólidos.
-
Ingeniería de software.
-
Construcción de horarios en grandes universidades, evitando conflictos de clases.
Referencias
Goldberg, V. A. P. H. D. E., Edward, G., Goldberg, D. E. G., Goldberg, D. H. O. E., & David Edward, G. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Van Haren Publishing.
EcuRed. (s. f.-a). Algoritmos Genéticos - EcuRed. https://www.ecured.cu/Algoritmos_Gen%C3%A9ticos
Algoritmos genéticos: Funcionamiento, Pasos y Aplicaciones. (s. f.). Tecnologías Información. https://www.tecnologias-informacion.com/algoritmosgeneticos.html#:%7E:text=Rob%C3%B3tica,humanas%20y%20no%20tan%20automatizables.