Contribuciones a la convergencia del algoritmo genético simple con estimaciones del tiempo de espera al óptimo global

Resum

En la Introducción, tras una exposición básica de los conceptos Evolutivos y de la Genética, se introducen las estrategias de Optimziación Evolutiva, como los algoritmos Evolutivos y los Algoritmos Genéticos y los métodos de búsqueda aleatoria en la Optimización Heurística Global, Posteriormente, se presetan los fundamentos matemáticos de las cadenas finitas de Markov, dando paso de manera natural a los ingredientes básicos de la Búsqueda Heurística Aleatoria y a los detalles del modelo dinámico estocástico de Nix y Vose para el Algoritmo Genético Simple, SGA, como una cadena de Markov ergódica. Las contribuciones de la presente tesis son: 1,- Dos nuevos algoritmos de Optimización Heurística Global, a partir del análisis estocástico del SGA; El Algoritmo Genético Estadístico, AAGE, que aprovecha la ergodicidad delSGA usando un colectivo estadístico con tiempos de ejecución pequeños. El Algoritmo de Multirrecombinación Selección, MRS, que potencia la exploración sobre las clases cerradas del operador de recombinación durante varias generaciones sin selección. Para ambos algoritmos se muestran y comentan los resultados obtendios con funciones de prueba usadas frecuentemente en la Optimización Heurística Global. 2,- Un resultado teórico explícito para el tiempo promedio de espera del modelo de Nix y Vose para elSGA, con parámetros de búsqueda cualesquiera, muestran las insuficiencias del modelo respecto a los datos experimentales. La introducción de un postulado empírico posibilita un nuevo modelo de Markov Absorbente para el comportamiento típico delSGA. La convergencia del modelo se sigue de la teoria clásica para cadenas de Markov absorbentes. 3,- Finalmente, se desarrolla una fórmula explícita para el tiempo promedio de espera del modelo Absorbente para el comportamiento típico del SGA, que coincide con la entropía del sistema y es compatible, en orden de magnitud, con los resultados e