Técnicas espectrales en la mejora de algoritmos genéticos

Resumen

Los Algoritmos Genéticos (GAs) son una clase de técnicas de búsqueda basadas en los principios de la evolución y la genética, que han sido aplicadas con razonable eficacia a múltiples problemas de optimización. Las principales características de los GAs son su gran robustez y versatilidad, lo que permite su empleo en problemas muy dispares. No obstante, se conoce la existencia de tipós de problemas en los que los GAs tienen un rendimiento probadamente bajo (denominados genéricamente problemas GA-hard). Estudios previos muestran la existencia de una relación entre la dificultad de un pro blema para un GA y la estructura del desarrollo en serie de Walsh de la función objetivo. Esta tesis desarrolla dicha relación a través del concepto de espectro, definido a partir de la expansión de Walsh: se presentan así diversas técnicas que mejoran el rendimiento de los GAs en problemas GA-hard y en problemas reales mediante la modificación de los correspondientes espectros. En primer lugar, se realiza un estudio del efecto que tiene la aplicación de una trans formación lineal (TL) en el espectro de una determinada función y, por tanto, en sus pres taciones. Se especifica en qué condiciones una TL puede mejorar el rendimiento de un GA y se propone un algoritmo para la búsqueda de TLs. Incidentalmente, estos desarrollos arrojan luz sobre resultados contradictorios que aparecen en la literatura a cerca de la viabilidad de TLs en esquemas evolutivos. En segundo lugar, se elabora una interpretación del funcionamiento de algoritmos híbridos (AHs) en problemas de optimización con restricciones fuertes. Concretamente, se propone un esquema híbrido -basado en la unión de un GA, como algoritmo global,y de una red de Hopfield, como algoritmo local-, que presenta ventajas en problemas de este tipo; y se estudian sus prestaciones a través de las modificaciones que causa en el espectro del problema. Por último, se aplica el AH diseñado a dosproblemas de optimización que aparecen en ingeniería de telecomunicación: el diseño de la trama de transmisión en una red PRN, y la minimización de la interferencia co-canal en sistemas de satélites mediante la reasignación de canales. En ambos problemas se consiguen ventajas significativas sobre algoritmos previos.