Algoritmos Genéticos

Los algoritmos genéticos han causado en la comunidad científica internacional un creciente interés en esta nueva técnica de búsqueda basada en la teoría de la evolución. Esta técnica esta basada en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos mas aptos de una población son los que sobreviven, al adaptarse mas fácilmente a los cambios que se producen en su entorno.

¿Qué es un algoritmo genético?

Un algoritmo genético (AG) es una técnica de programación que imita a la evolución biológica como estrategia para resolver problemas. Dado un problema específico a resolver, la entrada del AG es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de aptitud que permite evaluar cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente.

Son una parte de la computación evolutiva que a su vez es una creciente rama de la Inteligencia Artificial.

Los algoritmos genéticos son uno de los miembros más representativos de las técnicas heurísticas modernas.

Historia

La evolución biológica es el proceso continuo de transformación de las especies a través de cambios producidos en sucesivas generaciones. El naturalista Charles Darwin definió en su libro “Sobre el Origen de las Especies por medio de la Selección Natural” la Selección Natural o Supervivencia del más Adaptado como el proceso del resguardo de las variaciones y diferencias benévolas en cada individuo, así como la destrucción de aquellas variaciones dañinas. Dentro de la naturaleza, los individuos deberán de adaptarse a su entorno para poder sobrevivir mediante el proceso que llamamos evolución, en el cual aquellas características o cambios que favorecen su competitividad son preservados, y aquellas características que disminuyen su adaptación son excluidos.

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población

Como los Algoritmos Genéticos se encuentran basados en los procesos de evolución de los seres vivos, casi todos sus conceptos se basan en conceptos de biología y genética que son fáciles de comprender.

Aplicaciones

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han demostrado ser muy eficientes y confiables. Algunas características de estas aplicaciones:

v Su espacio de búsqueda o sus posibles soluciones debe estar delimitado dentro de un cierto rango.

v Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.

v Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.

Un AG utiliza reglas de transición probabilísticas, no deterministas, lo cual hace que dos aplicaciones consecutivas de un AG a un mismo problema puedan producir dos soluciones distintas.

Ventajas y desventajas

v No necesitan conocimientos específicos sobre el problema que intentan resolver.

v Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.

v Cuando se usan para problemas de optimización resultan menos afectados por los máximos locales que las técnicas tradicionales.

v Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo.

v Usan operadores probabilísticos, en vez de los típicos operadores deterministicos de las otras técnicas.

v 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, numero de generaciones, etc.)

v Pueden converger prematuramente debido a una serie de problemas de diversa índole.