Diferencia entre revisiones de «Optimización por enjambre de partículas»

De Wikipedia, la enciclopedia libre
Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Cinevoro (discusión · contribs.)
16 309 ediciones
Sin resumen de edición
Cinevoro (discusión · contribs.)
16 309 ediciones
Añadidas numerosas referencias
Línea 1: Línea 1:
En informática, la '''optimización por nube de partículas''' u '''optimización por enjambre de partículas''' (conocida por sus siglas en [[Idioma inglés|inglés]]: '''PSO''', de «''particle swarm optimization''») hace referencia a una serie de métodos y algoritmos de optimización [[Heurística|heurísticos]] que evocan el comportamiento de los [[Enjambre|enjambres de abejas]] en la naturaleza.
En informática, la '''optimización por nube de partículas''' u '''optimización por enjambre de partículas''' (conocida por sus siglas en [[Idioma inglés|inglés]]: '''PSO''', de «''particle swarm optimization''») hace referencia a una serie de métodos y algoritmos de optimización [[Heurística|heurísticos]] que evocan el comportamiento de los [[Enjambre|enjambres de abejas]] en la naturaleza.


Los métodos PSO se atribuyen originalmente a los investigadores Kennedy, Eberhart<ref name=kennedy95particle /> y Shi.<ref name=shi98modified /> En un principio fueron concebidos para elaborar modelos de conductas sociales,<ref name=kennedy97particle /> 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.
Los métodos PSO se atribuyen originalmente a los investigadores Kennedy, Eberhart<ref name=kennedy95particle /> y Shi.<ref name=shi98modified /> En un principio fueron concebidos para elaborar modelos de conductas sociales,<ref name=kennedy97particle /> 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<ref name=kennedy01swarm/> 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.<ref name=poli07analysis/><ref name=poli08analysis/>


PSO permite optimizar un problema a partir de una población de [[Espacio_de_búsqueda#Soluci.C3.B3n_candidata_y_soluci.C3.B3n_de_problema|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 permite optimizar un problema a partir de una población de [[Espacio_de_búsqueda#Soluci.C3.B3n_candidata_y_soluci.C3.B3n_de_problema|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.
Línea 38: Línea 38:
[[Archivo:PSO Meta-Fitness Landscape (12 benchmark problems).JPG|thumb|Gráfica bidimensional que muestra el rendimiento de una variante PSO ante un ''[[benchmark]]'' de problemas en función de dos parámetros.]]
[[Archivo:PSO Meta-Fitness Landscape (12 benchmark problems).JPG|thumb|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.
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..<ref name=shi98parameter/><ref name=eberhart00comparing/><ref name=carlisle01offtheshelf/><ref name=bergh01thesis/><ref name=clerc02explosion/><ref name=trelea03particle/><ref name=bratton08simplified/><ref name=evers09thesis/><ref name=massaoverview/>


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 [[Trashumancia|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 ([[Espacio_de_búsqueda#.C3.93ptimos_locales|óptimo local]]), usando pocas iteraciones.
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 [[Trashumancia|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 ([[Espacio_de_búsqueda#.C3.93ptimos_locales|óptimo local]]), usando pocas iteraciones.

En PSO, los parámetros pueden asimismo ajustarse para diversos escenarios de optimización<ref name=massaoverview/><ref name=pedersen10good-pso/><ref name=zhan09adaptive/> utilizando un optimizador "superpuesto", un concepto conocido como [[meta-optimización]].<ref name=meissner06optimized/><ref name=pedersen08thesis/><ref name=pedersen08simplifying/>


==Topologías==
==Topologías==
La PSO básica suele incurrir fácilmente en [[Espacio_de_búsqueda#.C3.93ptimos_locales|ó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.
La PSO básica suele incurrir fácilmente en [[Espacio_de_búsqueda#.C3.93ptimos_locales|ó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 [[Espacio_de_búsqueda#Topolog.C3.ADa|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).
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 [[Espacio_de_búsqueda#Topolog.C3.ADa|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.<ref>Mendes, R. (2004). Population Topologies and Their Influence in Particle Swarm Performance (PhD thesis). Universidade do Minho.</ref> La topología no es necesariamente fija, puede ser adaptativa según el caso (SPSO,<ref>SPSO, [http://www.particleswarm.info Particle Swarm Central]</ref> estrella estocástica,<ref>Miranda, V., Keko, H. and Duque, Á. J. (2008). Stochastic Star Communication Topology in Evolutionary Particle Swarms (EPSO). International Journal of Computational Intelligence Research (IJCIR), Volume 4, Number 2, pp. 105-116</ref> TRIBES,<ref>Clerc, M. (2006). Particle Swarm Optimization. ISTE (International Scientific and Technical Encyclopedia), 2006</ref> Cyber Swarm,<ref>Yin, P., Glover, F., Laguna, M., & Zhu, J. (2011). A Complementary Cyber Swarm Algorithm. International Journal of Swarm Intelligence Research (IJSIR), 2(2), 22-41</ref> C-PSO<ref name=elshamy07sis/>).


==Funcionamiento interno==
==Funcionamiento interno==
Hay diversas interpretaciones en cuanto a cómo y por qué un algoritmo de PSO es capaz de optimizar variables.
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 [[#Variantes|más adelante]].
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,<ref name=shi98modified/><ref name=kennedy97particle/><ref name=shi98parameter/><ref name=clerc02explosion/> 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 [[#Variantes|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 [[#Simplificaciones|en un apartado posterior]].
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 [[#Simplificaciones|en un apartado posterior]].
Línea 59: Línea 61:
* Convergencia puede referirse a una concentración del enjambre, donde todas las partículas confluyen hacia un punto del espacio de búsqueda, que puede o no ser el óptimo.
* Convergencia puede referirse a una concentración del enjambre, donde todas las partículas confluyen hacia un punto del espacio de búsqueda, que puede o no ser el óptimo.


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.
En la literatura especializada pueden encontrarse algunos intentos de analizar matemáticamente la convergencia en PSO.<ref name=bergh01thesis/><ref name=clerc02explosion/><ref name=trelea03particle/> 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,<ref name=pedersen08simplifying/> 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.


===Sesgos===
===Sesgos===
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, aun más fácil, si está justo en el centro.
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, aun más fácil, si está justo en el centro.<ref>Monson, C. K. & Seppi, K. D. (2005). Exposing Origin-Seeking Bias in PSO GECCO'05, pp. 241-248</ref><ref>Spears, W. M., Green, D. T. & Spears, D. F. (2010). Biases in Particle Swarm Optimization. International Journal of Swarm Intelligence Research, Vol. 1(2), pp. 34-57</ref>


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.
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.<ref>Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K.; Chen, Y. P., Auger, A. & Tiwari, S. (2005). Problem definitions and evaluation criteria for the CEC 2005 Special Session on Real Parameter Optimization. Nanyang Technological University</ref> Otra opción es modificar el propio algoritmo para hacerlo menos sensible al sistema de coordenadas.<ref>Wilke, D. N., Kok, S. & Groenwold, A. A. (2007). Comparison of linear and classical velocity update rules in particle swarm optimization: notes on scale and frame invariance. International Journal for Numerical Methods in Engineering, John Wiley & Sons, Ltd., 70, pp. 985-1008</ref><ref>SPSO 2011, [http://www.particleswarm.info Particle Swarm Central]</ref>


==Variantes==
==Variantes==
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.
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.<ref name=carlisle01offtheshelf/>


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]]. Por último, se han registrado avances en la adaptación de los parámetros de comportamiento durante la optimización.
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,<ref name=lovbjerg02lifecycle/><ref name=niknam10efficient/> por ej. incorporando un método eficaz de aprendizaje.<ref name=zhan10OLPSO/> 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.<ref name=evers09thesis/><ref name=lovbjerg02extending/><ref name=xinchao10perturbed/> 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]].<ref name=nobile2012 /> Asimismo, se han producido avances en la adaptación de los parámetros de comportamiento durante la optimización.<ref name=zhan09adaptive/>


===Simplificaciones===
===Simplificaciones===
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.
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,<ref name=kennedy97particle/> y desde entonces ha sido ampliamente estudiada.<ref name=bratton08simplified/><ref name=pedersen08thesis/><ref name=pedersen08simplifying/><ref name=yang08nature/> 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.
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<ref name=tu04robust/> 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.<ref name=tu04corrections/>


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''. <ref>{{cita web|autor=Xin-She Yang|título=Accelerated Particle Swarm Optimization|url=http://www.mathworks.com/matlabcentral/fileexchange/?term=APSO}}</ref>
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),<ref>X. S. Yang, S. Deb and S. Fong, Accelerated particle swarm optimization and support vector machine for business optimization and applications, NDT 2011, Springer CCIS 136, pp. 53-66 (2011).</ref> que permite acelerar la convergencia en muchas aplicaciones. Un sencillo código de ejemplo de APSO está disponible ''on-line''. <ref>{{cita web|autor=Xin-She Yang|título=Accelerated Particle Swarm Optimization|url=http://www.mathworks.com/matlabcentral/fileexchange/?term=APSO}}</ref>


===Optimización multiobjetivo===
===Optimización multiobjetivo===
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 "[[Eficiencia_de_Pareto#Formalizaci.C3.B3n|dominancia de Pareto]]" al mover las partículas, de manera que las soluciones no-dominadas son aproximadas al frente de Pareto.
La PSO también se ha aplicado a problemas multiobjetivo,<ref name=parsopoulos02particle/><ref name=coellocoello02MOPSO/> en los que la evaluación de la función objetivo tiene en cuenta la "[[Eficiencia_de_Pareto#Formalizaci.C3.B3n|dominancia de Pareto]]" al mover las partículas, de manera que las soluciones no-dominadas son aproximadas al frente de Pareto.


===PSO binaria, discreta y combinatoria===
===PSO binaria, discreta y combinatoria===
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.
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.<ref>Roy, R., Dehuri, S., & Cho, S. B. (2012). A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem. 'International Journal of Applied Metaheuristic Computing (IJAMC)', 2(4), 41-57</ref>


Sin embargo, las ecuaciones de movimiento hacen uso de operadores que controlan cuatro acciones:
Sin embargo, las ecuaciones de movimiento hacen uso de operadores que controlan cuatro acciones:
Línea 90: Línea 92:
* aplicar una velocidad a una posición
* aplicar una velocidad a una posición


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 basados en conjuntos.
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.<ref>Kennedy, J. & Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm, Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109</ref>
<ref>Clerc, M. (2004). Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem, New Optimization Techniques in Engineering, Springer, pp. 219-239</ref>
<ref>Clerc, M. (2005). Binary Particle Swarm Optimisers: toolbox, derivations, and mathematical insights, [http://hal.archives-ouvertes.fr/hal-00122809/en/ Open Archive HAL]</ref>
.<ref>Jarboui, B., Damak, N., Siarry, P., and Rebai, A.R. (2008). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. In Proceedings of Applied Mathematics and Computation, pp. 299-308.</ref> Una estrategia es redefinir los operadores como basados en conjuntos.<ref name=Chen10SPSO />


==Referencias==
==Referencias==
{{listaref|2|refs=
{{listaref|2|refs=

<ref name=kennedy95particle>
<ref name=kennedy95particle>
{{Cita conferencia
{{Cita conferencia
Línea 106: Línea 112:
|doi=10.1109/ICNN.1995.488968
|doi=10.1109/ICNN.1995.488968
|url=http://www.engr.iupui.edu/~shi/Coference/psopap4.html
|url=http://www.engr.iupui.edu/~shi/Coference/psopap4.html
}}
</ref>

<ref name=kennedy97particle>
{{Cita conferencia
|apellido=Kennedy
|nombre=J.
|título=The particle swarm: social adaptation of knowledge
|títulolibro=Proceedings of IEEE International Conference on Evolutionary Computation
|año=1997
|páginas=303–308
}}
}}
</ref>
</ref>
Línea 121: Línea 138:
</ref>
</ref>


<ref name=kennedy97particle>
<ref name=shi98parameter>
{{Cita conferencia
{{Cita conferencia
|apellido=Shi
|nombre=Y.
|apellidos2=Eberhart
|nombre2=R.C.
|título=Parameter selection in particle swarm optimization
|títulolibro=Proceedings of Evolutionary Programming VII (EP98)
|año=1998
|páginas=591–600
}}
</ref>

<ref name=lovbjerg02lifecycle>
{{Cita conferencia
|apellido=Lovbjerg
|nombre=M.
|apellidos2=Krink
|nombre2=T.
|título=The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers
|títulolibro=Proceedings of Parallel Problem Solving from Nature VII (PPSN)
|año=2002
|páginas=621–630
}}
</ref>

<ref name=niknam10efficient>
{{cita publicación
|apellido=Niknam
|nombre=T.
|apellidos2=Amiri
|nombre2=B.
|título=An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis
|publicación=Applied Soft Computing
|año=2010
|volumen=10
|número=1
|páginas=183–197
|doi=10.1016/j.asoc.2009.07.001
}}
</ref>

<ref name=massaoverview>
{{cita publicación
|apellido=Rocca
|nombre=P.
|apellidos2=Benedetti
|nombre2=M.
|apellidos3=Donelli
|nombre3=M.
|apellidos4=Franceschini
|nombre4=D.
|apellidos5=Massa
|nombre5=A.
|título=Evolutionary optimization as applied to inverse scattering problems
|publicación=Inverse Problems
|año=2009
|volumen=25
|páginas=1–41
|doi=10.1088/0266-5611/25/12/123003
}}
</ref>

<ref name=lovbjerg02extending>
{{Cita conferencia
|apellido=Lovbjerg
|nombre=M.
|apellidos2=Krink
|nombre2=T.
|título=Extending Particle Swarm Optimisers with Self-Organized Criticality
|títulolibro=Proceedings of the Fourth Congress on Evolutionary Computation (CEC)
|año=2002
|volumen=2
|páginas=1588–1593
}}
</ref>

<ref name=xinchao10perturbed>
{{cita publicación
|apellidos=Xinchao
|nombre=Z.
|título=A perturbed particle swarm algorithm for numerical optimization
|publicación=Applied Soft Computing
|año=2010
|volumen=10
|número=1
|páginas=119–124
|doi=10.1016/j.asoc.2009.06.010
}}
</ref>

<ref name=zhan09adaptive>
{{cita publicación
|apellido=Zhan
|nombre=Z-H.
|apellidos2=Zhang
|nombre2=J.
|apellidos3=Li
|nombre3=Y
|apellidos4=Chung
|nombre4=H.S-H.
|título=Adaptive Particle Swarm Optimization
|publicación=IEEE Transactions on Systems, Man, and Cybernetics
|año=2009
|volumen=39
|número=6
|páginas=1362–1381
|doi=10.1109/TSMCB.2009.2015956
|url=http://userweb.eng.gla.ac.uk/yun.li/ga_demo/
}}
</ref>

<ref name=zhan10OLPSO>
{{cita publicación
|apellido=Zhan
|nombre=Z-H.
|apellidos2=Zhang
|nombre2=J.
|apellidos3=Li
|nombre3=Y
|apellidos4=Shi
|nombre4=Y-H.
|título=Orthogonal Learning Particle Swarm Optimization
|publicación=IEEE Transactions on Evolutionary Computation
|año=2011
|volumen=15
|número=6
|páginas=832–847
|doi=10.1109/TEVC.2010.2052054
|url=http://eprints.gla.ac.uk/44801/1/44801.pdf
}}
</ref>

<ref name=eberhart00comparing>
{{Cita conferencia
|apellido=Eberhart
|nombre=R.C.
|apellidos2=Shi
|nombre2=Y.
|título=Comparing inertia weights and constriction factors in particle swarm optimization
|títulolibro=Proceedings of the Congress on Evolutionary Computation
|año=2000
|volumen=1
|páginas=84–88
}}
</ref>

<ref name=carlisle01offtheshelf>
{{Cita conferencia
|apellido=Carlisle
|nombre=A.
|apellidos2=Dozier
|nombre2=G.
|título=An Off-The-Shelf PSO
|títulolibro=Proceedings of the Particle Swarm Optimization Workshop
|año=2001
|páginas=1–6
}}
</ref>

<ref name=bergh01thesis>
{{cita libro
|format=PhD thesis
|título=An Analysis of Particle Swarm Optimizers
|apellidos=van den Bergh
|nombre=F.
|año=2001
|editor=University of Pretoria, Faculty of Natural and Agricultural Science
}}
</ref>

<ref name=trelea03particle>
{{cita publicación
|apellidos=Trelea
|nombre=I.C.
|título=The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection
|publicación=Information Processing Letters
|año=2003
|volumen=85
|páginas=317–325
|doi=10.1016/S0020-0190(02)00447-7
|número=6
}}
</ref>

<ref name=clerc02explosion>
{{cita publicación
|apellido=Clerc
|nombre=M.
|apellidos2=Kennedy
|nombre2=J.
|título=The particle swarm - explosion, stability, and convergence in a multidimensional complex space
|publicación=IEEE Transactions on Evolutionary Computation
|año=2002
|volumen=6
|número=1
|páginas=58–73
|doi=10.1109/4235.985692
}}
</ref>

<ref name=bratton08simplified>
{{cita publicación
|apellido=Bratton
|nombre=D.
|apellidos2=Blackwell
|nombre2=T.
|título=A Simplified Recombinant PSO
|publicación=Journal of Artificial Evolution and Applications
|año=2008
}}
</ref>

<ref name=kennedy01swarm>
{{cita libro
|título=Swarm Intelligence
|apellido=Kennedy
|apellido=Kennedy
|nombre=J.
|nombre=J.
|apellidos2=Eberhart
|título=The particle swarm: social adaptation of knowledge
|nombre2=R.C.
|títulolibro=Proceedings of IEEE International Conference on Evolutionary Computation
|año=1997
|año=2001
|editor=Morgan Kaufmann
|páginas=303–308
|isbn=1-55860-595-9
}}
</ref>

<ref name=pedersen08thesis>
{{cita libro
|format=PhD thesis
|título=Tuning & Simplifying Heuristical Optimization
|url=http://www.hvass-labs.org/people/magnus/thesis/pedersen08thesis.pdf
|apellidos=Pedersen
|nombre=M.E.H.
|año=2010
|editor=University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group
}}
</ref>

<ref name=pedersen08simplifying>
{{cita publicación
|apellidos=Pedersen
|nombre=M.E.H.
|coautor=Chipperfield, A.J.
|url=http://www.hvass-labs.org/people/magnus/publications/pedersen08simplifying.pdf
|título=Simplifying particle swarm optimization
|publicación=Applied Soft Computing
|año=2010
|volumen=10
|páginas=618–628
|doi=10.1016/j.asoc.2009.08.029
|número=2
}}
</ref>

<ref name=pedersen10good-pso>
{{cita publicación
|apellidos=Pedersen
|nombre=M.E.H.
|url=http://www.hvass-labs.org/people/magnus/publications/pedersen10good-pso.pdf
|título=Good parameters for particle swarm optimization
|publicación=Technical Report HL1001
|editor=Hvass Laboratories
|año=2010
}}
</ref>

<ref name=poli07analysis>
{{cita publicación
|apellidos=Poli
|nombre=R.
|url=http://cswww.essex.ac.uk/technical-reports/2007/tr-csm469.pdf
|título=An analysis of publications on particle swarm optimisation applications
|publicación=Technical Report CSM-469
|editor=Department of Computer Science, University of Essex, UK
|año=2007
}}
</ref>

<ref name=poli08analysis>
{{cita publicación
|apellidos=Poli
|nombre=R.
|url=http://downloads.hindawi.com/archive/2008/685175.pdf
|título=Analysis of the publications on the applications of particle swarm optimisation
|publicación=Journal of Artificial Evolution and Applications
|año=2008
|páginas=1–10
|doi=10.1155/2008/685175
|volumen=2008
}}
</ref>

<ref name=evers09thesis>
{{cita libro
|format=Master's thesis
|título=An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization
|url=http://www.georgeevers.org/publications.htm
|apellidos=Evers
|nombre=G.
|año=2009
|editor=The University of Texas - Pan American, Department of Electrical Engineering
}}
</ref>

<ref name=tu04robust>
{{cita publicación
|apellido=Tu
|nombre=Z.
|apellidos2=Lu
|nombre2=Y.
|título=A robust stochastic genetic algorithm (StGA) for global numerical optimization
|publicación=IEEE Transactions on Evolutionary Computation
|año=2004
|volumen=8
|número=5
|páginas=456–470
|doi=10.1109/TEVC.2004.831258
}}
</ref>

<ref name=tu04corrections>
{{cita publicación
|apellido=Tu
|nombre=Z.
|apellidos2=Lu
|nombre2=Y.
|título=Corrections to "A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization''
|publicación=IEEE Transactions on Evolutionary Computation
|año=2008
|volumen=12
|número=6
|páginas=781–781
|doi=10.1109/TEVC.2008.926734
}}
</ref>

<ref name=meissner06optimized>
{{cita publicación
|apellido=Meissner
|nombre=M.
|apellidos2=Schmuker
|nombre2=M.
|apellidos3=Schneider
|nombre3=G.
|título=Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training
|publicación=BMC Bioinformatics
|año=2006
|volumen=7
|pmc=1464136
|pmid=16529661
|doi=10.1186/1471-2105-7-125
|páginas=125
}}
</ref>

<ref name=yang08nature>
{{cita libro
|título=Nature-Inspired Metaheuristic Algorithms
|apellido=Yang
|nombre=X.S.
|año=2008
|editor=Luniver Press
|isbn=978-1-905986-10-1
}}
</ref>

<ref name=parsopoulos02particle>
{{Cita conferencia
|apellido=Parsopoulos
|nombre=K.
|apellidos2=Vrahatis
|nombre2=M.
|título=Particle swarm optimization method in multiobjective problems
|títulolibro=Proceedings of the ACM Symposium on Applied Computing (SAC)
|año=2002
|páginas=603–607
|url=http://doi.acm.org/10.1145/508791.508907
}}
</ref>

<ref name=coellocoello02MOPSO>
{{Cita conferencia
|apellido=Coello Coello
|nombre=C.
|apellidos2=Salazar Lechuga
|nombre2=M.
|título=MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization
|títulolibro=Congress on Evolutionary Computation (CEC'2002)
|año=2002
|páginas=1051–1056
|url=http://portal.acm.org/citation.cfm?id=1252327
}}
</ref>

<ref name=Chen10SPSO>
{{cita publicación
|apellido=Chen
|nombre=Wei-neng
|apellidos2=Zhang
|nombre2=Jun
|título=A novel set-based particle swarm optimization method for discrete optimization problem
|publicación=IEEE Transactions on Evolutionary Computation
|año=2010
|volumen=14
|páginas=278–300
|número=2
}}
</ref>

<ref name=elshamy07sis>
{{Cita conferencia
|apellido=Elshamy |nombre=W.
|apellidos2=Rashad |nombre2=H.
|apellidos3=Bahgat |nombre3=A.
|título=Clubs-based Particle Swarm Optimization
|títulolibro=IEEE Swarm Intelligence Symposium 2007 (SIS2007)
|ubicación=Honolulu, HI
|año=2007
|páginas=289–296
|url=http://people.cis.ksu.edu/~welshamy/pubs/ieee_sis07.pdf
}}
</ref>

<ref name=nobile2012>
{{Cita conferencia
|apellido=Nobile |nombre=M.
|apellidos2=Besozzi |nombre2=D.
|apellidos3=Cazzaniga |nombre3=P.
|apellidos4=Mauri |nombre4=G.
|apellidos5=Pescini |nombre5=D.
|título= A GPU-Based Multi-Swarm PSO Method for Parameter Estimation in Stochastic Biological Systems Exploiting Discrete-Time Target Series
|títulolibro=Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Lecture Notes in Computer Science.
|año=2012
|páginas=74–85
|volumen=7264
|url=http://link.springer.com/chapter/10.1007%2F978-3-642-29066-4_7
}}
}}
</ref>
</ref>

Revisión del 10:27 29 ago 2013

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 serie de métodos y algoritmos de optimización heurísticos que evocan el comportamiento de los enjambres de abejas en la naturaleza.

Los métodos PSO se atribuyen originalmente a los investigadores Kennedy, Eberhart[1]​ y Shi.[2]​ En un principio fueron concebidos para elaborar modelos de conductas sociales,[3]​ 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[4]​ 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.[5]​[6]​

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 optimal en todos los casos.

Analogía con la naturaleza

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.

Algoritmo

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 a ciertas 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:

  • Para cada partícula i = 1, ..., S:
    • Inicializar la posición de la partícula mediante un vector aleatorio uniformemente distribuido: xi ~ U(blo, bup), donde blo y bup 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: pi ← xi
    • Si (f(pi) < f(g)) actualizar la mejor posición global conocida: g ← pi
    • Inicializar la velocidad de la partícula: vi ~ U(-|bup-blo|, |bup-blo|)
  • Mientras no se cumpla el criterio de parada (p.ej. límite máximo de iteraciones, encontrada una solución satisfactoria), repetir:
    • Para cada partícula i = 1, ..., S:
      • Para cada dimensión d = 1, ..., n:
        • Elegir números aleatorios: rp, rg ~ U(0,1)
        • Actualizar la velocidad de la partícula: vi,d ← ω vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
      • Actualizar la posición de la partícula: xi ← xi + vi
      • Si (f(xi) < f(pi)) entonces:
        • Actualizar la mejor posición conocida de la partícula: pi ← xi
        • Si (f(pi) < f(g)) actualizar la mejor posición global: g ← pi
  • Devolver g como la mejor solución encontrada.

Los parámetros ω, φp y φg son definidos por un especialista y regulan el comportamiento y la eficacia del método PSO, como se expone a continuación.

Selección de parámetros

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 meta-optimización.[18]​[19]​[20]​

Topologías

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]​).

Funcionamiento interno

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.

Convergencia

En el contexto de la PSO, el término "convergencia" suele emplearse con dos significados (a veces considerados erróneamente como sinónimos):

  • Convergencia puede referirse a la mejor posición global g conocida, que se aproxima (converge) al óptimo del problema, independientemente de cómo se comporte el enjambre.
  • Convergencia puede referirse a una concentración del enjambre, donde todas las partículas confluyen hacia un punto del espacio de búsqueda, que puede o no ser el óptimo.

En la literatura especializada pueden encontrarse algunos intentos de analizar matemáticamente la convergencia en PSO.[10]​[11]​[12]​ 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,[20]​ 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.

Sesgos

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, aun más fácil, si está justo en el centro.[27]​[28]​

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.[29]​ Otra opción es modificar el propio algoritmo para hacerlo menos sensible al sistema de coordenadas.[30]​[31]​

Variantes

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]​

Simplificaciones

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,[3]​ y desde entonces ha sido ampliamente estudiada.[13]​[19]​[20]​[38]​ 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[39]​ 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.[40]​

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),[41]​ que permite acelerar la convergencia en muchas aplicaciones. Un sencillo código de ejemplo de APSO está disponible on-line. [42]​

Optimización multiobjetivo

La PSO también se ha aplicado a problemas multiobjetivo,[43]​[44]​ 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.

PSO binaria, discreta y combinatoria

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.[45]​

Sin embargo, las ecuaciones de movimiento hacen uso de operadores que controlan cuatro acciones:

  • calcular la diferencia entre dos posiciones (el resultado define un desplazamiento)
  • multiplicar una velocidad por un coeficiente numérico
  • sumar dos velocidades
  • aplicar una velocidad a una posición

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.[46]​ [47]​ [48]​ .[49]​ Una estrategia es redefinir los operadores como basados en conjuntos.[50]​

Referencias

  1. ↑ Kennedy, J.; Eberhart, R. (1995). «Particle Swarm Optimization». Proceedings of IEEE International Conference on Neural Networks IV. pp. 1942-1948. doi:10.1109/ICNN.1995.488968. 
  2. ↑ a b Shi, Y.; Eberhart, R. (1998). «A modified particle swarm optimizer». Proceedings of IEEE International Conference on Evolutionary Computation. pp. 69-73. 
  3. ↑ a b c Kennedy, J. (1997). «The particle swarm: social adaptation of knowledge». Proceedings of IEEE International Conference on Evolutionary Computation. pp. 303-308. 
  4. ↑ Kennedy, J.; Eberhart, R.C. (2001). Morgan Kaufmann, ed. Swarm Intelligence. ISBN 1-55860-595-9. 
  5. ↑ Poli, R. (2007). «An analysis of publications on particle swarm optimisation applications». En Department of Computer Science, University of Essex, UK, ed. Technical Report CSM-469. 
  6. ↑ Poli, R. (2008). «Analysis of the publications on the applications of particle swarm optimisation». Journal of Artificial Evolution and Applications 2008: 1-10. doi:10.1155/2008/685175. 
  7. ↑ a b Shi, Y.; Eberhart, R.C. (1998). «Parameter selection in particle swarm optimization». Proceedings of Evolutionary Programming VII (EP98). pp. 591-600. 
  8. ↑ Eberhart, R.C.; Shi, Y. (2000). «Comparing inertia weights and constriction factors in particle swarm optimization». Proceedings of the Congress on Evolutionary Computation 1. pp. 84-88. 
  9. ↑ a b Carlisle, A.; Dozier, G. (2001). «An Off-The-Shelf PSO». Proceedings of the Particle Swarm Optimization Workshop. pp. 1-6. 
  10. ↑ a b van den Bergh, F. (2001). University of Pretoria, Faculty of Natural and Agricultural Science, ed. An Analysis of Particle Swarm Optimizers (PhD thesis). 
  11. ↑ a b c Clerc, M.; Kennedy, J. (2002). «The particle swarm - explosion, stability, and convergence in a multidimensional complex space». IEEE Transactions on Evolutionary Computation 6 (1): 58-73. doi:10.1109/4235.985692. 
  12. ↑ a b Trelea, I.C. (2003). «The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection». Information Processing Letters 85 (6): 317-325. doi:10.1016/S0020-0190(02)00447-7. 
  13. ↑ a b Bratton, D.; Blackwell, T. (2008). «A Simplified Recombinant PSO». Journal of Artificial Evolution and Applications. 
  14. ↑ a b Evers, G. (2009). The University of Texas - Pan American, Department of Electrical Engineering, ed. An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization (Master's thesis). 
  15. ↑ a b Rocca, P.; Benedetti, M.; Donelli, M.; Franceschini, D.; Massa, A. (2009). «Evolutionary optimization as applied to inverse scattering problems». Inverse Problems 25: 1-41. doi:10.1088/0266-5611/25/12/123003. 
  16. ↑ Pedersen, M.E.H. (2010). «Good parameters for particle swarm optimization». En Hvass Laboratories, ed. Technical Report HL1001. 
  17. ↑ a b Zhan, Z-H.; Zhang, J.; Li, Y; Chung, H.S-H. (2009). «Adaptive Particle Swarm Optimization». IEEE Transactions on Systems, Man, and Cybernetics 39 (6): 1362-1381. doi:10.1109/TSMCB.2009.2015956. 
  18. ↑ Meissner, M.; Schmuker, M.; Schneider, G. (2006). «Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training». BMC Bioinformatics 7: 125. PMC 1464136. PMID 16529661. doi:10.1186/1471-2105-7-125. 
  19. ↑ a b Pedersen, M.E.H. (2010). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, ed. Tuning & Simplifying Heuristical Optimization (PhD thesis). 
  20. ↑ a b c Pedersen, M.E.H.; Chipperfield, A.J. (2010). «Simplifying particle swarm optimization». Applied Soft Computing 10 (2): 618-628. doi:10.1016/j.asoc.2009.08.029. 
  21. ↑ Mendes, R. (2004). Population Topologies and Their Influence in Particle Swarm Performance (PhD thesis). Universidade do Minho.
  22. ↑ SPSO, Particle Swarm Central
  23. ↑ Miranda, V., Keko, H. and Duque, Á. J. (2008). Stochastic Star Communication Topology in Evolutionary Particle Swarms (EPSO). International Journal of Computational Intelligence Research (IJCIR), Volume 4, Number 2, pp. 105-116
  24. ↑ Clerc, M. (2006). Particle Swarm Optimization. ISTE (International Scientific and Technical Encyclopedia), 2006
  25. ↑ Yin, P., Glover, F., Laguna, M., & Zhu, J. (2011). A Complementary Cyber Swarm Algorithm. International Journal of Swarm Intelligence Research (IJSIR), 2(2), 22-41
  26. ↑ Elshamy, W.; Rashad, H.; Bahgat, A. (2007). «Clubs-based Particle Swarm Optimization». IEEE Swarm Intelligence Symposium 2007 (SIS2007). Honolulu, HI. pp. 289-296. 
  27. ↑ Monson, C. K. & Seppi, K. D. (2005). Exposing Origin-Seeking Bias in PSO GECCO'05, pp. 241-248
  28. ↑ Spears, W. M., Green, D. T. & Spears, D. F. (2010). Biases in Particle Swarm Optimization. International Journal of Swarm Intelligence Research, Vol. 1(2), pp. 34-57
  29. ↑ Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K.; Chen, Y. P., Auger, A. & Tiwari, S. (2005). Problem definitions and evaluation criteria for the CEC 2005 Special Session on Real Parameter Optimization. Nanyang Technological University
  30. ↑ Wilke, D. N., Kok, S. & Groenwold, A. A. (2007). Comparison of linear and classical velocity update rules in particle swarm optimization: notes on scale and frame invariance. International Journal for Numerical Methods in Engineering, John Wiley & Sons, Ltd., 70, pp. 985-1008
  31. ↑ SPSO 2011, Particle Swarm Central
  32. ↑ Lovbjerg, M.; Krink, T. (2002). «The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers». Proceedings of Parallel Problem Solving from Nature VII (PPSN). pp. 621-630. 
  33. ↑ Niknam, T.; Amiri, B. (2010). «An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis». Applied Soft Computing 10 (1): 183-197. doi:10.1016/j.asoc.2009.07.001. 
  34. ↑ Zhan, Z-H.; Zhang, J.; Li, Y; Shi, Y-H. (2011). «Orthogonal Learning Particle Swarm Optimization». IEEE Transactions on Evolutionary Computation 15 (6): 832-847. doi:10.1109/TEVC.2010.2052054. 
  35. ↑ Lovbjerg, M.; Krink, T. (2002). «Extending Particle Swarm Optimisers with Self-Organized Criticality». Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2. pp. 1588-1593. 
  36. ↑ Xinchao, Z. (2010). «A perturbed particle swarm algorithm for numerical optimization». Applied Soft Computing 10 (1): 119-124. doi:10.1016/j.asoc.2009.06.010. 
  37. ↑ Nobile, M.; Besozzi, D.; Cazzaniga, P.; Mauri, G.; Pescini, D. (2012). «A GPU-Based Multi-Swarm PSO Method for Parameter Estimation in Stochastic Biological Systems Exploiting Discrete-Time Target Series». Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Lecture Notes in Computer Science. 7264. pp. 74-85. 
  38. ↑ Yang, X.S. (2008). Luniver Press, ed. Nature-Inspired Metaheuristic Algorithms. ISBN 978-1-905986-10-1. 
  39. ↑ Tu, Z.; Lu, Y. (2004). «A robust stochastic genetic algorithm (StGA) for global numerical optimization». IEEE Transactions on Evolutionary Computation 8 (5): 456-470. doi:10.1109/TEVC.2004.831258. 
  40. ↑ Tu, Z.; Lu, Y. (2008). «Corrections to "A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization». IEEE Transactions on Evolutionary Computation 12 (6): 781-781. doi:10.1109/TEVC.2008.926734. 
  41. ↑ X. S. Yang, S. Deb and S. Fong, Accelerated particle swarm optimization and support vector machine for business optimization and applications, NDT 2011, Springer CCIS 136, pp. 53-66 (2011).
  42. ↑ Xin-She Yang. «Accelerated Particle Swarm Optimization». 
  43. ↑ Parsopoulos, K.; Vrahatis, M. (2002). «Particle swarm optimization method in multiobjective problems». Proceedings of the ACM Symposium on Applied Computing (SAC). pp. 603-607. 
  44. ↑ Coello Coello, C.; Salazar Lechuga, M. (2002). «MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization». Congress on Evolutionary Computation (CEC'2002). pp. 1051-1056. 
  45. ↑ Roy, R., Dehuri, S., & Cho, S. B. (2012). A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem. 'International Journal of Applied Metaheuristic Computing (IJAMC)', 2(4), 41-57
  46. ↑ Kennedy, J. & Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm, Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109
  47. ↑ Clerc, M. (2004). Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem, New Optimization Techniques in Engineering, Springer, pp. 219-239
  48. ↑ Clerc, M. (2005). Binary Particle Swarm Optimisers: toolbox, derivations, and mathematical insights, Open Archive HAL
  49. ↑ Jarboui, B., Damak, N., Siarry, P., and Rebai, A.R. (2008). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. In Proceedings of Applied Mathematics and Computation, pp. 299-308.
  50. ↑ Chen, Wei-neng; Zhang, Jun (2010). «A novel set-based particle swarm optimization method for discrete optimization problem». IEEE Transactions on Evolutionary Computation 14 (2): 278-300. 

Véase también

Obtenido de «https://es.wikipedia.org/w/index.php?title=Optimización_por_enjambre_de_partículas&oldid=69303946»