Download análisis de la convergencia de los algoritmos estocasticos

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