Optimización por el método de Enjambre de Partículas Unificado para Resolver Problemas de Optimización de

Ingeniería Limitados.

K.E. Parsopoulos1 y M.N. Vrahatis2

1 Laboratorio de Inteligencia Computacional (CI Lab), Departamento de Matemáticas, Universidad de Patras, GR-26110 Patras, Grecia. kostasp@math.upatras.gr

2 Centro de Investigación en Inteligencia Artificial de la Universidad de Patras (UPAIRC), Universidad de Patras, GR-26110 Patras, Grecia. vrahatis@math.upatras.gr

Resumen. Investigamos el rendimiento del método recientemente propuesto de Optimización por Enjambre de Partículas Unificado en problemas limitados de optimización de ingeniería. Para este propósito, un “acercamiento de función de penalización” es empleado y el algoritmo es modificado para preservar factibilidad de la solución encontrada. El algoritmo es ilustrado en cuatro bien conocidos problemas de ingeniería con resultados prometedores. Comparaciones con los métodos de Optimización de Enjambre de Partículas con variante estándar local y global son mostradas y discutidas.

1. Introducción

Muchas aplicaciones de ingeniería, como la optimización estructural, diseño de ingeniería, diseño VLSI (Very Large Scale Integration, Integración a muy gran escala), economía, problemas de asignación y locación[1], implican difíciles problemas de optimización que deben ser resueltos de manera eficiente y efectiva. Dada la naturaleza de estas aplicaciones, las soluciones usualmente necesitan ser limitadas en partes específicas del espacio de búsqueda que son delimitadas por restricciones lineales o no lineales.

Diferentes algoritmos tanto determinísticos como estocásticos han sido desarrollados para abordar dichos problemas. Las aproximaciones determinísticas tal como “Dirección Factible” y “Descenso Gradiente Generalizado” hacen supuestos fuertes en la continuidad y diferenciabilidad de la función objetivo[1], [2]. Por esto, su aplicabilidad es limitada ya que estas características no son encontradas con frecuencia en problemas que surgen en aplicaciones de la vida real. Por otro lado, los algoritmos estocásticos de optimización tales como “Algoritmos Genéticos”, “Estrategias de Evolución”, Programación Evolutiva y Optimización por Enjambre de Partículas (PSO) no hacen dichas suposiciones y han sido aplicados exitosamente para abordar problemas de optimización limitados durante los últimos años [3, 4, 5, 6, 7].

Muchos de los antes mencionados algoritmos de optimización han sido diseñados ante todo para dirigirse a problemas de optimización ilimitados. Entonces, técnicas de manipulación de limitación son usualmente incorporadas en los algoritmos en orden de dirigir la búsqueda de las regiones deseadas (factibles) del espacio de búsqueda. La técnica de manipulación de limitación más comúnmente utilizada es la de “Función de Penalización”. En esta aproximación, el problema es resuelto como uno ilimitado, donde la función objetivo es diseñada de tal forma que las soluciones no factibles son caracterizadas por valores altos de función (en casos de minimización). La popularidad de las aproximaciones

fundamentadas en penalización para manipulación de limitación, está basada en su mayoría en su simplicidad y aplicabilidad directa que no implica modificaciones de los algoritmos empleados ni desarrollo de operadores especializados para abordar limitantes.

El UPSO es un reciente esquema PSO que engancha la variante local y global del PSO, combinando sus habilidades de exploración y explotación, sin imponer requerimientos adicionales en términos de evaluaciones de función [10]. Estudios preliminares han mostrado que UPSO puede abordar eficientemente diferentes problemas de optimización [10,11].

Investigamos el desempeño del UPSO en cuatro bien conocidos problemas de optimización de ingeniería limitados. Una aproximación de función de penalización es adoptada y los resultados obtenidos son comparados con los del algoritmo PSO estándar, suministrando conclusiones útiles acerca de la eficiencia del esquema unificado. El resto del artículo está organizado como sigue. La función de penalización empleada es descrita en la sección 2, mientras que la sección 3 es dedicada a la descripción del UPSO. Los problemas de prueba considerados como los resultados obtenidos son reportados y discutidos en la sección 4. El documento cierra con conclusiones en la sección 5.

2. La Aproximación de la Función de Penalización

El problema de optimización limitado se puede formular, en general, así:

minX∈ S⊂R n

f ( X ) (1)

Sujeto a:

gi (X )≤0 ; i=1 ,…,m (2)

Donde m es el número de limitantes. Diferentes limitaciones de desigualdad e igualdad pueden ser fácilmente transformadas en la forma de la ecuación 2. La función de penalización correspondiente puede ser definida por (3):

F ( X )=f ( X )+H (X ) (3)

Donde H(X) es un factor de penalización que es estrictamente positivo para todas las soluciones no factibles. Funciones con penalizaciones estáticas, dinámicas, recocido y adaptativas han sido propuestas y aplicadas satisfactoriamente en diferentes aplicaciones [3, 7].

En el actual estudio, se empleó una función de penalización que incluye información sobre, tanto el número de limitaciones violadas, como el grado de violación. Entonces, el factor de penalización es definido como [8]:

H (X )=w1 NVCX+w2SVCX ecuación(4)

Donde NVCX es el número de limitaciones que están siendo violadas por X; SVCX es la suma de todas las limitaciones violadas, por ejemplo:

SVCX=∑i=1

m

max {0 , gi (X ) } ,

Y w1 y w2 son cargas estáticas. La selección de esta forma de penalización está basada en los prometedores resultados obtenidos usando tales funciones de penalización con algoritmos evolutivos [8].

En general, la función de penalización influencia de gran forma el rendimiento de un algoritmo en la solución de problemas de optimización limitados. Funciones de penalización sofisticadas y basadas en problemas pueden incrementar significativamente el rendimiento del algoritmo. Para evadir la posible gran influencia de la función de penalización empleada en el rendimiento del algoritmo, se usaron cargas w1 y w2, aunque aproximaciones auto-adaptativas que modifican dinámicamente las cargas a través de esquemas de co-evolución, como también funciones de penalización más complicadas, han sido aplicadas exitosamente en trabajos relacionados [8, 6].

3. Optimización por Enjambre de Partículas Unificado

PSO (Particle Swarm Optimization | Optimización por Enjambre de Partículas) es un algoritmo estocástico, basado es poblaciones, para resolver problemas de optimización. Fue presentado en 1995 por Eberhart y Kennedy para tareas de optimización numérica y su dinámica está basada en principios que gobiernan grupos de individuos socialmente organizados [12].

En el contexto PSO, la población es llamada Enjambre y sus individuos (puntos de búsqueda) son llamados partículas. Cada partícula tiene tres características principales:

1- Una velocidad adaptable con la que se mueve en el espacio de búsqueda.

2- Una memoria donde guarda la mejor posición que ha visitado en el espacio de búsqueda (por ejemplo, la posición con el valor más bajo de la función).

3- La capacidad de compartir la información socialmente (por ejemplo, el conocimiento de la mejor posición visitada por todas las partículas en su vecindad).

Las vecindades son determinadas usualmente basándose en los indicios de las partículas, dando paso a las dos variantes principales del PSO, llamadas variante global y local. En la primera, todo el enjambre es considerado la vecindad de cada partícula, mientras que en la segunda, se utilizan estrictamente vecindades más pequeñas.

Asuma una función n-dimensional:

f : S⊂Rn→R

Y un enjambre de N partículas:

S={X1 , X2 ,…, XN }

La partícula i-ésima, Xi perteneciente a S, su velocidad, Vi, como también su mejor posición Pi perteneciente a S, son vectores n-dimensionales. Una vecindad de radio m de Xi consiste en partículas Xi-m,…, Xi,…, Xi+m. Asuma que bi sea el índice de la partícula que tiene la previa mejor posición entre todas las partículas de la vecindad de X i, y t sea el contador de iteraciones. Entonces, de acuerdo a la versión del coeficiente de limitación de PSO, el enjambre es actualizado usando las ecuaciones [13]:

V i ( t+1 )=X [V i ( t )+c1 r1 (P i ( t )−X i ( t ) )+c2r 2 (Pbi (t )−X i ( t ) ) ]ecuación(5)

X i (t+1 )=X i (t )+V i (t+1 ) ecuación(6)

Donde i = 1, 2,…, N; X es el coeficiente de limitación; c1 y c2 son constantes positivas, conocidas como parámetros cognitivo y social respectivamente; y r1 y r2 son vectores aleatorios con componentes uniformemente distribuidos en [0, 1]. Valores por defecto para X, c1 y c2 son determinados en el análisis teórico de Clerc y Kennedy[3].

El rendimiento de un algoritmo basado en poblaciones es altamente dependiente en los intercambios entre sus habilidades de exploración y su explosión, por ejemplo, su habilidad de explorar extensas áreas del espacio de búsqueda y su habilidad para converger rápidamente hacia las más prometedoras soluciones respectivamente. La variante global del PSO promueve la explosión ya que todas las partículas son atraídas por la misma posición, luego convergen más rápidamente hacia el mismo punto.

4. Referencias

[1] C. A. Floudas, “A collection of test problems for constrained global optimization algorithms,” Recherche, vol. 67, p. 02, 1990.

[2] D. M. Himmelblau, Applied Nonlinear Programming. New York: McGraw-Hill, 1972, p. 498.

[3] M. Clerc and J. Kennedy, “The Particle Swarm — Explosion, Stability, and Convergence in a Multidimensional Complex Space,” vol. 6, no. 1, pp. 58-73, 2002.