Colony of artificial bees
Autor: Dayana Silverio Ortega / dayana.silverio@pri.jovenclub.cu
Resumen
Colonia de Abejas Artificiales es una técnica metaheurística bioinspirada, propuesta por Karaboga que se basa en el comportamiento empleado por las abejas melíferas para encontrar buenas fuentes de alimento. Es un algoritmo diseñado para resolver problemas de optimización combinatoria. La calidad de las soluciones puede ser vista como la cantidad de néctar en la fuente de alimento. Las abejas artificiales se clasifican en tres grupos: abejas empleadas, abejas observadoras y abejas exploradoras. El trabajo coordinado de los tres tipos de abejas produce cambios en las soluciones, de tal forma que se pueden encontrar fuentes de alimento cada vez de mejor calidad.
Palabras claves: Algoritmo, bioinspirada, metaheurística
Abstract
Artificial Bee Colony is a bioinspired metaheuristic technique, proposed by Karaboga that is based on the behavior used by honey bees to find good sources of food. It is an algorithm designed to solve combinatorial optimization problems. The quality of the solutions can be seen as the amount of nectar in the food source. Artificial bees are classified into three groups: employed bees, observer bees, and scout bees. The coordinated work of the three types of bees produces changes in the solutions, in such a way that sources of food can be found each time of better quality.
Keywords: Algorithm, bioinspired, metaheuristic
Introducción
Colonia de Abejas Artificiales (ABC por sus siglas en inglés) es una técnica metaheurística bioinspirada, propuesta por Karaboga que se basa en el comportamiento empleado por las abejas melíferas para encontrar buenas fuentes de alimento y comunicar esta información al resto de la colmena.
ABC utiliza parámetros como el tamaño de la colonia y el número máximo de generaciones. ABC es un algoritmo diseñado para resolver problemas de optimización combinatoria, que se basa en poblaciones donde las soluciones, llamadas fuentes de alimento, son modificadas por abejas artificiales.
El objetivo de estas abejas es descubrir fuentes de alimento que tengan cada vez mayores cantidades de néctar, y finalmente devuelven la fuente de alimento más abundante que pudieron encontrar. De esta forma, se obtienen soluciones óptimas locales, e idealmente el óptimo global. En un sistema ABC, las abejas artificiales se mueven en un espacio de búsqueda multidimensional eligiendo fuentes de néctar dependiendo de su experiencia pasada y de sus compañeras de colmena.
Cuando una abeja encuentra una mejor fuente de néctar, la memorizan y olvida la anterior. De este modo, ABC combina métodos de búsqueda local y búsqueda global, intentando equilibrar el balance entre exploración y explotación.
Desarrollo
El algoritmo ABC emplea varias soluciones del problema al mismo tiempo, cada solución es considerada como una fuente de alimento. La calidad de las soluciones es evaluada mediante la función objetivo, y puede ser vista como la cantidad de néctar en la fuente de alimento. A las funciones destinadas a producir modificaciones en las soluciones, se les llamada abejas artificiales y por el tipo de función, se clasifican en tres grupos: abejas empleadas, abejas observadoras y abejas exploradoras. El trabajo coordinado de los tres tipos de abejas produce cambios en las soluciones, de tal forma que se pueden encontrar fuentes de alimento cada vez de mejor calidad.
Las abejas empleadas están asociadas con una fuente de alimento en particular, y son las que explotan el alimento, a la vez que llevan consigo la información de esta fuente particular de alimento a las observadoras. Las abejas observadoras son aquellas que están esperando en el área de danza de la colmena para que las abejas empleadas les compartan la información sobre las fuentes de alimento, y entonces tomen una decisión de elección de alguna fuente de alimento. Las abejas que salen del panal en busca de una fuente de alimento al azar son las llamadas exploradoras.
En el algoritmo de Colonia de Abejas Artificiales, el número de abejas empleadas y el número de abejas observadoras, es igual al número de fuentes de alimento que están alrededor del panal. Cuando una fuente de alimento se agota debe ser abandonada, y la abeja empleada que la explotaba se convierte en una abeja exploradora que busca de forma aleatoria una fuente nueva.
La posición de una fuente de alimento representa una solución factible del problema de optimización y el monto de néctar o de alimento de la fuente corresponde a la calidad de la solución asociada a dicha fuente. Proceso que se presenta en el pseudocódigo de colonia de abejas artificiales.
Para el diseño de distritos electorales, una fuente de alimento se define como una solución:
E = {D1,D2,…,Dn},
Donde Ds es un conjunto de UG para s = 1,2,…,n.
Una población inicial de M fuentes de alimento se genera utilizando la estrategia descrita anteriormente, de tal manera que cada solución está formada por n distritos conexos.
De acuerdo a la técnica propuesta por Karaboga, cada fuente de alimento, Ei, debe ser modificada por exactamente una abeja empleada. En este caso, cada solución sufre un cambio para obtener la solución E0 i siguiendo la estrategia descrita.
Si la nueva solución E0 i tiene una cantidad de néctar mejor que Ei, E0 i sustituye a Ei y se convierte en una nueva fuente de alimento explotada por la colmena. En otro caso, E0 i se rechaza y Ei se conserva.
Algoritmo de Colonia de Abejas Artificiales en pseudocódigo
1 INICIALIZA. Generar de forma aleatoria M fuentes de alimento E1,…,EM.
2Repite.
3 Para i:= 1 a M hacer.
4 Enviar una abeja empleada a la fuente de alimento Ei.
5 Modificar la fuente de alimento Ei y determinar la cantidad de néctar de la nueva solución, E0 i, mediante la función objetivo.
6 si la nueva solución es mejor entonces.
7 E0 i ←− Ei.
8 fin.
9 fin.
10 Para i:= 1 a M hacer.
11 Calcular la probabilidad de cada fuente de alimento para ser elegida por una abeja observadora.
12 fin.
13 Para i := 1 a M hacer.
14 Elegir en probabilidad una fuente de alimento Ej.
15 Enviar una abeja observadora a la fuente de alimento seleccionada.
16 Modificar la fuente de alimento Ej y determinar la cantidad de néctar de la nueva solución, E0 j, mediante la función objetivo.
17 si la nueva solución es mejor entonces.
18 E0 j ←− Ej
19 fin.
20 fin.
21 Detener la exploración de las fuentes de alimento que han sido agotadas por las abejas.
22 Enviar a las abejas exploradoras para encontrar nuevas fuentes de alimento de forma aleatoria.
23 Memorizar la mejor fuente de alimento encontrada hasta el momento.
24 hasta Cumplir criterio de paro.
25 Termina el algoritmo.
En cuanto el proceso de las abejas empleadas se ha realizado en todas las M fuentes de alimento, empieza el turno de las abejas observadoras. Cada abeja observadora evalúa la calidad de las soluciones obtenidas hasta este momento, y elije una fuente de alimento con base en la probabilidad pi, dada por:
pi = Calidadi PM j=1 Calidadj
Donde Calidadi es la calidad de la fuente de alimento Ei, calculada mediante la función objetivo. M es el número de fuentes de alimento.
Una vez que ha seleccionado una solución, EOrigen, la abeja observadora intentará mejorarla mediante un proceso que combina algunas características de esta fuente de alimento con otra solución, EDestino, elegida de forma aleatoria. Este proceso de combinación se resume en los siguientes pasos.
Sea EOrigen la fuente de alimento que se va a modificar y EDestino la solución con la que deberá combinarse. Se elige una UG, k, de forma aleatoria. Entonces, existen un distrito Di ∈ EOrigen y un distrito Dj ∈ EDestino tales que k ∈ Di∩Dj. Ahora se deben considerar los siguientes conjuntos:
H1 = {l : xli = 0,xlj = 1}
H2 = {l : xli = 1,xlj = 0}
Donde xli =(1, si la UG l pertenece al distrito i 0, en otro caso.
Entonces una UG en H1 es insertada en Di, y una UG en H2 es extraída de Di, e insertada en un distrito contiguo a Di.
Es importante observar que estos movimientos pueden producir desconexión en el distrito Di, por lo que debe realizarse un proceso que la repare. Para esto, se cuenta el número de componentes conexas en Di. Si el número de componentes conexas es 1, entonces el distrito no perdió su conexidad. En otro caso, la componente conexa que contiene a k (i.e., la UG usada en el proceso de combinación mencionado anteriormente) se define como el distrito Di, mientras que el resto de las componentes son asignadas a otros distritos adyacentes.
Una vez que han concluido los procesos de combinación y reparación antes mencionados, se obtiene una nueva fuente da alimento E0Origen. Si la nueva solución E0Origen tiene una cantidad de néctar mejor que EOrigen, E0Origen sustituye a EOrigen y se convierte en una nueva fuente de alimento explotada por la colmena. En otro caso, E0Origen es rechazada y EOrigen es conservada.
Se considera una iteración del algoritmo después de que las M abejas empleadas y las M abejas observadoras hacen su labor. El algoritmo finaliza después de L iteraciones.
En cada iteración se lleva una estadística del número de veces que cada fuente de alimento sufre un cambio. Si una fuente de alimento no cambia después de un número N de iteraciones, entonces una abeja exploradora sustituye esta fuente de alimento.
Conclusiones
En el artículo se explicó la metaheurística colonia artificial de abejas para resolver problemas de optimización combinatoria, logrando resultados que verifican que su eficacia (optimización) y eficiencia (tiempos de ejecución) es mejor para alcanzar soluciones óptimas, que la utilización de otros modelos metaherísticos. Esto se debe a que las heurísticas son técnicas que permiten llegar a buenos resultados, pero en un tiempo computacional aceptable.
El gran aporte de la metaheurística de la colonia artificial de abejas no es encontrar mejores soluciones que los modelos tradicionales, sino más bien encontrar soluciones bastante similares, pero con un costo computacional asociado a tiempo y recursos notablemente menor.
Referencias Bibliográficas
- D. Karaboga, “An idea based on honey bee swarm for numerical optimiza- tion”, Technical Report TR06, Computer Engineering Department, Erciyes University, Turkey 2005.
- D. Karaboga y B. Basturk, “A powerful and efficient algorithm for numeri- cal function optimization: artificial bee colony (ABC) algorithm”, Journal of Global Optimization 39 (2007) 459-471.
- D. Karaboga y B. Basturk, “On the performance of artificial bee colony (ABC) algorithm”, Applied Soft Computing 8 (2008) 687-697