Optimización por enjambre de partículas

Las abejas en busca de alimento tratan de localizar la región del espacio con mayor densidad de flores, ya que es allí donde presumiblemente existe más cantidad de polen. Cada abeja vuela de modo errático por el espacio, recordando en todo momento cuál es la región donde ha visto más flores. A su vez, el enjambre sabe colectivamente cuál es la región del espacio, de entre todas las exploradas, donde se han encontrado más flores. Cada abeja variará individualmente su movimiento con arreglo a estas dos direcciones, volando hacia algún lugar intermedio. Es posible que la abeja durante ese sobrevuelo encuentre una región con más densidad de flores que la conocida hasta entonces (óptimo local), o incluso que la conocida por el enjambre (óptimo global); en este último caso, todo el enjambre orientará la búsqueda hacia esa nueva dirección. Pasado un tiempo, si se descubre otra región con mayor densidad floral, el enjambre reorientará nuevamente la búsqueda hacia allí, y así sucesivamente.

Un algoritmo PSO trabaja con una población (llamada nube o enjambre) de soluciones candidatas (llamadas partículas). Dichas partículas se desplazan a lo largo del espacio de búsqueda conforme unas simples reglas matemáticas. El movimiento de cada partícula depende de su mejor posición obtenida, así como de la mejor posición global hallada en todo el espacio de búsqueda. A medida que se descubren nuevas y mejores posiciones, éstas pasan a orientar los movimientos de las partículas. El proceso se repite con el objetivo, no garantizado, de hallar en algún momento una solución lo suficientemente satisfactoria.

Lo descrito anteriormente puede formalizarse del siguiente modo: sea f: ℝⁿ → ℝ la función de coste que se desea minimizar. La función f toma como argumento una solución candidata, representada como un vector de números reales, y da como salida un número real que indica el valor de la función objetivo para la solución candidata obtenida. Las mejores posiciones se corresponden con los mejores valores de la función objetivo f. El objetivo es hallar una solución a que verifique f(a) ≤ f(b) para todo b en el espacio de búsqueda, lo que implicaría que a es el mínimo global. El proceso inverso, útil en problemas de maximización, puede lograrse considerando una función h = -f.

Sea S el número de partículas en la nube, cada una de las cuales tiene una posición x_i ∈ ℝⁿ en el espacio de búsqueda y una velocidad v_i ∈ ℝⁿ. Sea p_i la mejor posición conocida de una partícula i, y g la mejor posición global conocida. Un algoritmo PSO básico podría describirse como sigue:

• Para cada partícula ${\textstyle i=1,...,S}$:
  • Inicializar la posición de la partícula mediante un vector aleatorio uniformemente distribuido: ${\textstyle x_{i}\thicksim U(b_{lo},b_{up})}$, donde ${\textstyle b_{lo}}$y ${\displaystyle b_{up}}$ son respectivamente el límite inferior y el límite superior del espacio de búsqueda.
  • Inicializar la mejor posición conocida de la partícula a su posición inicial: ${\textstyle p_{i}\leftarrow x_{i}}$.
  • Si ${\textstyle f(p_{i})<f(g)}$ actualizar la mejor posición global conocida: ${\displaystyle g_{i}\leftarrow p_{i}}$.
  • Inicializar la velocidad de la partícula: ${\textstyle v_{i}\thicksim U(-|b_{up}-b_{lo}|,|b_{up}-b_{lo}|)}$.
• Mientras no se cumpla el criterio de parada (por.ej. límite máximo de iteraciones, encontrada una solución satisfactoria), repetir:
  • Para cada partícula ${\textstyle i=1,...,S}$:
    • Para cada dimensión ${\displaystyle d=1,...,n}$:
      • Elegir números aleatorios: ${\displaystyle r_{p},r_{g}\thicksim U(0,1)}$.
      • Actualizar la velocidad de la partícula: ${\textstyle v_{i}\leftarrow \omega v_{i,d}+\varphi _{p}r_{p}(p_{i,d}-x_{i,d})+\varphi _{g}r_{g}(g_{d}-x_{i,d})}$.
    • Actualizar la posición de la partícula: ${\displaystyle x_{i}\leftarrow x_{i}+v_{i}}$_.
    • Si ${\displaystyle f(x_{i})<f(p_{i})}$ entonces:
      • Actualizar la mejor posición conocida de la partícula: ${\displaystyle p_{i}\leftarrow x_{i}}$.
      • Si ${\displaystyle f(p_{i})<f(g)}$ actualizar la mejor posición global: ${\textstyle g\leftarrow p_{i}}$.
• Devolver ${\textstyle g}$ como la mejor solución encontrada.

Los parámetros ${\displaystyle \omega ,\varphi _{p}}$ y ${\displaystyle \varphi _{g}}$ son definidos por un especialista y regulan el comportamiento y la eficacia del método PSO, como se expone a continuación.

Gráfica bidimensional que muestra el rendimiento de una variante PSO ante un benchmark de problemas en función de dos parámetros.

En PSO, la elección de los parámetros es un aspecto determinante en el desempeño del algoritmo de optimización. Por ende, seleccionar un conjunto de parámetros que favorezcan un buen rendimiento del algoritmo es y ha sido objeto de abundantes investigaciones.[7][8][9][10][11][12][13][14][15]

De manera intuitiva, puede imaginarse que la función objetivo da lugar a una hipersuperficie de dimensionalidad equivalente al número de parámetros a optimizar (variables de búsqueda). La irregularidad de dicha hipersuperficie dependerá, obviamente, del problema en particular. Asimismo, la calidad de la búsqueda dependerá de cuán exhaustiva sea ésta, en función de los parámetros escogidos. Para obtener soluciones con una hipersuperfie "poco irregular" en general se necesitan pocas partículas e iteraciones; en cambio, para conseguir soluciones de hipersuperficie "más irregular" se requiere una búsqueda más a fondo, que involucre mayor cantidad de partículas e iteraciones. Este comportamiento es análogo al observado en situaciones reales, como por ej. la búsqueda de los mejores pastos llevada a cabo por la ganadería trashumante, donde grandes rebaños han de atravesar terrenos difíciles y abruptos para alcanzar los mejores prados (léase óptimo global), mientras que rebaños más pequeños pueden bastarse con terrenos menos densos en vegetación (óptimo local), usando pocas iteraciones.

En PSO, los parámetros pueden asimismo ajustarse para diversos escenarios de optimización[15][16][17] utilizando un optimizador "superpuesto", un concepto conocido como metaoptimización.[18][19][20]

La PSO básica suele incurrir fácilmente en óptimos locales. Esta convergencia prematura puede evitarse ignorando la mejor posición global g conocida, y atendiendo en su lugar a la mejor posición l conocida del sub-enjambre "circundante" a la partícula en movimiento. Este sub-enjambre puede definirse geométricamente –por ej. "las m partículas más cercanas"– o bien de forma social, es decir, como un conjunto de partículas relacionadas, con independencia de la distancia que las separa.

Si suponemos que existe un vínculo de información entre cada partícula y sus adyacentes, el conjunto de estos vínculos constituye un grafo, una red de comunicación, denominada topología. Una topología social muy frecuente es el anillo, en donde cada partícula tiene sólo dos partículas adyacentes, pero hay muchas otras.[21] La topología no es necesariamente fija, puede ser adaptativa según el caso (SPSO,[22] estrella estocástica,[23] TRIBES,[24] Cyber Swarm,[25] C-PSO[26]).

Hay diversas interpretaciones en cuanto a cómo y por qué un algoritmo de PSO es capaz de optimizar variables.

Una noción comúnmente aceptada por los investigadores es que el "comportamiento de enjambre" varía entre un "comportamiento de exploración" (de búsqueda en una amplia región del espacio de soluciones) y un "comportamiento de explotación" (de búsqueda local que se aproxima rápidamente hacia un óptimo, posiblemente local). Este es el criterio predominante desde los inicios de la PSO,[2][3][7][11] y sostiene que el algoritmo de PSO y sus parámetros han de ser cuidadosamente seleccionados para lograr un equilibrio idóneo entre exploración y explotación, a fin de evitar una convergencia prematura hacia óptimos locales, y, al mismo tiempo, asegurar una buena tasa de convergencia al óptimo global. Esta interpretación ha dado pie a numerosas variantes dentro de la PSO, como se expone más adelante.

Otra perspectiva aduce que aún no se ha logrado comprender exactamente cómo afecta el comportamiento del enjambre a la calidad del proceso de optimización, especialmente en problemas de optimización con espacios de búsqueda multidimensionales, discontinuos o variables en el tiempo. Desde este punto de vista, bastaría con encontrar algoritmos y parámetros que en la práctica den como resultado un buen rendimiento, independientemente de qué balance entre exploración y explotación adopte el enjambre. Este planteamiento ha llevado a simplificar los algoritmos de PSO, como se explica en un apartado posterior.

Incluso un algoritmo básico de PSO puede dar lugar a numerosas variantes. Por ejemplo, hay diferentes formas de inicializar las partículas y sus velocidades, de regular la velocidad, de actualizar p y g una vez que todo el enjambre ha sido actualizado, etc. Algunas de estas opciones y su impacto potencial en el rendimiento han sido discutidos en la literatura especializada.[9]

Como resultado, constantemente surgen nuevas y más sofisticadas variantes de PSO con el fin de mejorar el rendimiento del proceso de optimización. En la investigación llevada a cabo pueden distinguirse ciertas tendencias; una es lograr un método de optimización híbrido que combine PSO con otros mecanismos optimizadores,[32][33] por ej. incorporando un método eficaz de aprendizaje.[34] Otra vía de investigación trata de contrarrestar la convergencia prematura (es decir, el estancamiento de la búsqueda en un óptimo local), por ej. invirtiendo o perturbando el movimiento de las partículas.[14][35][36] Otro de los enfoques propone lidiar con la convergencia prematura mediante el uso de múltiples enjambres (optimización multi-enjambre); esta estrategia multi-enjambre también es aplicable a la optimización multiobjetivo.[37] Asimismo, se han producido avances en la adaptación de los parámetros de comportamiento durante la optimización.[17]

• Inteligencia de enjambre
• Optimización multi-enjambre
• Filtro de partículas