Optimizacios de enjambre de particulas

Algoritmos Basados en Cúmulos de Partículas Para la Resolución de Problemas Complejos
Autor: José Manuel García Nieto Directores: Enrique Alba Torres y Gabriel Jesús Luque Polo septiembre de 2006

2

Índice general
Prólogo 1. Algoritmos Basados en Cúmulos de Partículas
1.1. Introducción a las Técnicas Metaheurísticas de Optimización 1.1.1. Metaheurísticas Basadas en Trayectoria . . . . . . . .1.1.2. Metaheurísticas Basadas en Población . . . . . . . . 1.2. Algoritmos Basados en Cúmulos de Partículas (PSO) . . . . 1.3. Descripción del Algoritmo PSO . . . . . . . . . . . . . . . . 1.3.1. Tipos de Algoritmos de PSO . . . . . . . . . . . . . . 1.3.2. Topologías del Cúmulo de Partículas . . . . . . . . . 1.4. Aspectos Avanzados de PSO . . . . . . . . . . . . . . . . . . 2.1. Introducción .. . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. La Biblioteca MALLBA . . . . . . . . . . . . . . . . . . . . 2.3. Implementación de los Esqueletos . . . . . . . . . . . . . . . 2.3.1. Clases y Métodos Comunes . . . . . . . . . . . . . . 2.3.2. Clase Requerida Solution . . . . . . . . . . . . . . . 2.3.3. Clase Requerida Problem . . . . . . . . . . . . . . . . 2.3.4. Clase RequeridaUser_Statistics . . . . . . . . . . 2.3.5. Clase Proporcionada SetUpParams . . . . . . . . . . 2.3.6. Clase Proporcionada Statistics . . . . . . . . . . . 2.3.7. Clase Proporcionada Stop_Condition . . . . . . . . 2.3.8. Clases Proporcionadas State_Vble y State_Center . 2.3.9. Clases Proporcionadas Jerarquía Solver . . . . . . . 2.4. Usuarios de los Esqueletos de Código . . . . . . . . . . . . . 3.1.Introducción . . . . . . . . . . . . . . . . . . 3.2. Funcionamiento del PSO Básico . . . . . . . 3.3. PSO para Codicación Continua . . . . . . . 3.3.1. Representación de las Partículas . . . 3.3.2. Operador Actualización de Velocidad 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 11
11 14 16 18 19 2223 25

2. Esqueleto de Código Implementado

27
27 28 30 31 31 31 32 33 33 33 34 34 35 37 38 38 40 40

3. Esqueleto para el Algoritmo PSO

37

4 3.3.3. Operador Movimiento . . . . . . . . PSO para Codicación Binaria . . . . . . . . 3.4.1. Representación de las Partículas . . . 3.4.2. Operador Actualización de Velocidad 3.4.3. Operador Movimiento . . . . . . . . PSO para Permutaciones de Enteros. . . . 3.5.1. Representación de las Partículas . . . 3.5.2. Operador Actualización de Velocidad 3.5.3. Operador Movimiento . . . . . . . . Diseño del Esqueleto de Código . . . . . . . Implementación del Esqueleto de Código . . 3.7.1. Parte Requerida del Esqueleto . . . . 3.7.2. Parte Proporcionada del Esqueleto . Ficheros que Componen el Esqueleto . . . . Conguración del Esqueleto . . . . . . .. . . . . . . . . . . . . . . . .

ÍNDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 41 42 42 43 43 44 44 46 46 47 47 49 53 53

3.4.

3.5.

3.6. 3.7. 3.8. 3.9.4. Problemas Abordados

4.1. Caso de Estudio: Location Area Management (LA) . . . . . . 4.1.1. Modelo Empleado . . . . . . . . . . . . . . . . . . . . . 4.1.2. Función de Evaluación . . . . . . . . . . . . . . . . . . 4.1.3. Resolución del Problema LA con el Esqueleto PSO . . 4.2. Caso de Estudio: Gene Ordering in Microarray Data (GOMAD) 4.2.1. Modelo Empleado . . . . . . . . . . . . . . . . . . .. . 4.2.2. Función de Evaluación . . . . . . . . . . . . . . . . . . 4.2.3. Resolución del Problema GOMAD con el Esqueleto PSO 5.1. Problema LA . . . . . . 5.1.1. Instancias . . . . 5.1.2. Descripción de los 5.1.3. Resultados . . . . 5.1.4. Conclusiones . . 5.2. Problema GOMAD . . . 5.2.1. Instancias . . . . 5.2.2. Descripción de los 5.2.3. Resultados . . . . 5.2.4. Conclusiones . . . . . . . ....