lunes, 30 de junio de 2014

Algoritmo evolutivo de adaptación

Los algoritmos genéticos son técnicas de optimización que utilizan principios de evolución natural, según John Holland, en el libro escrito el año 1975 titulado “Adaptación en sistemas naturales y artificiales”, los algoritmos genéticos son también llamados algoritmos de búsqueda con heurística. En palabras de Mitchell, en el libro escrito el año 1996 titulado “Una introducción a los algoritmos genéticos”, este tipo de algoritmos se encuentran en un constante cambio, porque aún no se ha definido a cabalidad cómo obtener su mejor desempeño; razón por la cual investigadores en el área trabajan en cómo mejorar su desempeño a partir del perfeccionamiento de cada una de sus partes. Los algoritmos genéticos fueron desarrollados por Holland a principios de los años 1960 con la motivación de resolver problemas de aprendizaje automático y se convirtieron en uno de los enfoques más sobresalientes en el campo de los algoritmos evolutivos. La forma de operar de un algoritmo genético es la siguiente: Al iniciar su ejecución el algoritmo genera una población inicial de individuos, cada uno de estos es un candidato a solucionar el problema de optimización que se está resolviendo, a continuación los individuos son evaluados en su aptitud para resolver el problema y un esquema de selección es ejecutado para elegir los individuos sobre los cuales serán aplicados los operadores genéticos, los individuos resultantes después de aplicar los operadores genéticos se convertirán en la nueva población sobre la cual se repetirá el proceso de evolución descrito anteriormente hasta un número de generaciones determinado.

Según Nesmachnow, en la tesis de maestría escrita el año 2004 titulada “Algoritmos genéticos paralelos y su aplicación al diseño de redes de comunicaciones confiables”, la expresión genérica computación evolutiva designa a un amplio conjunto de técnicas heurísticas de resolución de problemas complejos que basan su funcionamiento en un mecanismo análogo a los procesos de la evolución natural. Trabajando sobre un conjunto de soluciones a un problema determinado, la metodología utilizada por estas técnicas se fundamenta en el uso de mecanismos de selección de las mejores soluciones potenciales y de construcción de nuevas soluciones candidatas mediante recombinación de características de las soluciones seleccionadas. El algoritmo evolutivo trabaja sobre individuos que representan potenciales soluciones al problema, codificados de acuerdo a un mecanismo prefijado. Los individuos son evaluados de acuerdo a una función de adaptabilidad que toma en cuenta la adecuación de cada solución al problema que se intenta resolver. La operativa del algoritmo evolutivo comienza con una etapa de inicialización de los individuos, que puede ser completamente aleatoria, muestreando al azar diferentes secciones del espacio de soluciones, o guiada de acuerdo a características del problema a resolver. El algoritmo evolutivo podría inclusive tomar como población inicial individuos resultantes como salida de algún otro algoritmo heurístico de resolución que permitiera calcular buenas soluciones iniciales aproximadas para el problema.

La evolución propiamente dicha se lleva a cabo en el ciclo que genera nuevos individuos a partir de la población actual mediante un procedimiento de aplicación de operadores estocásticos. En este ciclo se distinguen cuatro etapas: (1) Evaluación. Etapa que consiste en asignar un valor de adaptabilidad a cada individuo en la población. Este valor evalúa que tan bien resuelve cada individuo el problema en cuestión, y es utilizado para guiar el mecanismo evolutivo. (2) Selección. Proceso que determina candidatos adecuados, de acuerdo a sus valores de adaptabilidad, para la aplicación de los operadores evolutivos con el objetivo de engendrar la siguiente generación de individuos. (3) Aplicación de los operadores evolutivos. Etapa que genera un conjunto de descendientes a partir de los individuos seleccionados en la etapa anterior. (4) Reemplazo. Mecanismo que realiza el recambio generacional, sustituyendo individuos de la generación anterior por descendientes creados en la etapa anterior.

No hay comentarios:

Publicar un comentario en la entrada