Página principal

Lisis de la convergencia de los algoritmos estocasticos: algoritmos geneticos


Descargar 10.05 Kb.
Fecha de conversión18.07.2016
Tamaño10.05 Kb.


ANÁLISIS DE LA CONVERGENCIA DE LOS ALGORITMOS ESTOCASTICOS:

ALGORITMOS GENETICOS

Héctor Guardado Muro

Eunice Ponce de León Sentí

Universidad Autónoma de Aguascalientes




INTRODUCCIÓN

Los algoritmos genéticos fueron desarrollados por John Holland de la Universidad de Michigan, EU en el año 1975 con: “Adaptation in Natural and Artificial Systems”. Los algoritmos genéticos se emplean en la búsqueda de “poblaciones” de puntos los cuales poseen en gran medida la característica deseable. En el caso particular de la optimización de funciones, dicha característica es el valor de una función objetivo o adaptabilidad. Así, partiendo de una población de puntos, estos tienen una cierta probabilidad de cruzarse o reproducirse. En el algoritmo genético simple los mejores individuos tienen mayores probabilidades de reproducirse, manteniendo en las nuevas poblaciones, las características que los hacen mejores. Además se emplea un operador de mutación, donde con una probabilidad, los individuos cambian alguna característica. Esto es conveniente pues evita el estancamiento en óptimos locales. El proceso se repite hasta cumplir un cierto criterio de paro. Cada repetición representa una generación de la población. Pero las cuestiones principales serían: ¿El algoritmo antes descrito converge? ¿La población tendrá individuos con valores de adaptabilidad cercanos al óptimo?¿Qué tan cercanos al óptimo son? Para responder a estas preguntas John Holland establece el Teorema de Esquema, que fija una cota inferior para el número de casos pertenecientes a un esquema que existen en cada generación. Un esquema es un conjunto de cadenas con características similares, o más precisamente: si los individuos están dados por vectores, los esquemas serán conjuntos con posiciones fijas en el vector. De manera clara es conveniente estudiar aquellos esquemas donde las cadenas son mejores que el resto. Claramente los procesos de selección, cruza y mutación afectan a los bloques; dicha consideración es tomada en cuenta en el Teorema de Esquema. Es posible ver el número de cadenas de un esquema dado como una cadena de Markov y estudiarlo como tal.



OBJETIVOS

Realizar una revisión bibliográfica de los métodos empleados para el análisis de la

Resultados: De los trabajos publicados en análisis de la convergencia de los algoritmos genéticos (AG’s) se pueden destacar los siguientes: Günter Rudolph, que muestra por medio de cadenas de Markov la convergencia de los AG’s; los trabajos de Lixin Ding, Jinghu Yu, que usan las propiedades de cadenas de Markov y la fórmula de Dinkyn para acotar los tiempos de los algoritmos; Anna Pasynska, quién extiende el modelo de Vose de cadenas de Markov para el AG con los operadores de traslación y permutación de genes; U. Chandinmal de Silva, Joe Suzuki, que analizan la convergencia del AG cuando la probabilidad de mutación es baja y la presión de selección es alta; Diego F. Nehab que estudia el Teorema de Esquema cuando los genes varían dentro de alfabetos no finitos; y el trabajo de Takahashi Y. establece además una perspectiva general sobre la generalización de resultados resolviendo el problema de n-bits.

CONCLUSIONES Y TRABAJO FUTURO

Se ha hecho una revisión bibliográfica de los diferentes estudios de convergencia de los algoritmos genéticos, la cual nos sirve para conocer el estado del arte de esta rama. Como trabajo futuro nos interesa establecer una metodología para la convergencia de los algoritmos estocásticos en el área de la computación evolutiva.



BIBLIOGRAFÍA

[1] Goldberg, David E. Genetic: Algorithms in Search, Optimization and Machine Learning

Addison-Wesley Pub. Co. 1989. ISBN: 0201157675

[2]Li Meiyi,Cai Zixing,Sun Guoyun:Genetic Algorithms with Fitness&Diversity-guide Adaptive Operating Probabilities and Analyses of its Convergence

College of Information Science&Engineering, ,Changsha,China

[3]Kenneth A. De Jong,William M. Spears,Diana F. Gordon: Using Markov Chain to Analyse GAFO’s

Univ., Navy Center for Applied Research in Artificial Intelligence,Washington D.C.

[4] U. Chandimal de Silva, Joe Suzuky:On the Stationary Distribution of GAS With Fixed Crossover Probability

Department of Mathematics, Univ..,Osaka ,Japan.

[5]Thomas E. Davis ,Jose C. Principe:A Markov Framework for the Simple Genetic Algorithm

Electrical Engineering Department,Univ. of Florida, Gainesville FL 32611

[6]Lixin Ding,Jinghu Yu: Some Theorethical Reults About the Computation Time of Evolutionary Algorithms

Whuan Inst. of Physics And Mathematics, China

[7]Florian Schmitt and Franz Rothlauf:On the Mean of the Second Largest Eingevalue on the Convergence Rate of Genetics Algorithms

Univ. of Bayreuth, Germany.

[9]Diego F. Nehab,Marco Aurelio C. Pachecho :Schemata Theory for the Real Coding And Arithmetical Operators.

Computer Science Department Princeton Univ.

[10]Anna Paszynska:An Extension of Vose’s Markov Chain Model for Genetic Algorithms



Inst. of Computer Science, Jagielonian Univ.Polland




La base de datos está protegida por derechos de autor ©espanito.com 2016
enviar mensaje