Algoritmo colonia de abejas artificiales

En ciencias de la computacion y búsqueda de operaciones, el algoritmo colonia de abejas artificiales (CAA) es un algoritmo de optimización basado en el comportamiento inteligente de los enjambres de abejas en la búsqueda de miel, propuesto por Karaboga en 2005.

En el modelo CAA, la colonia consta de tres grupos de abejas: abejas empleadas, abejas en espera y abejas exploradoras. Se asume que hay solo una abeja empleada para cada fuente de alimento. En otras palabras, el número abejas empleadas en la colonia es igual al número de fuentes de alimentos alrededor de la colmena. Las abejas empleadas van a su fuente de alimento, vuelven a la colmena y danzan en esta área. La abeja empleada cuya fuente de alimentos ha sido abandonada se convierte en exploradora y empieza la búsqueda de nuevas fuentes de alimentación. Las abejas en espera observan las danzas de las abejas empleadas y escogen las fuentes de alimentos dependiendo de las danzas. Los pasos principales del algoritmo son:

En el algoritmo CAA, un algoritmo basado en poblaciones, la posición de una fuente de alimentos representa una posible solución al problema de optimización y la cantidad de néctar de una fuente alimentaria corresponde a la calidad de la solución asociada. El número de las abejas empleadas es igual al número de soluciones en la población. En el primer paso, es generada una población inicial distribuida aleatoriamente (posiciones de fuente de alimentos). Después de la inicialización, la población es encargada de repetir los ciclos de los procesos de búsqueda de las abejas empleadas, en espera, y exploradoras, respectivamente. Una abeja empleada produce una modificación en la posición de fuente en su memoria y descubre una posición de una fuente de alimentos. Previendo que la cantidad de néctar de la nueva sea mayor que la de la fuente anterior la abeja memoriza la posición de la fuente nueva y olvida la vieja, en otro caso mantiene la posición de la antigua en su memoria. Al terminar las abejas empleadas completan el proceso de búsqueda, comparten la información de posición de las fuentes con los espectadores en el área de baile. Cada espectador evalúa la información de néctar tomada de todas las abejas empleadas y entonces escoge una fuente de alimentos dependiendo de las cantidades de néctar de cada fuente. En el caso de la abeja empleada, produce una modificación en la posición de la fuente en su memoria y comprueba su cantidad de néctar. Previniendo que su néctar será mayor que el de su anterior fuente, la abeja memoriza la posición nueva y olvida la vieja. Las fuentes abandonadas quedan determinadas y las fuentes nuevas son aleatoriamente producidas para ser reemplazados con las abandonadas por las abejas exploradoras.

El algoritmo CAA es un algoritmo de inteligencia de enjambre propuesto por Karaboga en 2005, el cual es inspirado en el comportamiento de abejas en la búsqueda de miel. Desde su desarrollo, ha sido aplicado para solucionar diferentes clases de problemas. El algoritmo colonia de abeja artificial (CAA) es una técnica de optimización recientemente propuesta qué simula el comportamiento inteligente de las abejas en la búsqueda de la miel. Un conjunto de abejas se denomina enjambre cuando pueden realizar tareas a través de la cooperación social de manera exitosa. En el algoritmo CAA, hay tres tipos de abejas: abejas empleadas, abejas en espera, y abejas exploradoras. Las abejas empleadas buscan comida alrededor de la posición de las fuentes de alimentos guardadas en sus memorias; entretanto comparten la información de estas fuentes de alimentos con las abejas en espera. Las abejas en espera tienden a seleccionar buenas fuentes de alimentos de aquellas encontradas por las abejas empleadas. Las fuente de alimento que tiene calidad más alta tendrá una posibilidad más grande de ser seleccionada por las abejas en espera que la de calidad más baja. Las abejas exploradoras se trasladan hasta una nueva fuente determinando el abandono de dicha fuente por las empleadas.

En el algoritmo CAA, la primera mitad del enjambre consta de abejas empleadas, y la segunda mitad constituye las abejas en espera.

El número de abejas empleadas o de abejas en espera es igual al número de soluciones en el enjambre. El CAA genera una población inicial aleatoriamente distribuida de SN soluciones (fuentes de alimentos), donde SN denota el tamaño del enjambre.

Sea X_i = { X_i,1 , X_i,2 , ..., X_i,n } representando la i-esima solución en el enjambre, Donde n es el tamaño de dimensión. Cada abeja empleada X_i genera una nueva solución candidata V_i en la vecindad de su posición actual como en la ecuación:

${displaystyle V_{i_{k}}=X_{i_{k}}+Phi _{i_{k}}*(X_{i_{k}}-X_{j_{k}})}$

Donde X_j es una solución candidata seleccionada aleatoriamente ${displaystyle (i eq j)}$, es un índice aleatorio de dimensión seleccionado del conjunto

{ 1, 2,..., n} , y ${displaystyle Phi _{i_{k}}}$ es un número aleatorio en el intervalo [-1,1].

Una vez la nueva solución de candidata V_i es generada, se realiza un selección golosa. Si el valor de V_i es mejor que de su padre X_i , entonces se actualiza X_i con V_i; en otro caso se mantiene el valor de X_i sin cambios. Después de esto las abejas empeladas completan el proceso de búsqueda; comparten la información de sus fuentes de alimentos con las abejas en espera a través de las danzas. Una abeja en espera evalúa la información del néctar tomada de todas las abejas empleadas y escoge una fuente alimentaria con una probabilidad relacionada con su cantidad de néctar. La selección probabilística constituye un mecanismo de selección de ruleta qué está descrito en la siguiente ecuación:

${displaystyle P_{i}={frac {fit_{i}}{sum _{j}fit_{j}}}}$

Donde ${displaystyle fit_{i}}$ el valor proporcionado por la i-esima solución en el enjambre. A mejor solución i, más alto es la probabilidad de que la i-esima fuente de alimentos sea seleccionada. Si una posición no puede ser mejorada sobre un predefinido número (llamado límite) de ciclos, entonces la fuente de alimentos es abandonada. Suponer que la fuente abandonada es X_i, y entonces la abeja exploradora descubre una nueva fuente de alimentos para ser reemplazado por la i-esima como se muestra en la ecuación:

${displaystyle X_{i_{k}}=lm_{j}+rand(0,1)*(ls_{j}-lm_{j})}$

Donde rand(1,0) es un número aleatorio entre [0,1] basado en una distribución normal y lm, ls, son las fronteras más bajas y altas de la i-esima dimensión, respectivamente.

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

---