Cálculo de rutas en Sistemas de E-Learning utilizando un algoritmo de optimización por colonias de hormigas

CÁLCULO DE RUTAS EN SISTEMAS DE E-LEARNING UTILIZANDO UN ALGORITMO DE OPTIMIZACIÓN POR COLONIAS DE HORMIGAS D EPARTAMENTO DE L ENGUAJES Y S ISTEMAS I NFORMÁTICOS Memoria de Tesis Doctoral para optar al grado de Doctor en Informática por la Universidad de Sevilla presentada por José Manuel Márquez Vázquez Directores: Dr. Juan Antonio Ortega Ramírez Dr. Luis González Abril Sevilla, marzo de 2012 Cálculo de rutas en sistemas de e-learning utilizando algoritmos de Optimización por Colonias de Hormigas José Manuel Márquez Vázquez Cálculo de Rutas en Sistemas de e-Learning Utilizando Algoritmos de Optimización por Colonias de Hormigas José Manuel Márquez Vázquez Memoria de Tesis i Índice Agradecimientos ............................................................................................................. xv Prólogo ............................................................................................................................. 1 Capítulo 1. Introducción ................................................................................................... 3 1.1 Planteamiento ..................................................................................................... 5 1.2 Objetivos ............................................................................................................ 7 1.3 Período de Investigación .................................................................................... 9 Capítulo 2. Optimización por Colonias de Hormigas..................................................... 15 2.1 Introducción ..................................................................................................... 15 2.2 Características Principales ............................................................................... 18 2.3 La meta-heurística ACO .................................................................................. 20 2.4 Algoritmos ACO .............................................................................................. 22 2.5 Aplicación a problemas estáticos de optimización .......................................... 25 2.5.1 El Problema del Viajante .......................................................................... 25 2.5.2 El Problema de la Asignación Cuadrática ................................................ 33 2.5.3 El Problema de la Planificación de la Producción .................................... 35 2.5.4 El Problema del Enrutamiento de Vehículos ............................................ 35 2.5.5 El Problema del Ordenamiento Secuencial .............................................. 38 2.5.6 El Problema de Coloreado de Grafos ....................................................... 39 2.5.7 El Problema de la Supersecuencia Común más Corta .............................. 39 2.6 Aplicación a problemas dinámicos de optimización ....................................... 40 2.6.1 Aplicación al encaminamiento orientado a la conexión ........................... 41 2.6.2 Aplicación al encaminamiento no orientado a la conexión ...................... 43 2.7 Aplicación a la resolución de problemas multi-objetivos ................................ 45 2.7.1 Introducción a problemas multi-objetivos ................................................ 45 2.7.2 Adaptación de ACO a problemas multi-objetivos .................................... 48 Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje. ................................. 55 3.1 Escenario .......................................................................................................... 55 ii 3.2 Estudios previos ............................................................................................... 56 3.3 Propuesta de solución ...................................................................................... 57 3.3.1 Grafo de Itinerarios de Aprendizaje ......................................................... 58 3.3.2 Representación formal del grafo............................................................... 62 3.3.3 Transformación del Grafo ........................................................................ 70 3.3.4 Adaptación del mejor camino ................................................................... 74 3.3.5 Implementación ........................................................................................ 85 Capítulo 4. Resultados experimentales ......................................................................... 109 4.1 Entorno de pruebas ........................................................................................ 109 4.2 Descripción de la experimentación ................................................................ 109 4.2.1 Consideraciones previas ......................................................................... 110 4.2.2 Calibración del Sistema .......................................................................... 127 4.2.3 Estudio de la adaptabilidad ..................................................................... 153 Capítulo 5. Incorporación de itinerarios adaptativos a un LMS ................................... 169 5.1 Arquitecturas de los sistemas de enseñanza a distancia ................................ 169 5.2 Pasos para la adaptación de un LMS SCORM .............................................. 176 5.3 Implantación de plataformas de e-learning en SOA ...................................... 181 5.3.1 El Portal de e-learning ............................................................................ 186 5.3.2 Proveedor de Servicios de e-learning ..................................................... 192 5.3.3 Registro de Servicios de e-learning ........................................................ 194 5.3.4 Gestión de Itinerarios Adaptativos como Servicio Web ........................ 196 Capítulo 6. Conclusiones y trabajo futuro .................................................................... 199 6.1 Retrospectiva ................................................................................................. 199 6.2 Conclusiones .................................................................................................. 201 6.3 Aplicaciones ................................................................................................... 203 6.3.1 Adaptación del itinerario al estilo de aprendizaje del alumno................ 203 6.3.2 Recomendación del siguiente curso ....................................................... 209 6.4 Trabajo Futuro ............................................................................................... 210 Curriculum Vitae .......................................................................................................... 211 Referencias ................................................................................................................... 219 Anexo ........................................................................................................................... 231 iii Índice de Figuras Figura 1: Estudio de compatibilidad IMS CP y OSGi ................................................... 11 Figura 2: Dibujo que representa el experimento del puente binario de Deneubourg. .... 16 Figura 3: Representación del experimento con caminos alternativos de diferente longitud. 1. La primera hormiga sigue un camino elegido aleatoriamente. 2. El resto de la colonia se distribuye entre los caminos posibles. 3. Finalmente la mayor concentración de feromonas en los caminos más cortos hace que prácticamente todas sigan el mismo camino. .................................................................................................. 17 Figura 4: Algoritmo AS para el TSP. (M. Dorigo et al., 1996) ...................................... 23 Figura 5: Representación de una variante del VRP con depósito único central ............. 37 Figura 6: Incidencias que superan SLA frente al coste en técnicos de soporte .............. 46 Figura 7: Grafo de Itinerarios de Aprendizaje (GIA) ..................................................... 58 Figura 8: Identificación de competencias en el grafo de itinerarios de aprendizaje ....... 60 Figura 9: Ejemplo de grafo para itinerarios de aprendizaje independientes................... 60 Figura 10: Ejemplo de Grafo de Itinerarios de Aprendizaje .......................................... 71 Figura 11: Grafo equivalente sin restricciones ............................................................... 71 Figura 12: Diagrama de estados del itinerario de aprendizaje........................................ 73 Figura 13: Nodos del GIA ponderados con pesos pedagógicos ..................................... 77 Figura 14: Ejemplo de restricción OR ............................................................................ 78 Figura 15: Árbol de probabilidades conjuntas ................................................................ 79 Figura 16: Ejemplo de tabla hash con información a incluir en el nodo destino para calcular el factor de idoneidad de cada arco de entrada ................................................. 81 Figura 17: Jerarquía de Interfaces para el manejo de grafos de JUNG .......................... 86 Figura 18: Jerarquía de nuestro modelo para la definición de vértices y arcos .............. 86 Figura 19: Principales entidades del framework ACO ................................................... 89 Figura 20: Relaciones del planificador con otras interfaces del framework .................. 90 Figura 21: Esquema para la generación de números aleatorios fuera de un rango dado ...................................................................................................................................... 100 Figura 22: Distribución teórica de calificaciones antes y después de la formación ..... 110 Figura 23: Colonia de alumnos como ampliación de una Colonia genérica ................ 112 iv Figura 24: Aplicación ACO4ALI desarrollada para la experimentación ..................... 113 Figura 25: Función de densidad de probabilidad de un modelo normal N(4,0.5) ........ 114 Figura 26: Función de densidad de probabilidad de un modelo normal N (6,0.5) ....... 114 Figura 27: Función de densidad de probabilidad de un modelo normal N (8,05) ........ 115 Figura 28: Grafo utilizado para probar la estrategia de asignación de pesos iguales a todos los nodos. ............................................................................................................ 117 Figura 29: Evolución de la elecciones de caminos en una de las pruebas del experimento con alumnos de perfil High .......................................................................................... 119 Figura 30: Evolución de las elecciones de caminos en una de las pruebas del experimento con alumnos de perfil Medium ................................................................ 120 Figura 31: Evolución de las elecciones de caminos en una de las pruebas del experimento con alumnos de perfil Low ...................................................................... 120 Figura 32: Comparativa de la evolución de hormigas que seleccionaron el camino solución en los tres experimentos anteriores ................................................................ 121 Figura 33: Evolución de elecciones de caminos en una de las ejecuciones para la prueba de colonia heterogénea con proporciones 30-60-10 ..................................................... 122 Figura 34: Comparativa entre desviaciones típicas para las dos estrategias de ponderación en colonias con perfiles heterogéneos. .................................................... 125 Figura 35: Evolución de una de las ejecuciones de la experimentación para la estrategia de ponderación en función del nivel de dificultad en una colonia con hormigas de diferentes perfiles ......................................................................................................... 126 Figura 36: Grafo ponderado con 8 posibles itinerarios ................................................ 126 Figura 37: Evolución de las elecciones de cada itinerario en algunas pruebas realizadas con el algoritmo para el grafo de la Figura 36. En el eje de ordenadas se muestra el número de veces que cada itinerario ha sido elegido, y en el de abscisas el número de hormigas ACO que han terminado su itinerario. .......................................................... 128 Figura 38: Grafo de itinerarios de aprendizaje una vez eliminadas las restricciones de navegación .................................................................................................................... 129 Figura 39: Nodo de decisión para el cálculo de la influencia del parámetro β ............ 132 Figura 40: Estudio marginal de β. Reparto de itinerarios para β=1.............................. 134 Figura 41: Estudio marginal de β. Reparto de itinerarios para β=0.5........................... 134 Figura 42: Estudio marginal de β. Reparto de itinerarios para β=5.............................. 136 Figura 43: Estudio marginal de β. Reparto de itinerarios para β=2.............................. 136 Figura 44: Evolución de la distribución de hormigas por los itinerarios del grafo para α=0 y β=1.5 ................................................................................................................... 139 v Figura 45: Evolución de la distribución de hormigas por los itinerarios del grafo para α=1.0 y β=1.5 ................................................................................................................ 140 Figura 46: Evolución de feromonas τ en el primer nodo de decisión del grafo de la Figura 38 ....................................................................................................................... 142 Figura 47: Evolución de feromonas Φ en el primer nodo de decisión del grafo de la Figura 38 ....................................................................................................................... 142 Figura 48: Evolución de la f ij en el primer nodo de decisión de la Figura 38 .............. 142 Figura 49: Evolución del porcentaje de elección de cada itinerario en cada iteración. En cada iteración participan 100 hormigas. α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02; ω 3 =1.0. ...... 146 Figura 50: Evolución de feromonas τ y ϕ en cada iteración. α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02 y ω 3 =1.0 ......................................................................................................... 147 Figura 51: Evolución de la función de ajuste en 10 iteraciones con α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02 y ω 3 =1.0 ............................................................................................ 147 Figura 52: Evolución del porcentaje de elección de cada itinerario en cada iteración. En cada iteración participan 100 hormigas. α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02 y ω 3 =2.0. .... 148 Figura 53: Evolución de feromonas τ y ϕ en cada iteración. α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02 y ω 3 =2.0 ......................................................................................................... 149 Figura 54: Evolución de la función de ajuste en 10 iteraciones. α=1.0; β=1.5; ω 1 =1.0; ω 2 =0.02 y ω 3 =2.0 ......................................................................................................... 150 Figura 55: Ejemplo de comportamiento del algoritmo ASALI para los valores α=1.2, β=1.5, ω 1 =1.0, ω 2 =0.02, ω 3 =1.5 y ρ=0.5 ..................................................................... 151 Figura 56: Probabilidad de decisión para los arcos Link2 (N3N5), Link3 (N3N6) y Link4 (N3N7) en el experimento anterior. ............................................................... 153 Figura 57: Elecciones de itinerarios tras la primera iteración (estado inicial). ............ 158 Figura 58: Distribución inicial de feromonas en los arcos del grafo de itinerarios de aprendizaje. ................................................................................................................... 158 Figura 59: Comparativa en los experimentos E7, E8 y E9. .......................................... 161 Figura 60: Comparativa en los experimentos E10, E11 y E12. .................................... 162 Figura 61: Resultados tras cinco ejecuciones con alumnos de perfil escogido aleatoriamente ............................................................................................................... 163 Figura 62: Relación del Coeficiente de Gini y la Curva de Lorenz ............................. 164 Figura 63: Porcentaje de alumnos que eligen H, I y J en la segunda promoción en función del valor de α ................................................................................................... 166 Figura 64: Porcentaje de éxito de los itinerarios H, I y J respecto a la variación del parámetro α en la segunda promoción .......................................................................... 168 xii RFC Requests For Comments RSS Really Simple Syndication SCO Shareable Content Object SCORM Shareable Content Object Reusable Model SCSP Shortest Common Supersequence Problem SLA Service Level Agreement SMTP Simple Mail Transfer Protocol SOA Service Oriented Architecture SOAP Simple Object Access Protocol SOP Sequential Ordering Problem SQL Structured Query Language TSP Travelling Salesman Problem UML Unified Modeling Language VPN Virtual Private Network VRP Vehicle Routing Problem WADL Web Application Description Language WS-CDL Web Services Choreography Description Language WSDL Web Service Description Language WWW World Wide Web XML Extensible Markup Language XPDL XML Process Definition Language XSD XML Schema Definition xiii Índice de símbolos más utilizados Símbolo Descripción α Parámetro que controla la capacidad de un algoritmo ACO para explorar nuevos caminos. Es un potenciador del efecto de las feromonas. β Parámetro que controla la capacidad de un algoritmo ACO para explotar los caminos encontrados en base a la función heurística del problema. Es un potenciador del valor heurístico. ε Calificación obtenida en la evaluación final de un curso. η Función heurística de un problema. ρ Coeficiente de evaporación de las feromonas. φ Valor unitario de una feromona depositada por un alumno en un arco. τ Feromonas depositadas por el algoritmo ACO durante el cálculo de la solución óptima. ω Variable de calibración. Φ Cantidad de feromonas φ depositadas en un arco en un instante determinado. Es dependiente de la calificación obtenida. A i [] Tabla de decisión del nodo i a ij (t) Elemento de la tabla de decisión A i [] que indica la probabilidad de ser elegido el arco que va del nodo i al nodo j. F Función de ajuste. Es utilizada como función heurística que determina la distancia entre cursos. N i Conjunto de nodos vecinos al nodo i. xiv xv Agradecimientos En primer lugar, quiero agradecer la insistencia de mi madre y mi tía, que aunque rozando el agobio, han conseguido mantener en mí el espíritu de superación y sacrificio necesario para seguir adelante con esta dura tarea. Gracias. Otro tanto por ciento significativo de mis agradecimientos son sin duda para Juan Antonio, Luis y Paco. Ellos son los que en los momentos de desánimo, cuando he estado a punto de tirarlo todo por la borda, han sabido darme los ánimos necesarios para seguir adelante. Gracias. Y por último, y no menos importante, a mi esposa, Isabel, que ha sufrido como nadie mi falta de dedicación, mis momentos de ansiedad y mi ausencia en todos estos años. Mil gracias. xvi Prólogo 1 Prólogo Esta tesis doctoral se enmarca dentro del campo del razonamiento automático y es fruto de la evolución de la investigación, a partir de un proyecto fin de carrera y su ampliación durante el período investigador del doctorado en su participación en proyectos de investigación europeos del VI Programa Marco. Durante este período se propuso una arquitectura orientada a servicios [1], basada en la especificación OSGi (inicialmente siglas de Open Services Gateway Initiative, http://www.osgi.org), para los sistemas de gestión del aprendizaje o LMS (del inglés Learning Management System) y se implementó un reproductor de cursos que incorporaba capacidades de adaptación y recomendación de contenidos según el perfil del usuario (alumno). Los perfiles de usuario eran bastante simples y se reducían a “usuario con necesidades especiales de visión”, “usuario con necesidades especiales de audición” y “usuario estándar”, además de un complemento adicional de personalización relativo a “gustos musicales” y “gustos de fondo de escritorio”. A raíz de este trabajo previo, surgió la hipótesis de que los perfiles de usuario no estuvieran limitados a hándicaps o a gustos, sino que también pudiera tenerse en cuenta el ritmo de aprendizaje o una clasificación en función del aprovechamiento de cursos anteriores. Para ello era necesaria la existencia de una secuencia de cursos, y así nació el escenario del itinerario formativo. Este escenario además parecía en un principio adecuado para resolver un problema detectado en nuestra primera aproximación a la adaptación de contenidos educativos. En nuestro trabajo de investigación anterior, la adaptación se realizaba por el reproductor del curso, estando los contenidos alternativos incluidos dentro del propio paquete de contenidos, creímos que este enfoque no era escalable si el número de perfiles de usuario y sus características aumentaban considerablemente. La posibilidad de describir itinerarios formativos con caminos alternativos y poder procesarlos para calcular el camino adecuado para cada alumno en función de sus necesidades de aprendizaje (ritmo, nivel de aprovechamiento, etc.) y luego aplicar las técnicas de adaptación de contenidos ya utilizadas, dio lugar al trabajo expuesto en esta tesis. 2 Capítulo 1. Introducción 3 Capítulo 1. Introducción Como indica el profesor Castells [2], la aparición de la sociedad informacional ha tenido un impacto de una magnitud similar al que tuvo en su momento la Revolución Industrial. Para Castells, la información, en su sentido más amplio, es decir, como comunicación del conocimiento, ha sido fundamental en todas las sociedades, por eso no es correcto llamar a la sociedad actual, sociedad de la información. En contraste, Castells establece un paralelismos con la distinción entre industria e industrial, para definir el atributo informacional cómo la forma específica de organización social en la que generación, el procesamiento y la transmisión de la información se convierten en las fuentes fundamentales de la productividad y el poder, debido a las nuevas condiciones tecnológicas que surgen en este nuevo período histórico. En efecto, la aparición de Internet permitió por primera vez la comunicación de muchos a muchos en un tiempo acordado y a una escala global. Su impacto en la sociedad ha sido tal que actualmente las principales actividades sociales, políticas, económicas y culturales del mundo están presentes y se organizan en Internet. Incluso podemos decir que la economía de los países desarrollados es dependiente de Internet, puesto que la desaparición de esta red ocasionaría una crisis económica inimaginable. Con la misma velocidad que Internet ha penetrado en la sociedad desarrollada han ido apareciendo un gran número de sistemas de información destinados al aprendizaje. Su impacto en el plano laboral es igualmente considerable, al contar la mayoría de las grandes empresas con un departamento de formación que ofrece cursos online a sus empleados a través de un sistema de aprendizaje online, favoreciendo así la movilidad de éstos y la personalización de la formación a las necesidades de cada empleado. En algunos casos, los usuarios reciben la formación solicitada bajo demanda, cuando lo necesitan. En los últimos años, la explosión global de la telefonía móvil ha abierto un nuevo horizonte para la educación a distancia a través de medios electrónicos, más conocida como e-learning. Con la llegada de dispositivos móviles cada vez más versátiles, redes de comunicaciones con mayor ancho de banda y el acceso a Internet desde un dispositivo móvil, la diferenciación que durante la última época se hacía entre las apliaciones de e-learning y de m-learning ha quedado carente de sentido. Hasta ahora se denominaba m-learning (del inglés mobile learning) a la metodología de Capítulo 1. Introducción 4 enseñanza y aprendizaje que se vale del uso de pequeños dispositivos móviles como teléfonos, agendas electrónicas y en general todo dispositivo de mano que tenga alguna forma de conectividad inalámbrica, ya sea autónoma o dependiente de un punto de acceso auxiliar. Se establecía una diferenciación con las metodologías e-learning por las limitaciones tecnológicas introducidas por los propios dispositivos o las redes de comunicaciones, que hacían inviables ciertos tipos de contenidos. Pero ahora con la aparición de los teléfonos inteligentes y tabletas (tablet pc) la frontera entre e-learning y m-learning ha desaparecido claramente, especialmente desde la fuerte irrupción de los tablet pc, si bien aún la tecnología soportada por todos los modelos difiere bastante como para aún necesitar un desarrollo personalizado para cada dispositivo. Desarrollar un mismo curso y reproductores de contenidos para diferentes dispositivos encarece el producto de software, debido al mayor coste del desarrollo, de la gestión del proyecto y del mantenimiento asociado a las diferentes versiones. La necesidad de contar con sistemas de e-learning capaces de ofrecer cursos para cualquier dispositivo móvil es una prioridad para las empresas de hoy. La integración con un sistema de información móvil empresarial permitiría no sólo el acceso bajo demanda de los empleados a cursos de formación especialmente adaptados para su dispositivo móvil, sino que en algunos casos (dependiendo del tipo de dispositivo) podría facilitar la distribución de cursos formativos simultáneamente a un amplio número de empleados cuando la empresa así lo necesite, por ejemplo mediante el protocolo PAP 1 . Estas características aportan un alto valor añadido a los sistemas de información corporativos actuales. Sin embargo, en las empresas actuales es muy habitual que convivan aplicaciones y sistemas de información adquiridos o desarrollados a medida, según las necesidades de la empresa en cada momento, dando lugar a ecosistemas difíciles de gestionar y dificultando la integración de nuevos sistemas [3]. Si tenemos en cuenta que los gastos de integración superan en una proporción de entre cinco y veinte a los de desarrollo de nueva funcionalidad [4] no es despreciable tener en cuenta un enfoque de arquitectura orientada a servicios (SOA – Service Oriented Architecture) que facilite la integración de un LMS en el ecosistema tecnológico de la empresa. Hasta ahora, la mayoría de los LMS existentes han adoptado SCORM (Shareable Content Object Reference Model) como estándar de facto para el intercambio de sus contenidos educativos [5]. SCORM combina varias especificaciones (de IMS, IEEE y AICC principalmente) y las particulariza para un caso concreto como 1 Push Access Protocol. Wireless Application Protocol Forum, WAP-247-PAP-20010429-a, version 29 de Abril de 2001. http://www.openmobilealliance.org/tech/affiliates/wap/wap-247-pap-20010429-a.pdf Capítulo 1. Introducción 5 es el aprendizaje sobre la Web. SCORM define como secuenciar los contenidos dentro de un curso, como empaquetarlos, el marco de ejecución e incluso el protocolo de comunicación entre los contenidos de un curso con el LMS, lo que facilita que cualquier curso SCORM pueda utilizarse en cualquier LMS compatible. Sin embargo, dada la explosión exponencial del número de cursos de libre disposición en Internet y la creación de almacenes de contenidos didácticos, la problemática acerca de cómo organizar itinerarios compuestos por un conjunto de cursos, o como recomendar el curso más apropiado para cumplir con un cierto itinerario de formación, ha recabado el interés de la comunidad científica en la última década. 1.1 Planteamiento De acuerdo con Brusilovsky [98], la adaptabilidad es de gran importancia en los procesos de enseñanza-aprendizaje online, debido a la potencial gran diversidad de la audiencia en cuanto a objetivos, estilos de aprendizaje, andamiaje cognitivo y necesidades especiales. Frente al clásico enfoque de un mismo curso o mismo itinerario para todos los alumnos, surge así la aproximación que se ha denominado Aprendizaje Adaptativo [6][8]. En los últimos años el interés se ha centrado tanto en la adaptación y recomendación de los contenidos internos de los cursos [9]-[11] como en la organización del itinerario completo [12], [13]. El entorno de aprendizaje, como elemento de comunicación adquiere un papel relevante, convirtiéndose en instrumento de ayuda a los alumnos mediante adaptaciones de presentación de los contenidos y navegación para crear rutas de aprendizaje adaptadas a cada individuo. Ejemplos de adaptaciones de presentación son: proporcionar enlaces a explicaciones adicionales o ampliaciones que el alumno puede consultar a voluntad, ofrecer explicaciones comparativas que enfaticen las similitudes de los conceptos explicados con otros conocidos por el alumno, y ofrecer los conceptos ordenados por orden de relevancia [99], [100]. Las adaptaciones de presentación de los contenidos pueden afrontarse principalmente desde dos puntos de vista, siempre intentando ajustarse al estándar de facto de la industria, SCORM: desde fuera del paquete de contenidos, generando el LMS el paquete de contenidos ya adaptado a las necesidades del alumno [10], [13], o desde dentro del propio paquete de contenidos, incluyendo las reglas de adaptación necesarias [14]. Ambas soluciones concretan las necesidades en grupos que son Capítulo 1. Introducción 12 Desde que a finales de los 80, M. Hammer propusiera el concepto de reingeniería de procesos para mejorar los procesos de negocio de las empresas [5], se han propuesto numerosas técnicas para modelarlos, facilitando así la comprensión de los mismos y, en su caso, ayudar a la mejora de éstos para alcanzar sus objetivos de manera más eficaz y eficiente. El consorcio Workflow Management Coalition (http://www.wfmc.org/) ha establecido diferentes normas para poder compartir información entre sistemas de este tipo. Actualmente, el uso de XML (eXtensible Markup Language, http://www.w3.org/XML/) en su especificación XPDL (XML Process Definition Language. http://www.wfmc.org/xpdl.html), es el formato preferido para representar de forma textual los modelos de los procesos de negocio, y algunos trabajos recientes ya plantean escenarios para e-learning [21]. Aunque existen muchas técnicas de representación gráfica de los procesos, la notación de UML (Unified Modeling Language. http://www.uml.org) es la más utilizada. Para salvar las limitaciones que SCORM conlleva nació la especificación IMS LD (IMS Learning Design, http://www.imsglobal.org/learningdesign/). IMS LD define cómo describir y codificar las metodologías de aprendizaje y cómo incorporarlas en una solución e-learning. Soporta el uso de un amplio rango de pedagogías para aprendizaje on-line y permite definir nuevas metodologías pedagógicas haciendo uso de un lenguaje genérico y flexible diseñado para permitir la definición de muchas pedagogías diferentes. La Versión 1 es la única hasta la fecha, y fue publicada en Enero de 2003. IMS LD fue muy bien recibida por los educadores, especialmente pedagogos, pues su objetivo radica más en el diseño de pautas metodológicas que en la mera distribución de los contenidos. Algunos de los LMS ya la soportan pero no acaba de imponerse a SCORM por su mayor coste de producción de los cursos, falta de herramientas, y mayor complejidad técnica. IMS LD define su meta-modelo utilizando notación UML y proporciona la definición formal para el modelado de procesos de enseñanzaactividades en un esquema XSD (XML Schema Definition. http://www.w3.org/XML/). Ante la carencia de herramientas de autor (modelado de procesos de enseñanza-aprendizaje, edición itinerarios formativos, creación y edición de contenidos…) conformes con IMS LD y la abundancia de herramientas de gestión de procesos de negocio, la idea es clara: cómo transformar procesos IMS LD en XPDL [22]. Esta es una de las líneas de investigación abiertas recientemente en relación con nuestro trabajo. Capítulo 1. Introducción 13 Otra línea de investigación relacionada con el problema de definición del itinerario formativo, está relacionada con la incorporación de características a cada nodo del grafo que aporten información de cara a la toma de decisiones ante caminos alternativos. En este sentido se colaboró con la Universidad Politécnica de Valencia para estudiar la viabilidad de usar modelado de características y el software MosKitt (Modeling Software Kit. http://www.moskitt.org/) para conseguir nuestro objetivo, publicándose el resultado en [23]. Finalmente hemos comenzado a investigar la aplicación de ACO para el cálculo de caminos óptimos en grafos estocásticos que definen itinerarios formativos con caminos alternativos [26] estudio que estamos ampliando para su publicación en revistas internacionales relevantes. El siguiente capítulo resume el estado del arte sobre la optimización basada en algoritmos de colonias de hormigas. Capítulo 2. Optimización por Colonias de Hormigas 15 Capítulo 2. Optimización por Colonias de Hormigas 2.1 Introducción Inspirados en los estudios sobre el comportamiento social de las hormigas de los entomólogos Pierre-Paul Grassé [36], Bert Hölldobler y Edward Osborne Wilson [126], los algoritmos de optimización por colonias de hormigas o ACO (del inglés Ant Colony Optimization) fueron propuestos por Marco Dorigo [15] como para la optimización de problemas NP-completos como el problema del Viajante (TSP) [27] o el de asignación cuadrática (QAP) [28]. Desde entonces ha existido un gran interés en la comunidad científica por aplicar estos algoritmos a muy diversos problemas de optimización: planificación de tareas (JSP) [29]; enrutamiento de redes de Comunicaciones [30]; coloreado de Grafos [31]; y en el área del aprendizaje automático, especialmente en el diseño de algoritmos de aprendizaje para estructuras de representación del conocimiento: reglas clásicas [32], lógica difusa [33] y redes bayesianas [34]. Los algoritmos ACO están inspirados en el comportamiento colaborativo de las hormigas. Las hormigas son insectos sociales, que viven en colonias y para los que la preservación de la misma está por encima de la supervivencia de cualquier individuo. Uno de los comportamientos más interesantes de las colonias de hormigas, a parte de su alta jerarquización, es el relacionado con la búsqueda de alimento, en especial como encuentran siempre el camino más corto entre el nido y la fuente de alimento. El método empleado por las hormigas se basa en el seguimiento del rastro de una sustancia química que ellas mismas secretan por dónde pasan: las feromonas. Ante varios caminos posibles, una hormiga huele los diferentes rastros dejados por sus predecesores, y tiende a elegir, con mayor probabilidad, los de mayor concentración de feromonas. El rastro de feromona ayuda a las hormigas a identificar el camino hacia la fuente de alimento descubierta por sus compañeras de colonia y también el camino de vuelta al nido. Capítulo 2. Optimización por Colonias de Hormigas 16 Experimentos previos con hormigas reales [35] demostraron que en una bifurcación con dos ramas simétricas de idéntica longitud (Figura 2), tras un intervalo de tiempo en el que las hormigas escogían indistintamente una u otra rama, todas las hormigas tendieron a seguir la misma bifurcación, lo que hizo pensar que la probabilidad de escoger una u otra rama dependía del número de hormigas que hubieran escogido cada rama previamente. Figura 2: Dibujo que representa el experimento del puente binario de Deneubourg. Así, en este experimento la probabilidad de selección de una rama u otra es del 50% cada vez que se realice el experimento, dependiendo la selección de una u otra de la distribución de individuos que elijan una u otra. Puesto que cada hormiga deposita feromonas al desplazarse, cuantas más hormigas escojan una rama, mayor probabilidad habrá de ser esa rama la elegida por el resto en detrimento de la otra, al concentrarse en ella mayor cantidad de feromonas. Asumiendo que el nivel de feromonas en un camino es proporcional al número de hormigas que han pasado por él, el modelo probabilístico que describe la probabilidad, P u (m), de que la hormiga (m+1)-ésima de la colonia elija el camino superior es:                               (1) dónde U m y L m son el número de hormigas que han escogido el camino superior y el inferior respectivamente, después de haber tomado la decisión m hormigas. Las variables h y k sirven para ajustar el modelo a las observaciones de hormigas reales. A través de simulaciones utilizando el método Monte Carlo, Deneubourg y sus colegas [35] encontraron que para valores de k=20 y h=2, el modelo se ajustaba a los datos experimentales. Al modificar el experimento, de forma que los caminos no tuvieran igual longitud (Figura 3), se observó que en todos los casos, las hormigas acababan escogiendo el camino más corto. Capítulo 2. Optimización por Colonias de Hormigas 17 En este caso, las primeras hormigas en llegar a la comida suelen ser aquellas que toman los caminos más cortos, y al iniciar el camino de vuelta, el nivel de feromona en estos caminos también es mayor, por lo que además suelen volver por el mismo camino, aumentando aún más el nivel de feromona existente y estimulando a las demás hormigas. En este experimento, el tiempo de fluctuaciones aleatorias se reduce considerablemente respecto al caso de caminos de igual longitud. Figura 3: Representación del experimento con caminos alternativos de diferente longitud. 1. La primera hormiga sigue un camino elegido aleatoriamente. 2. El resto de la colonia se distribuye entre los caminos posibles. 3. Finalmente la mayor concentración de feromonas en los caminos más cortos hace que prácticamente todas sigan el mismo camino. Los experimentos descritos revelan una especie de mecanismo colaborativo de optimización en el que cada individuo aporta una pequeña contribución. Lo interesante es que, aunque un individuo podría encontrar por sí solo la solución, la búsqueda del camino más corto sólo es posible con la colaboración de toda la colonia. El biólogo francés Pierre-Paul Grassé, tras observar el comportamiento de las termitas, denominó a este comportamiento estigmergia 5 , definiéndolo como “estimulación de los trabajadores a través del rendimiento obtenido” [36]. En cierto modo, esta estimulación y la respuesta a los estímulos, puede entenderse como una forma de comunicación indirecta, caracterizada por la naturaleza física de la información liberada (las 5 Del griego estigma: marca, señal; y ergon: trabajo, acción. Capítulo 2. Optimización por Colonias de Hormigas 18 feromonas), que significa una modificación física del entorno; y la naturaleza local de la información, que requiere que otros visiten el mismo entorno para tener acceso a dicha información. Otra importante característica destacada por Marco Dorigo es la autocatálisis o realimentación positiva [37] y la evaluación implícita de soluciones. Esto es: implícitamente se busca siempre el camino más corto como solución, puesto que cuanto más corto sea, más probable es que se complete el camino con mayor rapidez, y por tanto, mayor refuerzo de feromonas recibirá, animando con más fuerza a un número mayor de hormigas a optar por él. Este comportamiento contribuye rápidamente a la convergencia hacia una solución óptima. 2.2 Características Principales La Optimización por Colonias de Hormigas es una meta-heurística que utiliza un conjunto de agentes que simulan el comportamiento cooperativo de las colonias de hormigas para encontrar buenas soluciones en problemas de optimización de elevada complejidad combinatoria. Se inspira en el comportamiento social de las hormigas, del que toma sus ideas principales: - Cooperación: La cooperación es un concepto clave en el diseño de algoritmos ACO. La solución se alcanza mediante las pequeñas contribuciones de cada individuo. Aunque un individuo por sí sólo puede encontrar una solución suficientemente buena, no es sino la suma de las contribuciones de todos lo que determinará la solución final que terminará adoptando la colonia. - Búsqueda de caminos cortos y movimientos locales: Tanto las hormigas reales como las artificiales de los algoritmos ACO tienen el mismo objetivo: encontrar el camino más corto entre el nido (origen) y la fuente de alimento (objetivo). Y ambas lo hacen del mismo modo: moviéndose paso a paso, de un estado a cualquiera de sus estados adyacentes. Ninguna de las dos salta ni vuela, y aunque existen hormigas aladas, estas no participan de la tarea de búsqueda de alimentos. - Rastro de feromonas: El rastro de feromonas es la forma de comunicación indirecta que utilizan las hormigas. No existe una comunicación directa entre los individuos sino que la única vía de comunicación entre ellos se realiza mediante la modificación del entorno que supone el depósito de feromonas. En los algoritmos ACO esta información suele modelarse mediante un valor Capítulo 2. Optimización por Colonias de Hormigas 19 numérico que es percibido por cada hormiga artificial como el valor de una función que representa el tráfico histórico de toda la colonia por ese punto hasta el momento. La evaporación de las feromonas (su disminución con el tiempo si no hay aportes continuos) ayuda a que poco a poco se olvide el pasado y facilite, gracias a procesos de decisión estocásticos, la búsqueda de nuevas soluciones. - Decisión probabilística y miope: Tanto las hormigas reales como las artificiales de ACO no ven más allá de los posibles estados adyacentes y la decisión del siguiente estado se realiza aplicando una política de decisión probabilística. No existen otros mecanismos más avanzados de decisión que analicen las consecuencias de su posible decisión, como por ejemplo se aplica en la inteligencia artificial aplicada a los juegos de ajedrez. En cambio las hormigas artificiales sí pueden enriquecerse con algunas habilidades que no se encuentran en su estado natural en las colonias reales para hacerlas más eficientes. Algunas de las características de estos agentes son: - A diferencia de las hormigas reales, las hormigas artificiales empleadas en los algoritmos ACO viven en un mundo discreto, y sus movimientos están limitados a una transición entre conjuntos discretos de estados. - Las hormigas artificiales poseen memoria, de forma que conocen el estado actual en el que se encuentran y sus acciones y estados anteriores. - Se puede definir una función que determine la cantidad de feromona a depositar en función del porcentaje de éxito alcanzado o de la calidad de la solución encontrada. En realidad, esto no es una diferencia, puesto que algunas especies de hormigas reales también presentan este comportamiento, variando la cantidad e intensidad de las feromonas depositadas en función del alimento encontrado. Estudios recientes [38] han corroborado que la hormiga argentina (Linepithema humile) cambia la composición de su dieta según la estación del año, prefiriendo en invierno alimentos ricos en carbohidratos, como el azúcar de caña o la miel, frente a alimentos ricos en proteínas como el huevo. - Se puede determinar el momento en el que realizar depósito de feromonas. En algunos casos podría decidirse que el depósito de feromona sólo se lleve a cabo una vez encontrada una solución y no con cada movimiento, como ocurre en las hormigas reales. - Para mejorar la eficiencia general del sistema, los algoritmos ACO pueden enriquecerse con otras técnicas como optimización local o backtracking que no están presentes en las hormigas reales. Capítulo 2. Optimización por Colonias de Hormigas 20 2.3 La meta-heurística ACO En los algoritmos ACO, una o más colonias, compuestas de un número determinado de hormigas, buscan una buena solución a problemas de optimización. Cada hormiga busca una solución o un componente de ésta, a partir de un estado inicial que depende del problema. Cada hormiga, mientras construye su solución, obtiene información del entorno, de las características del problema y de su propio rendimiento, y usa toda esta información para modificar la representación del problema e influir así en la visión del mismo que tienen el resto de hormigas. Las hormigas pueden actuar concurrentemente y de forma independiente, pero no intercambian información directamente, siguiendo así el paradigma de la estigmergia que gobierna la comunicación entre las hormigas. La construcción de la solución sigue un proceso incremental, expresándose como la ruta de menor coste a través de los estados que componen el problema, de acuerdo con las restricciones del mismo. El problema se representa como un grafo ,, en el que cada   ∈ es una componente posible de la solución (un nodo del grafo) y cada   ∈ una transición posible de la componente i a la j (arco del grafo). Tanto los nodos del grafo como los arcos pueden tener asociado un rastro de feromona,   si nos referimos al rastro acumulado en el nodo   , o   si se trata del rastro acumulado en el arco   . De la misma forma, ambos pueden tener asociados valores heurísticos,   y   respectivamente, que representan la visibilidad de cada componente o trayecto, generalmente en función del coste o de una estimación del coste asociado de elegir el siguiente estado. Cada hormiga construye una solución a través de una secuencia finita de movimientos entre estados vecinos. Cuando existan varias posibilidades de movimientos, se elegirá el estado siguiente aplicando una política de búsqueda local estocástica, en la que la probabilidad de visitar cada estado vendrá determinada por la propia memoria de la hormiga y por la información del entorno (feromonas). La cantidad de feromonas a liberar por una hormiga, así como el momento de su liberación dependen de las características y restricciones del problema, así como del diseño de la implementación. Las feromonas pueden ser liberadas con cada movimiento (liberación paso a paso) o una vez que la solución has sido construida (liberación retardada). La cantidad de feromona también puede variarse en función de la calidad de la solución construida. Además, cada hormiga construye una tabla de decisión utilizando una función que tiene en cuenta el nivel de feromona existente para cada movimiento como un conjunto de valores heurísticos. De esta forma se determina el siguiente estado para cada hormiga. Capítulo 2. Optimización por Colonias de Hormigas 21 El grado de aleatoriedad en la decisión de los movimientos y la rapidez de evaporación de las feromonas determinan el balance entre la exploración de nuevos caminos y la explotación del conocimiento acumulado. Hay numerosas implementaciones de esta meta-heurística aplicadas cada una de ellas a diferentes problemas de optimización combinatoria. El Listado 1 muestra el pseudocódigo de la meta-heurística ACO definida por Marco Dorigo. La meta-heurística define las tres actividades básicas que deben realizarse: gestionar las hormigas encargadas de buscar soluciones locales, evaporar feromonas y realizar acciones globales, pero no impone la forma de llevarlas a cabo. De hecho, la sentencia planificar da libertad para decidir si debe existir algún tipo de paralelismo entre ellas o deben sincronizarse de alguna manera. La función ejecutar_acciones_globales representa a un conjunto de acciones opcionales que podrían ser realizadas por un proceso con conocimiento global del entorno, una especie de observador externo. Por ejemplo, a partir del comportamiento de todas las hormigas este observador podría reunir información útil y decidir depositar feromonas adicionales, condicionando de esta forma la búsqueda local de cada hormiga desde una perspectiva diferente. La planificación de las actividades definidas por la meta-heurística ACO depende del problema y da lugar a diferentes algoritmos. Mientras algunos problemas tienen un único estado de inicio, otros cuentan con múltiples estados posibles de inicio. procedimiento ACO() mientras (! criterio_finalizacion) planificar gestionar_hormigas(); evaporar_feromonas(); ejecutar_acciones_globales(); // opcional fplanificar fmientras fprocedimiento Listado 1: Meta-heurística ACO Capítulo 2. Optimización por Colonias de Hormigas 28 En cambio, para este conjunto es fácil hallar a simple vista una ruta más corta: R' = {Madrid, Vigo, Bilbao, Barcelona, Valencia, Murcia, Sevilla, Cádiz, Madrid}, con una distancia total d'=3829 Km. Por el contrario, cuando β=0 el valor heurístico deja de tener influencia, influyendo únicamente en la decisión las feromonas depositadas previamente, lo que conduciría rápidamente a una situación de bloqueo en el camino que aleatoriamente se hubiera seleccionado primero, lo que generalmente lleva a soluciones no óptimas [39]. Cuando todas las hormigas han completado un camino, siguiendo la metaheurística ACO, se produce la evaporación de las feromonas. Puesto que se utiliza la deposición retardada de feromonas, la deposición coincide con el proceso de evaporación, depositándose en todos los arcos del grafo la cantidad de feromonas dada por la siguiente expresión:    '  1    1 ; <     '    ∆    '  (5) donde < es el denominado coeficiente de evaporación y es un valor positivo menor o igual que 1. ∆  ' es la variación total de feromonas correspondiente a la suma de los depósitos de feromonas de todas las hormigas, que responde a la ecuación: ∆    '     ∆   7  '   7 %  (6) siendo la cantidad de feromonas depositadas en cada trayecto (arco del nodo) l ij por cada hormiga k, ∆  ', inversamente proporcional a la distancia total del camino encontrado si el lado pertenece al recorrido R k de la hormiga k en el instante o iteración t. Si el lado l ij no pertenece al recorrido no se depositan feromonas, penalizando así al trayecto que va de la ciudad i a la j, es decir, ∆   7  '   > 1  7  '  ?@    ∈ A 7  '  0 CD  E'FE  *?E G (7) Dorigo estableció a través de la experimentación en su tesis doctoral [15] los valores óptimos siguientes para la calibración del sistema: m = n (número de hormigas igual al número de nodos), α=1, β=5 y <0,5. Además, en el proceso de inicialización, se deposita una cantidad de feromona  & I0, pero muy próxima a cero. Capítulo 2. Optimización por Colonias de Hormigas 29 Variantes del algoritmo AS Una variante del algoritmo AS es el Max-Min AS (MMAS) de Stützle y Hoos [41]. En este algoritmo, el depósito de feromonas no es llevado a cabo por cada hormiga, sino por un agente controlador externo, encargado de realizar acciones globales. A diferencia de AS, el algoritmo MMAS es un algoritmo de optimización elitista, puesto que sólo tiene en cuenta el resultado de la hormiga que ha obtenido la mejor solución en cada iteración para realizar el depósito de feromonas, que se corresponde con la siguiente ecuación:    '  1    < J    '    ∆   KLMN (8) donde ∆  KLMN   OMPQRS y f(s best ) denota el coste de la solución ,que puede corresponderse con el de la mejor iteración (s ib ) o con el de todas las iteraciones hasta el momento (s gb ). A diferencia de otros algoritmos como ACS (Ant Colony System) que usan s gb , MMAS se decanta por s ib . Esta decisión se debe a que Stützle y Hoos [44] demostraron que el hecho de usar s gb , refuerza en exceso la explotación de dicha solución limitando la exploración de nuevas soluciones, con el consiguiente riesgo de quedar el proceso de optimización atrapado en una solución de pobre calidad. En cambio, eligiendo s ib se minimiza este riesgo gracias a que las soluciones de cada iteración pueden diferir considerablemente entre iteraciones sucesivas, de forma que un gran número de componentes de posibles soluciones puede recibir un refuerzo ocasional en forma de feromonas, potenciando la exploración de nuevos caminos frente a la explotación de los ya encontrados, con un balance entre exploración y explotación más equilibrado. En contraposición, la elección de s ib tiene un impacto negativo en la eficiencia del algoritmo, al requerir numerosas iteraciones para obtener soluciones de calidad. De hecho, tanto para el TSP como para el QAP, los autores proponen una estrategia dinámica mixta, que aumente la frecuencia de uso de s gb conforme aumente el número de iteraciones, obteniendo muy buenos resultados en la comparativa respecto a otros algoritmos. Para evitar el bloqueo frecuente de los algoritmos elitistas, MMAS impone que sólo los arcos cuyo nivel de feromona esté comprendido en un rango determinado  " , TU # sean elegibles. Para garantizar la correcta inicialización, el nivel de feromonas en todos los arcos es inicializado a  TU . Aun así, se producen situaciones de bloqueo que disminuyen la exploración de nuevos trayectos cuando algunos arcos tienen un nivel de feromonas cercano al máximo y otros al mínimo, por lo que sus autores idearon un mecanismo diferente de actualización de feromonas, que denominaron “suavizado del rastro de feromonas”, y se expresa como sigue: Capítulo 2. Optimización por Colonias de Hormigas 30   ∗  '       '    W J X  TU  '  ;     '  Y  ED  0 Z W Z 1 (9) El suavizado del rastro consiste en facilitar la exploración mediante el aumento de la probabilidad de seleccionar componentes con bajo nivel de feromonas. En (9),   ' y   ∗ ' son, respectivamente, la cantidad de feromonas del arco l ij en el instante t antes y después del suavizado. Al ser 0 < δ < 1, el segundo sumando representa una proporción de la distancia relativa del nivel de feromonas actual con respecto al máximo nivel de feromonas definido. Esto contribuye a incrementar de una forma más rápida el nivel de feromonas en aquellos arcos con un nivel bajo de feromonas, pero también a disminuir a aquellos arcos cuyo nivel de feromonas actual es mayor al máximo definido, contribuyendo a que puedan volver al rango deseado. Con el suavizado del rastro de feromonas, el algoritmo MMAS obtuvo resultados significativamente mejores que el AS [41]. Otra variante del AS es el AS Rank [42], que también opta, al igual que el MMAS, por una deposición retardada de feromonas que se delega en una tarea externa. Esta tarea externa se encarga de confeccionar un ranking con las σ-1 mejores hormigas en función de la longitud del recorrido de cada una ella, recibiendo los arcos de cada recorrido un número proporcional de feromonas en función de la posición del ranking que ocupe cada hormiga que lo usó. Además, los arcos del recorrido de la mejor hormiga (aquella que ocupa la primera posición del ranking) reciben una cantidad adicional de feromonas, de forma similar a las hormigas elitistas del algoritmo Ant System. La ecuación que determina la deposición de feromonas en un arco en el algoritmo AS Rank es la siguiente:    '    1 ; <     ' ; 1    [ ∆     '    ∆   \  '  (10) donde ∆   ' representa el refuerzo adicional de feromonas para la mejor hormiga y es un factor proporcional a la inversa del camino encontrado en la iteración t, en este caso 1/L + (t). Como se observa en la ecuación, en este caso el factor de proporción es una unidad más que el número de hormigas que componen el ranking, esto es σ. Además cada hormiga r, recibe al final de cada iteración t una cantidad de feromonas dependiente de la longitud de los caminos encontrados por todas las hormigas en esa iteración: ∆  \ '∑∆  ] ' ^$ ]% , con ∆  \ '[;_/ ] ' si la hormiga de la posición µ del ranking usó el arco l ij en su recorrido o ∆  \ '0 si no lo hizo, siendo L µ (t) la longitud del recorrido de la hormiga que ocupa la posición µ en el instante t. Capítulo 2. Optimización por Colonias de Hormigas 31 Sistemas de Colonias de Hormigas Dorigo y Gambardella introdujeron el algoritmo Ant Colony System (ACS) en 1997 [27] para mejorar el rendimiento del AS, que no podía encontrar buenas soluciones en un tiempo razonable cuando el problema era de un tamaño moderadamente grande. Las principales diferencias con respecto a AS son: • ACS utiliza también deposición retardada de feromonas que es llevada a cabo por una tarea externa, pero en lugar de depositar las feromonas correspondientes a cada hormiga, ACS aplica una estrategia elitista, haciendo que sólo la hormiga que ha obtenido el camino de mejor coste sea la que deposite las feromonas en los arcos que componen su solución. En el caso del algoritmo ACS-3-opt además, esta tarea externa activa previamente un procedimiento de búsqueda local basado en una variante del procedimiento 3opt [66] para mejorar las soluciones obtenidas antes de proceder al depósito de feromonas. La regla para la deposición de feromonas es:    '    1 ; <     ' ; 1    < ∆    '  (11) donde <∈0,1# es el parámetro que controla la evaporación de feromonas y ∆  '1/  es la variación correspondientes al mejor camino, de longitud (o coste) L + . La ecuación sólo se aplica en este caso a los nodos que pertenecen al mejor camino en cada iteración. • La segunda diferencia radica en el mecanismo de selección probabilística de los arcos. En ACS se emplea una variable aleatoria Q, uniformemente distribuida en [0,1] y a & ∈0,1# un valor configurable. La regla pseudoaleatoria que se emplea para definir la probabilidad de selección de un arco depende del valor obtenido para Q con respecto a Q 0 . Así teniendo en cuenta la tabla de decisión (3) para cada hormiga a ij (t): o Si Q ≤ Q 0 :   7  '    b 1 ?@  4  C?  C  DEE  ED  *cEF  *  0 CD  E'FE  *?E                 G (12) o Si Q > Q 0 se aplica la ecuación (4) para el cálculo de la probabilidad de selección de cada nodo. De esta forma, cuando Q ≤ Q 0 se explota el conocimiento disponible del problema, es decir, el conocimiento heurístico acerca de las distancias entre los nodos y el conocimiento aprendido, memorizado en forma de rastro de feromonas. En cambio cuando Q > Q 0 se aplica la misma exploración sesgada Capítulo 2. Optimización por Colonias de Hormigas 32 de AS de la ecuación (4). La calibración de Q 0 permite modular el grado de exploración frente a explotación, permitiendo elegir cuando concentrar la actividad del sistema en la explotación de buenas soluciones (por ejemplo al obtener un valor mínimo deseado del coste). • La tercera diferencia es la deposición paso a paso de las hormigas en el algoritmo ACS, que se produce cada vez que una hormiga se mueve de un nodo a otro, aplicando la ecuación siguiente:    '    1 ; d     ' ; 1    d  & (13) con 0 < φ < 1 y τ 0 el valor inicial de feromonas de cada arco. En ACS no sólo se produce una deposición retardada teniendo en cuenta el mejor camino de la colonia en esa iteración, sino que cada hormiga también deposita paso a paso sus feromonas. La ecuación (13) permite calibrar la reducción de feromonas de un arco cada vez que una hormiga lo escoge con el fin de poder evitar que todas las hormigas de la colonia sigan el camino de una anterior cuyo camino coincide parcialmente. Por ejemplo, supongamos que la hormiga k 1 ha comenzado su recorrido en el nodo 2, continuando por el 3, luego 4, etc. Si la hormiga k 2 ha comenzado simultáneamente en el nodo 5 y elije el arco l 52 para llegar al nodo 2, encontrará en el nodo 2 que el arco de salida l 23 tiene un nivel de feromonas mayor, por lo que tenderá a seguir el camino marcado por las feromonas de la hormiga k 1 , con un paso de retraso, evitando la exploración de otros caminos que posiblemente ofrezcan soluciones mejores. Con la utilización de la ecuación (13) para la liberación de feromonas paso a paso por cada hormiga, se disminuye el nivel de feromonas de los arcos visitados, lo que los hace menos atractivos para las hormigas que lleguen a él en un paso posterior, evitando que todas las hormigas de una misma colonia sigan los mismos pasos y fomentando el descubrimiento de caminos alternativos más rápidamente que únicamente con deposición retardada por una tarea externa. Como inconveniente, esta medida hace que, en consecuencia, las hormigas tiendan a no converger a una ruta común. • Por último, el algoritmo ACS utiliza listas de candidatos con información heurística adicional que proporciona los nodos preferidos para visitar desde un nodo dado. En el algoritmo ACS cuando una hormiga está en un nodo examina la lista de nodos candidatos antes de desplazarse a otro, lo que ahorra las comprobaciones del total de nodos del problema, mejorando el rendimiento del algoritmo. Tan sólo si no hay nodos sin visitar en la lista de candidatos se pasa a buscar otros nodos. Capítulo 2. Optimización por Colonias de Hormigas 33 ACS fue el sucesor de Ant-Q [222], un algoritmo que intentaba combinar AS y Q-learning. En realidad, únicamente difieren en la cantidad de feromonas iniciales, para la que Ant-Q definía un valor variable que se correspondía con la máxima concentración de feromonas de un arco perteneciente al recorrido. Al tener un comportamiento similar, fue abandonado dada la mayor simplicidad del algoritmo ACS que evitaba tener que calcular en cada deposición dicho valor (el valor inicial de las feromonas en ACS es una constante que se calcula al inicio y que generalmente depende inversamente del número de arcos del problema). Según el estudio de Dorigo y Gambardella, ACS es el algoritmo con mejor rendimiento de todos los algoritmos combinatorios descritos anteriormente [27], obteniendo un rendimiento superior a algoritmos genéticos para problemas TSP de pequeño y medio tamaño (50, 75 y 100 ciudades). Uno de los problemas de ACS es determinar el número adecuado de hormigas que componen la colonia, puesto que a colonias más pobladas, el rendimiento suele ser peor debido a que un mayor número de hormigas se ven influenciadas por el rastro de feromonas dejado por otras, llegando a la misma solución y penalizando el tiempo total del algoritmo. El número adecuado de hormigas depende de las características del problema y la mayoría de las veces ha de calcularse experimentalmente. Debido a la convergencia de los algoritmos ACO cuando el número de iteraciones t es suficientemente grande [76], lo recomendable es seleccionar un número de hormigas m tal que multiplicado por el número de iteraciones que ejecute cada una resulte mayor al número de iteraciones t a partir de la cual los resultados convergen a una misma solución. Puesto que la rapidez de convergencia del algoritmo depende tanto de las características del problema como de la calibración del sistema (constantes α, β y otras), el número adecuado de hormigas sólo puede definirse mediante la experimentación. 2.5.2 El Problema de la Asignación Cuadrática El problema de la asignación cuadrática, que se denota por sus siglas en inglés QAP, Quadratic Assignment Problem, fue planteado por Koopmans y Beckman [67] en 1957. El problema de asignación cuadrática consiste en asignar n elementos a una cantidad n de ubicaciones con un coste asociado al desplazamiento entre diferentes ubicaciones y al asociado al cambio de asignación de un elemento por otro. Matemáticamente puede describirse como sigue. Capítulo 2. Optimización por Colonias de Hormigas 34 Dadas dos matrices cuadradas de orden n, A=(a ij ) y B=(b ij ), encontrar una permutación П * que minimice la función: e  f      *  J g h2h6  "  %  "  %  (14) donde P(n), es el conjunto de permutaciones de n elementos, siendo f∈D una permutación de las posibles. Se distinguen dos clases de QAP: aleatorios y estructurados, siendo los estructurados aquellos problemas tomados del mundo real. Por ejemplo un típico ejemplo de QAP estructurado es la planificación del reparto de diferentes mercancías por un mismo transportista por carretera, puesto que es necesario elegir la ruta a seguir para así decidir cómo cargar el camión. El coste dependerá de las distancias y entre las ubicaciones, además de un coste adicional por entregar cada elemento (la descarga) en cada ubicación específica. De este modo se buscará que este coste, en función de la distancia y flujo de la mercancía, sea mínimo. En cierto modo, puede considerarse QAP como una generalización del TSP. Maniezzo y Colorni, aplicaron el algoritmo AS a este problema usando la heurística Min-Max, denominándolo AS-QAP [43]. La única diferencia con el algoritmo AS del AS-QAP es la función objetivo que determina la cantidad de feromonas a depositar en los arcos del mejor recorrido en cada iteración. Los resultados obtenidos fueron de la misma calidad a los obtenidos con otras aproximaciones como programación evolutiva o algoritmos genéticos. Similares resultados obtuvieron Stützle y Hoos con la aplicación directa del algoritmo MMAS al QAP [44]. Por último Gambardella, Taillard y Dorigo implementan un algoritmo híbrido entre sistema de hormigas y búsqueda local, denominado HAS-QAP [45]. En el algoritmo HAS-QAP, durante cada iteración, existe el problema de la elección de la solución de partida asociada a cada hormiga, para lo que se definen dos mecanismos interesantes: intensificación y diversificación. La intensificación se usa para explorar los vecinos de buenas soluciones, haciendo que la hormiga regrese hacia la solución que tenía al principio de la iteración si la solución era mejor que la solución que ha encontrado al final de la iteración. La diversificación implementa un reinicio parcial del algoritmo cuando las soluciones parecen no poder mejorarse nunca más, y consiste en la reiniciación tanto de la matriz de feromonas como de las soluciones asociadas a cada hormiga. Lo más interesante del algoritmo HASQAP es el mecanismo de búsqueda local que aplica para mejorar la solución. Este procedimiento de búsqueda local, examina sistemáticamente todos los posibles intercambios de permutaciones de los elementos, procediendo al intercambio cuando Capítulo 2. Optimización por Colonias de Hormigas 35 encuentra alguna que mejora la solución actual. Se ha probado que el algoritmo HASQAP se comporta extraordinariamente bien con QAP estructurados. 2.5.3 El Problema de la Planificación de la Producción El problema de la planificación de la producción, más conocido por sus siglas en inglés JSP, Job-shop Scheduling Problem, es un problema de optimización en el que una serie de trabajos deben ser asignados a unos determinados recursos en un tiempo determinado. La versión más simple puede describirse de la siguiente forma: Dado un conjunto J de trabajos, un conjunto M de máquinas y un conjunto O de operaciones con N integrantes. Para cada operación @∈i tenemos relacionado un trabajo 4∈jy una máquina ∈k en la que debe realizarse, consumiendo un tiempo '∈l  . Además, es dada una relación de precedencia binaria ≺ que descompone O en cadenas, una para cada trabajo. Encontrar un tiempo de comienzo s i para cada operación tal que se minimice el máximo tiempo de finalización de todas las operaciones sin que se procesen dos trabajos simultáneamente en la misma máquina. El problema tiene las siguientes restricciones: a) Trabajos en tiempo futuro: ?  n0,∀@∈i b) Precedencia de trabajos: ?  n?  '  ,∀@,4∈i⋀@≺4 c) Máquinas dedicadas: ?  n?  '  ⋁?  n?  '  ,∀@,4∈i⋀     Colorni et al. [46] aplicaron el algoritmo AS directamente a este problema, con el único cambio del valor heurístico η que fue calculado usando la heurística LRT (Longest Remaining Time) para elegir el trabajo que necesite el mayor tiempo de proceso de entre los trabajos restantes por planificar. El algoritmo resultante, AS-JSP, fue probado con problemas de hasta 15 máquinas y 15 trabajos, encontrando soluciones óptimas aunque no excepcionales (dentro de un margen del 10% con la mejor solución), lo que sugiere que aún hay bastante margen de mejora en este problema. 2.5.4 El Problema del Enrutamiento de Vehículos El problema del enrutamiento de vehículos, VRP (Vehicle Routing Problem) es en realidad un conjunto de variantes del mismo problema. En general, en todos ellos se trata de averiguar la mejor ruta de una flota de transporte para dar servicio a una serie de clientes. El problema se estudió por primera vez en la distribución de gasolina para estaciones de carburante [68]. Capítulo 2. Optimización por Colonias de Hormigas 36 La función objetivo depende de la tipología y características del problema. Lo más habitual es intentar: minimizar el coste total de operación, minimizar el tiempo total de transporte, minimizar la distancia total recorrida, minimizar el tiempo de espera, maximizar el beneficio, maximizar el servicio al cliente, minimizar la utilización de vehículos, equilibrar la utilización de los recursos, etc. Los principales elementos que constituyen este conjunto de problemas son: • La red de transporte • La flota de vehículos • Los clientes y/o proveedores • El depósito central (o depósitos) • Los servicios a atender • Las rutas que componen la solución El modelado del problema depende de las restricciones impuestas (uno o varios proveedores, uno o varios almacenes, máxima distancia de una ruta, máximo tiempo de reparto para cada vehículo, etc.) Bullnheimer et al. [47] modelan el problema VRP mediante un grafo dirigido ponderado completo, en el que N={n 0 ,n 1 …n m } es el conjunto de nodos del grafo y A={(i,j): i≠j} es el conjunto de arcos que representan las vías de comunicación que unen dos nodos entre sí, teniendo cada uno un peso d ij que representa la distancia del nodo n i al n j .. El problema modelado en [47] sólo cuenta con un depósito central, representado por el nodo n 0 , en el que inicialmente está ubicada la flota de vehículos M={m 0 , m 1 … m l } del problema, cada uno de ellos con una capacidad D. El resto de nodos son nodos de clientes. Cada nodo n i tiene asociada una demanda d i ≥0 y un tiempo de servicio δ i ≥0 siendo obviamente la demanda y tiempo de servicio del almacén (n 0 ) cero. El objetivo del problema es encontrar las rutas de menor coste para cada cliente tales que: a) Cada cliente sea visitado exactamente una vez por un único vehículo. b) Para cada vehículo la demanda total no supere a su capacidad, D. c) La longitud total del recorrido no exceda a un máximo establecido, L. d) Cada vehículo comienza y termina su recorrido en el almacén. Capítulo 2. Optimización por Colonias de Hormigas 37 Figura 5: Representación de una variante del VRP con depósito único central El algoritmo AS-VRP [47] es una ampliación del AS rank en el que se tienen en cuenta las restricciones anteriores en el proceso de construcción de la tabla de memoria (nodos visitados) de cada hormiga. Los autores añadieron un proceso de optimización simple, basado en la heurística 2-opt. La comparación con otros métodos resultó bastante positiva, mejorando los resultados obtenidos con redes neuronales, por ejemplo. El algoritmo HAS-VRP [48] se basa en ACS: cada hormiga construye un recorrido completo sin violar las restricciones de capacidad de los vehículos. Un recorrido completo se compone de muchos sub-recorridos que conectan almacenes, y cada sub-recorrido se corresponde con el recorrido asociado a uno de los vehículos. La actualización del rastro de feromonas es retardada, como en ACS. Además, HAS-VRP incorpora un procedimiento de intercambio de arcos que es aplicado al final de cada iteración por una tarea externa. Los resultados obtenidos con esta aproximación son competitivos incluso con los mejores algoritmos conocidos llevando a establecer nuevos límites para algunos ejemplos muy estudiados. Los mismos autores estudiaron también el VRP con ventanas temporales, VRPTW, en el algoritmo MACS-VRPTW [69]. El VRPTW introduce un intervalo de tiempo para cada cliente, durante el cual ha de ser servido. Los vehículos que lleguen antes del inicio de la ventana de tiempo tendrán que esperar. Esta suele ser una típica restricción en los repartos a domicilio de muchas grandes superficies, que solicitan al Capítulo 2. Optimización por Colonias de Hormigas 44 Las principales diferencias de AntNet son el uso de modelos estadísticos locales que tienen en cuenta el tiempo empleado por las hormigas en recorrer un determinado camino, la deposición retardada de feromonas (una vez construido el recorrido) frente a la deposición paso a paso empleada en el ABC y la aplicación de heurísticas que tienen en cuenta el estado actual del tráfico para determinar la bondad de un camino respecto a otro. En AntNet el tiempo empleado por una hormiga en la construcción de un camino es una medida del retardo de la red en ese camino, pero es necesaria la evaluación de los caminos en relación con el estado actual de la red puesto que un tiempo T no es de por sí alto o bajo si no se tiene en cuenta el estado de congestión de la red. Esto es, el mismo tiempo T puede ser de baja calidad (excesivamente alto) en condiciones de baja congestión pero podría ser muy bueno si se da en condiciones de tráfico intenso. La cantidad de feromonas depositadas es proporcional a la bondad del camino construido. En AntNet la tabla de decisión )  * "! '# |12|,|1|$ del nodo i se construye como composición de los rastros de feromonas con los valores heurísticos de la forma siguiente: * "!  '    u  "!  '    1 ; u   " u   1 ; u   | 5  | ; 1  (16) donde N i es el conjunto de nodos vecinos del nodo i, n es un nodo perteneciente a dicho conjunto, d es el nodo destino, η n es el valor heurístico normalizado al rango [0,1] y ω es una variable de calibración también en el rango [0,1]. En los elementos de la tabla de decisión (16), el denominador es un término de normalización. En AntNet las hormigas son lanzadas de cada nodo de la red en busca de recorridos hacia los nodos destino, por lo que al menos son necesarias N·(N-1) hormigas. El algoritmo AntNet diferencia entre hormigas hacia adelante (forward ants), que van desde el nodo fuente al destino y hormigas hacia atrás (backward ants) que utilizan los caminos hallados por las primeras para volver al nido y son las encargadas del depósito de feromonas en cada arco (una vez calculado el coste del camino hallado por las forward ants). Todas las feromonas en un recorrido se actualizan respecto a todos los nodos sucesores y no sólo con respecto al nodo origen, tal y como aplicaron Bonebeau et al. en [53]. Además, AntNet elimina los ciclos que pueden producirse en el recorrido de las hormigas evitando que desde un nodo se vuelva a uno ya visitado. Aunque AntNet demostró ser muy eficiente, sus autores introdujeron nuevas variantes como AntNet-FA [54] en el que introducen el concepto de “hormigas Capítulo 2. Optimización por Colonias de Hormigas 45 voladoras” con una variación de las forward ants con la capacidad de movimiento hacia el siguiente nodo mucho más rápida (se descarga de tareas a la hormigas hacia adelante, por ejemplo evitándoles tener que almacenar el tiempo empleado en cada cambio de nodo). AntNet-FA es una versión mejorada de AntNet, en el que las hormigas se mueven más rápidamente sobre las colas con mayor prioridad. El rendimiento de AntNet-FA mejora con el incremento del tamaño de la red y su eficiencia es mejor que la de AntNet. 2.7 Aplicación a la resolución de problemas multi-objetivos 2.7.1 Introducción a problemas multi-objetivos La optimización multi-objetivo puede entenderse como el problema de encontrar un vector de variables de decisión que satisfacen restricciones y optimizan un vector cuyos elementos representan las funciones objetivo. Generalmente, en la vida real, muchos de los problemas presentados en las secciones anteriores tienen una variante multi-objetivo que es la que más utilidad (o valor) ofrece para los interesados. Ejemplos de problemas multi-objetivo habituales son la compra de un automóvil (minimizar precio, maximizar potencia, confort, financiación, etc.), la ubicación de torres de repetición para telefonía móvil (minimizar costes de adquisición del suelo, de materiales, maximizar la cobertura…) o el problema del viajante en la que se pretenda no sólo minimizar la distancia (para ahorrar gastos de combustible), sino también el tiempo empleado en el recorrido por el viajante, y en muchas ocasiones, el camino más corto no siempre es el más rápido. Los problemas multi-objetivo pueden tener más de una solución posible o vector vwv  ,v x …v " # z que satisface un conjunto de restricciones sobre los valores de este vector y optimiza el vector de funciones: e w  v w     e   v w  , e x  v w  …  e 7  v w   # z  ∈  l 7 . (17) El conjunto de todas las soluciones que satisfacen las restricciones se denomina conjunto de soluciones factibles y se representa como Ω, con {⊂l " . Su imagen Ω 0 es: { &   e w  v w  ∈  l 7  ∨  v w ∈ { (18) Capítulo 2. Optimización por Colonias de Hormigas 46 En la optimización de un solo objetivo el conjunto de variables de decisión factibles está ordenado mediante una función objetivo f, siendo fácil discernir si para dos soluciones a y b, se cumple que f(a) > f(b) o f(a) < f(b) o f(a) = f(b). En cambio en problemas con múltiples objetivos, el orden que se da suele ser parcial y no puede considerarse siempre que f(a) sea mejor que f(b) o al contrario. Estos casos son comunes en problemas en los que mejorar un objetivo suele empeorar otro, por ejemplo minimizar el coste de producción y maximizar la calidad en la fabricación de un producto. Para ilustrar este concepto, se presenta en la Figura 6 la relación entre inversión en recursos (humanos y materiales) y el número de incidencias que superan el acuerdo de nivel de servicio (o SLA del inglés Service Level Agreement) en una empresa de servicios. Se quieren minimizar ambos. Los puntos de la curva de la Figura 6 representan soluciones Pareto-óptimas. Ninguna de ellas se puede definir como “mejor” que las demás, a menos que se incluya alguna otra información (restricciones, ponderaciones, etc.) que determine cuál de los objetivos es más importante. Figura 6: Incidencias que superan SLA frente al coste en técnicos de soporte La solución representada por el punto B es mejor que la representada por el punto C, puesto que optimiza los dos objetivos. Sin embargo en la comparación entre C y A, se obtiene que, disminuyendo mucho los costes de los recursos, el número de incidencias en A es ligeramente mayor al de C pero no podemos decir que una solución sea mejor que otra puesto que no son comparables entre ellos si consideramos todos los Capítulo 2. Optimización por Colonias de Hormigas 47 objetivos. Tampoco podemos afirmar al comparar A con B que alguna de las dos sea mejor si se considera que ambos objetivos son igualmente importantes y no se introduce alguna restricción adicional. Sin embargo, B es claramente superior a C en ambos objetivos. ¿Cuándo podemos decir que un vector de soluciones es igual a otro, mayor o menor? Para dar respuesta a esta pregunta se utiliza ampliamente en economía y en ingeniería el concepto de eficiencia de Pareto; lo cual se define como sigue. Según Pareto, una situación A es superior o preferible a una situación B cuando el paso de B a A supone una mejora para todos los miembros de la sociedad, o bien una mejora para algunos, sin que los demás resulten perjudicados. Aplicando este concepto, dados dos vectores ~∈, v∈ se tiene que: e  ~   e     ?@  c  ? ó E  ?@  ∀ @ ∈  1 , 2 …   : e   ~   e     (19) e  ~  n e     ?@  c  ? ó E  ?@  ∀ @ ∈  1 , 2 …   : e   ~  n e     (20) e  ~  I e     ?@  c  ? ó E  ?@  e  ~  n e     c  e  ~  ( e    (21) e  ~   e     ?@  c  ? ó E  ?@  ∀ @ ∈  1 , 2 …   : e   ~   e     (22) e  ~  Z e     ?@  c  ? ó E  ?@  e  ~   e     c  e  ~  ( e    (23) A partir de estas relaciones se define el concepto de dominancia de Pareto: Se dice que, en un contexto de minimización (como el del ejemplo de la Figura 6) para dos soluciones ~,∈{: • ~ domina a  (y se denota como ~≺) si y sólo si u es menor o igual que  en cada uno de los objetivos y estrictamente menor en al menos un objetivo: e   ~   e     ∀ @ ∈  1 , 2 … g #  ∧  ∃ 4 ∈  1 , 2 …  #    e   ~  Z G e     (24) • u y v no son comparables si y sólo si ~⊀∧⊀~. Es decir si ninguna de las dos domina a la otra. Se denota como: ~~ En un contexto de maximización, el concepto de dominancia se define de forma similar a los dos puntos anteriores pero cambiando la relación < por > y la relación ≤ por ≥ en (24). En un contexto de maximización, la dominancia de u sobre v se denota como ~≻. Capítulo 2. Optimización por Colonias de Hormigas 48 A partir del concepto de dominancia se define el concepto de optimalidad de Pareto: Dado un vector de decisión vw∈ O , y su correspondiente vector objetivo cevw∈ O , se dice que x es no dominado respecto a un conjunto )⊆ O si y sólo si ∀*∈),v≺*∨v~*. En caso de que x sea no dominado respecto de todo el conjunto X f se dice que x es una solución Pareto óptima (también llamado óptimo paretiano) y se representa como x*, formando parte su correspondiente vector objetivo y del frente Pareto óptimo, denotado por Y true . De esta forma, al conjunto de vectores de decisión no dominados con respecto a todo X f , X true , se le denomina Conjunto de Pareto y se representan como x* mientras que el conjunto correspondiente de vectores objetivo Y true = f(X true ) constituye el Frente de Pareto. En otras palabras, la solución x* es un óptimo de Pareto si no existe un vector que haga mejorar alguno de los objetivos -respecto a los valores obtenidos para x*- sin que empeore de forma simultánea alguno de los otros. En general, la solución en el sentido de Pareto al problema de optimización multi-objetivo no será única, sino que estará formada por el conjunto de todos los vectores no dominados del Frente de Pareto. 2.7.2 Adaptación de ACO a problemas multi-objetivos Pinto y Barán [62] proponen, como adaptación del ACS a problemas con r objetivos (con r>1), tener en cuenta en la ecuación de actualización retardada de feromonas (5) la suma de las variaciones de las mismas para cada objetivo, de forma que la ecuación (7) aplicada a un problema con r objetivos se expresaría como: ∆   7  '    1 ∑  "7  '  \"% ?@    ∈ A 7  '  0 CD  E'FE  *?E G  (25) En la ecuación (25)  "7 ' representa la distancia del recorrido obtenido por la hormiga k en el instante t, según la métrica de distancia dada para el objetivo n. Por motivos de normalización, los valores de dicha función de distancia son divididos por un valor máximo definido a priori y que normalmente, es el valor máximo posible para cada objetivo. Capítulo 2. Optimización por Colonias de Hormigas 49 La hormiga que completó una solución debe actualizar el conjunto de Pareto (CP) si la solución encontrada es no dominada con respecto a las existentes en CP y luego debe eliminar las soluciones dominadas por la misma. Este comportamiento modifica la meta-heurística ACO para adaptarla a problemas multi-objetivos en lo que algunos autores [58], [61][62][64] han denominado MOACO (Multio-Objective ACO) aunque, como muestra el Listado 2, no es sino una particularización de la metaheurística ACO (Listado 1), en la que la función de gestión de las hormigas debe hacerse cargo de esta casuística. Las aproximaciones de adaptación a problemas multi-objetivo son variadas, basándose en alguno de los diferentes algoritmos de un sólo objetivo expuestos con anterioridad. Para que realmente sea un problema multi-objetivo, todos han de contemplar las diferentes visibilidades independientemente, puesto que el definir una visibilidad en función de alguna función que tenga en cuenta los diferentes objetivos (ponderados en función de su relevancia) convierte al problema en un problema de un único objetivo. Todos los algoritmos que se presentan a continuación consideran una visibilidad para cada objetivo pero difieren en el número de matrices de feromonas o de colonias de hormigas usadas. Algoritmos con múltiples colonias y una matriz de feromonas El algoritmo Multi-objective Ant Q (MOAQ) [58] es una adaptación en el algoritmo Ant-Q en la que utiliza una colonia por cada objetivo. El algoritmo gestiona funcion gestionar_hormigas() para ant=1 to m // m = tamaño de la colonia solucion = {∅} mientras hay_estados_no_visitados() siguiente=seleccionar_siguiente_estado() solucion = solucion ∪ {siguiente} marcar_como_visitado(siguiente) si(actualizacion_paso_a_paso) actualizar_feromonas_paso_a_paso() // según (13) fsi fmientras evaluar_solucion(solucion) actualizar_conjunto_pareto() fpara ffuncion Listado 2: Adaptación de la gestión de las hormigas a problemas multi-objetivos Capítulo 2. Optimización por Colonias de Hormigas 50 una única matriz de feromonas, actualizando cada colonia la misma matriz de feromonas en función de su objetivo particular. Algoritmos con una colonia y varias matrices de feromonas El algoritmo Bicreterion Ant (BiAnt) [59] se diseñó para dar solución a problemas con dos objetivos. Hace uso de una única colonia pero mantiene dos matrices de feromonas, τ y τ’, una para cada objetivo. La visibilidad depende de cada objetivo, por lo que en el caso del BiAnt se contemplan dos visibilidades η y η´. La ecuación de la probabilidad de selección del siguiente nodo se complica:        -   ′    $   -    .   ′    $   .  ∑  U - U∈12  ′ U $-   U .   ′ U $. ?@  4 ∈ 5  0     CD  E'FE  *?E G (26) donde el valor de λ se calcula para la hormiga ∈1,2… como:  7    ; 1  ; 1 (27) Con la introducción del modificador λ k se asegura que la colonia de hormigas realice búsquedas en distintas regiones del frente de Pareto. El BiAnt ofrece además la posibilidad de controlar el carácter explorador o explotador de resultados de las hormigas con variables α y β diferentes para cada objetivo (26). El algoritmo Pareto Ant Colony Optimization (PACO) [60] también hace uso de matrices de feromonas independientes, una para cada uno de los r objetivos. Cada vez que una hormiga avanza a otro estado, se realiza una actualización local paso a paso de las r matrices de feromonas según la ecuación (13) y considerando un valor constante para el incremento de feromonas, que se corresponde con la cantidad inicial ∆ & . La función para calcular la transición hacia el siguiente nodo se basa en la probabilidad de selección del algoritmo ACS, comentado anteriormente en la página 31, utilizando un vector con r pesos uniformemente aleatorios que se emplean para seleccionar el siguiente nodo j aplicando la ecuación Capítulo 2. Optimización por Colonias de Hormigas 51 4    *v ∈12     7    7 K 7%  -   .   ?@  a  a &    CD  E'FE  *?E G (28) calculándose la variable aleatoria  de acuerdo con la siguiente probabilidad:      + ∑   7    "  K " %  , - +   " , . ∑   ∑   7   U "  K"% # -   U " # .  U∈12   ?@  4 ∈ 5  0 CD  E'FE  *?E G (29) Para cada posible nodo siguiente j se calcula su probabilidad de ser elegido y de entre todos los posibles se elige uno teniendo en cuenta las probabilidades de cada uno. Una forma sencilla de implementar un algoritmo de selección en base a la probabilidad de cada uno es añadir E(10 k ·p j ) copias de cada nodo candidato j a un vector de N elementos, con N= k*100, siendo k la precisión de los decimales que se quiera tener en cuenta para la probabilidad p j de cada nodo. E(n) representa la parte entera de n. Este algoritmo es sencillo de implementar pero introduce un error inversamente proporcional a k. Por otro lado a mayor precisión k (y menor error por tanto) mayor lentitud de cálculo. Algoritmos con una colonia y una matriz de feromonas Multiobjective Ant Colony System (MOACS), implementado para dos objetivos, utiliza una matriz de feromonas y dos visibilidades, η 0 y η 1 , una para cada objetivo a optimizar. La regla de transición entre estados es similar a la del algoritmo PACO: 4  > *v  ∈ 1 2 X   +   & , . +    ,   $   . Y ?@  a Z a &   CD  E'FE  *?E G (30) calculándose la variable aleatoria , que representa el siguiente nodo a seleccionar, de la siguiente forma:       +   & , . +    ,   $   . ∑   U   U & # .   U  # $.  U∈12  ?@  4 ∈ 5  0 CD  E'FE  *?E G  (31) Capítulo 2. Optimización por Colonias de Hormigas 52 Al igual que en PACO, cada hormiga al llegar al nodo j, deposita feromonas en el arco l ij según la ecuación (11), teniendo en cuenta una variación de feromonas fija, mayor que cero e igual a la cantidad de feromonas inicial (∆ & ). Al final de cada iteración, si la solución encontrada es no dominada, se actualiza el Conjunto de Pareto y se reinicia la matriz de feromonas con todos sus elementos iguales a τ 0 . Si la solución encontrada es dominada se realiza la actualización de feromonas según la ecuación (11) teniendo en cuenta, ahora sí, la variación de feromonas correspondiente al mejor camino para ∆. Un enfoque parecido sigue la ampliación del algoritmo Max-Min propuesta por Pinto et al. en [62] con el objetivo de resolver problemas de cuatro objetivos. Dicha ampliación, denominada Multiple Max-Min Ant System (M3AS), mantiene una única matriz de feromonas que se actualiza conjuntamente en función del refuerzo para cada objetivo. Las soluciones no dominadas actualizan la matriz según la ecuación (11) aplicando las cotas máximas y mínimas que se definen en el algoritmo Max-Min a los niveles de feromonas. Esto significa que: Si   I  TU ⇒    ←  TU Si   Z " ⇒  ← " (32) El valor máximo permitido para el nivel de feromonas en una colonia de m hormigas es  TU  ∆¢8 $£ , y el valor mínimo  "  ∆¢8 x$£ , dónde k representa a la solución de la hormiga k-ésima y su variación de feromonas, ∆ 7 , se calcula según la ecuación (23). Otro algoritmo de enfoque similar al M3AS es el Multiobjective Omicron [64] ACO (MOA), que utiliza una única tabla de feromonas y dos visibilidades, una para cada uno de los objetivos para los que fue diseñado. El algoritmo almacena una población de soluciones no dominadas durante un número k iteraciones, antes de actualizar con ellas la tabla de feromonas. La cantidad de feromonas que cada hormiga deposita es fija, y recibe el nombre de ómicron, siendo la regla de actualización de feromonas     ¤/¥, dónde θ es el ómicron y h el número de soluciones no dominadas. Capítulo 2. Optimización por Colonias de Hormigas 53 Algoritmos con varias colonias y varias matrices de feromonas El Bicriterion Multi Colony (BiMC) [59] es una ampliación del BiAnt dada por los mismos autores. En BiMC se consideran tantas colonias como objetivos, cada una con su matriz de feromonas asociada y su propia visibilidad (valor heurístico) y se fuerza explícitamente a cada colonia a buscar cada una en una región diferente del frente de Pareto. Otro algoritmo que opta por la solución basada en más de una colonia de hormigas y varias matrices de feromonas es el COMPETants [63] (cuyo significado es Competing ants). Definido para un problema con dos objetivos a optimizar, usa dos matrices de feromonas, dos visibilidades y dos colonias de hormigas. El número de hormigas para cada colonia no es fijo, sino que varía dinámicamente durante la ejecución del algoritmo, recibiendo la colonia con mejor solución más hormigas para la siguiente iteración. Cada colonia se centra en la optimización de un objetivo, utilizando sus miembros únicamente las feromonas depositadas por otras hormigas pertenecientes a la misma colonia. Una de las novedades del algoritmo COMPETants es la definición del concepto de hormiga espía, como aquella que usa, además, las feromonas depositadas por las hormigas de la otra colonia para la creación de su camino. Las hormigas espías se crean tras la primera iteración, una vez concluido el procedimiento de adaptación del número de miembros de cada colonia, que aumenta la población de la colonia que ha obtenido el mejor coste medio y disminuye la de su colonia competidora. El número de hormigas espías depende de la calidad del mejor recorrido de cada colonia, necesitando la colonia cuyo mejor recorrido sea de mayor coste (peor en un contexto de minimización) un mayor número de espías que su colonia oponente. Las hormigas normales eligen el siguiente nodo con la probabilidad indicada en la ecuación siguiente:      +   , - +   , . ∑    U # -   U # .  U∈12  ?@  4 ∈ 5  0 CD  E'FE  *?E G (33) Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 60 El itinerario propuesto en la Figura 7 podría representar tres grandes competencias A, B y C, determinadas por la primera relación AND que relaciona el nodo 2 con los nodos destino 3 y 4. De la misma forma la relación 4&(10,11) puede identificar dos bloques dentro de la competencia C (Figura 8). En este caso se pretende definir en el grafo itinerarios alternativos al habitual formado por la secuencia ordenada de nodos 1, 2, 3, 5, 4, 10, 11, 12. De esta forma según criterio del equipo pedagógico pueden definirse itinerarios de refuerzo a diferentes niveles, mediante relaciones OR, por ejemplo en los nodos 3, 6 y 11. Figura 8: Identificación de competencias en el grafo de itinerarios de aprendizaje El GIA permite diferentes grafos inconexos en caso de que no exista relación entre los cursos de uno y otro, y el orden en el que se completen sea irrelevante (Figura 9). Figura 9: Ejemplo de grafo para itinerarios de aprendizaje independientes Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 61 El objetivo es encontrar el mejor itinerario para la mayoría de alumnos, pero haciendo posible la recomendación de caminos alternativos en función de las necesidades específicas de cada uno de ellos. La personalización del itinerario consiste un camino alternativo entre dos nodos. Existen ciertas condiciones que deben cumplir todos y cada uno de los grafos que componen el GIA: a) Han de ser grafos dirigidos. b) Han de contar con al menos un nodo con grado de entrada 0, a los que llamaremos nodos raíz. c) Han de tener al menos un nodo con grado de salida 0, a los que llamaremos nodos hoja. d) No pueden tener ciclos. e) Los arcos de salida de un nodo pertenecen a alguno de los tres tipos de restricciones posibles: AND, OR o LINK. f) Una restricción de navegación agrupa a todos los arcos de salida de un nodo. g) Una misma restricción de navegación no puede afectar a arcos cuyos orígenes sean nodos diferentes. h) Los nodos participantes en una restricción de navegación de tipo AND no están conectados entre sí ni directa, ni indirectamente. Es decir, no existe un camino que los conecte. i) Sea el grafo G=(N,A) y °,±∈5 dos nodos unidos con una restricción de navegación de tipo AND, y F∈5 otro nodo del grafo, entonces si existe un camino entre q y r, no existe camino entre p y r. Dada la posibilidad de contar con multigrafos, para evitar un mayor nivel de complejidad en el procesado del mismo, es necesario transformar el Grafo de Itinerarios de Aprendizaje en un grafo conexo siguiendo los siguientes pasos que se describen a continuación: 1. Eliminar relaciones AND de cada grafo del GIA. 2. Crear un único nodo Inicial y un único nodo Final. 3. Conectar cada nodo inicial con todos los nodos raíz del GIA. 4. Conectar todos los nodos hoja con el nodo final. Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 62 3.3.2 Representación formal del grafo Son varios los formatos existentes para la representación de grafos, entre los que podemos destacar Graph eXchange Language (GXL 11 ), Graph Markup Language (GML 12 ), eXtensible Graph Markup and Modeling Language (XGMML 13 ) y GraphML 14 . Se ha elegido GraphML principalmente por su sencillez y extensibilidad. GraphML es un lenguaje basado en XML que permite definir la estructura del grafo, y además ofrece un sencillo mecanismo de extensión para dar soporte a datos específicos de cada problema. GraphML soporta tanto grafos dirigidos como no dirigidos. La sintaxis de un grafo en formato GraphML viene definida por su esquema 15 XML. El Listado 3 muestra la representación gráfica de un grafo dirigido sencillo. El formato de un documento GraphML consta un elemento graphml y varios subelementos: graph, node y edge que definen los diferentes grafos, nodos y arcos que lo componen. A continuación se describe brevemente la estructura de un documento en formato GraphML. Cabecera La cabecera de un documento GraphML tiene el formato que se muestra en el Listado 4. La primera línea del documento indica que es un document conforme con el estándar XML 1.0 y que el juego de caracteres utilizado es UTF-8, la codificación estándar para documentos XML. Por supuesto otras codificaciones podrían tenerse en cuenta para documentos GraphML. 11 http://www.grupo.de/GXL/ 12 http://www.infosun.fim.uni-passau.de/Graphlet/GML/ 13 http://www.cs.rpi.edu/~puninj/XGMML/ 14 http://graphml.graphdrawing.org/ 15 http://graphml.graphdrawing.org/xmlns/1.1/graphml.xsd Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 63 En el Listado 4, la segunda línea contiene el elemento raíz: graphml. El elemento graphml, al igual que otros elementos de GraphML, se definen en el espacio de nombres del lenguaje y por este motivo se define este espacio de nombres como el espacio de nombres por defecto, por lo que no es necesario prefijar los elementos del lenguaje con ningún prefijo distintivo. <?xml version="1.0" encoding="UTF-8"?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns/graphml" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/graphml"> <key id="y" for="node"> <desc>Y coordinate</desc> <default>0</default> </key> <key id="x" for="node"> <desc>X coordinate</desc> <default>0</default> </key> <key id="id" for="edge"> <desc>ID of the link</desc> </key> <key id="weight" for="edge"> <desc>Weight of the arc</desc> <default>0</default> </key> <graph edgedefault="directed"> <node id="Node1"> <data key="y">226.0</data> <data key="x">271.0</data> </node> <node id="Node0"> <data key="y">54.0</data> <data key="x">376.0</data> </node> <edge source="Node0" target="Node1"> <data key="id">0</data> <data key="weight">5.0</data> </edge> </graph> </graphml> Listado 3: Ejemplo de grafo serializado en formato GrahML Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 64 Los otros dos atributos XML son necesarios para especificar el esquema XML para este documento. En el ejemplo se usa el esquema estándar de GraphML ubicado en el servidor graphdrawing.org . EL primer atributo, define el prefijo xsi para los elementos del espacio de nombres de XML. xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" El segundo atributo, indica la ubicación para todos los elementos del espacio de nombres de GraphML: xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd" Aunque es útil para poder validar que el documento esté correctamente formado, las referencias al esquema XML no es obligatoria y la primera parte del documento puede quedar mucho más sencilla (ver Listado 5). Grafo El grafo se declara con el elemento graph. Como elementos internos del grafo, se definen los elementos node y edge para los nodos y arcos del grafo respectivamente. Aunque en el Listado 6 aparecen primero los nodos y luego los arcos, no existe un orden definido para ello y podrían aparecer mezclados. <?xml version="1.0" encoding="UTF-8"?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"> Listado 4: Cabecera de un documento GraphML <?xml version="1.0" encoding="UTF-8"?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns"> ... </graphml> Listado 5: Cabecera reducida de un documento GraphML Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 65 Declaración de un grafo El lenguaje permite mezclar arcos dirigidos y no dirigidos, por lo que si no se especifica ninguna dirección en la declaración de un arco, se aplicará el tipo definido de arco definido por defecto en el atributo edgedefault del elemento graph (Listado 7). Puesto que el lenguaje permite multigrafos, opcionalmente puede asociarse un identificador a cada grafo, a través del atributo id, para poder referenciarlo. Declaración de un nodo Un nodo se declara mediante el elemento node dentro de un elemento graph. Cada nodo ha de tener un identificador único en todo el documento. Es decir, no puede existir otro nodo con el mismo identificador, ni dentro del mismo grafo ni en ningún otro grafo. <graph edgedefault="directed"> <node id="Node1"> <data key="y">226.0</data> <data key="x">271.0</data> </node> <node id="Node0"> <data key="y">54.0</data> <data key="x">376.0</data> </node> <edge source="Node0" target="Node1"> <data key="id">0</data> <data key="weight">5.0</data> </edge> </graph> Listado 6: Ejemplo de grafo en GraphML <graph id=”G1” edgedefault="directed"> ... </graph> Listado 7: Declaración de un grafo en GraphML Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 66 Declaración de un arco Los arcos del grafo se declaran con el elemento edge. Cada arco debe definir sus extremos mediante los atributos source y target que denotan el nodo origen y el nodo destino respectivamente. Los arcos con destino el propio nodo origen, también denominados nodos reflexivos, se declaran con el mismo identificador de nodo para los atributos source y target. Se puede indicar si un arco es dirigido o no con el atributo directed. Si no se especifica este atributo se tendrá en cuenta el definido por defecto para el grafo. Opcionalmente puede diferenciarse el arco del resto mediante el atributo id que, en ese caso, ha de ser único. Declaración de atributos adicionales Como puede verse en el Listado 3, la sintaxis de GraphML define una etiqueta key que permite identificar datos específicos que pueden asociarse a los elementos estructurales del grafo (nodos y arcos), así como al propio grafo. La etiqueta key puede incorporar atributos para especificar el identificador de dicho atributo y, opcionalmente, un nombre y tipo para el mismo. Los atributos nombre y tipo, attr.name y attr.type respectivamente no se usan en el documento y su funcionalidad es poder ser de utilidad a las aplicaciones que procesan el grafo y crean las instancias en algún lenguaje de programación. El tipo está especialmente pensado para un mapeo directo con los tipos de Java, pudiendo tomar los valores boolean, int, long, float, double, o string. El atributo for de un elemento key (Listado 9) puede hacer referencia, como se ha indicado, tanto a los nodos como a los arcos, pero también al propio grafo y a todos los elementos, pudiendo tomar los valores graph, node, edge y all. ... <edge id="e1" directed="true" source="n0" target="n2"/> ... Listado 8: Declaración de un arco en GraphML Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 67 Las propiedades que pueden definirse para cada atributo se limitan a la descripción del atributo y a su valor por defecto, que se definen respectivamente con los elementos description y default, incluidos dentro del elemento key, tal y como muestra el Listado 9. Este mecanismo de declaración de atributos adicionales es el empleado para la relación de cursos SCORM con nodos del grafo (Listado 10). Se utiliza una cadena de texto que representa la URL desde la que acceder al paquete SCORM que contiene el curso. Esta URL ha de ser codificada en Base64 16 para evitar conflictos con el lenguaje XML empleado. Base64 es un sistema de numeración posicional que usa 64 como base. Es la mayor potencia de dos que puede ser representada usando únicamente los caracteres imprimibles de ASCII. Esto ha propiciado su uso para codificación de correos electrónicos y otras aplicaciones. Todas las variantes famosas que se conocen con el nombre de Base64 usan el rango de caracteres A-Z, a-z y 0-9. El uso de un codificador de URL sobre Base64 estándar, sin embargo, no resulta adecuado ya que traducirá los caracteres '+' y '/' en las secuencias especiales '%2B' y '%2F' respectivamente. Si se usa para almacenamiento en base de datos o entre sistemas heterogéneos, producirán un conflicto en el carácter '%' generado por el codificador de URL debido a que este carácter es usado en ANSI SQL como comodín. Este inconveniente puede solucionarse fácilmente modificando el algoritmo de codificación en base 64, para sustituir directamente los caracteres '+' y '/' por '*' y '-' respectivamente, de manera que ya no se necesita usar codificadores de URL (Listado 11). 16 RFC 2045: http://www.ietf.org/rfc/rfc2045.txt ... <key id="weight" for="edge" attr.name="weight" attr.type="double"> <desc>Weight of the arc</desc> <default>0.0</default> </key> ... Listado 9: Declaración de la descripción de un atributo y su valor por defecto Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 68 En el código del ejemplo del Listado 11 se ha utilizado codificado en Base64 la URL http://repository.us.es/scorm/lsi1234, que representa al recurso lsi1234 obtenido como un recurso REST. Para la codificación se utiliza el algoritmo de codificación/decodificación en base 64 de Stephen Ostermiller 17 . Declaración de restricciones de navegación El formato de definición de atributos asociados a los nodos de GraphML facilita la definición de las restricciones del problema. En el escenario propuesto, las restricciones pueden declararse como atributos asociados al nodo origen de la restricción (Listado 12). 17 Base64.java Source Code. © 2001-2010 Stephen Ostermiller. Licencia GPL v2. http://ostermiller.org/utils/Base64.html ... <key id="rel" for="node" attr.name="constraint" attr.type="string"> <desc>Constraint</desc> <default>LINK</default> </key> ... Listado 12: Declaración de restricciones como atributos de los nodos ... <key id="course" for="node" attr.name="course" attr.type="string"> <desc>URL to the SCORM Course</desc> <default></default> </key> ... Listado 10: Declaración de la URL de un curso SCORM como atributo de un nodo ... <node id="Node1"> <data key="y">226.0</data> <data key="x">271.0</data> <data key="course"> aHR0cDovL3JlcG9zaXRvcnl1c2VzL3Njb3JtL2xzaTEyMzQ=</data> </node> ... Listado 11: Ejemplo de nodo con atributo para la URL del curso (http://repository.us.es/scorm/lsi1234) Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 69 Y en la declaración de cada nodo podría utilizarse el atributo restricción para indicar el tipo de restricción aplicable a los arcos de salida. Como puede apreciarse en el Listado 13, se utiliza un lenguaje basado en tokens para diferenciar las diferentes restricciones de navegación. El principal problema asociado a este mecanismo de definición de restricciones de navegación a través del uso de atributos asociados a los nodos, es que a pesar de cumplir con la especificación del lenguaje, carece de información semántica para poder validar una de las restricciones indicadas para los GIA: no es posible garantizar que las restricciones de navegación “LINK” no sean asociadas a nodos con grados de salida mayor que 1. Desde el punto de vista sintáctico el XML es correcto, pero desde el punto de vista semántico, tal y como se ha definido el concepto de GIA, no. Por tanto, la herramienta que se implemente para dar soporte al diseño de GIA a equipos pedagógicos debe realizar esta validación al cargar un fichero GraphML y también en tiempo de edición de un grafo. Para evitar este inconveniente se ha investigado [23], [79] la definición de restricciones mediante el modelado del grafo basado en características, usando el framework de modelado de características MosKitt desarrollado por la Universidad Politécnica de Valencia, que nos permite introducir la información semántica necesaria para validar el documento, evitando el problema anterior. Para integrarlo en el documento GraphML es necesario importar el esquema de MosKitt en la cabecera del documento y definir las restricciones de navegación como características. En [79] además, las restricciones de navegación se consideraron relaciones, definiéndose además las relaciones que indican el carácter opcional u obligatorio de un nodo, así como la inclusión o exclusión de un nodo para indicar relaciones de dependencia entre nodos. Esta última está más relacionada con la implementación de la ... <node id="Node0"> <data key="y">209.0</data> <data key="x">37.0</data> <data key="rel">&Node0::Node1::Node2</data> </node> ... Listado 13: Restricción de navegación en la declaración de un nodo Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 76 donde φ representa una constante con el valor unitario de una feromona y ω 3 es una constante de calibración del sistema. La cantidad de feromonas a depositar depende por tanto de la calificación obtenida por el alumno, así como del mínimo deseado, m i , y de la máxima calificación posible, M i , que pueden ser ambos definidos para cada curso. El procedimiento utilizado se basa en la utilización de las acciones de los alumnos aplicando la meta-heurística ACO, de forma que los alumnos actúan como las hormigas utilizadas en los algoritmos ACO modificando la probabilidad a ij de la ecuación (3) en cada arco a través del depósito paso a paso de Φ feromonas adicionales en cada arco recorrido. De esta forma se aporta un pequeño refuerzo a los arcos que han llevado al alumno a una calificación superior al mínimo requerido y se penaliza a aquellos arcos que no. En realidad, aunque las hemos llamado feromonas para facilitar la comprensión de su objetivo, la cantidad de refuerzo positivo o negativo añadido por la expresión (38) no son feromonas tal y como se entiende en las técnicas ACO, ni son utilizadas por una colonia de agentes (hormigas), sino que simplemente son un modificador de la función de visibilidad en la tabla de decisión de las hormigas. La ecuación para el cálculo de Φ es el nexo de unión entre el mundo real (acciones de los alumnos) y el mundo virtual (hormigas), lo que facilitará la adaptación en tiempo de ejecución y la evolución del sistema. Cada vez que un alumno es evaluado al finalizar un curso, obtiene una calificación ε y se depositan las feromonas correspondientes según la ecuación (38). Si la tabla de probabilidad de cada nodo se basa únicamente en las feromonas depositadas en los arcos que lo tienen como destino, el algoritmo pronto quedará bloqueado en un mínimo local formado por la secuencia de nodos que garantizan una mayor calificación media, pero esto no siempre equivale a un mayor aprendizaje, sino que más bien suele corresponder con la secuencia de cursos que exige un menor esfuerzo o tiene unos test de evaluación de menor dificultad en cada momento. Para minimizar la probabilidad de un rápido bloqueo en el camino de menor esfuerzo es necesario tener en cuenta algún factor relacionado con la complejidad de un curso o con la tasa de éxito. Al igual que en [18] nuestra aproximación [82] también estudia la utilización de pesos, definidos por el equipo pedagógico que diseña el itinerario. Estos pesos se asignan a cada nodo del itinerario (Figura 13). Además del peso aportado por el equipo pedagógico nuestra aproximación tiene en cuenta la idoneidad asociada a cada arco en las restricciones OR: e    u  ·      u x ´  (39) Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 77 donde ω 1 y ω 2 son constantes de calibración que permiten ajustar el sistema durante la experimentación; W j es el peso asignado por el equipo pedagógico, P ij es el factor de idoneidad del arco L ij y Φ ij es la suma de feromonas depositadas en él: ´     ¸  7 " 7 %   µ  (40) Mientras que el peso pedagógico, W j , es definido en tiempo de diseño del itinerario, para el factor de idoneidad, P ij , se propone definir el factor de idoneidad en función de la probabilidad de éxito de cada arco. Figura 13: Nodos del GIA ponderados con pesos pedagógicos Factor de idoneidad basado en la probabilidad de éxito Para calcular el factor de idoneidad P ij según la probabilidad de éxito se utiliza una red bayesiana. Conociendo la probabilidad de éxito de cada rama se puede recomendar una u otra rama. El teorema de Bayes puede aplicarse en el cálculo del factor de idoneidad de la siguiente forma: Sea el nodo de decisión planteado en la Figura 14, parte de un itinerario de aprendizaje del que se conoce, de ediciones anteriores, que del total de alumnos que finalizan el curso F, el 30% continúa con el curso G, el 50% lo hace por el curso H y el 20% restante por el E. También se conoce, de los datos de ediciones anteriores, la probabilidad de que un alumno que ha realizado un determinado curso supere un mínimo deseado al final del itinerario. Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 78 Tabla 6: Probabilidad de obtener una calificación óptima en el nodo Final Nodo   ¹ º»¼½¾ n  ¿ À  G 0,8 H 0,6 E 0,5 Con estos datos podemos calcular: a) la probabilidad, P(Q) de que un alumno obtenga una calificación superior al mínimo deseado, b) la probabilidad de que un alumno que ha obtenido una calificación superior al mínimo deseado, haya elegido el curso G en la restricción OR de la Figura 14. Teniendo en cuenta las probabilidades conjuntas, la probabilidad de que un alumno obtenga una calificación superior al mínimo, P(Q), habiendo realizado el curso G, es P(G∩Q)=P(G)·P(Q|G). Esta probabilidad, y de la misma forma la del resto de nodos de la restricción pueden calcularse con la creación del árbol de probabilidades conjuntas. La probabilidad de obtener una calificación superior al mínimo en el nodo Final de la Figura 14 es (Teorema de la Probabilidad Total): a∑a|³  ³   ¶% (41) que para el ejemplo resulta,   a      ∩ a     ³ ∩ a      ∩ a   0 , 24  0 , 30  0 , 10  0 , 64 Figura 14: Ejemplo de restricción OR Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 79 Para la segunda cuestión aplicamos el teorema de Bayes: |a∩a a 0,24 0,640,375 que indica que un alumno que haya obtenido una calificación superior al mínimo deseado tiene un 37,5% de probabilidad de haber realizado el curso G, siguiendo el arco L FG . De la misma forma, siguiendo el árbol de probabilidades conjuntas (Figura 15) puede calcularse para el resto de nodos de la restricción. Si suponemos que la calificación que se obtenga será superior al mínimo deseado, pueden calcularse las probabilidades para cada nodo de una restricción y usarse para recomendar el mejor camino, haciendo que esta probabilidad basada en los datos históricos pueda influir en la función de ajuste de cada arco (39). De esta forma se utiliza P(G|Q) en la ecuación (39) como P FG , P(H|Q) como P FH y P(E|Q) como P FE . Además ofrece una prestación interesante, pues las probabilidades pueden ser calculadas on-line por el LMS cada vez que un alumno finaliza el itinerario, lo que ayudaría al sistema a evolucionar por sí sólo adaptándose a las nuevas poblaciones de alumnos. Figura 15: Árbol de probabilidades conjuntas Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 80 Este mecanismo es similar al empleado en los filtros anti-spam, y se emplea también para el diagnóstico de fallos estocásticos en e-learning [83] y para la elección de un curso que refuerce ciertos conocimientos que carecen de un andamiaje lo suficientemente robusto. Una aproximación similar a la nuestra se describe en [84], dónde se usa una red bayesiana para combinar la estructura de contenidos con el perfil del usuario y su estilo de aprendizaje, de forma que el sistema pueda recomendar direcciones alternativas. Otros autores [85] han aplicado también las redes bayesianas a la educación para modelar las necesidades de los alumnos, su estado y estilo de aprendizaje con el objetivo de personalizar el contenido educativo que se distribuirá a cada alumno. En una primera aproximación [82] la probabilidad de obtener una determinada calificación se clasificó en tres intervalos, High (0.7MεMM), Medium (0.5M εMZ0.7k ) y Low (0εMZ0.5k), definiendo la función de idoneidad de cada arco L ij como:     É   j | a ÊËÌÊ     j | a ÍÎÏËÐÍ  ?@  0 . 7 k  µ    1 1 5  Ñ CD  E'FE  *?E G (42) La ecuación (42) asigna una probabilidad a cada arco en función de la calificación obtenida en el nodo inicial. Si esta calificación se encuentra en un determinado intervalo, se supone que la probabilidad de superar el mínimo deseado en el nodo siguiente será lo suficientemente alta como para anticipar esa evidencia. A partir de ahí, aplicando el Teorema de Bayes, se asigna al arco L ij la suma de las probabilidades de obtener una calificación en el intervalo High o en el Medium, o lo que es lo mismo, la probabilidad de obtener una calificación superior a la cota inferior del intervalo Medium. En caso de no haber obtenido el alumno una calificación adecuada en el nodo inicio de la restricción OR, se asignará a todos los arcos salientes de i la misma probabilidad, 1/N i , dónde N i es el grado de salida del nodo i. Esta función de idoneidad modifica el impacto introducido por el peso pedagógico definido para cada nodo, lo que hace que la influencia dependa no sólo de la complejidad definida a priori por el equipo pedagógico sino también del rendimiento que los alumnos han obtenido de este curso. Esta combinación es adecuada puesto que el empleo de únicamente el peso pedagógico haría la función de ajuste tendente rápidamente a seleccionar los cursos de mayor peso al principio, y únicamente se produciría un lento cambio en la ruta de aprendizaje tras una gran cantidad de bajas calificaciones. Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 81 El factor de idoneidad se va modificando durante el curso a medida que los alumnos van navegando a través del grafo. Para ello es necesario tener en cuenta algunas consideraciones en la definición del modelo de datos que represente los nodos y arcos del grafo, y que se representan gráficamente en la Figura 16: • Al iniciarse un curso por primera vez, el factor de idoneidad de cada camino L ij será 1/N i , dónde N i representa el número de vecinos del nodo i. • Cada nodo incluirá un contador que reflejará el número de alumnos que lo han recibido y que permitirá calcular la calificación media en dicho nodo. • Cada nodo almacenará en una estructura de tipo clave-valor (ejemplo una tabla Hash) la nota media obtenida en el curso para los alumnos procedentes por cada uno de los arcos de entrada al nodo. Así, para un nodo que tiene tres arcos de entrada, esta estructura contendrá tres entradas cada una asociada a un arco, y contabilizará la nota media en el curso para los alumnos que hayan llegado por cada arco. Este punto obliga a mantener el arco seguido por el alumno durante la realización del curso de ese nodo. • También se almacenará en la estructura anterior, por cada arco de entrada, el número de alumnos que han llegado al curso por dicho arco y el número de ellos que han obtenido una calificación superior a la mínima exigida por el nodo de dicho curso. Figura 16: Ejemplo de tabla hash con información a incluir en el nodo destino para calcular el factor de idoneidad de cada arco de entrada Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 82 Con estas consideraciones se facilita el cálculo de las probabilidades de cada nodo durante la ejecución del algoritmo. Como se vio en el Capítulo 2, la tabla de decisión de un hormiga, )  *  '#, en el nodo i se construye mediante la composición de los rastros locales de feromonas con los valores heurísticos (3). En nuestra aproximación la tabla de decisión de una hormiga se construye con los valores de la función de ajuste, normalizados al intervalo [0,1]: *   '    +   , - + e   '  , . ∑   0 # -  e 0  '  # . 0 ∈ 1 2      ∀ 4 ∈  5  (43) La función de ajuste f ij representa la visibilidad de cada nodo, siendo directamente proporcional a la idoneidad de selección del nodo. La función de ajuste es la que define el concepto de distancia para el problema de las rutas de aprendizaje adaptativas en sistemas e-learning. Las variables α y β son las variables de calibración descritas en el capítulo 2, que sirven para controlar la tendencia del sistema a la exploración de nuevos caminos o a la explotación de los óptimos locales. Esta definición de tabla de decisión nos permite utilizar dos tipos de hormigas diferentes, que depositan dos clases de feromonas diferentes. Las feromonas de la ecuación (38), Φ ij , son depositadas en función de las acciones de los alumnos tras finalizar la evaluación en cada nodo. En otras palabras, podemos decir que son los propios alumnos los que toman el rol de las hormigas de la meta-heurística ACO. Estas feromonas sirven para influir en la distancia entre un curso y el siguiente, modificando la función de ajuste que toma el papel de la visibilidad del arco, η ij , del algoritmo AS. En cambio, las feromonas τ ij son depositadas al finalizar el itinerario completo en los arcos que pertenecen al itinerario, reforzándose además en aquellos arcos que pertenecen a la mejor solución. Estas feromonas servirán de refuerzo a las próximas ediciones de la misma promoción (una nueva convocatoria para realizar los cursos que doten de las competencias necesarias). La probabilidad con la que se selecciona cada nodo se define en la ecuación (4). El siguiente nodo (cursos) en la secuencia de cursos que conforman el itinerario se selecciona aleatoriamente teniendo en cuenta la probabilidad de cada arco. Para implementar este mecanismo de selección se utiliza el algoritmo del Listado 17. Para evitar a largo plazo un excesivo impacto de las feromonas en la función de ajuste f ij , las feromonas sufren el proceso de evaporación igual que en la vida real. En Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 83 una primera aproximación [82] se estudió la evaporación paso a paso de las feromonas, pero al considerar a los alumnos como hormigas en la técnica ACO propuesta se dificulta la experimentación y se pierde una de las principales características de ACO: la exploración de caminos por las hormigas de una colonia. Con alumnos reales no es posible esta opción, pues no es aceptable guiar a determinados alumnos por caminos excesivamente fáciles (en términos de nivel de exigencia requerido) o tediosos (en términos de números de cursos y/o horas necesarias de dedicación). Aunque en un primer experimento los resultados fueron interesantes [82], no son significativos, por lo que se ha planteado una política de evaporación ligeramente diferente, definida por la siguiente ecuación: ´   '  1    1 ; <  ´   '    ¤ O"T0  µ  (44) donde ´  '1 representa la cantidad de feromonas existentes en el arco l ij en el instante t+1 y ρ es la tasa de evaporación. Mientras que la deposición de las feromonas por el recorrido de los alumnos se realiza paso a paso, la evaporación de las feromonas depositadas por éstos se lleva a cabo una vez que el grupo de alumnos ha completado el itinerario. El término ¤ O"T0 µ representa la variación de feromonas dependientes de la calificación final obtenida por el alumno k, y se deposita sólo en los arcos del recorrido seguido, una vez completado el recorrido. ¤   µ    b ´ O"T0  µ  ?@     ∈  A 7 0 CD  E'FE  *?E G (45) donde ´ O"T0 µ se calcula como sigue: ´ O"T0  µ    ;  1 ; µ O"T0  d ;  u ¶ X  O"T0 k ; µ O"T0 Y , ?@  µ O"T0 Z  O"T0 k µ O"T0 d   u ¶ X µ O"T0 ;  O"T0 k Y , ?@  µ O"T0 n  O"T0 k G  (46) L  Lista de elementos vacía tam = 0; Para cada arco L ij de una restricción OR n  a ij *100; Desde k=0 hasta n añadir L ij a L; tam = tam + 1; finDesde finPara r  generar número aleatorio entre 1 y tam seleccionar arco en la posición r-ésima de L Listado 17: Algoritmo de selección aleatoria con probabilidad determinada de un arco Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 84 La actualización y evaporación de las feromonas τ ij , depositadas por las hormigas artificiales, se rigen por las ecuaciones del algoritmo AS (5), (6) y (7), teniendo en cuenta que en la ecuación (7), la distancia entre dos nodos es el valor de la función de ajuste para el arco que los une, y por tanto la distancia total del recorrido seguido por el alumno es la suma de los valores de la función de ajuste para los arcos del recorrido. El refuerzo se divide entre el número de nodos o vértices que tiene el recorrido para potenciar también los recorridos más cortos. ∆   7  '     e  7  '  D~ _ CF'@C?  A 7  '   ?@    ∈ A 7  '  0 ?@    ∉  A 7  '  G (47) Esta distancia, al estar sujeta a actualizaciones paso a paso del resto de alumnos no es constante, sino que evoluciona y varía con el uso del sistema, por lo que se calcula cada vez que se ejecuta el proceso de evaporación de estas feromonas. Nótese que en la ecuación (39), la cantidad de feromonas, Φ ij , existentes en el arco l ij en el momento de calcularse la función de ajuste, es debida a otros alumnos que han escogido el mismo arco y han depositado feromonas en el nodo j pero no al propio alumno cuya decisión del siguiente curso se esté evaluando. Por tanto, el valor en ese momento de Φ ij debe existir en cada arco, por lo que además de las feromonas τ ij debe existir también este otro tipo de feromonas Φ ij como atributos de los elementos de un grafo. Esto también es un proceso de influencia estigmérgica, en el que un conjunto de miembros de un colectivo está influenciando a otro igual en una decisión, modificando el entorno (la función de ajuste en este caso). Esto es lo que se pretendía desde un principio, encontrar una forma de influir de un grupo de individuos en otro, obteniendo algún beneficio para todo el grupo. Las feromonas Φ ij son depositadas por las acciones llevadas a cabo por los alumnos reales (humanos) mientras que las tradicionales feromonas τ ij son las calculadas mediante un algoritmo ACO para la búsqueda de una solución óptima. Las primeras sirven para modificar la función de ajuste de cada arco, de forma que el valor heurístico “distancia” entre dos cursos varíe en función de los resultados obtenidos por los alumnos. Las segundas son creadas por el sistema gestor de aprendizaje en el proceso de búsqueda del mejor camino. Capítulo 3. Aplicación al Problema de las Rutas de Aprendizaje 85 3.3.5 Implementación El objetivo de esta sección no es documentar el proyecto software sino simplemente las decisiones más importantes en cuanto a diseño del framework que posteriormente se ha utilizado para la experimentación. El lenguaje utilizado ha sido Java en su versión J2SE 1.6. Tras analizar varias librerías para el manejo de grafos (JGraphT 18 , JGraph 19 y JUNG 20 ) nos decidimos por la librería de código abierto JUNG por su madurez, por tener soporte para múltiples tipos de grafos (multigrafos, grafos dirigidos, anidados), gestores de presentación (para el color, disposición en pantalla, formas, etc), ser capaz de almacenar los grafos en diferentes formatos (entre ellos GraphML que se adapta a nuestros requisitos), la buena documentación que ofrece y los extras que la diferencian de otras librerías: análisis estadístico, algoritmos para el cálculo de distancias, clustering, etc. Una vez decidida la librería gráfica a utilizar, el siguiente paso es definir los objetos necesarios en el dominio de nuestro problema, que en nuestro caso se resumen en la definición del nodo, arco, hormiga, colonia de hormigas, feromonas, rastro de feromonas, condiciones de parada y el planificador o demonio de ejecución de los algoritmos ACO. Elementos de un grafo: nodos y arcos La librería JUNG define la jerarquía de interfaces según la Figura 17. La base de toda la jerarquía de grafos de esta librería es la interfaz HyperGraph, de la que hereda la interfaz Graph (que define la funcionalidad básica de un grafo) y de ésta a su vez, las interfaces DirectedGraph (que define la funcionalidad de un grafo dirigido) y UndirectedGraph (que define la funcionalidad de un grafo no dirigido). Lo primero que observamos en esta librería es que la interfaz Graph está parametrizada con dos tipos genéricos, V y E, correspondientes a los vértices y arcos del grafo respectivamente, por lo que nos exige definir en nuestro modelo estos tipos. Para facilitar la separación de la funcionalidad necesaria para la visualización se define ésta en la interfaz GraphMember que representa a cualquier elemento miembro de un grafo dibujable en un plano (nombre del elemento y coordenadas x e y que determinen su 18 http://www.jgrapht.org/ 19 http://www.jgraph.com 20 The Java Universal Network/Graph Framework. http://jung.sourceforge.net/ Capítulo 3. El Problema de las Rutas de Aprendizaje 92 elementos del grafo que tengan un nivel de feromonas p=0) y evitar un error al leer o escribir el grafo (null = NaN 22 ) se implementa la clase Weight, como un envoltorio 23 de los números reales apropiado para cualquier tipo de peso del grafo, y de la que hereda la clase Pheromone. La condición de parada para el planificador se especifica a través de la interfaz StopCondition y ha de ser proporcionada por cada algoritmo ACO que use nuestro framework, si bien se proporcionan en el framework una sencilla implementación basada en el número de iteraciones finalizadas, que hará que el planificador detenga la ejecución una vez alcanzado el número máximo de iteraciones establecida. Aplicación de ACO a la construcción de itinerarios de aprendizaje adaptativos Nuestra aproximación se basa en la aplicación de técnicas ACO en e-learning con el objetivo de conseguir un sistema capaz de evolucionar los itinerarios de aprendizaje según las necesidades de cada momento. El procedimiento consiste en simular el comportamiento de un conjunto de alumnos participantes en un itinerario formativo para intentar proponer el mejor camino. En este trabajo tan sólo se tiene en cuenta la calificación obtenida en los cursos como criterio de la bondad de un camino, aunque ésta puede depender de múltiples factores, que quedan fuera del alcance de este trabajo, como la mejor adaptación de un arco frente al resto (en un nodo con grado de salida mayor que 1) debido al tipo de aprendizaje más adecuado en cada alumno (personalización del proceso de aprendizaje: deductivo, inductivo, etc.). Debido a que la distancia entre dos cursos (nodos en el grafo de itinerarios de aprendizaje) depende, entre otros factores, de la calificación que los alumnos obtengan en el nodo destino, la ejecución de un algoritmo ACO clásico en el que una colonia de hormigas busca la solución óptima a lo largo de un número determinado de iteraciones no es aplicable, puesto que aunque podríamos simular las calificaciones mediante generación de números aleatorios, esto no nos garantiza que se correspondan con las calificaciones de los alumnos reales que participan de la formación. La aplicación de ACO a este problema, requiere que los propios alumnos asuman el rol de hormigas del algoritmo ACO empleado, depositando las feromonas correspondientes en función de la 22 Not a Number. 23 Patrón de diseño Wrapper, del libro Design Patterns, de Erich Gamma et al. [86] Capítulo 3. El Problema de las Rutas de Aprendizaje 93 calificación obtenida en el arco del grafo seguido. Por tanto no existen hormigas virtuales, sino que este rol es desempeñado por los alumnos reales. De la misma forma, el número de iteraciones que conduce a una colonia de hormigas a encontrar una solución lo suficientemente buena, pasa a convertirse en nuestro problema en el número de promociones que participarán en la formación, pudiendo este número de promociones ser infinito, puesto que lo que realmente interesa es la capacidad de adaptación (de variación) a los cambios por parte del algoritmo y no elegir una mejor solución tras un número predeterminado de iteraciones. Esta adaptación, se medirá mediante la observación de los resultados obtenidos mediante simulación, analizando la sensibilidad del algoritmo para reforzar los mejores caminos de promociones anteriores, en mayor o menor grado, así como midiendo la distribución del reparto (en términos porcentuales) de alumnos por cada itinerario durante las sucesivas promociones. En nuestra aproximación, al desempeñar los alumnos el rol de hormigas virtuales, no existe una colonia de hormigas como tal, puesto que, los miembros de la colonia no repiten promociones, sino que se renuevan en cada promoción. Para la implementación, se tendrán en cuenta los siguientes puntos para la experimentación: 1. El punto de partida es único en el itinerario formativo diseñado por un equipo pedagógico, teniendo en cuenta itinerarios alternativos de aprendizaje (cursos de refuerzo, de ampliación, etc.). Si se cuenta con datos históricos para el mismo grafo de itinerarios de aprendizaje (no es la primera edición del itinerario formativo) se utilizarán para el cálculo del factor de idoneidad P ij aplicando la ecuación (42). Puesto que en un instante inicial no se dispone de datos históricos para poder calcular el factor de idoneidad P ij (42) de la función de ajuste, se tendrá en cuenta que: a) En los nodos con grado de salida 1, el factor de idoneidad de su arco de salida es 1. b) En los nodos con grado de salida n>1, el factor de idoneidad de cada arco es 1/n. 2. Cada vez que un alumno es evaluado al finalizar el curso de un nodo j, se producirá una realimentación Φ ij que modificará la visibilidad del arco l ij seguido para llegar a j, de acuerdo con la ecuación (38). Capítulo 3. El Problema de las Rutas de Aprendizaje 94 3. En los nodos con grado de salida n>1, la elección del siguiente curso se llevará a cabo probabilísticamente en función de las feromonas τ ij depositadas en los n arcos de salida. 4. Nuestra aproximación permite la adición de nodos en cualquier momento. Cuando se añada un nuevo nodo, su factor de idoneidad P ij será 1 y Φ 0 =0, por lo que la visibilidad inicial de un nodo será un factor proporcional de su complejidad (indicada por su peso pedagógico): ω 2 ·W j 5. El número de feromonas en el instante inicial es τ ij =0.1 para cada arco, para evitar una indeterminación en los valores a ij de la tabla de decisión. 6. El modelo empleado para representar los itinerarios de aprendizaje permitirá contabilizar la cantidad de feromonas depositadas en los arcos y nodos del grafo en cualquier instante. Algoritmo ASALI A continuación, mostramos el algoritmo ASALI (Ant System for Adaptive Learning Itineraries) para hacer posible la adaptación del itinerario formativo de los alumnos según las necesidades del colectivo, basándonos en el procedimiento descrito en este trabajo. Se han eliminado las instrucciones relacionadas con la obtención de datos de la interfaz gráfica y tratamiento de estructuras de datos, que no son de gran interés para el estudio de aplicación de ACO en el contexto descrito. La ejecución del algoritmo se inicia con la ejecución de una instancia del hilo (Thread) ASALIOptimizer, cuyo método run se resume en el Listado 20. Este método consiste en comprobar que existe un grafo para el que se puede calcular el mejor camino, iniciando en este caso, mediante una técnica de inmersión, el procedimiento de inicialización con los parámetros para el algoritmo y el inicio del planificador encargado del cálculo del mejor camino. Todo este proceso se realiza en la llamada al método evolve()que devuelve el mejor camino encontrado a través del objeto de retorno Trail (Listado 21). Capítulo 3. El Problema de las Rutas de Aprendizaje 95 La clase Scheduler es la que implementa la meta-heurística ACO. Esta clase pertenece al framework desarrollado para trabajar con algoritmos ACO y es la misma para cualquier implementación de ACO. A continuación se describe como volver a traspasar la responsabilidad a las clases concretas de cada algoritmo. En la construcción del planificador, además de establecer como atributos los parámetros que se pasan en el constructor como la colonia de hormigas, la condición de finalización, la función objetivo y el actualizador de feromonas (Listado 22), se crea el entorno en el que la colonia actuará. La ejecución del algoritmo es llevada a cabo por el planificador en un hilo de ejecución independiente, tras la invocación al método run del planificador (Listado 23). El proceso de inicialización consiste en el establecimiento de un valor inicial para las feromonas de cada arco del grafo. En nuestro caso lo que se hace es establecer como valor inicial la inversa del número de vértices que tiene el grafo, al igual que en al algoritmo ACS [27]. Posteriormente, mientras no se haya alcanzado la condición de parada, que en nuestro caso se corresponde con un número de iteraciones determinado, se procede secuencialmente a la creación de soluciones, la actualización de feromonas y la ejecución de acciones por parte del planificador public void run() { if (graph == null || graph.getVertexCount() == 0) { frame.noGraphWarning(); // WARNING: No hay grafo }else { // Obtener el mejor camino this.trail = evolve(); // Calcular el coste del camino Collection<GraphElement> elements = trail.getElements(); Iterator<GraphElement> iterator = elements.iterator(); double cost = 0.0; while (iterator.hasNext()) { cost = cost + iterator.next().getWeight(); } // Luego este coste puede mostrarse por pantalla. } } Listado 20: Inicio del algoritmo Capítulo 3. El Problema de las Rutas de Aprendizaje 96 . public Scheduler(Colony colony, StopCondition condition, ObjectiveFunction function, PheromoneUpdater updater) { this.condition = condition; this.function = function; this.updater = updater; environment = new Environment(colony); } Listado 22: Constructor del planificador public Trail evolve() { // Crear factoria AsaliTrailFactory factory = new AsaliTrailFactory(this.graph); // Añadimos los valores de ω, α y β desde la interfaz gráfica (no se muestra) // Crear colonia de hormigas con niveles de rendimiento h m y l LearnersColony colony = new LearnersColony(this.csize, h, m, l); colony.setTrailFactory(factory); // La condición de parada compuesta por una o más condiciones CompoundStopCondition condition = new CompoundStopCondition(); // Una de las condiciones es el número de iteraciones IterationTest itest = new IterationTest(this.iterations); condition.add(itest); // Función objetivo DefaultObjectiveFunction function = new DefaultObjectiveFunction(); // Acción a ejecutar por el demonio AsaliDaemonAction daemonAction = new AsaliDaemonAction("asali"); // Actualizador de feromonas DefaultPheromoneUpdater updater = new DefaultPheromoneUpdater(); // Creamos el planificador (demonio) Scheduler sc = new Scheduler(colony, condition, function, updater); // No establecemos ningún mecanismo de búsqueda local sc.setLocalSearch(new NoLocalSearch()); sc.setDaemonAction(daemonAction); // Iniciamos la ejecución sc.run(); // Devolvemos el mejor camino return colony.getBest().getBestTrail(); } Listado 21: Procedimiento de inicio Capítulo 3. El Problema de las Rutas de Aprendizaje 97 Creación de Soluciones La creación de soluciones es tarea de la factoría encargada de crear caminos, pues una solución no es sino un camino en el grafo. Para ello el planificador delega en cada hormiga, para que cree su camino y éstas a su vez en la factoría de la colonia (Listado 25). A la hora de crear un camino, la hormiga indica a la factoría qué tipo de hormiga es a través del parámetro type (Listado 25). public void run(){ initialize(); while (!condition.isReached(environment)) { environment.increment(); createSolutions(); updatePheromones(); daemonActions(); } } Listado 23: Ejecución del planificador. Método Scheduler::run. protected void createSolutions() { for (Ant ant : environment.getColony().getPopulation()) { Trail trail = ant.walk(); // La hormiga camina trail = search.explore(trail); // mejorar con búsqueda local ant.setTrail(trail); // fijar mejor camino trail.setCost(function.evaluate(trail)); // fijar coste trail.setIteration(environment.getIteration()); // fijar iteración } } Listado 24: Método de creación de soluciones del planificador public Trail walk(){ setTrail(colony.getTrailFactory().createTrail(type)); return trail; } Listado 25: La hormiga crea su camino apoyándose en la factoría de la colonia Capítulo 3. El Problema de las Rutas de Aprendizaje 98 El algoritmo de creación de un camino por la factoría se describe a continuación (Listado 26). public Trail createTrail(int type){ double score = 0.0; double coste = 0.0; double peso = 0.0; double phi = 0.0; Edge previousEdge = null; Trail trail = new DefaultTrail(type); LearnerProfile p = new LearnerProfile(type); // Perfil de la hormiga Set<Vertex> visited = new HashSet<Vertex>(); Vertex v = getRootVertex(); double drops = 0.0; while (graph.outDegree(v) > 0) { if (!visited.contains(v)) { // Simular la evaluacion del alumno en v score = takeExam(v, p); // Incrementar feromonas en función de la nota obtenida if (previousEdge != null) { phi = calcularPhi(score, v.getMinimum(), v.getMaximum(), PHI, OMEGA3); drops = previousEdge.getRecentDrops().getValue(); previousEdge.setRecentDrops(new Pheromone(drops + phi)); v.addScore(score, ""+previousEdge.getId()); }else { v.addScore(score); } v.setLastScore(score); trail.add(v); // Añadir al recorrido peso = peso + v.getPeso();// Sumar al peso total coste = coste + v.getAverageScore(); } Vertex next = nextVertexOnTrail(trail, v, prob, score); // Obtenemos el arco a partir del siguiente vértice previousEdge = (Edge) graph.findEdge(v, next); v = next; } // Último nodo score = takeExam(v, p); if (previousEdge != null) { phi = calcularPhi(score, v.getMinimum(), v.getMaximum(), PHI, OMEGA3); drops = previousEdge.getRecentDrops().getValue(); previousEdge.setRecentDrops(new Pheromone(drops + phi)); v.addScore(score, ""+previousEdge.getId()); }else { v.setLastScore(score); } v.setLastScore(score); trail.add(v); // Añadir la hoja al recorrido peso = peso + v.getPeso(); coste = (coste + v.getAverageScore())/peso; trail.setCost(new NumericCost(coste)); return trail; } Listado 26: Creación de un camino por la factoría Capítulo 3. El Problema de las Rutas de Aprendizaje 99 El rendimiento de cada alumno puede simularse por las hormigas ACO, que según su perfil, obtendrán una mayor o menor calificación en el proceso de simulación del examen de cada nodo. Cada vez que una hormiga calcula un nuevo camino lo almacena en su memoria. Tras crear el perfil como alumno para la hormiga actual, comienza un recorrido por el grafo, siempre desde el nodo raíz (con grado de entrada 0) hasta el nodo final (con grado de salida 0). Durante el recorrido, se va simulando la evaluación del alumno (representado por la hormiga virtual) mediante el método takeExam(v, p) que devuelve la calificación para el alumno en el nodo v, de acuerdo a las probabilidades dadas por su perfil p. La generación de la calificación se calcula mediante una función que devuelve con una probabilidad pr un número aleatorio dentro del rango [min, max] determinado por el perfil de rendimiento del alumno, con MIN_SCORE < min < max < MAX_SCORE siendo el intervalo [MIN_SCORE, MAX_SCORE] el rango de calificaciones posibles. /** * Genera con probabilidad p un valor aleatorio comprendido en el intervalo * R = [min,max] incluido en el intervalo [rangeMin,rangeMax]. * * Precondiciones: 0<E(probability)<100 & RANGE_MINIMUM<min<max<RANGE_MAXIMUM * Postcondiciones: n in [min,max] con probabilidad = probability * @param probability Probabilidad de obtener un entero entre el intervalo dado dentro del rango [RANGE_MINIMUN,RANGE_MAXIMUM] * @param min Número mínimo del intervalo * @param max Número máximo del intervalo * @param rangeMin mínimo valor del intervalo de búsqueda * @param rangeMax máximo valor del intervalo de búsqueda * @return Devuele un númoer aleatorio dentro del rango [min,max] con una probabilidad dada. * @throws IllegalArgumentException Si no se cumplen las precondiciones */ public int generateRandomIn(float probability, int min, int max, int rangeMin, int rangeMax )throws IllegalArgumentException { int result; int p; if (min > max || min < rangeMin || max > rangeMax || probability < 0f || probability > 100f) { throw new IllegalArgumentException("Invalid range"); } p = Math.round((rangeMax - rangeMin)*(probability/100)); // En el constructor se construye: Random random = new Random(); int r = random.nextInt(rangeMax); if (r < p) { result = generateRandomIn(min,max,rangeMin,rangeMax); }else { result = generateRandomOut(min,max,rangeMin,rangeMax); } return result; } Listado 27 : Generación aleatoria de un numero con una probabilidad dada de estar contenido en un rango determinado Capítulo 3. El Problema de las Rutas de Aprendizaje 100 Para la generación de un número aleatorio dentro de un rango determinado utilizamos la función matemática nextInt de la clase Random del paquete java.util de Java. La función nextInt(int n) función genera números pseudoaleatorios con una distribución aproximadamente uniforme en el rango [0, n]. Para conseguir un número aleatorio en el rango [min,max] utilizamos la expresión: random.nextInt(max - min) + min Puesto que esta clase sólo ofrece la posibilidad de generar un número aleatorio dentro de un rango determinado, la forma de actuar para obtener un número aleatorio fuera de un determinado rango es rellenar un vector con números aleatorios que se encuentren en los diferentes intervalos fuera del rango deseado, tal y como se describe en el ejemplo de la Figura 21: Figura 21: Esquema para la generación de números aleatorios fuera de un rango dado EL algoritmo del Listado 26 construye caminos desde el nodo raíz al nodo final. En cada iteración, se obtiene un nuevo nodo mediante el método nextVertexOnTrail que se muestra en el Listado 28. Capítulo 3. El Problema de las Rutas de Aprendizaje 101 Cada vez que el algoritmo busca el siguiente vértice en el camino que está construyendo, vuelve a construir la tabla de decisión para cada arco. En lugar de crear la tabla de decisión al inicio del proceso y actualizarla durante la ejecución, se ha optado por esta opción para permitir cambios estructurales en el grafo de itinerarios de aprendizaje en tiempos de ejecución. Esto es, la eliminación o adicción de nodos y sus correspondientes arcos, lo que podría dar lugar a la desaparición o aparición de caminos respectivamente. Es por esta razón que se ha optado por una tabla Hash como estructura de datos para la tabla de decisión en lugar de utilizar un array de tamaño fijo. El Listado 29 muestra el algoritmo encargado de la creación de la tabla de decisión. Este algoritmo recorre el conjunto de arcos del grafo y calcula para cada uno de ellos el valor correspondiente para la tabla de decisión, según la ecuación (3). La creación de cada elemento de la tabla de decisión se divide en dos tareas: calcular el numerador y calcular el denominador de la expresión (3). En el cálculo del numerador (Listado 30) se introduce la principal novedad de este trabajo, mediante el cálculo de la función de ajuste que actuará como valor heurístico, η, del problema. private Vertex nextVertexOnTrail(Trail trail, Vertex v, float prob, double score) { Vertex destino = null; // Obtenemos los arcos de salida Collection<Edge> arcos = graph.getOutEdges(v); // Obtenemos los vecinos del nodo Collection<Vertex> vecinos = graph.getNeighbors(v); // Para cada arco saliente calcular su tabla de decisión Hashtable<Edge,Double> decisionTable = createDecissionTable(arcos, score); // Seleccionar uno de ellos en base a dicha tabla de decision Edge edge = chooseEdge(decisionTable); // Y se añade al recorrido si no lo estaba Collection<Vertex> incidents = graph.getIncidentVertices(edge); if (incidents.size() > 1) { // El vértice no está conectado consigo mismo destino = (Vertex) graph.getDest(edge); } return destino; } Listado 28: Método que calcula el siguiente arco en la construcción de un posible itinerario solución Capítulo 3. El Problema de las Rutas de Aprendizaje 108 ficheros de texto con extensión .csv los datos necesarios para el estudio del algoritmo. En concreto graba dos ficheros, uno con los itinerarios seleccionados por cada hormiga en cada iteración y otro con la evolución de los pesos y feromonas de cada arco del grafo, según el comportamiento (calificaciones obtenidas) de la colonia. Consideraciones Mientras que en la vida real, las feromonas se evaporan con el tiempo, medido éste en segundos, en nuestra solución las feromonas se evaporan al final de una iteración. El final de una iteración coincide en nuestro caso con el final de una promoción de alumnos que participa en la formación, y sucede cuando o bien todos los alumnos han finalizado la formación o bien cuando se ha llegado a la fecha límite para su finalización. A diferencia de lo que sucede en la vida real, nuestro algoritmo lanza a las hormigas en busca de solución secuencialmente y no en paralelo. En la formación online en la vida real, es muy frecuente que los alumnos de la misma promoción comiencen sus primeros cursos en momentos diferentes, y vayan completando su itinerario a velocidades diferentes. El tipo de hormiga que se lanza cada vez (High, Medium o Low) es aleatorio, esto es, no se lanzan todas las de un tipo y seguidamente las de otro. private Vertex getPreviousVertex(Collection<GraphElement> tvertices, Vertex dest) { Vertex pv = null; Vertex aux = null; boolean enc = false; Iterator<GraphElement> iterator = tvertices.iterator(); while (!enc && iterator.hasNext()) { aux = (Vertex) iterator.next(); if (aux.equals(dest)) { enc = true; }else { pv = aux; } } if (!enc) { pv = null; } return pv; } Listado 37: Método que obtiene el vértice anterior a uno dado Capítulo 4. Resultados experimentales 109 Capítulo 4. Resultados experimentales 4.1 Entorno de pruebas Las pruebas del comportamiento de los algoritmos se han realizado con un ordenador HP 6730b con procesador Intel Centrino ® 2, con 2Gb de memoria RAM. El programa de pruebas se ha implementado en Java™ y se ejecuta sobre el JRE 1.6. 4.2 Descripción de la experimentación El objetivo de la experimentación es estudiar la capacidad del algoritmo ASALI para, utilizando las calificaciones obtenidas por los alumnos en cada curso, poder adaptar el itinerario más recomendable para la mayoría de alumnos en las sucesivas promociones e incluso, en menor medida, en la misma promoción. El método usado consiste en la simulación del comportamiento de los alumnos por las hormigas del algoritmo ACO, de forma que aplicando el método de Monte Carlo pueda generarse un estado inicial y a partir de él comprobarse la capacidad de la solución propuesta para adaptar de forma autónoma el itinerario en función de las calificaciones medias obtenidas en cada nodo. El comportamiento de los alumnos queda limitado en este experimento a la simulación de la realización del examen que proporcionará al alumno la calificación en cada curso, para lo que se usará un generador de calificaciones pseudoaleatorias. Una vez obtenida la calificación el alumno continuará el itinerario por el siguiente curso que asigne el algoritmo. En este caso no se ofrece al alumno varias opciones a elegir, puesto que esto dificultaría el estudio de adaptabilidad del algoritmo, al estar sometido entonces el proceso a la libre e impredecible elección del alumno. Se ha optado por simular el comportamiento del alumno ante la dificultad para llevar a cabo experimentos con alumnos reales, lo que aumentaría el tiempo y coste del experimento, y dificultaría la extracción de conclusiones relativas al comportamiento del algoritmo al estar presente una componente humana sobre la que no se tiene control. En este experimento nos interesa estudiar la variación en refuerzo del mejor camino (el de mayor calificación media final) en diferentes muestras de alumnos, cada una de ellas Capítulo 4. Resultados experimentales 110 con diferentes proporciones de alumnos de cada perfil (que en nuestro experimento simplificaremos en tres perfiles, según su rendimiento). Puesto que el objetivo es estudiar el comportamiento del algoritmo, y no realmente el beneficio que puedan obtener los alumnos reales de la aplicación de éste en un entorno de e-learning real (cuyo estudio supondría un trabajo futuro de continuación de esta tesis) partimos de la hipótesis de que existen estas promociones de alumnos, cuyas calificaciones simularemos mediante un generador aleatorio de calificaciones, dentro de un rango adecuado a cada perfil. Para la experimentación se utiliza el algoritmo ASALI en sucesivas iteraciones, guardando el estado al final de cada iteración en una hoja de cálculo, para comprobar la evolución del itinerario en cada iteración. 4.2.1 Consideraciones previas Frente a la evaluación sistemática como mecanismo de selección de los mejores individuos este trabajo persigue la concepción de la evaluación como método de identificación de necesidades de refuerzo, y en consecuencia un mecanismo causal para poder plantear caminos alternativos. Estos caminos podrían ser detectados de entre los cursos alternativos, que a pesar de tener un menor peso pedagógico se ajustaran mejor a las características de los usuarios. Esta detección podría ser identificada a través de la función de ajuste planteada en este trabajo (39), que vería reforzado su valor bien por el factor de idoneidad del curso (42) o por el refuerzo proporcionado por otros alumnos que lo hubieran realizado a través de las feromonas on-line depositadas (44). Siguiendo un enfoque optimista, si al inicio del itinerario los alumnos están distribuidos en forma normal respecto a su aptitud para una determinada materia, y durante el proceso se les proporciona una instrucción de acuerdo a las características y necesidades de cada alumno, el rendimiento de ellos al término del proceso deberá indicar que casi todos logran el dominio del aprendizaje, superando una determinada calificación mínima deseada (Figura 22). Figura 22: Distribución teórica de calificaciones antes y después de la formación Capítulo 4. Resultados experimentales 111 Para simplificar la complejidad de la experimentación y poder simular la diversidad de alumnos en cuanto a diferente ritmo de aprendizaje y diferentes resultados (calificaciones) se discretiza la población de alumnos en tres perfiles: Low, Medium y High, correspondiéndose respectivamente con alumnos que obtienen calificaciones bajas (es un caso muy común en la formación on-line en empresas, con profesionales que tienen durante la formación un pico de trabajo alto que les resta tiempo de dedicación a la formación), medias (que sería el caso más frecuente) y alumnos que obtienen calificaciones excelentes (no hay correspondencia directa con los alumnos más brillantes, sino que, en muchas ocasiones, suele ser indicativo de utilización de algún método de respuesta fraudulento en los tests de evaluación, y generalmente se corresponde con un tiempo de dedicación a la realización del test inferior a la media). Así, en lugar de suponer una probabilidad uniforme para la variable que representa la calificación, se aplican los perfiles indicados tal y como se muestra a continuación. Esta clasificación no supone que los alumnos pertenezcan a uno u otro grupo antes de comenzar el curso, sino que es una previsión de lo que queremos obtener una vez finalizado el curso por todos los alumnos, pues las calificaciones serán simuladas mediante algoritmos de generación de números aleatorios con una probabilidad dada. Para simular esta variedad en la población de alumnos, se modifica la colonia de hormigas del algoritmo ACO propuesto para que incluya hormigas de los tres tipos diferentes de perfil. Para ello se añade al framework la clase LearnersColony que amplía la funcionalidad de una colonia genérica de hormigas (clase Colony) para dar cabida a varios tipos de hormigas diferentes (Figura 23), cada uno tendente a obtener una calificación dentro del rango más probable que le corresponde. Capítulo 4. Resultados experimentales 112 Consecuentemente hay que adaptar la interfaz gráfica de la aplicación de prueba con el objeto de poder especificar la proporción de la población de la colonia que pertenece a un perfil u otro, de forma que pueda crearse la colonia con estas proporciones. La Figura 24 muestra una captura de la interfaz gráfica del programa creado para la experimentación y que utiliza el framework descrito en el capítulo anterior. Mediante unos controles deslizantes se permite modificar la proporción (en porcentaje) de un perfil u otro de la población de la colonia, lo que permitirá simular una audiencia de alumnos compuesta por alumnos de estos perfiles en igual proporción. Además de las proporciones de cada perfil de alumno, el panel de configuración permite modificar las variables de calibración del sistema (ω 1 , ω 2 y ω 3 ), las variables que controlan la tendencia a explorar o explotar soluciones (α y β), la composición de la colonia (número de colonias y número de hormigas por colonia) y el número de iteraciones que cada hormiga realizará. Figura 23: Colonia de alumnos como ampliación de una Colonia genérica Capítulo 4. Resultados experimentales 113 Figura 24: Aplicación ACO4ALI desarrollada para la experimentación Para simular los diferentes perfiles de alumnos utilizaremos un generador de números pseudoaleatorios, que ha sido modificado para generar números de forma aleatoria dentro de un rango dado con una probabilidad determinada. Se utiliza una distribución de probabilidad normal. Esto no implica que la distribución de las calificaciones pudiese corresponder a un modelo probabilístico tras un período de enseñanza-aprendizaje, puesto que, supuestamente, el azar no tendría cabida cuando ha existido un esfuerzo sistemático por mejorar los niveles del conocimiento de los alumnos. Para nuestro experimento vamos a suponer que el resultado de la evaluación de un curso es independiente de los obtenidos en cualquier otro anterior, El perfil Low clasifica los alumnos participantes en el itinerario formativo cuyas calificaciones en los test de evaluación de curso se encuentran en un 95% entre un 3 y un 5 (en una escala de 0 a 10). Es el perfil menos habitual, y cuando aparece suele ser indicativo de falta de dedicación al curso o de mala comprensión del mismo. La gráfica de la Figura 25 muestra la función de distribución de probabilidad de las calificaciones obtenidas por alumnos de este perfil. Capítulo 4. Resultados experimentales 114 Los alumnos del perfil Medium obtienen el 95% de sus calificaciones entre un 5 y un 7 (en una escala de 0 a 10). Los alumnos de este perfil superan el mínimo exigido (un 5) pero no adquieren un dominio notable de las capacidades y conocimientos para los que fueron formados. Es el perfil medio y su gráfica de distribución de probabilidad para sus calificaciones es la mostrada en la Figura 26. Por último, los alumnos etiquetados como perfil High son los alumnos que obtienen el 95% de sus resultados de evaluaciones en una calificación comprendida entre el 7 y el 9 en una escala de 0 a 10. Los alumnos de este perfil evidencian un dominio excelente de las capacidades para las que han sido formados. Es el perfil más deseado y en entornos de formación online suele ser el más habitual. La función de distribución de probabilidad usada para la generación de las calificaciones pseudoaleatorias para este perfil es la indicada en la Figura 27. Figura 25 : Función de densidad de probabilidad de un modelo normal N(4,0.5) Figura 26 : Función de densidad de probabilidad de un modelo normal N (6,0.5) Capítulo 4. Resultados experimentales 115 El programa nos permitirá simular la realización del curso por un conjunto de alumnos, determinando a priori la proporción de cada nivel de alumnos que se desea para el estudio de la variación del itinerario (a través de los controles de selección del panel de configuración), en función de las características del alumnado. Para los alumnos que no pertenezcan a ningún perfil, se utilizará una función que genera las calificaciones correspondientes a las evaluaciones de cada curso de forma aleatoria y con una probabilidad uniforme. Esta última opción se habilita activando la casilla Random Scores del panel de configuración. Además de considerar diferentes perfiles para las hormigas del algoritmo, que simularán el comportamiento de los alumnos reales, es necesario considerar la estrategia de ponderación del grafo así como la calibración del mismo, estudiando el comportamiento del algoritmo con la variación de los parámetros del algoritmo: α, β, ω 1 , ω 2 , ω 3 y ρ. El objetivo final del algoritmo es maximizar el resultado de la función beneficio B k que nos devuelve la calificación media ponderada con el peso total del recorrido realizado por la hormiga k. El beneficio obtenido por la hormiga k en su recorrido es: Ô 7   ∑ µ   "  ∑ ·  "  (48) Figura 27: Función de densidad de probabilidad de un modelo normal N (8,05) Capítulo 4. Resultados experimentales 116 donde @∈A 7 y su grado de entrada, g in (i), es mayor que cero. Se obtiene mediante la división de la suma de las calificaciones medias de cada nodo perteneciente al recorrido (excepto el nodo inicial) entre la suma de los pesos de los nodos de este recorrido (a excepción del peso del primer nodo). Puesto que el denominador de la ecuación (48) permanece constante para cada itinerario, el beneficio será mayor en un itinerario cuanto mayor sea la suma de las notas medias de ese itinerario, o lo que es lo mismo, cuando aumente la nota media del itinerario. Los pesos asignados a cada nodo pueden influir en la probabilidad de selección de un arco, y en consecuencia en el beneficio obtenido, puesto que al actuar como factor multiplicador en el primer sumando de la función de ajuste (39), podrían influir en la construcción del camino, por ejemplo, seleccionando los nodos cuyos cursos sean de menor dificultad. A continuación estudiamos las estrategias de ponderación del grafo. Estrategias de Ponderación del Grafo de Itinerarios de Aprendizaje Equiponderar Si asignamos el mismo peso a todos los cursos, entonces el beneficio será mayor cuanto mayor sea la calificación media del itinerario. Así si un recorrido k está formado por m cursos, si todos tienen el mismo peso, la función beneficio del recorrido k viene dada por la ecuación: Ô 7 ∑µÖ @  @1 ∑· @  @1 µÖ @ µÖ @1 ...µÖ D J· & µÖ A  · & A priori, esta medida puede potenciar en exceso los caminos más fáciles. El razonamiento es sencillo: al tener los caminos posibles una función de ajuste similar en un primer momento, todos los caminos tendrán unas probabilidades similares de ser elegidos. Aquellos caminos que tengan un menor nivel de dificultad, obtendrían un mayor depósito de feromonas que llevaría rápidamente al algoritmo al bloqueo en un mínimo local, encaminando al resto de hormigas (alumnos en nuestro caso) por el itinerario de menor dificultad. En cambio, si el nivel de dificultad de los cursos es homogéneo, el resultado será impredecible, dependiendo la elección de los nodos de las calificaciones obtenidas en cada curso. Capítulo 4. Res ultados experimentales Para comprobar el comportamiento del algoritmo, utilizare Figura 28, en el que todos sus nodos tienen mismo peso, Figura 28: Grafo utilizado para probar la estrategia de asignación de pesos iguales a todos los nodos. Los valores para cada nodo - Peso Pedagógico ( - Mínima calificación deseada ( - Máxima calificación posible (M): 10.0 - Calif icación media ( Todos los arcos del grafo tienen también los mismos atributos inicialmente: - Peso: 192.0 (el valor no importa, siempre que todos los nodos tengan el mismo peso) - Feromonas (τ): 0.0 Se realizan una serie de ejecuciones del algoritmo promoción de alumnos en los siguientes casos: Población de alumnos homogénea obtiene todos el mismo rango de los alumnos de perfil Medium ultados experimentales Para comprobar el comportamiento del algoritmo, utilizare mos el grafo en el que todos sus nodos tienen mismo peso, mínimos deseados y máximos para probar la estrategia de asignación de pesos iguales a todos los Los valores para cada nodo i del grafo son los indicados a continuación: Peso Pedagógico ( W i ): 1.0 Mínima calificación deseada ( m): 5.0 Máxima calificación posible (M): 10.0 icación media ( : 0.0 Todos los arcos del grafo tienen también los mismos atributos inicialmente: Peso: 192.0 (el valor no importa, siempre que todos los nodos tengan el Feromonas (τ): 0.0 Se realizan una serie de ejecuciones del algoritmo ASALI para simular en los siguientes casos: Población de alumnos homogénea : se cuenta con un grupo de alumnos obtiene todos el mismo rango de calificaciones (todos los alumnos de perfil Medium o todos los alumnos de perfil Low 117 mos el grafo de la mínimos deseados y máximos . para probar la estrategia de asignación de pesos iguales a todos los del grafo son los indicados a continuación: Todos los arcos del grafo tienen también los mismos atributos inicialmente: Peso: 192.0 (el valor no importa, siempre que todos los nodos tengan el ASALI para simular : se cuenta con un grupo de alumnos que perfil High, todos Low ). Se ejecuta el Capítulo 4. Resultados experimentales 124 Tras la experimentación se observa que el bloqueo en una solución aparece, con respecto al número de hormigas que terminan de construir su solución, ligeramente antes al observado en la estrategia anterior (equiponderación) con hormigas de perfil Medium. Para perfiles High y Low el comportamiento es similar, bloqueándose al completar su solución aproximadamente el mismo número de hormigas. A diferencia de lo observado con la estrategia basada en la asignar los mismos pesos a todos los nodos, con esta estrategia basada en el nivel de dificultad si se observa una característica interesante en los experimentos realizados: el camino que pasa por el nodo de peso 1 (aquel con un nivel de dificultad adecuado) acaba siendo el que causa el bloqueo en el 90% de las veces, mientras que asignando el mismo peso a todos los nodos, los cuatro caminos tendían a ser los bloqueantes en el mismo número de veces. Por tanto esta estrategia, con los valores asignados a las variables de calibración y que posteriormente estudiaremos, cuando el número de alumnos es suficientemente alto, favorecerá el bloqueo de la solución en alguno de los caminos diseñado como base del itinerario por el equipo pedagógico (el camino con nivel de dificultad adecuada). La Figura 34 compara las desviaciones típicas para una colonia de hormigas con diferente perfil, en proporciones de 30%, 60% y 10% de perfiles High, Medium y Low respectivamente. Mientras que a partir de una colonia de 200 hormigas, apenas hay diferencia en la desviación típica, entre 20 y 200 sí se observan diferencias sensibles, mostrando una desviación típica menor en la segunda estrategia de ponderación, lo que significan una menor diferencia entre el número de elecciones de cada camino con respecto a la media (calculada de forma equitativa) y por tanto, se traduce en un bloqueo más tardío, puesto que las elecciones del siguiente nodo se reparten entre los posibles, evitando que exista un excesivo depósito de feromonas en alguno de ellos. En la mayoría de los casos, el bloqueo se produjo en el camino Node0Node1Node5, que es aquél que elige como primer arco a aquél que tiene como nodo destino el de mayor peso (peso 1). Por tanto como primera conclusión podemos deducir que el algoritmo en las primeras iteraciones (a las primeras hormigas de cada colonia) puede asignar cualquier camino de entre los posibles y gracias al depósito de feromonas (que no logran evaporarse totalmente) acaba bloqueándose una vez han finalizado su itinerario un número de hormigas. Este número de hormigas, que oscila entre 20 y 100 para los parámetros del algoritmo utilizados, dependerá de las calificaciones obtenidas por éstas y no puede determinarse a priori. Capítulo 4. Resultados experimentales 125 La muestra la evolución de las selecciones de camino en el nodo 0 para la estrategia de ponderación en función del nivel de dificultad. Para el grafo de la Figura 28, la estrategia consistente en la ponderación según el nivel de dificultad, se ajusta bien con los parámetros utilizados para el algoritmo, mostrándose cambiante para una colonia inferior a las 100 hormigas. Esto es, podría utilizarse en promociones con un número inferior a 100 alumnos, puesto que para grupos más numerosos, el efecto bloqueante de las feromonas aumentaría proporcionalmente el número de malos resultados necesarios para cambiar el itinerario de los alumnos. Figura 34: Comparativa entre desviaciones típicas para las dos estrategias de po nderación en colonias con perfiles heterogéneos. Capítulo 4. Resultados experimentales 126 Para investigar cómo afecta el número de opciones en un nodo a la rapidez con que se llega a una situación de bloqueo, modificamos el grafo de la Figura 28, aumentando el número de nodos intermedios posibles entre el Nodo0 y el Nodo5, tal y como muestra la Figura 36. La ponderación del grafo se realiza de forma simétrica, de forma que tanto peso como calificación mínima de los nodos añadidos se corresponda con las de los nodos previamente existentes de la siguiente forma: Tabla 12: Ponderación para los nodos añadidos al grafo de la Figura 28 Nodo W i m M × Ø Grado Salida Arcos de Salida N9 1 5.0 10.0 - 1 Link15 N8 0.85 6.0 10.0 - 1 Link13 N7 0.70 7.0 10.0 - 1 Link11 N6 0.55 8.0 10.0 - 1 Link9 Figura 36: Grafo ponderado con 8 posibles itinerarios Figura 35: Evolución de una de las ejecuciones de la experimentación para la estrategia de ponderación en función del nivel de dificultad en una colonia con hormigas de diferentes perfiles Capítulo 4. Resultados experimentales 127 El comportamiento del algoritmo no varía en exceso con respecto a un menor número de opciones, tal y como puede apreciarse en algunas de las evoluciones de las elecciones de itinerarios de la Figura 37. En esta figura, lo relevante no es identificar cada itinerario en cada gráfica, sino como en todas ellas existe un itinerario que acaba siendo el predominante. En algunas de ellas, se observa como el bloqueo aparece más tarde, respecto al grafo de la Figura 28. En cambio, en otras pruebas el número de hormigas que terminan sus recorridos antes de que se produzca el bloqueo es prácticamente el mismo, por lo que no parece existir una dependencia única entre el número de opciones o itinerarios alternativos y el número de hormigas que necesitan terminar su recorrido para favorecer la aparición de un bloqueo. Es lógico que un mayor número de opciones pueda retrasar la aparición de un bloqueo, al contar la tabla de decisión con más entradas y minimizar la probabilidad de repetición de una misma opción en un corto intervalo de tiempo. No obstante, no existe una implicación directa, pues al depender la cantidad de feromonas a depositar de la calificación obtenida, valor éste último que es impredecible, no se puede asegurar. Tras este primer estudio podemos concluir que el algoritmo ASALI, al igual que en la vida real sucede con las hormigas, tiende a encontrar una solución que hace que el resto de hormigas virtuales se decanten por ella. El Itinerario es elegido aleatoriamente teniendo en cuenta el éxito obtenido (medido en feromonas) en cada una de las opciones posibles, por lo que los itinerarios de mayor éxito, tendrán más probabilidades de ser elegidos. Para no favorecer que el itinerario elegido coincida con el más fácil, esta función de ajuste tiene en cuenta el peso asignado por el equipo pedagógico que, según resultados experimentales favorece la elección de los cursos de mayor peso. Para estudiar las propiedades del algoritmo ASALI y como poder ajustar su comportamiento es necesario estudiar la calibración del mismo. 4.2.2 Calibración del Sistema El comportamiento del algoritmo puede ser modificado mediante las variables α y β que controlan la tendencia del algoritmo a tener un comportamiento más explorador de nuevos caminos o explotador de los ya encontrados. Durante la experimentación, hemos encontrado que esta variación de comportamiento también influye en la proporción de hormigas que sigue los caminos de más éxito. Para calibrar el sistema estudiaremos la variación de la selección de itinerarios para un caso concreto de perfiles de alumnos. En nuestro caso 30% perfil High, 60% perfil Medium y 10% perfil Low. Capítulo 4. Resultados experimentales 128 Figura 37: Evolución de las elecciones de cada itinerario en algunas pruebas realizadas con el algoritmo para el grafo de la Figura 36. En el eje de ordenadas se muestra el número de veces que cada itinerario ha sido elegido, y en el de abscisas el número de hormigas ACO que han terminado su itinerario. Capítulo 4. Resultados experimentales 129 Para el estudio de calibración se utilizará el grafo resultante de procesar el Grafo de Itinerarios de Aprendizaje propuesto como escenario de este trabajo (Figura 13) resultando el grafo de la Figura 38: Figura 38: Grafo de itinerarios de aprendizaje una vez eliminadas las restricciones de navegación La colonia de hormigas estará compuesta por cien hormigas, que simularán el comportamiento de 100 alumnos, que realizarán un recorrido cada una. Tras la ejecución, los pesos de los arcos del grafo quedarán modificados con la función de ajuste calculada para cada uno de ellos. Para una siguiente iteración, se volverá a utilizar el grafo en las condiciones iniciales y no en el estado (funciones de ajuste y feromonas en cada arco) que hubiera quedado tras la iteración anterior. La Tabla 13 muestra los valores iniciales para cada nodo del grafo, siendo los principales puntos de interés en el grafo los llamados Nodos de Decisión: aquellos nodos con grado de salida mayor que uno (N3, N6 y N11). Capítulo 4. Resultados experimentales 130 Tabla 13: Estado inicial de los nodos del grafo Nodo W i m M × Ø Grado Salida Arcos N1 1 5 10 0 1 Link0 N2 1 5 10 0 1 Link1 N3 1 5 10 0 3 Link2, Link3, Link4 N4 1 5 10 0 1 Link11 N5 1 5 10 0 1 Link5 N6 0,5 8 10 0 2 Link7, Link9 N7 0,25 8 10 0 1 Link6 N8 0,75 6 10 0 1 Link10 N9 0,6 7 10 0 1 Link8 N10 1 5 10 0 1 Link12 N11 1 5 10 0 2 Link13, Link14 N12 1 5 10 0 1 Link16 N13 0,7 5 10 0 1 Link15 Fin - - - - - - Los itinerarios posibles se identifican en la Tabla 14 indicando para cada itinerario la suma de los pesos pedagógicos de los nodos que lo componen. Tabla 14: Itinerarios posibles ID Itinerario Peso A N1 N2N3N6N9N8N4N10N11N12Fin 9.85 B N1N2N3N6N9N8N4N10N11N13N12Fin 10.55 C N1N2N3N6N8N4N10N11N12Fin 9.25 D N1N2N3N6N8N4N10N11N13N12Fin 9.95 E N1N2N3N7N6N9N8N4N10N11N12Fin 10.10 F N1N2N3N7N6N9N8N4N10N11N13N12Fin 10.80 G N1N2N3N7N6N8N4N10N11N12Fin 9.50 H N1N2N3N7N6N8N4N10N11N13N12Fin 10.20 I N1N2N3N5N4N10N11N12Fin 9.00 J N1N2N3N5N4N10N11N13N12Fin 9.70 El equipo pedagógico ha diseñado un itinerario base que se corresponde con el itinerario I. Es el itinerario más corto y en el que todos sus nodos tienen peso 1. El resto de itinerarios alternativos son itinerarios de repaso de contenido. Por ejemplo el itinerario C, sustituye el curso del nodo 5 por dos cursos, situados en los nodos N6 y N8. El N6 está enfocado a reforzar el andamiaje de conocimiento necesario e introducir los conocimientos que se presentan en el N5 y el N8 sería una continuación, repitiendo y ampliando los conceptos del N5. Es decir, los nodos N6 y N8 representan la misma carga didáctica que el N5 pero ralentizando el aprendizaje (con más ejemplos, más Capítulo 4. Resultados experimentales 131 ejercicios, más tests, etc). Por tanto el itinerario C es un itinerario más lento que el itinerario I. Lo normal es que las calificaciones en el itinerario C sean ligeramente más alta, lo que se contrarresta con los pesos que el equipo asigna a estos nodos, más bajos. De la misma forma, otros itinerarios posibles plantean más cursos de repaso para contenidos anteriores o de introducción a los siguientes. Por ejemplo el nodo N7 podría ser un repaso de los contenidos del N3, el nodo N9 podría ser una introducción a los contenidos del N8 y el N13 repaso del N11 e introducción a los del N12. Estudio marginal del parámetro β Para estudiar el comportamiento del algoritmo según la variación de β, se ejecutará el algoritmo ASALI en el grafo de la Figura 38 con varios valores para el parámetro β (0.5, 1, 2, 5, 10 y 25), realizando además varias ejecuciones con diferentes valores de α: 0, 1, 2, 5, 10, 25 y 50 para comprobar igualmente su influencia. Recordemos la interpretación de los parámetros α y β: • El parámetro α es un intensificador de la influencia de las feromonas. Cuando α = 0 éstas no influyen y el algoritmo se convierte en el clásico algoritmo voraz que seleccionará como siguiente nodo al más cercano según la función de distancia definida para el problema, en nuestro caso, según la función de ajuste. En este caso sólo el valor heurístico tiene influencia sobre la probabilidad de selección de cada nodo. Cuando α > 0, las feromonas comienzan a tener efecto en la decisión de los nodos, siendo más determinantes cuanto mayor sea el parámetro α. • El parámetro β controla la influencia del valor heurístico, que deja de tener influencia cuando β = 0, influyendo en este caso únicamente en la decisión del siguiente nodo las feromonas depositadas previamente en cada arco, lo que conduciría rápidamente a una situación de bloqueo en el camino que aleatoriamente se hubiera seleccionado primero, lo que generalmente lleva a soluciones no óptimas. En nuestro algoritmo, los elementos de la tabla de decisión se calculan según la expresión (3) y con η ij = f ij , dónde f ij es la función de ajuste para el arco l ij y se calcula según la ecuación (39). Aunque las feromonas Φ se evaporan al finalizar la iteración (cuando toda la colonia ha construido una solución) en cambio son depositadas al vuelo, por lo que la Capítulo 4. Resultados experimentales 132 acción de una hormiga puede tener un efecto inmediato sobre las siguientes en la misma iteración. Por tanto el valor de β puede aumentar el impacto de la actuación de la hormiga anterior si β > 1 o minimizarlo β < 1. En cuanto al parámetro α, no debe tener influencia alguna, puesto que no se realizará más de una iteración por cada prueba y se partirá de un grafo en cuyo estado inicial las feromonas τ son las mismas en todos los arcos y positivas (τ 0 = 15  Ñ). En este caso: *   '    +    '  , - + e  , . ∑   0  '  # -  e 0 # . 0 ∈ 1 2     & # - + e  , .   & # - ∑  e 0 # . 0 ∈ 1 2  + e  , . ∑  e 0 # . 0 ∈ 1 2 (49) El parámetro β actuará modificando los valores de la tabla de decisión, aumentando las diferencias de probabilidad de selección entre los arcos vecinos, otorgando mayor probabilidad de ser seleccionado a aquel arco cuya función de ajuste sea mayor y disminuyéndola a aquellos cuya función de ajuste sea menor, con respecto a un valor de β menor. Por ejemplo, sean los arcos de la Figura 39: Figura 39: Nodo de decisión para el cálculo de la influencia del parámetro β En la primera ejecución del algoritmo ASALI sobre un grafo de itinerarios de aprendizaje, el factor de idoneidad de cada arco, al no haber calificaciones disponibles se incializa a 1. Inicialmente las feromonas Φ se inicializan a cero, aunque durante la iteración se irán depositando feromonas. Por tanto la función de ajuste, inicialmente depende en gran medida del peso pedagógico del nodo destino. Aplicando la ecuación (49) la variación inicial de los elementos de la tabla de decisión para los arcos que van del nodo N3 a los nodos N5, N6 y N7 es la que se muestra en la Tabla 15. Esas probabilidades se verían modificadas cada vez que se recalcule la tabla de decisión, es Capítulo 4. Resultados experimentales 133 decir, cada vez que una hormiga se disponga a seleccionar el siguiente nodo, por lo que las acciones de una hormiga influirán en la siguiente. Tabla 15: Influencia del parámetro β en la probabilidad de decisión de los nodos β = 0.5 β = 1 β = 2 β = 5 β = 10 β = 25 N3N5 42% 50% 61% 81% 95% 100% N3N6 37% 38% 35% 19% 5% 0% N3N7 21% 12% 4% 0% 0% 0% Total 1 1 1 1 1 1 En el grafo utilizado, los arcos que deberían verse beneficiados por el aumento de β son los itinerarios I y J, puesto que son los que cuentan con un nodo destino de peso 1, por lo que al aumentar el valor de β la mayor parte de las hormigas seleccionaría los arcos que van del nodo N3 al nodo N5 y del nodo N11 al N12 en perjuicio de sus respectivos nodos vecinos. De los resultados obtenidos (Figura 41) no se deduce que la variación de α afecte de alguna manera a la probabilidad de selección de los itinerarios posibles, pues no existe una relación causa-efecto entre el aumento o disminución de α sobre un mismo valor de β en los resultados obtenidos. Para β = 0.5, los itinerarios “recomendados” (aquellos en los que el nodo de destino del arco tiene mayor peso), I y J, son los elegidos entre el 30% y el 69% de las veces. Todos los itinerarios son recorridos por al menos una hormiga. En la mayoría de las ocasiones (salvo en una) el reparto de las hormigas por los distintos itinerarios es relativamente homogéneo, no existiendo un único camino que atraiga a la mayoría absoluta (más del 50%) de las hormigas. Tampoco se observa influencia alguna de la variable α cuando β = 1 (Figura 40). En cambio si se observa en este caso que los itinerarios I y J aglutinan una mayor proporción de hormigas que los recorren, concretamente entre un 57% y el 92%. Como consecuencia, comienzan a aparecer varios itinerarios que no son visitados por ninguna de las 100 hormigas de la colonia, siendo los primeros itinerarios perjudicados aquellos que en los nodos de decisión no incluyen al arco cuyo nodo destino tiene mayor peso. En todas las ejecuciones de esta prueba, independientemente del valor de α, hay al menos un itinerario que no ha sido elegido por ni una sola hormiga. Esta tesis se acabó de imprimir en Triana el 19 de marzo de 2012, Bicentenario de la primera Constitución española.