Publication: Técnicas espectrales en la mejora de algoritmos genéticos
Loading...
Identifiers
Publication date
2002
Defense date
2002-10-07
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
Genetic Aigorithms (GAs) are a class of search techniques based on the principies of evolution and genetics, which have been efficiently applied to a wide variety of optimization probiems. The most irnportant characteristics of GAs arerobustness and versatility,which allow their application to very different kinds of problems. However, there exists optimization problems in which GAs are known to perform pooriy (these problems are generically denoted as GA-hard problerns). Previous studies have shown that there exists a reiationship between GA performance and the structure of the Waish series expansion of the problern’s objective function. This thesis eiaborates on this relationship by means of the spectrum concept, defined from the Waish expansion: thus, sorne techniques to improve GA perforrnance in GA-hard problems, and in real problems, are presented. The interpretation for these techniques rests on the modifications they cause to probiems’ espectra. Firstiy, we provide sorne new results about the effect of Linear Transforrnations (LTs) in function spectra, and therefore in the corresponding GA performance. We investigate the conditions for a LT to improve GA performance in a given function, and propose an aigorithm to search a feasible LT. Eventually, the obtained resuits shed light on sorne apparently contradictory resuits in the literature about the viability of using LTs to enhance evolutionary algorithms. Secondiy, we elaborate an explanation of Hybrid Aigonthms (HAs) performance in hard constrained optimization probierns. A HA based on mixing GAs and Hopfield neural network is proposed (HNN-GA) and its features studied by means of spectra modifica tions. Finaliy, the HNN-GA is applied to two optimization problems in telecommunications: The design of a Packet Radio Network transmission frarne, and the minimization of co-channel interference in satellite systems using channel reassignment. In both problems HNN-GA outperforms existing algonthms.
Genetic Aigorithms (GAs) are a class of search techniques based on the principies of evolution and genetics, which have been efficiently applied to a wide variety of optimization probiems. The most irnportant characteristics of GAs arerobustness and versatility,which allow their application to very different kinds of problems. However, there exists optimization problems in which GAs are known to perform pooriy (these problems are generically denoted as GA-hard problerns). Previous studies have shown that there exists a reiationship between GA performance and the structure of the Waish series expansion of the problern’s objective function. This thesis eiaborates on this relationship by means of the spectrum concept, defined from the Waish expansion: thus, sorne techniques to improve GA perforrnance in GA-hard problems, and in real problems, are presented. The interpretation for these techniques rests on the modifications they cause to probiems’ espectra. Firstiy, we provide sorne new results about the effect of Linear Transforrnations (LTs) in function spectra, and therefore in the corresponding GA performance. We investigate the conditions for a LT to improve GA performance in a given function, and propose an aigorithm to search a feasible LT. Eventually, the obtained resuits shed light on sorne apparently contradictory resuits in the literature about the viability of using LTs to enhance evolutionary algorithms. Secondiy, we elaborate an explanation of Hybrid Aigonthms (HAs) performance in hard constrained optimization probierns. A HA based on mixing GAs and Hopfield neural network is proposed (HNN-GA) and its features studied by means of spectra modifica tions. Finaliy, the HNN-GA is applied to two optimization problems in telecommunications: The design of a Packet Radio Network transmission frarne, and the minimization of co-channel interference in satellite systems using channel reassignment. In both problems HNN-GA outperforms existing algonthms.
Description
Keywords
Algoritmos genéticos