Optimización de Funciones Inspirada en el Comportamiento de Búsqueda de Néctar en Abejas

CONGRESO INTERNACIONAL DE INTELIGENCIA COMPUTACIONAL - CIIC 2007

´ Optimizaci´on de Funciones Inspirada en el Comportamiento de Busqueda de N´ectar en Abejas Wilfredo Alfonso, Mario A. Mu˜noz, Jes´us A. L´opez, Eduardo F. Caicedo Grupo Percepci´on y Sistemas Inteligentes, Universidad del Valle, Cali, Colombia, Sur-Am´erica E-mail: {walfomor,andremun,jesuslop,ecaicedo}@univalle.edu.co Abstract

[9, 5], donde otras t´ecnicas no han dado resultados adecuados. Este art´ıculo describe el proceso de foraging colectivo de las abejas en la b´usqueda y recolecci´on de n´ectar, a partir del cual se dise˜no´ un algoritmo que integra algunas caracter´ısticas del comportamiento de los insectos reales y las caracter´ısticas de auto–organizaci´on descritas en [3], convierti´endolo en un algoritmo orientado a la soluci´on en la b´usqueda de m´aximos o m´ınimos de una funci´on as´ı como un mecanismo que permite resolver problemas de control multivariable [2]. El algoritmo de optimizaci´on de b´usqueda del n´ectar de abejas (BNSO, por sus siglas en ingl´es), es dise˜nado a partir del modelado orientado al individuo (i-o) descrito en [4], mejorando las propiedades cognoscitivas de los agentes en la b´usqueda del n´ectar. El art´ıculo esta organizado de la siguiente manera: inicialmente, la secci´on 2 hace una breve descripci´on de los procesos de foraging que han sido identificados en las abejas. La secci´on 3, describe las particularidades del modelo BNSO, con los par´ametros y la terminolog´ıa empleada en [4] a partir del modelo i-o, adem´as de identificar los cuatro ingredientes b´asicos de la auto–organizaci´on sobre el algoritmo, tal como se describe en [3]. La secci´on 4, muestra un ejemplo en la b´usqueda de m´aximos de una funci´on. Finalmente, en la secci´on 5 se presentan algunas conclusiones.

En este art´ıculo se presenta el funcionamiento del algoritmo basado en el comportamiento de b´usqueda de n´ectar por abejas, aplicado a la soluci´on de problemas en el campo de optimizaci´on de funciones. Este algoritmo puede ser clasificado como parte de la computaci´on evolutiva, m´as espec´ıficamente dentro de la inteligencia de enjambres. Se presenta una aplicaci´on, donde el algoritmo representa fielmente el comportamiento de las abejas en la b´usqueda de n´ectar hallando los puntos m´aximos de una funci´on. Los resultados obtenidos permiten mostrar que la inteligencia colectiva y espec´ıficamente el algoritmo basado en abejas pueden ser una herramienta adicional en la soluci´on de problemas de ingenier´ıa. Palabras Clave: Cooperative systems, Swarm Intelligence, Self-Organization, Optimization methods.

1

Introducci´on

El t´ermino inteligencia de enjambres (Swarm Intelligence - SI) hace referencia a las propiedades cognoscitivas que organismos simples realizan para mantener un enjambre o colonia y est´a basada en las observaciones de insectos sociales. Las colonias de hormigas y colmenas, por ejemplo, tienen la propiedad de tener un comportamiento aparentemente organizado con el prop´osito de aumentar la supervivencia colectiva usando reglas simples de interacci´on. Es incre´ıble que los enjambres de criaturas con capacidades cerebrales y de comunicaci´on relativamente limitadas puedan tener un “comportamiento emergente” reflejado de alguna “inteligencia colectiva” [5]. Los procesos biol´ogicos que dichos organismos simples realizan para suplir las necesidades de alimentaci´on, reproducci´on, defensa, etc., han logrado captar la atenci´on de cient´ıficos e investigadores que imitan estos comportamientos a trav´es de algoritmos, para resolver problemas de ingenier´ıa u otras aplicaciones afines como la optimizaci´on y control de procesos

2

El foraging en las abejas

Las abejas, en particular la especie Apis Mellifera, son uno de los insectos sociales m´as estudiados. Ellas poseen muchas caracter´ısticas que pueden ser usadas como modelos de comportamiento inteligente, entre las cuales est´an la divisi´on de labores, la comunicaci´on sobre un individuo y grupos, el comportamiento cooperativo y su estrategia reproductiva. Estos comportamientos realizan una secuencia de acciones producto de su potencialidad gen´etica, ambientes ecol´ogicos y fisiol´ogicos, las condiciones sociales de la colonia, y otras prioridades [1]. Una aproximaci´on algor´ıtmica al comportamiento de las abejas usando su estrategia reproductiva, se presenta en 1

146

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

´ VIII JORNADAS ACADEMICAS EN INTELIGENCIA ARTIFICIAL

[1], donde las reinas de la colonia se aparean con varios z´anganos, obteniendo una biblioteca gen´etica y donde se extraen nuevos individuos que representan las reinas de la siguiente iteraci´on. Dicho algoritmo tiene mecanismos muy similares a los algoritmos gen´eticos, por lo cual no puede ser considerado de Inteligencia de Enjambres. Un comportamiento que se puede modelar de forma algor´ıtmica es el sistema de b´usqueda y recolecci´on de N´ectar. Tal vez, lo m´as particular de este comportamiento es la forma como las abejas se comunican a trav´es de danzas para informar posibles fuentes de alimento a toda la colonia. Muchos estudios alrededor de este comportamiento han sido hechos en [4, 6, 7], entre otros. El modelo orientado al individuo (Individual–Oriented Model – i–o) [4] simula el comportamiento de la b´usqueda y recolecci´on de n´ectar colectivo de una colonia de abejas Apis Mellifera. Cada abeja sigue el mismo conjunto de reglas comportamentales, las cuales consisten en un conjunto de condiciones que definen una acci´on a ser desarrollada. Las condiciones incluyen informaci´on externa e interna, como la danza de otras abejas y la localizaci´on memorizada de una fuente de alimento, respectivamente. La colonia de abejas tiene que adaptarse continuamente a cada nueva situaci´on, procurando tener la cantidad de n´ectar necesario para el mantenimiento de la colmena, por medio de la divisi´on apropiada de la fuerza de trabajo entre la exploraci´on del campo de nuevas fuentes de alimento y la explotaci´on de las fuentes conocidas. El comportamiento de foraging de cada abeja como individuo es regulada, y la informaci´on externa e interna juegan roles importantes en el comportamiento del foraging. Las reglas incluyen especificaciones para el viaje de partida de la abeja del nido a la fuente, la b´usqueda de la fuente para una abeja, la recolecci´on de n´ectar de una fuente, el viaje de regreso al nido, el medio por el cual la informaci´on acerca de la fuente sea transmitida a otras abejas en el nido, como el baile al regreso de la abeja y las reacciones de una abeja en el nido por el baile de una compa˜nera. Adicionalmente, hay reglas a-cerca del olvido de las fuentes y la precisi´on en la transmisi´on de la informaci´on en los bailes o el viaje. La informaci´on representada por las danzas indica la localizaci´on de las fuentes en la distancia (por medio de la duraci´on), la posici´on (por medio de la direcci´on) y la productividad de la fuente (por medio de la insistencia y vigorosidad del baile). Entre m´as vigoroso y alargado sean los bailes m´as seguidores podr´ıan ser atra´ıdos. Es seguro que la distancia y la direcci´on de las fuentes de alimento codificado en las danzas no son el u´ nico tipo de informaci´on que puede guiar el encuentro de las abejas a encontrar fuentes provechosas de alimento. El olor influye en la colmena y en el campo, y los est´ımulos visuales influencian el comportamiento de b´usqueda y hallazgo de las abejas. Adem´as las abejas tienen una especie de memoria, la cual guarda

informaci´on que percibe del ambiente para usarla posteriormente. Una serie de par´ametros est´an presentes en el modelo i– o para regular el comportamiento de los individuos en la colmena a saber: • El n´umero de abejas (N ): Representa la cantidad de individuos especializados en la b´usqueda y recolecci´on de n´ectar o fuerza de trabajo. • La precisi´on de transmisi´on (t ∈ [0 1]): Controla la precisi´on con la cual la ubicaci´on de la fuente es transmitida por medio de la danza. • La habilidad de b´usqueda (s): Controla c´omo una fuente puede ser localizada a partir de la informaci´on aproximada de posici´on obtenida. Un valor bajo de s significa que la abeja toma rutas m´as irregulares hacia las fuentes memorizadas y que al mismo tiempo la posici´on de la fuente memorizada est´a sujeta a cambios aleatorios. • La probabilidad de Abandono (a ∈ [0 0.20]): Controla la tendencia a abandonar la fuente conocida por el individuo. B´asicamente, un individuo tender´a a abandonar una fuente menos provechosa, si otra con mayor concentraci´on se presenta, o si la actual pierde su provecho. Adem´as, este par´ametro tambi´en controla la tendencia de la abeja para atender a las baila-rinas nuevamente, despu´es de convertirse en una abeja sin oficio. Tan pronto como su tendencia de abandono llegue al m´aximo, e´ sta comenzar´a a seguir a las baila-rinas de nuevo. En este punto, la abeja ha abandonado completamente su antigua fuente y la experiencia adquirida. Para describir la carrera de las abejas en el foraging se usa la terminolog´ıa descrita en [4], donde cada individuo pertenece a una categor´ıa y clase, de acuerdo al comportamiento realizado en la b´usqueda y recolecci´on de n´ectar. Las categor´ıas, que corresponden al nivel m´as alto, y clases, que identifica a cada individuo por categor´ıa, son: • Forager empleado: Conoce y explota una fuente lucrativa sin seguir las danzas de las bailarinas. • Forager sin oficio: No explota alguna fuente. – Forager ingenuo (o novato). – Explorador: Comienza a buscar espont´aneamente; no conoce alguna fuente. – Recluta: Comienza a buscar a partir de la atenci´on a una danza; conoce aproximadamente la posici´on de una fuente, pero no su lucratividad. • Forager experimentado: Conoce la posici´on y la lucratividad de una fuente. 2

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

147

CONGRESO INTERNACIONAL DE INTELIGENCIA COMPUTACIONAL - CIIC 2007

a cada dimensi´on; es decir, que si el forager se mueve en dos dimensiones puede llegar a desplazarse es un m´aximo de dos veces la ra´ız del SM configurado. No existe por lo tanto una ecuaci´on que defina la forma del movimiento de los agentes sobre el espacio de b´usqueda; sin embargo, al igual que los giros y desplazamientos de las bacterias en el algoritmo BSFO (Bacterial Swarming Foraging Optimization) [9], los foragers exploradores cambian la direcci´on y el tama˜no del desplazamiento, si es necesario, una vez hayan alcanzado un tope de tiempo de b´usqueda. Particularmente, el algoritmo intenta darle ca-racter´ısticas de exploraci´on-explotaci´on a los foragers que hacen la b´usqueda de las fuentes de n´ectar. Los agentes que se encuentran explorando toman con 60% del HomeMot en seguir una sola direcci´on y un desplazamiento de acuerdo al paso aleatorio adquirido, el 40% restante es usado por los agentes para intentar seguir un gradiente positivo de alimento que lo aproximen al objetivo de la fuente (el punto m´as provechoso). Los incrementos en el HomeMot son del 10% por cada iteraci´on; es decir, que los agentes exploradores cuentan con un m´aximo de 10 iteraciones antes de regresar definitivamente a la colmena. El giro y desplazamiento de los agentes durante la fase explotativa de las fuentes var´ıa en cada agente de forma aleatoria si el paso realizado por el agente lo lleva a un punto de menor concentraci´on que el anterior, y de paso le brinda la posibilidad de regresar a su posici´on anterior para iniciar la b´usqueda del gradiente desde el punto ha donde hab´ıa llegado. El Algoritmo 2 es una descripci´on de alto nivel del proceso realizado por los foragers exploradores.

– Inspector: Se reactiva espont´aneamente para hacer una visita de reconocimiento para inspeccionar el estado de lucratividad de una fuente. – Forager reactivado: Es reactivado de acuerdo a la atenci´on de un baile que contiene informaci´on confirmada. – Explorador: Comienza buscando espont´aneamente por alguna nueva fuente, despu´es que su vieja fuente fue deteriorada. – Recluta: Comienza buscando una nueva fuente, previniendo que la fuente sobre la cual atiende una danza contiene informaci´on que no concuerda con su fuente conocida.

3

´ Optimizaci´on de Busqueda de N´ectar de Abejas (BNSO)

El algoritmo de B´usqueda de N´ectar (Bees Nectar Search Optimization - BNSO) sigue el modelo biol´ogico i–o [4], modificando algunas de sus caracter´ısticas para efectuar algunas tareas de una manera m´as eficiente de tal manera que se pueda utilizar como algoritmo de optimizaci´on, haciendo uso de la informaci´on local, la transmisi´on de informaci´on por medio de danzas y un balance entre la exploraci´on y la explotaci´on. Como se mostr´o en la anterior secci´on, las abejas son separadas en distintas clases y categor´ıas de acuerdo a su capacidad de encontrar fuentes de alimento y la capacidad de informar a sus compa˜neras la ubicaci´on de las fuentes a trav´es de danzas. El algoritmo BNSO toma como par´ametros de entrada los existentes en el modelo i–o a excepci´on de la habilidad de b´usqueda y algunas propiedades motivacionales de la abeja (excepto la motivaci´on de foraging) [2]. La descripci´on en alto nivel del algoritmo BNSO se presenta en los algoritmos 1, 2 y 3, donde se toman las tres posibles ubicaciones de los foragers en el proceso de b´usqueda de n´ectar los cuales son: dentro de la Colmena, fuera de la Colmena y een las Fuentes, respectivamente. Inicialmente dentro del algoritmo, algunos agentes son motivados a salir de la colmena a buscar de forma aleatoria fuentes de alimento. La cantidad de agentes iniciales para la b´usqueda aleatoria de fuentes, o mejor, la cantidad de individuos que se convierten autom´aticamente en fo-ragers exploradores, es un par´ametro del algoritmo el cual se ha establecido con el nombre de Exploradoras. La ubicaci´on inicial de estos foragers se hace de manera aleatoria sobre el espacio de b´usqueda. La oportunidad de encontrar una fuente rica de alimento por estos foragers exploradores es limitada por la “motivaci´on a casa” (HomeMot), la cual se aumenta con cada paso que estos den sobre un espacio desconocido. El tama˜no m´aximo del paso (SM) es un par´ametro adicional del algoritmo BNSO e independiente

A diferencia del algoritmo BSFO, cuando las bacterias realizan un paso chemot´actico, estas realizan tantos movimientos como la direcci´on de gradiente indique buenas aproximaciones hacia un punto de alto contenido nutricional limitando este movimiento a un tope que es una par´ametro del algoritmo, mientras que para el caso de las abejas, este trabajo se hace aprovechando las caracter´ısticas colectivas presentes en estos agentes. Es importante resaltar que es poco probable que un agente explorador pueda llegar directamente al punto de mayor concentraci´on de nutrientes y que podr´ıa ser efecto de agentes recolectores, debido al error en la transmisi´on de la informaci´on a la que es sometido el algoritmo en la danzas. Una vez alguna fuente es encontrada y se ha cumplido su tiempo de b´usqueda (HomeMot = 1), los foragers regresan a la colmena para informar al resto de la poblaci´on la ubicaci´on relativa y lo provechoso de la fuente hallada. La posici´on de la fuente se informa con cierto error en la comunicaci´on, siendo esto un mecanismo de exploraci´on para hallar m´aximos locales. La posibilidad que cada agente salga de la colmena con un conocimiento de lo provechoso de la fuente, permite una r´apida convergencia hacia el m´aximo local de la zona explorada; desde luego, este tipo 3

148

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

´ VIII JORNADAS ACADEMICAS EN INTELIGENCIA ARTIFICIAL

Algoritmo 1 -Descripci´on de alto nivel del algoritmo BNSO (En la Colmena) /* En la Colmena */ /* 1. Depositar N´ectar */ If transporta carga then Descargar el n´ectar en la colmena End If /* 2. Salir a volar o permanecer en la Colmena */ If Categor´ıa es experimentada then // Conoce la posici´on de una fuente. If (T A < U T A y Class 6= Inspector) o (T A ≥ U T A y Class = Inspector) then // Seguir explotando la fuente conocida. F ly = T rue y P os = M emory; End If // Incrementar TA de acuerdo con: T A = T A + ξ; Elseif Categoria = empleada y T A < 1 then // Explotaci´on por parte de las recolectoras. F ly = T rue y P os = M emory; T A = T A + ξ; Elseif T A > 1 then T A = 0, Categoria = N Oempleado; Class = N ovato, HomeM ot = 0; M emory = Posici´on de la Colmena; End If /* 3. Seguir o No a una Danza */ // En caso que sea un forager no empleado // Escoga a qui´en seguir deacuerdo con:  [M ax, j] = arg maxu∈J

de sus compa˜neras al informar un punto de mejores caracter´ısticas, evitando que algunos agentes presentes en la colmena sigan la danza con informaci´on que ahora es poco adecuada. Una vez, el forager logra esto, regresa al punto donde se encuentra su nueva fuente y explora un poco m´as tratando de encontrar un gradiente positivo de alimento, como el objetivo es que regrese r´apido con la informaci´on de la fuente hallada y que adem´as intente llegar a una mejor posici´on, se trata al agente con un HomeMot inicial de 0.6, que es la fase explotativa. Una vez su HomeMot se ha completado, regresa a la colmena para informar la ubicaci´on de la fuente. Adicionalmente, cuando el agente intenta detener al forager que le inform´o la posici´on de la fuente anterior, podr´ıa llegar a detener a una abeja que informa una fuente muy cercana ocasionando una p´erdida de informaci´on que lleve a nuevos foragers puntos de concentraci´on de n´ectar. Por lo tanto, el algoritmo de abejas puede cometer errores sobre funciones donde los m´aximos locales est´en pr´oximos entre s´ı, aunque siempre converge a la fuente de mayor provecho en esa zona. El algoritmo BNSO, maneja una funci´on probabil´ıstica P (Ecuaci´on 1) que ayuda a los agentes de la colmena a tomar decisiones acerca de cual forager bailarina deben seguir; el agente con el m´aximo valor de provecho (Prof ) hallado es aquel que tiene el privilegio de informar a un individuo de la colmena la posici´on de su fuente. Pu = P

P rof (u) , P rof (k)

(1)

k∈J

(u) Pu = P P rof P rof (k) k∈J

[M ax, j] = arg maxu∈J {Pu } ,

For Todas las Bailarinas do T A = T A + ξ; End For For j do // j es el forager m´as insistente. T A = T A + ξ; If T A ≥ 90% de UTA then Pare de Danzar y Adquiera la clase Inspector End If End For // Retomando al forager que sigui´o la danza. Adquiera Categoria empleado y clase recluta Dirijase a la posici´on percibida en la danza (Error t%) // Optimizaci´on del comportamiento Tome el provecho transmitido F ly = true;

(2)

De acuerdo al modelo biol´ogico, las abejas no dejan por completo alguna fuente hallada y siempre se encuentran en zonas donde hay mayor cantidad de alimento, por ello el algoritmo BNSO regula la cantidad de agentes que visitan las fuentes modificando la “Tendencia de Abandono” (T A). El T A es un par´ametro adicional del algoritmo BNSO y se encarga de regular tanto la tendencia en abandonar una fuente como, en el caso de los foragers baila-rines, de detener la danza; adem´as este par´ametro es usado dentro del algoritmo para reactivar un forager experimentado que ha permanecido alg´un tiempo dentro de la colmena. En la medida que un miembro de la colmena desea reclutarse para la recolecci´on de n´ectar, la T A de todos los foragers bailarines es aumentada de acuerdo a la constante de abandono (ξ). Adicionalmente se aumenta un ξ m´as al T A del forager que logr´o captar su atenci´on. Ello hace que el comportamiento general de la colmena tienda a seguir a los foragers bailarines con las fuentes m´as provechosas de alimento, sin dejar de lado, al resto de las bailarinas que pueden tener su oportunidad una vez el forager con la fuente m´as provechosa halla abandonado su deseo de bailar.

de informaci´on adicional que recibe el forager es una caracter´ıstica de optimizaci´on en la b´usqueda de n´ectar. Otra caracter´ıstica del foraging que permite la r´apida convergencia, es la capacidad de detener la danza de una 4

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

149

CONGRESO INTERNACIONAL DE INTELIGENCIA COMPUTACIONAL - CIIC 2007

Algoritmo 2 -Descripci´on de alto nivel de los foragers exploradores /* Fuera de la Colmena */ /* Inicializaci´on */ For k = 1 toN do // k es el contador de los agentes. // N es la cantidad total de agentes. If Class es scout & F ly es true then Poner el ´ındice k en Arreglo Aux End If End For // Generar paso aleatorio por agente de Arreglo Aux For i = 1 to longitud Arreglo Aux do //random – N´umero aleatorio entre 0 y 1 // por dimensi´on. Step = SM · random; //SM – Paso m´aximo //Pos – Posici´on actual del agente. Calcular J de cada agente en Pos End For /* Bucle Principal */ For i = 1 to longitud Arreglo Aux do N ewP os = P os + Step; Calcule JNew en NewPos If JN ew > J en Pos o´ HomeM ot < 0.6 then P os = N ewP os; J = JN ew; Else Step = SM · random End If //Actualizar HomeM ot de la i-´esima abeja: HomeM ot = HomeM ot + 0.1; If HomeMot ≥ 1 then If J > 0 then Regrese a la colmena Transmita Informaci´on (Dance) Adquiera clase experimentada Else Regrese a la colmena Adquiera clase novata Espere compa˜neros con danzas End If End If End For //J = Es el valor de la funci´on es el espacio de b´usqueda.

fuente memorizada o simplemente deje de danzar.

T Ai =



1 P rofi · a T Aiant +

si 1era vez en la F uente ξ.

(3)

El uso de las clases y las categor´ıas en el algoritmo BNSO, permite un mayor control de la poblaci´on y la asignaci´on de tareas para el foraging de las abejas. Los par´ametros del algoritmo determinan el cambio de un forager de una clase a otra, o de una categor´ıa a otra. Por ejemplo, cuando un forager sale por primera vez de la colmena a buscar fuentes de alimento, esta se convierte en una forager exploradora sin conocimiento alguno, es decir que pertenece a la categor´ıa de forager sin oficio. Una vez un forager a tenido e´ xito al encontrar una fuente provechosa se convierte en una forager experimentada, la cual podr´ıa convertirse en una inspectora si su fuente es altamente provechosa, o en una recluta si uno de los agentes que sali´o en busca de esa fuente encuentra un punto de concentraci´on m´as alto. Cuando un agente a logrado establecerse como una forager experimentada, permanece en la colmena y es reactivada de acuerdo a su T A o por simple observaci´on de los foragers que ahora se encuentran informando fuentes. La mayor´ıa de los agentes presentes en la colmena no llegan a ser tan especializados, y es bastante frecuente encontrarlos como foragers reclutas o novatos, dedicados exclusivamente a la explotaci´on de las fuentes. El algoritmo BNSO posee una caracter´ıstica que permite la exploraci´on de nuevas fuentes de n´ectar, a trav´es de un umbral de exploraci´on (Umbral). Esta condici´on se presenta en aquellos individuos, que siguiendo las coordenadas de una fuente informada, llegan a puntos sin alg´un provecho. Al sobrepasar el Umbral se favorece la exploraci´on para hallar nuevas fuentes desde el punto donde actualmente se encuentra. El par´ametro Umbral es ajustado en un rango de [0 1], por lo tanto, entre m´as cercano a uno, menos es la posibilidad que halla exploraci´on por parte de un agente de la colmena. La auto–organizaci´on es un conjunto de mecanismos din´amicos por medio del cual aparecen estructuras de nivel global de un sistema de interacciones entre los componentes de bajo nivel. Las reglas espec´ıficas de las interacciones entre las unidades constituyentes del sistema ejecutadas sobre las bases de informaci´on puramente local, sin hacer referencia a los patrones globales, los cuales son una propiedad emergente m´as bien del sistema que una propiedad impuesta sobre el sistema por una influencia de ordenamiento externa [3].

El valor inicial que toma T A para cada individuo de la colmena es inverso al provecho (Prof ) de la fuente hallada por la “Probabilidad de Abandono” (a), tal como se muestra en la Ecuaci´on 3. El l´ımite m´aximo en el incremento de esta variable es determinado por el par´ametro “Umbral de la Tendencia de Abandono” (U T A), el cual una vez superado hace que el forager, sea cual sea su condici´on, olvide la

• La Realimentaci´on Positiva (Amplificaci´on) son las “reglas emp´ıricas” que promueven la creaci´on de estructuras y que incluyen el reclutamiento y el refuerzo, en las colmenas de abejas esto se observa cuando un 5

150

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

´ VIII JORNADAS ACADEMICAS EN INTELIGENCIA ARTIFICIAL

Algoritmo 3 -Descripci´on de alto nivel del algoritmo BNSO (En las Fuentes) /* En las Fuentes */ // Comparar el provecho transmitido con el obtenido // en la posici´on actual. If J > 0 then // Si la Abeja llega a una mejor ubicaci´on de la fuente. // M´as Provechosa que la que le informaron. If J > P rof then M emory = P os; Categoria = Experimentada; Class = scout, HomeM ot = 0.6; P rof = J; Else
T A = J1 ) · a; //a es la probabilidad //de abandono. M emory = P os; End If HomeM ot = 1 y Carga = 1; If Class es inspector then P rof = = 1;   J y Dance 1 ) · a, F ly = f alse; T A = P rof End If P os = Posici´on de la colmena; Elseif Class es recluta then Categoria = N O empleado; M emory = Posici´on de la colmena; Carga = 0; If random > U mbral then Class = scout y F ly = 1; Else T A = 1; P os = Posici´on de la colmena; Class = novato y F ly = f alse; End If End If

bros de la colmena y de esta generar una competencia entre las fuentes de alimento. • Amplificaci´on de Fluctuaciones, es decir, los recorridos aleatorios y errores, donde un agente desorientado o perdido puede llegar a nuevas fuentes de alimento no-explotadas. El algoritmo BNSO cumple con estas fluctuaciones cuando le da la posibilidad a alguno de sus agentes en explorar en el espacio de b´usqueda, desde un punto relativo de una fuente informada por su compa˜nera, hacia zonas desconocidas que pueden poseer alg´un tipo de fuente de alimento. ´ • Multiple reciprocidad entre los individuos, cuando en las colmenas, un agente que se encuentra observando las danzas, encuentra que una de ellas, indica un camino similar al que e´ sta ha almacenado dentro de su memoria, dichos individuos son reactivados para regresar a su fuente o intentar seguir a su compa˜nera, si desconf´ıa de la informaci´on que ella posee; en ese mismo sentido, un agente especializado es capaz de retomar los resultados de sus propias actividades en el momento que decide inspeccionar su fuente.

4

´ Busqueda de m´aximos de una funci´on

Un ejemplo del funcionamiento del algoritmo BNSO, se presenta a continuaci´on, donde la superficie empleada es peaks (Ecuaci´on 4) de MATLAB, en donde las posiciones x y y, se variaron de acuerdo a la Ecuaci´on 5 para ce-rrar la superficie en un espacio normalizado de 1∗1. Se supone que las abejas deben intentar llegar a las fuentes m´as lucrativas y explotarlas. Adem´as, y siguiendo un poco lo expuesto en [4], las fuentes no pueden ser totalmente abandonadas y cierta cantidad de foragers deben mante-nerse en estas fuentes. Los par´ametros configurados para esta simulaci´on fueron: N = 50, a = 0.07, t = 0.85, U T A = 0.50, ξ = 0.05, Exploradoras = 4, SM = 0.05, U mbral = 0.98 y posici´on de la Colmena en [−0.1 − 0.1]. 2

forager explorador o experimentado recluta nuevos compa˜neros para que se dirijan hacia la fuente que e´ stas informan a trav´es de las danzas. • La realimentaci´on negativa la cual ayuda a estabilizar el patr´on colectivo es observado en el algoritmo BNSO cuando los foragers que localizan mejores fuentes intentan regresar a la colmena para detener al forager que danza, el cual no esta direccionando el verdadero blanco de la fuente de alimento. Otra manera en la cual se puede observar este tipo de influencia, es a trav´es de la competencia, donde en ocasiones muchos foragers intentan seducir con sus danzas a los miem-

2

2

Z = 3 · (1 − x) · e−x −(y+1) . . .
2 2 −10 · x5 − x3 − y 5 · e−x −y . . . 1 −(x+1)2 −y 2 −3 · e

(4)

X = 0.5 3 · x + 0.5 Y = 0.5 3 · y + 0.5

(5)

En el ejemplo de la figura 1, se puede observar el comportamiento de las abejas cuando encuentran fuentes provechosas de alimento. Con el paso de cada iteraci´on el incremento de las abejas que visitan alguna de las fuentes se hace m´as notable de acuerdo a lo provechoso de la misma. En la figura 2, es posible observar que algunas de las abejas se han convertido en foragers experimentadas (punto de 6

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

151

CONGRESO INTERNACIONAL DE INTELIGENCIA COMPUTACIONAL - CIIC 2007

Test Surface

The Foraging Workforce upon of Sources 40

35

30

8

Number of workers

6

Profitability

4 2 0 −2

25

S1 S2

20

S

3

15

−4 10

1

−6 0.8

5

−8 1

0.6 0.9

0.8

0.7

0.6

0.4 0.5

0.4

0.3

0

0.2 0.2

0.1

0

Axis x

40

60

80

100

120

140

160

180

200

De acuerdo a la funci´on que finalmente se us´o, se encuentran los puntos de los m´aximos de la funci´on peaks, como se muestra en la tabla 1.

color amarillo), lo cual indica que se quedan cerca de las fuentes (asteriscos azules [S1 S2 S3 ]), explotando los recursos de n´ectar. Dentro del proceso de explotaci´on muchas de las foragers experimentadas son reactivadas, es decir, no tienden a otras fuentes y crean un lazo con la fuente que almacenan en su memoria hasta lograr desgastar la fuente o hasta que la fuente desaparezca. Adicionalmente, se observa como las abejas tienden a ir a fuentes con mayor concentraci´on de nutrientes, luego que han logrado explorar la superficie y abandonar las menos provechosas para explotar al m´aximo el recurso de alimento hallado en el proceso (Figura 3), adem´as demuestra que las abejas no abandonan completamente las fuentes con alg´un grado de lucratividad de N´ectar dejando que algunas sigan explotando dicha fuente.

´ Table 1. Posiciones de los puntos maximos Source Axis X Axis Y Maximum S1 0.4984 0.7636 8.1062 S2 0.4233 0.3951 3.7766 S3 0.7143 0.4992 3.5925 Para observar la repetibi-lidad del algoritmo, se hicieron 1000 experimentos con 200 iteraciones obteniendo los resultados que se consignan en la tabla 2, donde se muestran los criterios de evaluaci´on m´as relevantes para algoritmos implementados en la optimizaci´on de funciones [8]. Como el algoritmo est´a en la capacidad de hallar las tres fuentes o puntos de mayor provecho, para cada fuente se consignan el mejor hallado, la mediana, el peor hallado, la media y la desviaci´on est´andar entre los 1000 experimentos realizados.

Test Surface (Contour) 1

0.9

←S

1

Table 2. Resultados experimentales BNSO Source S1 S2 S3 Best 8.1062 3.7765 3.5925 Median 8.1062 3.7756 3.5903 Worst 8.1037 2.1720 1.0328 Mean 8.1062 3.7682 3.5786 Std 0.0003 0.0734 0.0925

0.7

0.6

Axis y

20

Figure 3. Cantidad de agentes vs. iteraciones

´ peaks Normalizada. Figure 1. Funcion

0.8

0

Iterations

0

Axis y

←S

0.5

3

←S

0.4

2

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Claramente la tabla 2 deja entre ver que la convergencia de los agentes de la colmena hacia la fuente m´as provechosa es muy alta sin dejar de obtener resultados aceptables para las otras fuentes, que aunque mostraron deficiencia en alguno de los resultados (al observar los peores), la mediana muestra que la mayor frecuencia de los datos est´a cerca a los

1

Axis x

´ peaks junto Figure 2. Contorno de la funcion ´ final de los foragers. con la ubicacion

7

152

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

´ VIII JORNADAS ACADEMICAS EN INTELIGENCIA ARTIFICIAL

de eliminaci´on-dispersi´on), datrayente = 0.1 (Profundidad de atracci´on), watrayente = 0.2 (Ancho de atracci´on), hrepelente = 0.1 (Altura de efecto repelente), wrepelente = 10 (Ancho de repulsi´on) y C = 0.05 (Tama˜no del paso).

puntos o´ ptimos de las fuentes mostrando una alta repetibilidad de acuerdo a la desviaci´on est´andar y el promedio de los resultados. Table 3. Complejidad algor´ıtmica T T (s) T 1 (s) T 1min (s) 3292.796 3.2929 3.2285

´ de Resultados Table 5. Comparacion Source (S1) BSFO BNSO Best 8.1056 8.1062 Median 7.9951 8.1062 Worst 6.5508 8.1037 Mean 7.9313 8.1062 Std 0.1961 0.0003

Por otro lado, para medir la complejidad del algoritmo, se toman algunos criterios a saber: T1 representa el valor promedio en segundos de ejecuci´on de las 200 iteraciones en cada uno de los 1000 experimentos y TT es el tiempo total en segundos en ejecutar los 1000 experimentos. La tabla 3 registra estos resultados y muestra el valor m´ınimo de tiempo obtenido al hacer 200 iteraciones. Como una informaci´on adicional, la tabla 4 muestra las posiciones de las fuentes reales y las mejor encontradas, as´ı como la distancia m´ınima obtenida con estas coordenadas. Esta informaci´on tiene un valor agregado que permite estimar el error que no puede ser observado en los datos consignados en la tabla 2, ya que la diferencia entre los puntos m´aximos reales y obtenidos es muy peque˜na. Como se puede observar en la tabla 4 la diferencia a los puntos donde se encuentran las fuentes reales est´an en orden de 10−3 .

Minimum Distance 0.0642e-03

Con los par´ametros configurados en estos dos algoritmos y de acuerdo a la tabla 5 se puede notar la superioridad en los resultados obtenidos con el algoritmo BNSO. Las otras fuentes no pudieron ser parte de este experimento ya que el algoritmo BSFO con los pasos de eliminaci´on-dispersi´on da mayor prioridad a los agentes que tienen la mejor funci´on de costo y por lo tanto, tiende a eliminar a los agentes que podr´ıan haberse ubicado en la m´aximos locales y por ende darle mayor prioridad a los puntos m´as alto de la funci´on. Los algoritmos gen´eticos, pueden ser utilizados para hallar el punto m´aximo de la funci´on, sin embargo, es importante resaltar, que aunque cuenta con diversas estrategias y metodolog´ıas para hallarlo, es muy poco probable que pueda encontrar los o´ ptimos locales de toda la funci´on, sin antes limitar el rango de b´usqueda en diferentes sectores de la superficie. Los algoritmos basados en inteligencia de enjambres por su parte ofrecen una alta versatilidad en la b´usqueda o recolecci´on de diferentes puntos con la misma poblaci´on en una u´ nica ejecuci´on del algoritmo.

0.5720e-03

5

0.3733e-03

Los resultados obtenidos en estos experimentos, muestran que el algoritmo BNSO empleado presenta caracter´ısticas que le permiten obtener un buen acercamiento a su contraparte real, adem´as de la convergencia de estos agentes presentan en cuanto al prop´osito de explotar fuentes con mayor provecho. El algoritmo BNSO basado en la inteligencia de enjambres es robusto, ya que al simular el comportamiento biol´ogico siempre se acondiciona a los ambientes virtuales a los que es sometido, logrando el prop´osito b´asico del bienestar de la colmena. Adem´as, puede aplicarse con cambios m´ınimos, a otro problema de optimizaci´on combinatoria y por ende mostrando caracter´ısticas de versatilidad. Los mejores resultados se observan sobre la fuente S1, ya que hay mayor concurrencia sobre la fuente m´as provechosa y por lo tanto, mayor probabilidad que los movimientos realizados por los agentes lo lleven a ubicarse sobre el

Table 4. Mejores posiciones y distancias m´ınimas a las fuentes Source S1 S2 S3

Real Best Position X = 0.4984 Y = 0.7636 X = 0.4233 Y = 0.3951 X = 0.7143 Y = 0.4992

Found Best Position X = 0.4984 Y = 0.7636 X = 0.4235 Y = 0.3957 X = 0.7146 Y = 0.4990

Este experimento fue realizado con otras funciones obteniendo excelentes resultados. Todas las funciones a las que es sometido el algoritmo han sido normalizadas entre cero y uno para mantener los par´ametros sin cambios. Por otro lado es posible comparar los resultados obtenidos con otro algoritmo basado en inteligencia colectiva, como el desarrollado por K. Passino, el cual imita el proceso biol´ogico de las bacterias E. Coli y se conoce como BSFO. Los resultados entre estos algoritmos, respecto funci´on normalizada de peaks se muestran el la tabla 5. Los par´ametros de configuraci´on para el algoritmo BSFO fueron: Nc = 20 (Pasos chemot´acticos), Ns = 10 (Pasos posibles en un solo sentido), Nre = 5 (Pasos reproductivos), Ned = 2 (Eventos de eliminaci´on-dispersi´on), ped = 20% (Probabilidad

Conclusiones

8

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...

153

CONGRESO INTERNACIONAL DE INTELIGENCIA COMPUTACIONAL - CIIC 2007

punto m´aximo de la superficie. Caso contrario ocurre con las otras dos fuentes, ya que si no hay buena concurrencia de los agentes pocas posibilidades existen para que estos puedan ubicarse en mejores posiciones. Actualmente, el algoritmo es estudiado para darle ma-yores posibilidades en t´erminos de exploraci´onexplotaci´on, ya que el camino seguido por los agentes es err´atico e impide que un agente que se dirija a un fuente informada pueda explorar un poco su camino de ida a la fuente y por lo tanto, impidiendo mayor posibilidad de encontrar una fuente m´as provechosa.

References [1] H. A. Abbass. Mbo: Marriage in honey bees optimization - a haplometrosis polygynous swarming approach. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 207–214, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27-30 May 2001. IEEE Press. [2] W. Alfonso. Regulaci´on de temperatura en la plataforma uv-ptm01 basada en agentes cooperativos para la asignaci´on din´amica de recursos. Technical report, Universidad del Valle, 2007. [3] E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm intelligence: from natural to artificial systems. Oxford University Press, Inc., New York, NY, USA, 1999. [4] H. de Vries and J. C. Biesmeijer. Modelling collective foraging by means of individual behaviour rules in honey-bees. Behav Ecol Sociobiol, 44:109–124, 1998. [5] M. Fleischer. Foundations of swarm intelligence: From principles to practice. ArXiv Nonlinear Sciences e-prints, Feb. 2005. [6] S. Ghosh and I. W. Marshall. Simple model of learning and collective decision making during nectar source selection by honey-bees. 2005. [7] D. C. Gilley. The identity of nest-site scouts in honey bee swarm. pages 229–240, 1998. [8] V. L. Huang, A. K. Qin, K. Deb, E. Zitzler, P. N. Suganthan, J. J. Liang, M. Preuss, and S. Huband. Problem definitions for performance assessment on multi-objective optimization algorithms. Technical report, School of EEE, Nanyang Technological University and Kanpur Genetic Algorithms Laboratory (KanGAL),Indian Institute of Technology and Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology and University Dortmund, Lehrstuhl f¨ur Algorithm Engineering and School of Computer Science & Software Engineering, The University of Western Australia, 2007. [9] K. M. Passino. Biomimicry of bacterial foraging for distributed optimization and control. IEEE Control Systems Magazine, 22(3):52–67, 2002.

9

154

´ OPTIMIZACION DE FUNCIONES INSPIRADA EN EL COMPORTAMIENTO DE...