Algoritme colónia d'abelles artificials

En ciències de la computacion i busca d'operacions, el algoritme colónia d'abelles artificials (CAA) és un algoritme d'optimisació basat en el comportament inteligent dels eixams d'abelles en la busca de mel, propost per Karaboga en 2005.

Algoritme

En el model CAA, la colónia consta de tres grups d'abelles: abelles amprades, abelles en espera i abelles exploradores. S'assumix que hi ha solament una abella amprada per a cada font d'aliment. En atres paraules, el número abelles amprades en la colónia és igual al número de fonts d'aliments al voltant de la colmena. Les abelles amprades van a la seua font d'aliment, tornen a la colmena i dansen en esta àrea. L'abella amprada la font de la qual d'aliments ha segut abandonada es convertix en exploradora i escomença la busca de noves fonts d'alimentació. Les abelles en espera observen les danses de les abelles amprades i trien les fonts d'aliments depenent de les danses. Els passos principals de l'algoritme són:

• Es produïxen fonts d'aliments inicials per cada abella amprada:
• REPETIR
  • Cada abella amprada va a una font d'aliment en la seua memòria i determina una font veïna, llavors evalua la seua cantitat de néctar i dansa en la colmena
  • Cada abella en espera observa el ball de cada abella amprada i tria una de les seues fonts depenent de les danses, i llavors va a eixa font. Despuix de triar un veí entorn, evalua la seua cantitat de néctar.
  • Són determinades les fonts d'aliments a abandonar i reemplaçades per les noves fonts d'aliments descobertes per les exploradores.
  • La millor font d'aliments trobada és registrada.
• HASTA QUE (els requisits es complixquen)

En l'algoritme CAA, un algoritme basat en poblacions, la posició d'una font d'aliments representa una possible solució al problema d'optimisació i la cantitat de néctar d'una font alimentària correspon a la calitat de la solució associada. El número de les abelles amprades és igual al número de solucions en la població. En el primer pas, és generada una població inicial distribuïda aleatoriamente (posicions de font d'aliments). Despuix de la inicialización, la població és encarregada de repetir els cicles dels processos de busca de les abelles amprades, en espera, i exploradores, respectivament. Una abella amprada produïx una modificació en la posició de font en la seua memòria i descobrix una posició d'una font d'aliments. Preveent que la cantitat de néctar de la nova siga major que la de la font anterior l'abella memorisa la posició de la font nova i oblida la vella, en un atre cas manté la posició de l'antiga en la seua memòria. En terminar les abelles amprades completen el procés de busca, compartixen l'informació de posició de les fonts en els espectadors en l'àrea de ball. Cada espectador evalua l'informació de néctar presa de totes les abelles amprades i llavors tria una font d'aliments depenent de les cantitats de néctar de cada font. En el cas de l'abella amprada, produïx una modificació en la posició de la font en la seua memòria i comprova la seua cantitat de néctar. Prevenint que el seu néctar serà major que el de la seua anterior font, l'abella memorisa la posició nova i oblida la vella. Les fonts abandonades queden determinades i les fonts noves són aleatoriamente produïdes per a ser reemplaçats en les abandonades per les abelles exploradores.

Algoritme colónia d'abelles artificials

L'algoritme CAA és un algoritme d'inteligència d'eixam propost per Karaboga en 2005, el qual és inspirat en el comportament d'abelles en la busca de mel. Des del seu desenroll, ha segut aplicat per a solucionar diferents classes de problemes. L'algoritme colónia d'abella artificial (CAA) és una tècnica d'optimisació recentment proposta qué simula el comportament inteligent de les abelles en la busca de la mel. Un conjunt d'abelles es denomina eixam quan poden realisar tasques a través de la cooperació social de manera exitosa. En l'algoritme CAA, hi ha tres tipos d'abelles: abelles amprades, abelles en espera, i abelles exploradores. Les abelles amprades busquen menjar al voltant de la posició de les fonts d'aliments guardades en les seues memòries; entretant compartixen l'informació d'estes fonts d'aliments en les abelles en espera. Les abelles en espera tendixen a seleccionar bones fonts d'aliments d'aquelles trobades per les abelles amprades. Les font d'aliment que té calitat més alta tindrà una possibilitat més gran de ser seleccionada per les abelles en espera que la de calitat més baixa. Les abelles exploradores es traslladen fins a una nova font determinant l'abandó de dita font per les empleades.

En l'algoritme CAA, la primera mitat de l'eixam consta d'abelles amprades, i la segona mitat constituïx les abelles en espera.

El número d'abelles amprades o d'abelles en espera és igual al número de solucions en l'eixam. El CAA genera una població inicial aleatoriamente distribuïda de SN solucions (fonts d'aliments), a on SN denota el tamany de l'eixam.

Siga X_i = { X_i,1 , X_i,2 , ..., X_i,n } representant la i-esima solució en l'eixam, A on n és el tamany de dimensió. Cada abella amprada X_i genera una nova solució candidata V_i en el veïnat de la seua posició actual com en l'equació:

$V_{i_k}=X_{i_k}+{\Phi }_{i_k}*(X_{i_k}-X_{j_k})$

A on X_j és una solució candidata seleccionada aleatoriamente $(i\ne j)$, és un índex aleatori de dimensió seleccionat del conjunt

{ 1, 2,..., n} , i ${\Phi }_{i_k}$ és un número aleatori en l'interval [-1,1].

Una volta la nova solució de candidata V_i és generada, es realisa un selecció golosa. Si el valor de V_i és millor que del seu pare X_i , llavors s'actualisa X_i en V_i; en un atre cas es manté el valor de X_i sense canvis. Despuix d'açò les abelles empeladas completen el procés de busca; compartixen l'informació de les seues fonts d'aliments en les abelles en espera a través de les danses. Una abella en espera evalua l'informació del néctar presa de totes les abelles amprades i tria una font alimentària en una provabilitat relacionada en la seua cantitat de néctar. La selecció provabilística constituïx un mecanisme de selecció de ruleta qué està descrit en la següent equació:

$P_i=\frac{fi{t}_i}{\sum _{j}fi{t}_j}$

A on $fi{t}_i$ el valor proporcionat per la i-esima solució en l'eixam. A millor solució i, més alt és la provabilitat de que la i-esima font d'aliments siga seleccionada. Si una posició no pot ser millorada sobre un predefinit número (cridat llímit) de cicles, llavors la font d'aliments és abandonada. Supondre que la font abandonada és X_i, i llavors l'abella exploradora descobrix una nova font d'aliments per a ser reemplaçat per la i-esima com es mostra en l'equació:

$X_{i_k}=l{m}_j+rand(0,1)*(l{s}_j-l{m}_j)$

A on rand(1,0) és un número aleatori entre [0,1] basat en una distribució normal i lm, ls, són les fronteres més baixes i altes de la i-esima dimensió, respectivament.

Vore també

• Computació evolutiva
• Evolutiu multi-optimisació modal
• Optimisació d'eixam de la partícula
• Inteligència d'eixam
• Algoritme d'abelles
• Peixcar Busca Escolar

Referències

D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.