PROPUESTA DE DISEÑO DE UN SISTEMA MULTI-AGENTE DIFUSO USANDO EL MODELO DE FLOCKING DE REYNOLDS Y AJUSTADO POR UN ALGORITMO EVOLUTIVO BASADO EN ABEJAS

˜ DE UN SISTEMA MULTI-AGENTE DIFUSO PROPUESTA DE DISENO USANDO EL MODELO DE FLOCKING DE REYNOLDS Y AJUSTADO POR UN ALGORITMO EVOLUTIVO BASADO EN ABEJAS

Carlos Alberto Riveros Varela 20071020087 Ferney Beltr´ an Velandia 20081005012

Universidad Distrital Francisco Jos´ e de Caldas Facultad de Ingenier´ıa Bogota D.C. - Colombia Febrero de 2015.

Trabajo de Grado Requisito para optar por el t´ıtulo de Ingeniero de Sistemas e Ingeniero Electr´onico, respectivamente.

Carlos Alberto Riveros Varela 20071020087 Ferney Beltr´ an Velandia 20081005012

Director: Miguel Alberto Melgarejo Rey Profesor Asociado Facultad de Ingenier´ıa - Laboratorio de Autom´atica e Inteligencia Computacional

Universidad Distrital Francisco Jos´ e de Caldas Facultad de Ingenier´ıa Bogota D.C. - Colombia

1

”No es muy importante que una persona aprenda datos. Para eso en verdad no necesita de una universidad. Puede encontrarlos en los libros. El valor de la educaci´ on universitaria no reside en el aprendizaje de muchos datos sino en capacitar a la mente para que piense de manera que lo haga sobre aquello que no se encuentra en los textos.” Albert Einstein, 1921. Citado por Philipp Frank en Einstein: His Life And Times.

2

Nota de aceptaci´ on:

Firma del Jurado

Firma del Jurado

Firma del Director del Trabajo de Grado

Bogot´a, Febrero de 2015.

3

A mis magn´ıficos padres, Roberto y Sonia. A mis hermanas Andrea y Tatiana. A mi querida Pilar. Carlos. A mi padre Emilio, mi monchita Anita, y mi magn´ıfica hermana Tico. Sin su dosis diaria de locura me ser´ıa imposible soportar la gravedad del mundo. Ferney.

4

Resumen Este libro condensa el desarrollo de un trabajo de grado realizado en el grupo de investigaci´ on LAMIC (Laboratorio de Autom´ atica e Inteligencia Computacional) desde finales del a˜ no 2013 hasta finales del a˜ no 2014, por parte de dos aspirantes al t´ıtulo de Ingeniero de Sistemas, para el primero de ellos, e Ingeniero Electr´ onico para el segundo. Del inter´es por los sistemas complejos como ´area de estudio en el grupo de investigaci´on, ha surgido la motivaci´ on de emplear t´ecnicas como los aut´omatas celulares en un trabajo previo y dos en curso, mientras en este caso ha sido por los sistemas multi-agente y el fen´omeno de flocking. Aqu´ı se presenta una propuesta de dise˜ no de un sistema multi-agente difuso basado en el modelo de flocking de Reynolds y un algoritmo evolutivo creado por los autores. Se emplea el sistema difuso para modelar a escala microsc´ opica un comportamiento de los agentes (cohesi´on-separaci´ on), que es ajustado por medio del algoritmo evolutivo y cuatro funciones objetivo basadas en medidas macrosc´opicas. Las cuatro funciones objetivo empleadas son: minimizar el RMSE de la separaci´on entre agentes y una distancia deseada, minimizar el RMSE del n´ umero de colisiones sumado con la conectividad relativa del flock, minimizar el RMSE de la desviaci´on de energ´ıa del flock y minimizar la entrop´ıa informacional de la se˜ nal de energ´ıa del flock. Con cada una de estas funciones se ejecutan 33 experimentos obteniendo un sistema difuso resultante por cada uno de ellos. Posteriormente son clasificados en cuatro categor´ıas diferentes seg´ un su desempe˜ no, donde el criterio es la formaci´ on de un flock cohesionado sin colisiones. Luego se elige la mejor funci´ on objetivo, es decir, la que produce en su mayor´ıa sistemas difusos que cumplen satisfactoriamente el criterio de evaluaci´on. De esta se toma alg´ un sistema difuso de los resultantes para recrear una din´ amica circular y una senoidal variando el n´ umero de agentes informados y no informados y se obtienen algunas medidas que son presentadas en tablas para su posterior comparaci´ on frente a las mismas provenientes del sistema multi-agente configurado matem´aticamente y el sistema multi-agente con un sistema difuso definido a priori. Espec´ıficamente se observa que la mejor funci´on objetivo es la basada en el n´ umero de colisiones y conectividad debido a que produce flocks cohesionados sin colisiones, mientras la basada en el RMSE de la separaci´ on promedio produjo los peores resultados, para sorpresa de los autores. Por otro lado se obtienen sistemas difusos que modelan el comportamiento de cohesi´on-separaci´on con un n´ umero de reglas que es inferior a la mitad de las empleadas en la literatura encontrada, lo cual tiene un impacto importante en cuanto a costo computacional se refiere. Finalmente los resultados muestran que s´ı es posible configurar comportamientos microsc´opicos a partir de observaciones macrosc´ opicos, a´ un cuando a priori no es posible establecer cu´al es la mejor forma de hacerlo (la mejor funci´ on objetivo).

5

Agradecimientos A la vida y su creador por permitirme llegar a este punto. A mi padre por sus ratos de conversaci´on que despertaron mi curiosidad y la motivaci´on por el estudio de la ciencia y la ingenier´ıa. A mis padres y hermanas por su gran apoyo y comprensi´on durante este largo proceso. A la Universidad Distrital Francisco Jos´e de Caldas por ampliar un poco mi visi´on de la vida y del mundo. A mis profesores y compa˜ neros de clase con quienes he compartido estos a˜ nos por sus ense˜ nanzas, cr´ıticas y motivaciones. Al profesor Helbert Esp´ıtia por sus consejos y motivaciones. Al profesor Miguel Melgarejo por invitarme a trabajar con ´el, por sus ense˜ nanzas, su dedicaci´ on y por los ratos de fruct´ıfera discusi´ on. Al grupo de investigaci´ on LAMIC, sus profesores y colegas. A Ferney Beltr´ an por su buena energ´ıa frente a las situaciones, su dedicaci´on, su paciencia y las largas conversaciones. A la Rama IEEE por albergarme durante varios a˜ nos porque conoc´ı personas geniales all´a. A Pilar Pinto por su amor, comprensi´ on y apoyo. Carlos. Ingresar a la Universidad fue para m´ı un gran reto y cuando esa victoria me fue concedida despu´es de un a˜ no de luchas, aprend´ı a valorar cada d´ıa en la Universidad Distrital; me entregu´e de lleno a los valores que la m´ usica, el deporte y mi familia me han brindado durante mi corto camino por la vida. Las experiencias que viv´ı son tan ricas y tan extensas que una hoja de papel es muy poco para lo que se podr´ıa contar, as´ı que me esforzar´e por nombrar a quienes han dejado una huella en m´ı para ser lo que soy hoy en d´ıa: A Jesus Peralta, Iv´ an Ria˜ no y Luis Alzate con quienes recorr´ı un gran camino entre clases, robots, risas, llantos, viajes a otras ciudades y pa´ıses, a ellos los valoro como parte de mi familia y la promesa de encontrarnos en los rincones del mundo perdurar´a como nuestra misma palabra, en la que conf´ıo plenamente. A Pilar Rodriguez, Lina Barrera, N´elida Hern´andez, Alejandra Rojas, Ana Lozano, Daisy Riveros, Laura Dur´an, Angie Casta˜ neda, Matilde Gasca, Karen Navarrete, Hasbleidy Hern´andez. Grandes mujeres de enorme coraz´ on y un car´ acter fuerte, ejemplo a seguir en medio de paradigmas tradicionalistas hacia las ingenieras; sin sus sabios consejos, ternura, comprensi´on, doble sentido y cari˜ no, hubiera perdido conocer la sensibilidad por la belleza del mundo que me rodea. A Carlos Mario Ramos, Jos´e Lara, Rafael Mu˜ noz, Manuel Cely, Oscar Perdomo, el gran Jesus Ramos, Juan David Reyes y otra gran cantidad de guerreros que luchamos codo a codo en nuestra cancha de f´ utbol; dejamos l´ agrimas, sudor y sangre en cada partido, aprendimos a valorar el sacrificio y el trabajo en equipo. Sin todos ustedes y el f´ utbol, tendr´ıa una parte de mi alma vac´ıa. A todos mis amigos y conocidos de la rama IEEE, con quienes tuve la fortuna de compartir un pedacito de historia, donde aprend´ı mucho sobre hacer m´as de lo que se espera y ver m´as all´ a del pa´ıs; especialmente a Edwin Hurtado y Luisa Quiroga, de quienes valoro inmensamente su sencillo coraje de luchar por los ideales de la humanidad que tanto se han olvidado. Al profesor Miguel Melgarejo, quien ha sido un modelo a seguir no s´olo en el ´ambito acad´emico, sino por la calidad de ser humano y el gran potencial social que me ha hecho a˜ norar en los escasos dos a˜ nos de trabajo conjunto, llevar´e sus ense˜ nanzas y amor por la patria a cada lugar que vaya. A mi gran compa˜ nero de Tesis Carlos Riveros, su paciencia y su calma ha sido vitales para desarrollar 6

este trabajo, la admiraci´ on y el respeto que tengo por ´el en estos tres a˜ nos me han hecho valorar la gran persona que es, he aprendido mucho de ´el y s´e que su vida estar´a llena de grandes logros. A profesores como Nadya Gonz´ alez, Hans L´opez, Juli´an Camargo, Pablo Rozo, Vladimir V´asquez, sus ense˜ nanzas trascendieron las aulas de clase y viven en mi forma de ser. Ha sido un gran placer empezar y terminar esta etapa de la vida en mi querida alma mater a la cual agradezco enormemente conocer tan hermosas personas y grandes experiencias en las aulas, los laboratorios, la sala IEEE, las canchas de f´ utbol, las calles, las fiestas, las ciudades, los d´ıas y las noches, los pa´ıses visitados, gracias a todo lo que ella me brind´o y trat´e de aprovechar al m´aximo. Ferney.

7

Tabla de Contenidos 1 Introducci´ on 13 1.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2. Soluci´ on propuesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3. Contenido del libro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Marco de referencia 2.1. Sistemas Complejos . . . . . . . . . . . . . . . 2.2. Sistemas Adaptativos Complejos (CAS) . . . . 2.3. Sistemas Multi-Agente (MAS) . . . . . . . . . . 2.4. Sistemas de Inferencia Difuso . . . . . . . . . . 2.5. Flocking . . . . . . . . . . . . . . . . . . . . . . 2.6. Sistema din´ amico de un modelo de flocking . . 2.7. Algoritmos de control de flocking . . . . . . . . 2.8. Sistemas difusos en los algoritmos de control de 2.9. Algoritmos de optimizaci´ on basados en abejas . 2.10. MASON . . . . . . . . . . . . . . . . . . . . . . 2.11. Resumen . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . flocking . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

3 Dise˜ no de un sistema multi-agente difuso empleando un basado en abejas 3.1. Soluci´ on propuesta . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Sistema multi-agente . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. Agente gamma (γ-agente) . . . . . . . . . . . . . . . . 3.2.2. Agentes informados y no informados . . . . . . . . . . 3.2.3. Dise˜ no del diagrama de clases UML . . . . . . . . . . 3.2.4. Implementaci´ on y ejecuci´on . . . . . . . . . . . . . . . 3.3. Sistema difuso . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4. Bee Algorithm (BA) . . . . . . . . . . . . . . . . . . . . . . . 3.5. Group Bee Algorithm (GBA) . . . . . . . . . . . . . . . . . . 3.6. Medidas globales . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1. Separaci´ on promedio entre vecinos (S(t)) . . . . . . . 3.6.2. Desviaci´ on de energ´ıa normalizada del flock (σE (t)) . 3.6.3. Conectividad relativa del flock (C(t)) . . . . . . . . . 3.6.4. Entrop´ıa de la desviaci´on de energ´ıa del flock H(σE ) . 3.6.5. N´ umero de colisiones del flock (Col) . . . . . . . . . . 3.7. Funciones objetivo . . . . . . . . . . . . . . . . . . . . . . . .

8

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

17 17 18 18 19 20 20 22 25 26 28 29

algoritmo evolutivo . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

30 30 30 32 33 33 34 36 37 40 43 43 44 45 45 45 46

3.7.1. Minimizar el RMSE de la separaci´on promedio entre vecinos y una separaci´on deseada sep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7.2. Minimizar el RMSE del n´ umero de colisiones sumado con la conectividad relativa del flock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7.3. Minimizar el RMSE de la desviaci´on de energ´ıa del flock . . . . . . . . . . . . 3.7.4. Minimizar la entrop´ıa informacional de la energ´ıa . . . . . . . . . . . . . . . . 3.8. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46 46 47 47 47

4 Experimentos y resultados 4.1. Etapa de evoluci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Etapa de comparaci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1. MAS con funci´ on potencial conformada por un sistema difuso 4.2.2. MAS con funci´ on potencial difusa definida a priori . . . . . . 4.2.3. MAS con funci´ on potencial matem´atica . . . . . . . . . . . . 4.2.4. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . evolucionado . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

48 48 50 50 50 52 53

5 Conclusiones y trabajo 5.1. Aportes originales . 5.2. Trabajo futuro . . . ANEXOS . . . . . . . . . BIBLIOGRAF´IA . . . . .

. . . .

. . . .

59 60 60 61 69

futuro . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

9

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Lista de Figuras 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11

3.12 3.13 3.14

3.15 3.16

Arquitectura de un Sistema de Inferencia Difuso. Tomado de [51]. . . . . . . . . . . Ejemplo de un flock de aves. Fuente: www.freefoto.com . . . . . . . . . . . . . . . . Vecindario de un agente dentro de un flock. Tomado de [19] . . . . . . . . . . . . . . Fuerzas de control actuando sobre un agente. Tomado de [44]. . . . . . . . . . . . . . Propuesta de funci´ on potencial entre agentes descrita por la ecuaci´on 2.13. Tomado de [48]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fen´ omeno de fragmentaci´ on. Tomado de [19]. . . . . . . . . . . . . . . . . . . . . . . Funciones de pertenencia del tama˜ no definidas en [38] . . . . . . . . . . . . . . . . . Funciones de pertenencia de la fuerza definidas en [38]. . . . . . . . . . . . . . . . . . Base de reglas del sistema difuso de [38]. . . . . . . . . . . . . . . . . . . . . . . . . . Base de reglas del sistema difuso que se utiliza en [32] y [33]. . . . . . . . . . . . . . Conjuntos difusos definidos en [32] y [33]. . . . . . . . . . . . . . . . . . . . . . . . . Base de reglas del sistema difuso que se define en [36]. . . . . . . . . . . . . . . . . . Conjuntos difusos empleados en [36]. . . . . . . . . . . . . . . . . . . . . . . . . . . . B´ usqueda de alimento en las abejas. Tomado de [58]. . . . . . . . . . . . . . . . . . . Bee Algorithm (BA). Tomado de [58]. . . . . . . . . . . . . . . . . . . . . . . . . . . Diagrama de la propuesta desarrollada. . . . . . . . . . . . . . . . . . . . . . . . . . Funci´ on de vecindad definida por la ecuaci´on 3.4. . . . . . . . . . . . . . . . . . . . . Funci´ on potencial definida por la ecuaci´on 3.5. . . . . . . . . . . . . . . . . . . . . . Diagrama de clases de los agentes informados y no informados. . . . . . . . . . . . . Diagrama de clases del agente gamma. . . . . . . . . . . . . . . . . . . . . . . . . . . Diagrama de clases de los comportamientos de los agentes. . . . . . . . . . . . . . . . Diagrama de clases de los agentes con sus comportamientos. . . . . . . . . . . . . . . Vista de ejecuci´ on del sistema multi-agente implementado usando MASON. . . . . . Vista del sistema multi-agente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Radio de visi´ on y vecinos de un agente en una topolog´ıa din´amica. . . . . . . . . . . Conexiones de un agente seleccionado con sus vecinos usando topolog´ıa din´amica.(Las lineas de lado a lado de las figuras se deben a que el entorno es toroidal y se encuentran vecinos situados en extremos del toroide.) . . . . . . . . . . . . . . . . . . . . . . . . Simulaci´ on del sistema multi-agente empleando topolog´ıa est´atica. Se observa la conexi´ on entre los agentes (l´ıneas) independientemente de su distancia espacial. . . . Conjunto difuso de tipo trapezoidal. . . . . . . . . . . . . . . . . . . . . . . . . . . . Partici´ on tipo Ruspini. Se observa c´omo se comparten par´ametros entre los distintos conjuntos para lograr la ocupaci´on total del universo de discurso y reducir el n´ umero de par´ ametros necesarios para definir el sistema difuso. . . . . . . . . . . . . . . . . . Dise˜ no de clases UML del sistema difuso. . . . . . . . . . . . . . . . . . . . . . . . . Abejas candidatas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

19 20 21 23 24 24 25 26 26 26 26 27 27 28 29 31 32 33 34 34 35 35 36 36 37

38 39 39

40 41 41

3.17 3.18 3.19 3.20 3.21

Abeja sobre un espacio unidimensional R

(3.4)

Se define una funci´ on potencial matem´atica no-negativa para el t´ermino Vij la cual est´ a en funci´on de la distancia ||xi − xj || entre dos agentes y regula su comportamiento de cohesi´ onseparaci´on. En la figura 3.3 se presenta la funci´on potencial definida en la ecuaci´on 3.5 que cumple los objetivos especificados en la secci´ on 2.7. Esta se basa en el comportamiento de la funci´ on potencial definida en la ecuaci´ on 2.13. ( Vij =

||x −x ||

−4 sin(π i2d j ) + 5 , 0 ≤ ||xi − xj || ≤ d ||x −xj ||−d −cos(π ∗ i R−d ) + 2 , d < ||xi − xj || ≤ R 3 , ||xi − xj || > R

(3.5)

Las constantes que acompa˜ nan a los t´erminos de realimentaci´on para los agentes informados se mantienen a lo largo de las simulaciones tal que c1 = 0.001 y c2 = 0.01. Estas se ajustaron de forma tal que se produjera un flock cohesionado y estable teniendo en cuenta la se˜ nal de control definida en 3.3.

3.2.1.

Agente gamma (γ-agente)

Este agente, u ´nico en todo el sistema multi-agente, modela el objetivo grupal o conocimiento interno (instinto) pose´ıdo por los agentes informados dentro del flock, y por tanto, no posee las caracter´ısticas y comportamientos mostrados en la tabla 3.1. Su din´amica, como se present´o en el cap´ıtulo anterior,

Figura 3.2: Funci´ on de vecindad definida por la ecuaci´on 3.4.

32

est´a representada por la ecuaci´ on 2.19 y es de quien depende el comportamiento de realimentaci´ on de navegaci´on presente en los agentes informados. Las din´amicas seleccionadas que describe este agente corresponden a una trayectoria circular y una senoidal.

3.2.2.

Agentes informados y no informados

Estos son agentes que poseen las caracter´ısticas y comportamientos mostrados en la tabla 3.1, sin embargo, los agentes informados, a diferencia de los no informados, cuentan con el comportamiento de realimentaci´ on de navegaci´ on que se describi´o en el cap´ıtulo anterior y se especifica por la ecuaci´ on 2.18. El entorno de simulaci´ on de los agentes es un espacio bidimensional toroidal de 350x350 pixeles.

3.2.3.

Dise˜ no del diagrama de clases UML

Seg´ un lo presentado en la tabla 3.1, las caracter´ısticas y comportamientos de los agentes son los mismos tanto para los informados como para los que no lo son, con la u ´nica excepci´on del comportamiento de realimentaci´ on de navegaci´on que s´olo pertenece a los agentes informados. A partir de lo anterior, el dise˜ no realizado se compone de una clase abstracta llamada Agente, donde se encuentran las caracter´ısticas de la tabla nombrada y de la que heredan la clase AgenteInformado y la clase AgenteNoInformado, como se muestra en la figura 3.4. Como el agente gamma no posee ninguna de estas caracter´ısticas, se propone la clase AgenteGamma fuera de esta jerarqu´ıa. Adem´as, debido a que existe un u ´nico agente gamma en el sistema multi-agente, se implementa el patr´on singleton en ella. Su dise˜ no se presenta en la figura 3.5. Con el fin de obtener modularidad en el dise˜ no de los comportamientos de los agentes, se propone crear una jerarqu´ıa de clases para agregar o eliminar comportamientos f´acilmente. Teniendo en cuenta esto se crea una clase abstracta llamada Comportamiento, de la cual heredan las clases Alineamiento, CohesionSeparaci´ on y Realimentaci´ on. Adicionalmente, como se explic´ o al final de la secci´on 2.6, existen dos tipos de topolog´ıas: la din´amica, cuando el vecindario de un agente dentro de un flock var´ıa con el tiempo, y la est´ atica, cuando el vecindario permanece constante, es decir, se mantienen los mismos vecinos independientemente de su distancia espacial. Estos dos tipos de vecindades se incluyen como comportamientos en este dise˜ no, que se encuentra en la figura 3.6. Debido a que los agentes se componen de los comportamientos previamente dise˜ nados, el diagrama definitivo se presenta en la figura 3.7.

Figura 3.3: Funci´ on potencial definida por la ecuaci´on 3.5.

33

Figura 3.4: Diagrama de clases de los agentes informados y no informados. Cabe anotar que no se incluyen la totalidad de variables o m´etodos implementados debido a la extensi´on del diagrama y a que el objetivo es describir u ´nicamente la arquitectura del dise˜ no realizado.

3.2.4.

Implementaci´ on y ejecuci´ on

Al implementar el dise˜ no del sistema multi-agente usando el conjunto de herramientas MASON descrito en la secci´ on 2.10 y la plataforma de desarrollo Eclipse, se obtiene la aplicaci´on de la figura 3.8. En esta se observan dos ventanas, la de la derecha hace parte de MASON y contiene en la pesta˜ na Model las configuraciones del sistema multi-agente mientras la de la izquierda muestra al sistema multi-agente en funcionamiento. Para explicar con m´ as detalle lo que se observa en esta segunda ventana se presenta la gr´afica de la figura 3.9. Los puntos rojos representan a los agentes informados y los verdes a los no informados. El punto azul encerrado por el c´ırculo rojo contiene al l´ıder virtual, u ´nico en el sistema multi-agente. Las l´ıneas entre ellos muestran las conexiones existentes con sus vecinos, determinadas por su radio de visi´on, como se observa en la figura 3.10. La simulaci´ on mostrada en este caso usa una topolog´ıa din´amica. Para visualizar f´acilmente c´omo var´ıan las conexiones entre los agentes conforme avanza la simulaci´on, se procede a seleccionar alg´ un agente y observar en distintos instantes de tiempo su configuraci´on con sus vecinos. Esto se presenta en la figura 3.11. La vista de una simulaci´ on con topolog´ıa est´atica se encuentra en la figura 3.12. Se observa,

Figura 3.5: Diagrama de clases del agente gamma. 34

Figura 3.6: Diagrama de clases de los comportamientos de los agentes.

Figura 3.7: Diagrama de clases de los agentes con sus comportamientos. como se mencion´ o en la secci´ on anterior, que independientemente de la distancia espacial un agente conserva las conexiones con los mismos vecinos. En principio se implement´ o el sistema multi-agente sin incluir un sistema difuso en el comportamiento de cohesi´ on-separaci´ on, es decir, se implementaron los comportamientos como se describen en la secci´on 2.7, lo que al cabo de un tiempo de simulaci´on permiti´o la emergencia del flock que se muestra al lado izquierdo de la figura 3.8.

35

Figura 3.8: Vista de ejecuci´ on del sistema multi-agente implementado usando MASON.

Figura 3.9: Vista del sistema multi-agente.

3.3.

Sistema difuso

Como se explic´ o en la secci´ on 2.4, un sistema difuso se compone de cuatro partes: un fusificador, un motor de inferencia, una base de reglas y un defusificador. Todo esto puede representarse como una funci´on y = f (x) donde y representa la salida del defusificador y f (x) una funci´on no lineal conocida como Expansi´ on de Funciones de Base Difusa (EFBD). El sistema difuso reemplaza la funci´on potencial de cada agente, por tanto tiene una entrada (distancia entre vecinos) y una salida (fuerza de cohesi´on-separaci´on). Se define un sistema difuso 36

Figura 3.10: Radio de visi´ on y vecinos de un agente en una topolog´ıa din´amica. de tres reglas con el fin de representar este comportamiento de forma sencilla e interpretable. El fusificador empleado es de tipo singleton, el motor de inferencia es de tipo producto, el defusificador es por promedio de centros y los conjuntos difusos definidos para los antecedentes y consecuentes de las reglas son de tipo pseudo-trapezoidal como se muestra en la figura 3.13, es decir que cada conjunto necesita 4 par´ ametros (A, B, C, D) siguiendo el esquema pseudo-trapezoidal de conjuntos difusos [53]. Con el fin de asegurar la ocupaci´ on del dominio del universo de discurso completamente, es decir, que no queden espacios en el dominio que no pertenezcan a ning´ un conjunto, se emplea una partici´on de tipo Ruspini cuya forma se muestra en la figura 3.14. De este modo, se observa al conjunto rojo compartir dos par´ ametros (C y D) con el conjunto verde y este a su vez dos con el azul (E y F), lo que ocasiona que el n´ umero de par´ametros para definir los tres conjuntos difusos se reduzca a 8 (A, B, C, D, E, F, G, H). Finalmente, como se conoce el dominio de la variable ling¨ u´ıstica (radio de visi´ on de 0 a 8) no son necesarios los par´ametros A y H, terminando en un total de 6 par´ametros para definir los 3 conjuntos difusos. Este m´etodo descrito se emplea para reducir el n´ umero de par´ ametros necesarios a ser buscados por el algoritmo evolutivo que se explicar´a en la siguiente secci´ on. El resumen de las caracter´ısticas del sistema difuso a utilizar se encuentran en la tabla 4.2 y el dise˜ no del diagrama de clases UML se presenta en la figura 3.15. En la tabla 3.2 se observa que se emplear´an 3 conjuntos difusos en el antecedente (12 par´ametros) y 3 en el consecuente (3 par´ ametros para los centros) para una u ´nica entrada, por tanto, la cantidad de par´ametros para definir el sistema difuso es 15. Sin embargo, la cantidad de par´ametros a buscar por el algoritmo evolutivo ser´ a 9 (B, C, D, E, F y G para los conjuntos del antecedente y 3 par´ametros para los centros de los consecuentes), por motivo de las particiones Ruspini.

3.4.

Bee Algorithm (BA)

En la secci´on 2.9 se explic´ o el funcionamiento del Bee Algorithm. En este, cada abeja es candidata a convertirse en el punto ´ optimo de una funci´on objetivo, es decir, cada abeja se mueve en el espacio al que pertenece la funci´ on y codifica en el valor de su posici´on el posible punto ´optimo. Los procedimientos ejecutados en cada generaci´on se resumen en la figura 2.15 y los par´ametros del algoritmo en la tabla 2.1. A partir de esto es posible deducir la cantidad de evaluaciones realizadas por el algoritmo sobre la funci´ on objetivo de la siguiente forma: Una vez se disponen las abejas en el espacio de b´ usqueda como se muestra en la figura 2.15a, deben realizarse n evaluaciones sobre la funci´on objetivo para elegir las m con mejor fitness sobre las que se crean vecindarios de tama˜ no ngh. Posteriormente se eligen los e mejores sitios dentro de 37

(a) Step 0 de la simulaci´ on

(b) Step 14 de la simulaci´on

(c) Step 35 de la simulaci´ on

(d) Step 56 de la simulaci´on

Figura 3.11: Conexiones de un agente seleccionado con sus vecinos usando topolog´ıa din´amica.(Las lineas de lado a lado de las figuras se deben a que el entorno es toroidal y se encuentran vecinos situados en extremos del toroide.)

38

Figura 3.12: Simulaci´ on del sistema multi-agente empleando topolog´ıa est´atica. Se observa la conexi´on entre los agentes (l´ıneas) independientemente de su distancia espacial.

Figura 3.13: Conjunto difuso de tipo trapezoidal. los que se sit´ uan nep abejas y sobre los restantes nsp abejas, por lo que se efect´ uan respectivamente nep y nsp evaluaciones de la funci´ on objetivo para elegir las mejores en cada sitio. Finalmente se conservan las abejas elegidas y se crean nuevas para la siguiente generaci´on. Por tanto, el n´ umero total de evaluaciones de la funci´ on objetivo est´a dado por la ecuaci´on 3.6. evaluaciones = (n + (e ∗ nep) + ((m − e) ∗ nsp)) ∗ generaciones

(3.6)

Entre mayor sea la cantidad de operaciones a realizarse, mayor ser´a el tiempo que tarde la ejecuci´on del algoritmo. Debido a que este trabajo requiere desarrollar una cantidad de experimentos que permitan proporcionar conclusiones basadas en an´alisis estad´ısticos, el tiempo es un factor 39

Figura 3.14: Partici´ on tipo Ruspini. Se observa c´omo se comparten par´ametros entre los distintos conjuntos para lograr la ocupaci´ on total del universo de discurso y reducir el n´ umero de par´ametros necesarios para definir el sistema difuso. relevante, por lo que surge la propuesta de un algoritmo evolutivo basado en el BA que reduzca el espacio de b´ usqueda, llamado Group Bee Algorithm (GBA).

3.5.

Group Bee Algorithm (GBA)

Un algoritmo se considera evolutivo si posee las siguientes tres caracter´ısticas [60] [61]: • Mecanismo de variaci´ on: consiste en alguna estrategia (mutaci´on o recombinaci´on, o ambas) para introducir cambios en las entidades que codifican los posibles puntos ´optimos. • Mecanismo de selecci´ on: busca elegir de alguna forma, entre todas las posibles entidades, las mejores seg´ un el problema. • Mecanismo de retenci´ on: garantiza que la evoluci´on ocurra conservando las mejores entidades para la siguiente generaci´ on. El algoritmo propuesto funciona de la siguiente forma: Consid´erese una funci´on objetivo de d variables reales que debe minimizarse, por tanto los posibles valores ´optimos deben buscarse en un espacio