Optimisació per eixam de partícules

En informàtica, la optimisació per núvol de partícules o optimisació per eixam de partícules (coneguda per les seues sigles en anglés: PSO, de «particle swarm optimization») fa referència a una metaheurística que evoca el comportament de les partícules en la naturalea.

Els métodos PSO s'atribuïxen originalment als investigadors Kennedy, Eberhart i Shi. En un principi varen ser concebuts per a elaborar models de conductes socials, com el moviment descrit pels organismes vius en una bandada d'aus o un banc de peixos. Posteriorment l'algoritme es va simplificar i es va comprovar que era adequat per a problemes d'optimisació. El llibre de Kennedy i Eberhart descriu numerosos aspectes teòrics de la PSO i l'inteligència d'eixam. Un ampli estudi de les aplicacions de PSO es pot trobar en Poli.

PSO permet optimisar un problema a partir d'una població de soluciones candidates, denotades com "partícules", movent estes per tot l'espai de busca segons regles matemàtiques que tenen en conte la posició i la velocitat de les partícules. El moviment de cada partícula es veu influït per la seua millor posició local trobada fins al moment, aixina com per les millors posicions globals trobades per atres partícules a mida que recorren l'espai de busca. El fonament teòric d'açò és fer que el núvol de partícules convergixca ràpidament cap a les millors solucions.

PSO és una metaheurística, ya que assumix poques o cap hipòtesis sobre el problema a optimisar i pot aplicar-se en grans espais de soluciones candidates. No obstant, com tota metaheurística, PSO no garantisa l'obtenció d'una solució òptima en tots els casos.

Analogia en la naturalea

Les abellas en busca d'aliment tracten de localisar la regió de l'espai en major densitat de flors, ya que és allí a on presumiblement existix més cantitat de polen. Cada abella vola de modo errático per l'espai, recordant en tot moment quin és la regió a on ha vist més flors. A la seua volta, l'eixam sap colectivament quin és la regió de l'espai, d'entre totes les explorades, a on s'han trobat més flors. Cada abella variarà individualment el seu moviment segons estes dos direccions, volant cap a algun lloc intermig. És possible que l'abella durant eixe sobrevole trobe una regió en més densitat de flors que la coneguda fins a llavors (òptim local), o inclús que la coneguda per l'eixam (òptim global); en este últim cas, tot l'eixam orientarà la busca cap a eixa nova direcció. Passat un temps, si es descobrix una atra regió en major densitat floral, l'eixam reorientará novament la busca cap a allí, i aixina successivament.

Algoritme

Un algoritme PSO treballa en una població (cridada núvol o eixam) de solucions candidates (cridades partícules). Dites partícules es desplacen a lo llarc de l'espai de busca conforme unes simples regles matemàtiques. El moviment de cada partícula depén de la seua millor posició obtinguda, aixina com de la millor posició global trobada en tot l'espai de busca. A mida que es descobrixen noves i millors posicions, estes passen a orientar els moviments de les partícules. El procés es repetix en l'objectiu, no garantisat, de trobar en algun moment una solució lo suficientment satisfactòria.

Lo descrit anteriorment pot formalisar-se del següent modo: siga f: &x211D;ⁿ → &x211D; la funció de cost que es desija minimisar. La funció f pren com a argument una solució candidata, representada com un vector de número real, i dona com a eixida un número real que indica el valor de la funció objectiu per a la solució candidata obtinguda. Les millors posicions es corresponen en els millors valors de la funció objectiu f. L'objectiu és trobar una solució a que verifique f(a) ≤ f(b) para tot b en l'espai de busca, lo que implicaria que a és el mínim global. El procés invers, útil en problemes d'maximización, pot conseguir-se considerant una funció h = -f.

Siga S el número de partícules en el núvol, cada una de les quals té una posició x_i ∈ &x211D;ⁿ en l'espai de busca i una velocitat v_i ∈ &x211D;ⁿ. Siga p_i la millor posició coneguda d'una partícula i, i g la millor posició global coneguda. Un algoritme PSO bàsic podria descriure's com seguix:

• Per a cada partícula ___MATH_0___:
  • Inicializar la posició de la partícula per mig d'un vector aleatori uniformemente distribuït: ___MATH_1___, a on ___MATH_2___i ___MATH_3___ són respectivament el llímit inferior i el llímit superior de l'espai de busca.
  • Inicializar la millor posició coneguda de la partícula a la seua posició inicial: ___MATH_4___.
  • Si ___MATH_5___ actualisar la millor posició global coneguda: ___MATH_6___.
  • Inicializar la velocitat de la partícula: ___MATH_7___.
• Mentres no es complixca el criteri de parada (per.ej. llímit màxim de iteraciones, trobada una solució satisfactòria), repetir:
  • Per a cada partícula ___MATH_8___:
    • Per a cada dimensió ___MATH_9___:
      • Elegir números aleatoris: ___MATH_10___.
      • Actualisar la velocitat de la partícula: ___MATH_11___.
    • Actualisar la posició de la partícula: ___MATH_12____.
    • Si ___MATH_13___ llavors:
      • Actualisar la millor posició coneguda de la partícula: ___MATH_14___.
      • Si ___MATH_15___ actualisar la millor posició global: ___MATH_16___.
• Tornar ___MATH_17___ com la millor solució trobada.

Els paràmetros ___MATH_18___ i ___MATH_19___ són definits per un especialiste i regulen el comportament i l'eficàcia del método PSO, com s'expon a continuació.