PDF de programación - UN ALGORITMO HÍBRIDO PARA LA OPTIMIZACIÓN EN PARALELO DE PROBLEMAS CONTINUOS

SUBSECRETARÍA DE EDUCACIÓN SUPERIOR
DIRECCIÓN GENERAL DE EDUCACIÓN
SUPERIOR TECNOLÓGICA
INSTITUTO TECNOLÓGICO DE LA PAZ



INSTITUTO TECNOLÓGICO DE LA PAZ

UN ALGORITMO HÍBRIDO PARA LA OPTIMIZACIÓN

EN PARALELO DE PROBLEMAS CONTINUOS



TESIS PROFESIONAL



que para obtener el título de



INGENIERO EN SISTEMAS COMPUTACIONES



Presenta

JOEL ARTEMIO MORALES VISCAYA



Asesor

DR. MARCO ANTONIO CASTRO LIERA



La Paz, Baja California Sur, Agosto 2012.







Índice Temático

1. Introducción ................................................................................................ 1

1.1 Motivación ...................................................................................... 1

1.2 Definición del problema ................................................................. 2

1.3 Objetivos ........................................................................................ 4

1.3.1 Objetivo general ............................................................... 4

1.3.2 Objetivos específicos ....................................................... 4

2. Optimización de problemas continuos en paralelo ..................................... 5

2.1 Inteligencia artificial y heurística .................................................... 5

2.2 Algoritmos genéticos ...................................................................... 6

2.2.1 Individuo, población y aptitud ........................................... 6

2.2.2 Operadores genéticos ...................................................... 8

2.2.2.1 Selección ............................................................ 8

2.2.2.2 Cruzamiento ....................................................... 9

2.2.2.3 Mutación ........................................................... 10

2.2.3 Algoritmos genéticos en paralelo ................................... 11

2.2.4 Características de los algoritmos genéticos ................... 16

2.3 Optimización por enjambre de partículas ..................................... 17

2.3.1 Enjambre y partícula ...................................................... 17

2.3.2 Movimiento de una partícula .......................................... 19

2.3.3 Optimización por enjambre de partículas en paralelo .... 23

2.3.4 Características de PSO .................................................. 25

2.4 Métodos híbridos ......................................................................... 26

2.5 Arquitecturas paralelas de bajo costo .......................................... 27

2.5.1 GPGPU .......................................................................... 27

2.5.2 Clúster ............................................................................ 28

2.5.2.1 Estructura de PVM ............................................ 29

3. Algoritmo propuesto ................................................................................. 32

3.1 Estructura .................................................................................... 32

3.2 Algoritmo híbrido .......................................................................... 35

3.2.1 Paso de parámetros ....................................................... 35

3.2.2 Algoritmo genético .......................................................... 36

3.2.3 PSO ................................................................................ 37

3.3 Desarrollo e implementación ....................................................... 38

3.4 Pruebas y resultados ................................................................... 39

3.4.1 Funciones probadas ....................................................... 39

3.4.2 Metodología de las pruebas ........................................... 43

3.4.3 Determinación de los parámetros de las pruebas .......... 44

3.4.4 Resultados ..................................................................... 45

3.4.5 Conclusiones .................................................................. 46

3.5 Trabajo Futuro ............................................................................. 48

4. Referencias .............................................................................................. 49

Anexo: código fuente del programa .............................................................. 52

1. Introducción

1.1 Motivación

La optimización se puede definir de manera muy general como la ciencia

encargada de encontrar

las mejores soluciones a

los problemas, que

generalmente modelan una realidad física.

En el día a día tratamos con decenas de problemas de optimización, los cuales

resolvemos muchas veces sin percatarnos de que lo estamos haciendo, son

problemas simples, que pueden ser resueltos de manera analítica, o con simple

observación, sin embargo, entre más grande es el abanico de posibilidades y

mayor la cantidad de variables a considerar, los problemas se van volviendo más

complejos y es entonces que necesitamos algoritmos y herramientas, que nos

ayuden a solucionarlos.

La optimización numérica ha sido ampliamente usada para resolver problemas en

áreas como la economía, ingeniería de control, arquitectura, investigación de

operaciones y mecatrónica, por nombrar solo algunas. Los principales obstáculos

de los algoritmos existentes es que los problemas son demasiado demandantes

computacionalmente, es decir requieren recursos significativamente grandes en

tiempo y hardware; y que la mayoría de los problemas están plagados de óptimos

locales, soluciones que parecen ser las mejores del problema entero pero sólo lo

son de una parte del mismo.

El uso eficiente de los recursos computacionales es un aspecto cada vez más

importante en el desarrollo de algoritmos de optimización, partícularmente en lo

que respecta al aprovechamiento de arquitecturas de cómputo paralelo, ya que, en

la actualidad, prácticamente todos los modelos de computadoras personales

1



cuentan con procesadores multi-núcleo o con más de un procesador, por lo que el

desarrollo de aplicaciones en paralelo ya no está restringido a grandes y costosos

equipos especializados.

Existen además una gran cantidad de programas o librerías que facilitan la

conexión de varios equipos en una red, que se comportan como una sola

computadora en paralelo, lo que se conoce como Clúster.

Han sido desarrollados muchos algoritmos convencionales para la optimización de

funciones, sin embargo para problemas altamente complejos: con espacios de

búsqueda grandes, de muchas variables, no diferenciales, o altamente no lineales;

algoritmos heurísticos basados en poblaciones han sido aplicados con éxito.



1.2 Definición del problema

La optimización se puede mostrar en dos tipos de problemas igualmente

importantes, de variables continuas o de variables discretas, en este caso nos

concentraremos en los de variables continuas, donde el número de valores

posibles a tomar para cada variable es infinito, es decir, dentro de un rango

definido, siempre, entre dos valores asignables observados podemos encontrar un

tercer valor observable que también puede ser asignado.

Sugartan, Hansen et al. Propusieron un conjunto de funciones (o una batería de

funciones) para la competencia de computación evolutiva (CEC05), el cual se usó

para analizar y comparar la eficacia y eficiencia de la estrategia desarrollada

contra otras ya existentes [1]. Todas las funciones que se encuentran en la batería

de pruebas cumplen con la condición de ser escalables, es decir que se puede

aumentar el número de variables independientes en las mismas con facilidad y



2

con ello volverlas más y más complejas de optimizar. Dentro del conjunto de

funciones que se encuentran en la batería se eligieron algunas de las más

características y complejas; las funciones Rastrigin, Schwefel y Ackley que cuenta

con muchos puntos críticos, así como Weierstrass que además no es derivable,

funciones para las que ya se han hecho esfuerzos por optimizarlas [2, 3, 4].

“Se conoce como heurísticos a todos aquellos métodos que solamente

necesitan la definición de un espacio de soluciones, los operadores, y la

función objetivo, sin exigir el cumplimiento de ninguna característica especial,

como podría ser la continuidad, la existencia de derivadas, etc. La importancia

vital de estos métodos está en que son la única posibilidad para resolver

problemas con las condiciones siguientes:

- No existe un algoritmo eficiente para la solución partícular del mismo.

- No es posible la exploración exhaustiva del espacio completo de

búsqueda, debido a las dimensiones del mismo.

Ninguno de ellos garantiza la obtención del óptimo global en el marco de

condiciones prácticas. Sin embargo, ellos permiten obtener buenas soluciones

que en muchos casos satisfacen a los usuarios” [5].

Los algoritmos genéticos son un heurístico basado en poblaciones propuesto por

Holland dónde los individuos más aptos son los que sobreviven y producen

nuevos individuos [6].

Los algoritmos basados en enjambres de partículas, conocidos como PSO son

otra estrategia heurística creada por Eberhart y Kennedy basados en el

movimiento de algunas especies animales dónde la mayoría de la población sigue



3

a los miembros que se encuentran en mejo