¿Qué son los Algorítmos Genéticos?

 
por Violeta León

   En la naturaleza los individuos de una población compiten entre  en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a frecuentemente en la búsqueda de un compañero. Aquellos individuos que tienen mas éxito en sobrevivir y en atraer pareja tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes "superindividuos", cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven. 

   Los Algorítmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor  o puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldrá al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor ser a la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos descendientes de los anteriores los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones. 

   De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así  a lo largo de las generaciones las buenas caracterí sticas se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas mas prometedoras del espacio de búsqueda. Si el Algorítmo Genético ha sido bien diseñado, la población convergerá hacia una solución óptima del problema. 

Definición de Algorítmo Genético


   El poder de los Algorítmos Genéticos provienen del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algorítmo Genético encuentre la solución óptima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo m as probable es que superen al Algorítmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algorítmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algorítmos Genéticos

   En este sentido, el Ingeniero Eugene Ossipov en su artículo "Algorítmos Genéticos: búsqueda y optimización por selección natural" define a los algorítmos genéticos desde el punto de vista de las grandes compañías como Google, Apple y Microsoft, de la siguiente manera:

  • Los Algorítmos Genéticos (AG) son solo una de las herramientas inteligentes que buscan a través de muchas soluciones posibles. 
  • El AG es una búsqueda meta-heurística al igual que una técnica de optimización basada en principios presentes en la evolución natural. Pertenece a una clase más larga de algoritmos evolutivas.
  • El AG mantiene una población de cromosomas—un set de soluciones posibles para el problema. La idea es que la “evolución” encuentre una solución óptima para el problema después de un número de generaciones sucesivas—similar a una selección natural
  • El AG imita tres procesos evolutivos: selección, entrecruzamiento cromosómico y mutación.

    Por otra parte, en su artículo, concluye que, es muy interesante tomar un problema de la vida real y aplicar el algorítmo genético a éste. Puesto que descubriremos diferentes acercamientos al codificar entradas de data reales, al igual que diferentes implementaciones de entrecruzamiento y mutación. Puedes acceder al artículo completo mediante: Algorítmos Genéticos: búsqueda y optimización por selección natural.






Anuncio

Comentarios