Optimización de Enjambre de partículas
En ciencia computacional , la optimización de enjambre de partículas ( PSO ) [1] es un método computacional que optimiza un problema al tratar iterativamente de mejorar una solución candidata con respecto a una medida dada de calidad. Resuelve un problema al tener una población de soluciones candidatas, aquí denominadas partículas , y mover estas partículas en el espacio de búsqueda de acuerdo con una fórmula matemática simple sobre la posición y la velocidad de la partícula.. El movimiento de cada partícula está influenciado por su posición local más conocida, pero también se guía hacia las posiciones más conocidas en el espacio de búsqueda, que se actualizan a medida que otras partículas encuentran mejores posiciones. Se espera que esto mueva al enjambre hacia las mejores soluciones.
PSO se atribuye originalmente a Kennedy , Eberhart y Shi [2] [3] y se pensó primero para simular el comportamiento social , [4] como una representación estilizada del movimiento de organismos en una bandada de pájaros o bancos de peces . Se simplificó el algoritmo y se observó que estaba realizando la optimización. El libro de Kennedy y Eberhart [5] describe muchos aspectos filosóficos de la PSO y la inteligencia de enjambre . Poli . _ [6] [7]Recientemente, Bonyadi y Michalewicz han publicado una revisión exhaustiva de trabajos teóricos y experimentales sobre PSO. [1]
PSO es una metaheurística , ya que hace pocas o ninguna suposición sobre el problema que se está optimizando y puede buscar soluciones candidatas en espacios muy grandes. Además, PSO no usa el gradiente del problema que se está optimizando, lo que significa que PSO no requiere que el problema de optimización sea diferenciable como lo requieren los métodos de optimización clásicos como el descenso de gradiente y los métodos cuasi-newton . Sin embargo, las metaheurísticas como PSO no garantizan que se encuentre una solución óptima.
Una variante básica del algoritmo PSO funciona teniendo una población (llamada enjambre) de soluciones candidatas (llamadas partículas). Estas partículas se mueven en el espacio de búsqueda de acuerdo con algunas fórmulas simples. [8] Los movimientos de las partículas están guiados por su propia posición más conocida en el espacio de búsqueda, así como por la posición más conocida de todo el enjambre. Cuando se descubran posiciones mejoradas, estas vendrán a guiar los movimientos del enjambre. El proceso se repite y al hacerlo se espera, pero no se garantiza, que finalmente se descubra una solución satisfactoria.
Formalmente, sea f : ℝ n → ℝ la función de costo que debe minimizarse. La función toma una solución candidata como argumento en forma de vector de números reales y produce un número real como salida que indica el valor de la función objetivo de la solución candidata dada. No se conoce el gradiente de f . El objetivo es encontrar una solución a para la cual f ( a ) ≤ f ( b ) para todo b en el espacio de búsqueda, lo que significaría que a es el mínimo global.
Sea S el número de partículas en el enjambre, cada una con una posición x i ∈ ℝ n en el espacio de búsqueda y una velocidad v i ∈ ℝ n . Sea p i la posición mejor conocida de la partícula i y sea g la posición mejor conocida de todo el enjambre. Un algoritmo PSO básico es entonces: [9]
.JPG/440px-PSO_Meta-Fitness_Landscape_(12_benchmark_problems).JPG)
.JPG){kind=link}