Optimización por enjambre de partículas
En informática, la optimización por nube de partículas u optimización por enjambre de partículas (conocida por sus siglas en inglés: PSO, de «particle swarm optimization») hace referencia a una metaheurística que evoca el comportamiento de las partículas en la naturaleza.
Los métodos PSO se atribuyen originalmente a los investigadores Kennedy, Eberhart y Shi. En un principio fueron concebidos para elaborar modelos de conductas sociales, como el movimiento descrito por los organismos vivos en una bandada de aves o un banco de peces. Posteriormente el algoritmo se simplificó y se comprobó que era adecuado para problemas de optimización. El libro de Kennedy y Eberhart describe numerosos aspectos teóricos de la PSO y la inteligencia de enjambre. Un amplio estudio de las aplicaciones de PSO se puede encontrar en Poli.
PSO permite optimizar un problema a partir de una población de soluciones candidatas, denotadas como "partículas", moviendo éstas por todo el espacio de búsqueda según reglas matemáticas que tienen en cuenta la posición y la velocidad de las partículas. El movimiento de cada partícula se ve influido por su mejor posición local hallada hasta el momento, así como por las mejores posiciones globales encontradas por otras partículas a medida que recorren el espacio de búsqueda. El fundamento teórico de esto es hacer que la nube de partículas converja rápidamente hacia las mejores soluciones.
PSO es una metaheurística, ya que asume pocas o ninguna hipótesis sobre el problema a optimizar y puede aplicarse en grandes espacios de soluciones candidatas. Sin embargo, como toda metaheurística, PSO no garantiza la obtención de una solución óptima en todos los casos.
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: ℝn → ℝ 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 xi ∈ ℝn en el espacio de búsqueda y una velocidad vi ∈ ℝn. Sea pi 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:
Los parámetros y son definidos por un especialista y regulan el comportamiento y la eficacia del método PSO, como se expone a continuación.
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.
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 utilizando un optimizador "superpuesto", un concepto conocido como metaoptimización.
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. La topología no es necesariamente fija, puede ser adaptativa según el caso (SPSO, estrella estocástica, TRIBES, Cyber Swarm, C-PSO).
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, 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.
En el contexto de la PSO, el término "convergencia" suele emplearse con dos significados (a veces considerados erróneamente como sinónimos):
En la literatura especializada pueden encontrarse algunos intentos de analizar matemáticamente la convergencia en PSO. Estos análisis han servido para establecer pautas de selección de los parámetros que determinarían la convergencia, divergencia u oscilación de las partículas del enjambre, lo que a la postre ha propiciado nuevas variantes en la PSO. No obstante, estos análisis han sido objeto de críticas al ser considerados demasiado simplistas, toda vez que asumen que el enjambre posee una sola partícula, sin variables aleatorias, y que la mejor posición p conocida de la partícula y la mejor posición global g del enjambre permanecen constantes durante el proceso de optimización. Asimismo, ciertos análisis admiten un número infinito de iteraciones en la optimización, lo cual no es posible en un escenario real. Por tanto, el estudio de las características de convergencia de los diversos algoritmos de PSO y sus parámetros asociados está fuertemente ligado a los resultados empíricos.
A medida que el algoritmo de PSO avanza, dimensión por dimensión, el punto solución es más fácil de encontrar si se halla en un eje del espacio de búsqueda, en una diagonal o, aún más fácil, si está justo en el centro.
Una primera forma de evitar este sesgo, permitiendo hacer comparaciones más ponderadas, es por ejemplo tomar como referencia problemas no sesgados, y luego rotarlos o desplazarlos. Otra opción es modificar el propio algoritmo para hacerlo menos sensible al sistema de coordenadas.
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.
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, por ej. incorporando un método eficaz de aprendizaje. 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. 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. Asimismo, se han producido avances en la adaptación de los parámetros de comportamiento durante la optimización.
Como se apuntó anteriormente, existe una corriente de opinión que considera que la PSO debe simplificarse tanto como sea posible, mientras no afecte al rendimiento, en aplicación de la navaja de Occam. La simplificación de la PSO fue propuesta originalmente por Kennedy, y desde entonces ha sido ampliamente estudiada. Con su puesta en práctica se han observado mejoras en el rendimiento, mayor facilidad para ajustar los parámetros y un comportamiento más consistente ante distintos problemas de optimización.
Otro argumento a favor de la simplificación es que sólo puede probarse empíricamente la eficacia de una metaheurística haciendo ensayos sobre un número finito de problemas de optimización. Esto significa que una metaheurística como PSO no puede validarse, lo que aumenta el riesgo de cometer errores en su descripción e implementación. Una buena muestra de ello fue una variante prometedora de un algoritmo genético (otra popular metaheurística), que más tarde se reveló defectuosa al presentar una búsqueda de optimización fuertemente sesgada; el sesgo se debía a un error de programación, que ya ha sido corregido.
Si se desea inicializar la velocidad asociada a las partículas se requieren entradas adicionales. Una variante simple es la "optimización con enjambre de partículas aceleradas" (APSO), que permite acelerar la convergencia en muchas aplicaciones. Un sencillo código de ejemplo de APSO está disponible on-line.
La PSO también se ha aplicado a problemas multiobjetivo, en los que la evaluación de la función objetivo tiene en cuenta la "dominancia de Pareto" al mover las partículas, de manera que las soluciones no-dominadas son aproximadas al frente de Pareto.
Como las ecuaciones usadas en PSO operan con números reales, un método común a la hora de resolver problemas discretos es mapear el espacio de búsqueda a un dominio continuo, para aplicar PSO clásica, y luego desmapear el resultado. El proceso de mapeo puede consistir en una conversión muy simple (por ej. redondeo de valores) o, por el contrario, bastante compleja.
Sin embargo, las ecuaciones de movimiento hacen uso de operadores que controlan cuatro acciones:
Generalmente, la posición y la velocidad están representadas por n números reales, y los operadores básicos son -, *, +. Pero tales entidades matemáticas pueden definirse de una manera completamente diferente, a fin de hacer frente a problemas binarios (o discretos, en un sentido más amplio), e incluso combinatorios. . Una estrategia es redefinir los operadores como basados en conjuntos.