Optimización Basada en Colonias de Hormigas en Dos Etapas

Universidad Central “Marta Abreu” de Las Villas

Facultad de Matemática, Física y Computación

Trabajo para optar por el título de Máster en Ciencia de la Computación

Optimización Basada en Colonias de Hormigas en Dos Etapas

Autor

Lic. Amilkar Yudier Puris Cáceres

Tutor

Dr. Rafael Esteban Bello Pérez

Consultante

Ricardo Grau Avalos

2007

Agradecimiento

A mi madre que es lo más lindo que hay en la vida, a mi padre que me ha servido de guia. A mis abuelos, mis hermanos, mis padres de crianza, mi tutor Bello que siempre lo estuve y lo estaré molestando,a mi novia y sus padres,a mis compañeros de trabajo Lety, Yailen, Yanet, Marilyn, Falcon, Yudel, Donis y Morell por todo el trabajo que les hice pasar, y no por estar de último les agradezco menos, a mis hermanos de la calle, Raydel, Karel, Lucho y Gabriel.

Agradecimiento

Resumen

Resumen La metaheurística “Optimización basada en colonias de hormigas” (Ant Colony Optimization, ACO) es uno de los nuevos paradigmas que permite la solución de problemas combinatorios del tipo NP-Hard. En este trabajo se presenta un nuevo modelo basado en el comportamiento de las hormigas nombrado “Optimización basada en colonias de hormigas en dos Etapas”( Two Steage Ant Colony Optimization, TS-ACO). La nueva estrategia de exploración que presenta este modelo propone hacer una división en dos del espacio de búsqueda, donde en la primera etapa solo una parte de las hormigas van a solucionar un subproblema de tamaño inferior al problema original, estas subsoluciones encontradas servirán de punto de partida para que en la segunda etapa las hormigas restantes de la colonia busquen soluciones al problema en general, haciéndose de esta forma más cooperativo el trabajo de estos agentes. El nuevo modelo muestra un mayor rendimiento en cuanto al tiempo de ejecución y la calidad de las soluciones encontradas. Para probar la nueva estrategia se escogieron los algoritmos Ant Colony System (ACS) y Ant System (AS) para darle solución a tres problemas de optimización combinatoria, el Viajante de Comercio (TSP), el problema de Secuenciación de Tareas (JSSP) y el problema de Cubrimiento de Conjuntos (SCP).

Resumen

Abstract

6

Abstract

The Ant Colony Optimization (ACO) meta-heuristic is one of the new paradigms that allow solving NP-Hard combinatorial problems. In this study, a new ant-behavior-based model named “Two Stage Ant Colony Optimization” (TS-ACO) is formally introduced. The fresh exploration strategy splits the search space into two parts. During the first stage, only a subset of the available ants is intended to solve a sub-problem of the original problem. The solutions found herein will serve as the starting point for the remaining ants of the colony to perform at the second stage, leading to a tighter cooperation between those agents. The proposed model exhibits a higher performance in terms of the execution time and the quality of the solutions yielded. In order to test our approach, the Ant Colony System (ACS) and Ant System (AS) algorithms were chosen as benchmarks for being applied to three well-known combinatorial optimization problems, namely the Traveling Salesman Problem (TSP), the Job Shop Scheduling Problem (JSSP) and the Set Covering Problem (SCP).

Introducción

7

Introducción En el lenguaje coloquial, optimizar significa poco más que mejorar; sin embargo, en el contexto científico la optimización es el proceso de tratar de encontrar la mejor solución posible para un determinado problema. En un problema de optimización existen diferentes soluciones y un criterio para discriminar entre ellas. De forma más precisa, estos problemas se pueden expresar como encontrar el valor de unas variables de decisión para los que una determinada función objetivo alcanza su valor máximo o mínimo. El valor de las variables en ocasiones está sujeto a unas restricciones. Podemos encontrar una gran cantidad de problemas de optimización, tanto en la industria como en la ciencia. Desde los clásicos problemas de diseño de redes de telecomunicación u organización de la producción hasta los más actuales en ingeniería y re-ingeniería de software, existe una infinidad de problemas teóricos y prácticos que involucran a la optimización. Algunas clases de problemas de optimización son relativamente fáciles de resolver. Este es el caso, por ejemplo, de los problemas lineales, en los que tanto la función objetivo como las restricciones son expresiones lineales. Estos problemas pueden ser resueltos con el conocido método Simplex

introducido en su forma original por Spendley; Hext y Himsworth en 1962; sin embargo, muchos tipos de problemas de optimización son muy difíciles de resolver. De hecho, la mayor parte de los que podemos encontrar en la práctica entran dentro de esta categoría. La idea intuitiva de problema ”difícil de resolver” queda reflejada en el término científico NP-hard [1] utilizado en el contexto de la complejidad algorítmica. Podemos decir que un problema de optimización difícil es aquel para el que no podemos garantizar el encontrar la mejor solución posible en un tiempo razonable. La existencia de una gran cantidad y variedad de problemas difíciles, que aparecen en la práctica y que necesitan ser resueltos de forma eficiente, impulsó el desarrollo de procedimientos eficientes para encontrar buenas soluciones aunque no fueran óptimas. Estos métodos, en los que la rapidez del proceso es tan importante como la calidad de la solución obtenida, se denominan heurísticos o aproximados. En [2] se recogen hasta 3 definiciones diferentes de algoritmo heurístico, entre las que destacamos la siguiente: Un método heurístico es un procedimiento para resolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución. En contraposición a los métodos exactos que proporcionan una solución óptima del problema, los métodos heurísticos se limitan a proporcionar una buena solución no necesariamente óptima. Lógicamente, el tiempo invertido por un método exacto para encontrar la solución óptima de un problema difícil, si es que existe tal método, es de un orden de magnitud muy superior al del

Introducción

8

heurístico (pudiendo llegar a ser tan grande en muchos casos, que sea inaplicable). Una clasificación usual de los problemas de optimización es en: Estocástica y Determinista. La diferencia radica en los valores que toman las variables en el proceso de optimización, en la estocástica son valores probabilísticos y en la determinista los valores pueden ser discretos o continuos, de ahí que la optimización determinista se clasifique en dos, Optimización Combinatoria o Discreta y Optimización Continua. En este trabajo consideraremos los llamados problemas de Optimización Combinatoria. En estos problemas el objetivo es encontrar el máximo (o el mínimo) de una determinada función sobre un conjunto finito de soluciones que denotaremos por S. No se exige ninguna condición o propiedad sobre la función objetivo o la definición del conjunto S. Es importante notar que dada la finitud de S, las variables han de ser discretas, restringiendo su dominio a una serie finita de valores. Habitualmente, el número de elementos de S es muy elevado, haciendo impracticable la evaluación de todas sus soluciones para determinar el óptimo. En los últimos años ha habido un crecimiento espectacular en el desarrollo de procedimientos heurísticos para resolver problemas de optimización. Este hecho queda claramente reflejado en el gran número de artículos publicados en revistas especializadas. En 1995 se edita el primer número de la revista Journal of Heuristics dedicada íntegramente a la difusión de los procedimientos heurísticos. Aunque hemos mencionado el caso de la resolución de un problema difícil, existen otras razones para utilizar métodos heurísticos, entre las que podemos destacar:

El problema es de una naturaleza tal que no se conoce ningún método exacto para su resolución.

Aunque existe un método exacto para resolver el problema, su uso es computacionalmente muy costoso.

El método heurístico es más flexible que un método exacto, permitiendo, por ejemplo, la incorporación de condiciones de difícil modelación.

El método heurístico se utiliza como parte de un procedimiento global que garantiza el óptimo de un problema. Existen dos posibilidades: - El método heurístico proporciona una buena solución inicial de partida. - El método heurístico participa en un paso intermedio del procedimiento, como por

ejemplo las reglas de selección de la variable a entrar en la base en el método Simplex. Al abordar el estudio de los algoritmos heurísticos podemos comprobar que dependen en gran medida del problema concreto para el que se han diseñado. En otros métodos de resolución de propósito general, como pueden ser los algoritmos exactos de Ramificación y Acotación, existe un procedimiento conciso y preestablecido, independiente en gran medida del problema abordado. En los métodos heurísticos esto no es así. Las técnicas e ideas aplicadas a la resolución de un problema son específicas de éste y aunque, en general, pueden ser trasladadas a otros problemas, han de

Introducción

9

particularizarse en cada caso. Así pues, es necesario referirse a un problema concreto para estudiar con detalle los procedimientos heurísticos. En los últimos años han aparecido una serie de métodos bajo el nombre de meta-heurísticos con el propósito de obtener mejores resultados que los alcanzados por los heurísticos tradicionales. El término meta-heurístico fue introducido en [3] por Fred Glover. En este trabajo utilizaremos la acepción de heurísticos para referirnos a los métodos clásicos en contraposición a la de meta-heurísticos que reservamos para los más recientes y complejos. En algunos textos podemos encontrar la expresión “heurísticos modernos” refiriéndose a los meta-heurísticos [4]. Los profesores Osman y Kelly en [5] introducen la siguiente definición: Los procedimientos meta-heurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son efectivos. Los meta-heurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los mecanismos estadísticos. Los procedimientos meta-heurísticos se sitúan conceptualmente “por encima” de los heurísticos en el sentido que guían el diseño de éstos. Así, al enfrentarnos a un problema de optimización, podemos escoger cualquiera de estos métodos para diseñar un algoritmo específico que lo resuelva aproximadamente. En estos momentos existe un gran desarrollo y crecimiento de estos métodos los cuales han probado su eficiencia sobre una colección significativa de problemas; entre los que podemos destacar, la Búsqueda Tabú [6], el Recocido Simulado [7], GRASP [8], los Algoritmos Genéticos [9], Optimización Basada en Enjambre de Partículas [10] (Particle Swarm Optimization, PSO) y Optimización Basada en Colonias de Hormigas (Ant Colony Optimization, ACO) [11, 12], entre otros. Estas últimas dos meta-heurísticas caen en la categoría de algoritmos bioinspirados o de vida artificial y de inteligencia colectiva, ya que la potencialidad de estos modelos para resolver problemas está dada por la cooperación entre individuos de una forma directa o indirecta. Específicamente en la meta-heurística ACO, la cooperación se realiza entre hormigas de una forma indirecta.

Es creciente el interés científico en este nuevo modelo computacional ACO por su alta aplicabilidad para resolver diferentes problemas de optimización discreta. Este modelo se basa en usar el comportamiento de las colonias de hormigas naturales, las cuales minimizan el recorrido entre su nido y cualquier fuente de alimento. Esta meta-heurística desde su surgimiento ha representado una muy buena herramienta para solucionar problemas de optimización combinatoria, pero la

Introducción

10

inteligencia colectiva que es el arma principal de estos algoritmos hace que la calidad de las soluciones encontradas tenga una muy estrecha relación con la cantidad de agentes que estén interactuando en la colonia, esto a su vez trae grandes consecuencias para el tiempo que se emplea para alcanzar dichas soluciones. En otras palabras, la cantidad de hormigas que conforman la colonia y la cantidad de veces que estarán interactuando para solucionar un problema trae consigo que se encuentren buenas soluciones, pero su costo computacional en cuanto a tiempo de ejecución aumenta en gran medida.

Por lo anteriormente expuesto, se deriva el problema científico a resolver que se manifiesta en que la meta-heurística ACO presenta deficiencias en cuanto al tiempo que emplea en converger a buenas soluciones de problemas combinatorios, ya que la calidad de las soluciones es directamente proporcional a la cantidad de agentes que interactúan en el modelo.

Para contribuir a la solución del problema científico antes plateado, se formuló la hipótesis general de investigación siguiente:

Con la modificación de la estrategia de exploración del espacio de búsqueda de la meta-heurística ACO es posible conseguir que los algoritmos converjan a buenas soluciones en un tiempo mucho menor que el empleado por el modelo original.

Esta hipótesis quedará validada si se comprueba que:

1. La nueva estrategia de exploración del espacio de búsqueda es capaz de disminuir el costo computacional en cuanto a tiempo de encontrar buenas soluciones con respecto al modelo original.

2. Los cambios introducidos no hagan muy compleja la etapa de aplicabilidad del nuevo modelo.

En conformidad con la hipótesis de investigación identificada, el objetivo general de la investigación consiste en desarrollar una nueva metodología de trabajo con la meta-heurística ACO, que ofrezca a los investigadores y desarrolladores en el campo de la optimización combinatoria una herramienta que posibilite un mejor rendimiento de los algoritmos basados en colonias de hormigas.

Este objetivo general fue desglosado en los objetivos específicos siguientes:

1. Construir el marco teórico-referencial de la investigación derivado de la consulta de la literatura nacional e internacional actualizada, y otras fuentes de referencia sobre el temático objeto de estudio.

2. Realizar un análisis crítico sobre el estado actual del desarrollo de la meta-heurística ACO para solucionar problemas de optimización combinatoria.

Introducción

11

3. Diseñar y proponer sobre bases científicas, una nueva metodología de trabajo con la meta-heurística ACO que mejore la estrategia de exploración del espacio de búsqueda y garantice una mejor eficiencia en la solución de problemas de optimización.

4. Validar la nueva metodología a partir de comparaciones experimentales y estadísticas con el modelo original en la solución de problemas de prueba.

La novedad científica principal que aporta esta investigación, radica en la concepción y definición de un nuevo modelo de trabajo con la meta-heurística ACO que sea capaz de garantizar una convergencia más temprana a buenas soluciones que el modelo original.

El valor teórico de la investigación está directamente vinculado con su novedad científica.

El valor metodológico se manifiesta a través del desarrollo del modelo y que es aplicable a cualquier algoritmo de la meta-heurística ACO.

El valor práctico se relaciona con la introducción de un modelo que brinda la posibilidad de ser aplicado para la solución de problemas reales por el grupo de Inteligencia Artificial del Centro de Estudios de Informática.

El valor social de la investigación radica en su dimensión interna, en la contribución al desarrollo de investigaciones en el área de la optimización, y en su dimensión externa, en dar a conocer un nuevo modelo que permita resolver problemas reales en distintas áreas de la vida.

Para la presentación de esta investigación, esta Tesis de Maestría se estructuró de la forma siguiente. En la Introducción, se caracteriza la situación problémica y se fundamenta el problema científico a resolver, así como la estrategia general seguida para su solución como problema científico. El Capítulo 1, contiene el marco teórico-referencial que sustentó la investigación originaria. En el Capítulo 2, se resume y explica todo el nuevo modelo desarrollado. En el Capítulo 3, se pone a prueba el desempeño del nuevo modelo en la solución de problemas de experimentación, además de un análisis estadístico de los resultados, donde se muestran los casos de aplicación que evidencian la factibilidad y utilidad del empleo del modelo y el procedimiento desarrollado como vía para demostrar la hipótesis de investigación planteada. Un cuerpo de Conclusiones y Recomendaciones derivadas de la investigación realizada, la Bibliografía consultada y un grupo de Anexos como complemento de los resultados expuestos.

Capítulo1

12

Capítulo 1 Problemas de Optimización Combinatoria, meta-heurística ACO y algoritmos de Búsqueda Local La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software.

Existen muchos métodos heurísticos de naturaleza muy diferente, por lo que es complicado dar una clasificación completa. Además, muchos de ellos han sido diseñados para un problema específico sin posibilidad de generalización o aplicación a otros problemas similares. El siguiente esquema trata de dar una categoría amplia, no excluyentes, en donde ubicar a los heurísticos más conocidos: Métodos de Descomposición: El problema original se descompone en subproblemas más sencillos de resolver, teniendo en cuenta, aunque sea de manera general, que todos pertenecen al mismo problema. Métodos Inductivos: La idea de estos métodos es generalizar de versiones pequeñas o más sencillas al caso completo. Propiedades o técnicas identificadas en estos casos más fáciles de analizar pueden ser aplicadas al problema completo. Métodos de Reducción: Consiste en identificar propiedades que se cumplen mayoritariamente por las buenas soluciones e introducirlas como restricciones del problema. El objeto es restringir el espacio de soluciones simplificando el problema. El riesgo obvio es dejar fuera las soluciones óptimas del problema original. Métodos Constructivos: Consisten en construir literalmente paso a paso una solución del problema. Usualmente son métodos deterministas y suelen estar basados en la mejor elección en cada iteración. Estos métodos han sido muy utilizados en problemas clásicos como el del viajante de comercio. Métodos de Búsqueda Local: A diferencia de los métodos anteriores, los procedimientos de búsqueda o mejora local comienzan con una solución del problema y la mejoran progresivamente. El procedimiento realiza en cada paso un movimiento de una solución a otra con mejor valor. El método finaliza cuando, para una solución, no existe ninguna solución accesible que la mejore. Si bien todos estos métodos han contribuido a ampliar nuestro conocimiento para la resolución de problemas reales, los métodos constructivos y los de búsqueda local constituyen la base de los procedimientos meta-heurísticos.

Los modelos meta-heurísticos son una herramienta muy estudiada en la actualidad para resolver instancias de problemas que se creen difíciles en general, explorando el espacio de soluciones

Capítulo 1

13

(usualmente grande) para estas instancias. Estos modelos logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.

1.1 Problemas de Optimización Combinatoria Una característica recurrente en los problemas de optimización combinatoria es el hecho de que son muy fáciles de entender y de enunciar, pero generalmente son difíciles de resolver. Podría pensarse que la solución de un problema de optimización combinatoria se restringe únicamente a buscar de manera exhaustiva el valor máximo o mínimo en un conjunto finito de posibilidades y que usando una computadora veloz, el problema carecería de interés matemático, sin pensar por un momento en el tamaño de este conjunto, que hace inviable cualquier intento de búsqueda exhaustiva en problemas de tamaño no muy restringidos.

Un problema de optimización combinatoria puede definirse de forma más precisa de la siguiente manera:

Una tupla P=(S, Ω, f) donde

S: un conjunto finito de variables de decisión discretas

Ω: restricciones entre las variables.

f: una función objetivo

La búsqueda en el espacio S se define como sigue: Xi, i=1,…,n, un conjunto de variables discretas

con valores . Una instancia de una variable no es más que asignarle a Xi un

valor , una solución es una asignación completa si todas las variables de decisión tienen

asignado un valor y si satisface todas las restricciones Ω es una solución factible.

Existen una gran cantidad de problemas de optimización combinatoria por ejemplo, el Problema del Viajante de Comercio, el Problema de la Secuenciación de Tareas y el Problema de Cubrimiento de Conjuntos los cuales serán explicados en este epígrafe entre otros.

1.1.1 Problema del Viajante de Comercio

Este problema, también conocido como Travelling Salesman Problem (TSP), ha sido uno de los más estudiados en Investigación Operativa, por lo que merece una atención especial. Cuando la teoría de la Complejidad Algorítmica se desarrolló, el TSP fue uno de los primeros problemas en estudiarse, probando Karp en [13] que pertenece a la clase de los problemas difíciles (NP-hard). Desde los métodos de Ramificación y Acotación hasta los basados en la Combinatoria Poliédrica, pasando por

Capítulo 1

14

⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

09631109058346502413820321343061041260

los procedimientos meta-heurísticos, todos han sido inicialmente probados en el TSP, convirtiéndose éste en una prueba obligada para validar cualquier técnica de resolución de problemas combinatorios. La librería TSPLIB [14] de dominio público contiene un conjunto de ejemplos del TSP con la mejor solución obtenida hasta la fecha y, en algunos casos, con la solución óptima. El Problema del Viajante puede enunciarse del siguiente modo: Un viajante de comercio ha de visitar n ciudades, comenzando y finalizando en su propia ciudad y no visitando más de una vez ninguna ciudad intermedia. Conociendo el costo de ir de cada ciudad a otra, determinar el recorrido de costo mínimo. Para enunciar el problema formalmente introducimos la siguiente terminología: Sea un grafo G = (V; A; C) donde V es el conjunto de vértices, A es el de aristas y C = (cij) es la matriz de costos. Donde cada elemento (i, j) de la matriz C representa un costo o distancia de la arista (i; j).

- Un camino (o cadena) es una sucesión de aristas (a1; a2;…; ak) en donde el vértice final de cada arista coincide con el inicial de la siguiente. También puede representarse por la sucesión de vértices utilizados.

- Un camino es simple o elemental si no utiliza el mismo vértice más de una vez. - Un ciclo es un camino (v1; v2;…; vk) en el que el vértice final vk coincide con el inicial v1. - Un ciclo es simple si lo es el camino que lo define. - Un subtour es un ciclo simple que no pasa por todos los vértices del grafo. - Un tour o ciclo hamiltoniano es un ciclo simple que pasa por todos los vértices del grafo.

Pueden surgir otras restricciones debidas a la representación elegida. También existen muchas variantes del problema que introducen restricciones de todo tipo. Para el presente trabajo se contemplará únicamente la versión más habitual (matriz simétrica). El Problema del Viajante consiste en determinar un tour de costo mínimo. La Figura 1.1 Muestra una instancia del TSP.

A continuación se presentan algunos de los trabajos publicados con la aplicación de diferentes técnicas para atacar este problema:

- El trabajo de Johnson [15] presenta un estudio sobre la optimización local aplicada al problema del Viajante de Comercio. Trata dos métodos específicos, 2-opt y 3-opt .

Figura1.1 Instancia del TSP simétrico de 6 ciudades

Capítulo 1

15

- El primer algoritmo Tabu Search implementado para TSP fue descrito por Glover (1986), además de otra variantes desarrolladas por Glover (1989), Knox y Glover (1989), Knox (1989, 1994), y métodos similares fueron estudiados por Troyon (1988) y Malek, Guyruswamy, y Pandya (1989).

- El TSP fue uno de los primeros problemas para el cual Simulated Annealing fue aplicado [15], sirve de ejemplo para Kirkpatrick et al. (1983) y Cerny (1985) y luego en [16, 17].

- El uso de Genetic Algorithms como método de optimización se inició a principios de 1970 [15] y aplicado al TSP por Brady (1985) [18] también en el trabajo presentado por Mühlenbein, Gorges-Schleuter, y Krämer (1988) y más recientemente [19, 20] .

- La primera aplicación de Neural Networks al TSP [18] apareció en el trabajo de Hopfield and Tank (1985).

- Stützle et al. [21] presenta un interesante trabajo comparando métodos heurísticos inspirados en la naturaleza para resolver el TSP, donde se encuentran; ACO, Evolutionary Computation, etc.

1.1.2 Secuenciación de Tareas

Los problemas de Scheduling son una familia de problemas que aparecen con frecuencia en la realidad. Podemos encontrar problemas de esta familia en muchas áreas de la industria, la administración y la ciencia; problemas que van desde la organización de la producción hasta la planificación de multiprocesadores. Los problemas de Scheduling son en general NP-duros por lo que para resolverlos se han aplicado prácticamente todas las técnicas de Inteligencia Artificial, con mayor o menor éxito. Así, podemos encontrar en la literatura (véase, por ejemplo, el número de la revista Artificial Intelligence 1992) soluciones con técnicas heurísticas [22, 23], Programación Lógica [24, 25], Redes Neuronales [26], Aprendizaje Automático [27], Ramificación y Poda [28], Búsqueda Local [29], Búsqueda Tabú [30], Recocido Simulado [31] y Algoritmos Genéticos [32-34], entre otros. Uno de los problemas de Scheduling más clásicos es el de secuenciación de tareas (Job Shop Scheduling, JSS). El problema JSS aparece con profusión en la literatura científica como ejemplo de prueba de muchas técnicas de resolución de problemas. Hay también disponibles un banco de numerosas instancias [35] de uso común entre los investigadores, lo que facilita el contraste de resultados experimentales. En [36], Jain y Meeran ofrecen una clasificación de las principales técnicas que han sido aplicadas para resolver el problema de secuenciación. Existen distintas variantes del problema de secuenciación de tareas (Job Shop Scheduling, JSS) dependiendo del criterio de optimización. En este trabajo consideramos el más clásico: el problema conocido en la literatura como J//Cmax. Se trata de planificar la ejecución de un conjunto de trabajos J1,...,Jn sobre un conjunto de máquinas M1,...,Mm. Cada trabajo Ji está compuesto por un conjunto de operaciones o tareas

Capítulo 1

16

oi1,...,oim que deben ser ejecutadas secuencialmente. Cada operación oij requiere el uso exclusivo e ininterrumpido de una de las máquinas durante su tiempo de procesamiento duij. Supondremos además que para cada trabajo hay un tiempo mínimo de inicio (tik) y un tiempo máximo de terminación (pik) entre los cuales deben ser planificadas todas sus tareas. El objetivo es conseguir un tiempo de inicio para cada una de las tareas de modo que se satisfagan todas las restricciones del problema y que además se minimice el tiempo de finalización de todas las tareas, es decir el makespan.

M J,J:maxminmin kimax*max MptCC ikikschedulingfactible

∈∀∈∀+== (1.1)

Se trata de uno de los problemas de optimización combinatoria más difíciles de resolver. No sólo es del tipo NP-hard, sino que entre los que pertenecen a esta tipología, es de los más complejos.

Para poder ser más claros listaremos las restricciones del JSSP clásico:

No está permitido que dos operaciones del mismo trabajo se procesen simultáneamente. No hay prioridad entre operaciones de distintos trabajos. Ningún trabajo puede ser procesado más de una vez en la misma máquina. Cada trabajo es procesado hasta concluirse, aunque haya que esperar y retardarse entre las

operaciones procesadas. Un trabajo puede iniciarse en cualquier momento siempre y cuando esté disponible la

máquina y no se haya especificado un tiempo de inicio. Los trabajos tienen que esperar a que la máquina procesara la siguiente operación esté

disponible para que este sea procesado. Ninguna máquina puede procesar más de un trabajo a la vez. Los tiempos de configuración y cambio de máquina son independientes del orden de

procesamiento y este está incluido en los tiempos de procesamiento. Hay solo un tipo de máquina. Las máquinas pueden estar ociosas en cualquier momento del plan de trabajo. Las máquinas están disponibles en cualquier momento. Las restricciones tecnológicas están bien definidas y son previamente conocidas, además

de que son inamovibles, en otras palabras, el orden en que deben de ser ejecutadas las operaciones de cada trabajo.

Tipos de planes de trabajo

Los planes de trabajo generalmente se categorizan en las siguientes clases:

Capítulo 1

17

- Un plan de trabajo en que ninguna operación puede iniciarse sin cambiar el orden de procesamiento o sin que se viole alguna de las restricciones tecnológicas es llamado semi activo.

- Un plan de trabajo en que ninguna operación puede iniciarse sin que se retarde cualquier otra operación o sin que se viole alguna de las restricciones tecnológicas es llamado activo.

- Un plan de trabajo en que ninguna máquina está nunca ociosa si una operación está lista para ser procesada en esta es llamado sin retardo.

Figura 1.2 Jerarquía de tipos de Scheduling factibles

Esta figura muestra la jerarquía de las clases de planes de trabajo para las medidas de desempeño normal. El conjunto de los planes de trabajo sin retardo es un subconjunto de los planes de trabajo activos. Los planes de trabajo óptimos son un subconjunto de los planes de trabajo activos, pero estos no son un subconjunto de los planes de trabajo sin retardo. Por lo que para este problema se deben de construir planes activos, trayendo como consecuencia la reducción del espacio de búsqueda y garantizando que pueda ser encontrada la solución óptima.

(2,10)

1 (1, 2)

2 (4,7)

3 (3, 5)

4

(1,12) 5

(4,6) 6

(3,5) 7

(2,2) 8

Tabla 1.1 Instancia de 2 trabajos y 4 máquinas del JSSP

En la tabla anterior se muestra un ejemplo para una instancia del JSSP simple con dos tareas a procesar en cuatro máquinas. La forma de los datos son (máquina, duración), los números en negritos representan los nodos del grafo generado para dicha instancia, en el próximo capítulo se explicará la forma de construcción.

Capítulo 1

18

1.1.3 Problema del Cubrimiento de Conjuntos

Este problema, también conocido como Set Covering Problem (SCP) [37-39], se puede enunciar del siguiente modo: Sea un conjunto de objetos (filas) S = 1,2,…m y una clase H (columnas) de subconjuntos de S, H = H1, H2 …, Hn donde cada Hi tiene un costo ci asociado. El problema consiste en cubrir con costo mínimo todos los elementos de S con subconjuntos Hi. Para formular el problema se define una variable xi que vale 1 si Hi está en la solución y 0 en otro caso. También se introduce una matriz A = aij en donde el aij vale 1 si el elemento j de S está en Hi y 0 en otro caso. MIN : c1x1 + c2x2 + … + cnxn s.a.: a1jx1 + a2jx2 + …+ anjxn ≥ 1, j = 1,…,m xi = 1, 0 i = 1,…, n Una instancia de este problema se puede representar de la siguiente forma:

Figura 1.3 Instancia del problema SCP de 5 elementos de S y 10 de H

Donde la tabla de la figura 1.3 muestra para cada elemento de H (columnas) cuales elementos de S (filas) cubre y Ci los costos asociados a cada elemento de H, se trata de encontrar el conjunto de columnas de costo mínimo que cubran todas las filas. Este problema tiene diferentes aplicaciones, entre las que podemos destacar la localización de servicios, tales como hospitales, bomberos y la asignación de tripulaciones a vuelos etc. El SCP es relativamente fácil de resolver con métodos de Ramificación y Acotación ya que la solución óptima del problema lineal coincide, en ocasiones, con la del entero o está bastante cerca de él. La dificultad del problema viene del número enorme de variables que suelen aparecer en problemas reales.

1.2 Vida artificial y algoritmos de Búsqueda Local En la naturaleza, los seres vivos se enfrentan a problemas que deben resolver con éxito para desarrollarse, como obtener más luz del sol, o conseguir alimento para su subsistencia. La sapiencia

Capítulo 1

19

de la naturaleza para resolver estos problemas ha sido siempre admirada e imitada en muchos campos de la ciencia. Una de ellas, la computación, ha creado técnicas de Inteligencia Artificial con el objeto de plasmar en sistemas computacionales la esencia misma de la naturaleza observable. La Vida Artificial [40-42] o algoritmos bioinspirados es una disciplina que estudia la vida natural, recreando los fenómenos biológicos en ordenadores y otros medios artificiales. Complementa el estudio teórico de la biología pero en lugar de tomar organismos aislados y analizar su comportamiento, lo que se intenta es colocar juntos organismos que actúan como los seres vivos. Esta técnica se puede encontrar en aplicaciones prácticas como en el diseño de ordenadores (hardware y software), robots móviles, medicina, nanotecnología, etc. El presente trabajo trata sobre una de las más recientes técnicas de Inteligencia Artificial en el área de Vida Artificial, conocida como Optimización Basada en Colonias de Hormigas (Ant Colony Optimization, ACO) [11, 12], meta-heurística inspirada en el comportamiento (a nivel de especie) de una colonia de hormigas que optimizan el camino para llegar desde el nido hasta su fuente de alimento, utilizando para éste fin, comunicación indirecta por medio de una sustancia química denominada feromona y su capacidad para adaptarse a cambios de ambiente. Se tratará el tema con profundidad en el epígrafe siguiente.

1.2.1 Optimización Basada en Colonias de Hormigas

Esta novedosa técnica cae en la categoría de meta-heurística [5, 43, 44] en la cual una colonia de hormigas artificiales coopera para encontrar buenas soluciones a diferentes problemas de optimización discreta. La cooperación es un componente clave de los algoritmos ACO. Se inspira en el comportamiento de las hormigas, animales casi ciegos pero con la habilidad de optimizar el camino hasta llegar a la fuente de su alimento y regresar al nido. Cae en la categoría de la llamada “Inteligencia Colectiva” (Swarm Intelligence) [45]. Un enjambre (swarm) puede ser definido como una colección estructurada de organismos (agentes) que interactúan. La inteligencia no está en los individuos sino en el colectivo. La base de la misma está en la interacción social directa o indirecta entre los individuos. La interacción directa ocurre cuando un individuo es capaz de comunicar de forma directa a los otros agentes del enjambre la información recopilada por él. La interacción indirecta se manifiesta cuando un individuo cambia el ambiente y el otro agente responde al nuevo ambiente. Ejemplos de inteligencia colectiva son las colonias de hormigas (ant colonies), las bandadas de pájaros (bird flocks) y colonias de peces (fish colonies), etc. Las colonias de hormigas, y más general las sociedades de insectos, son sistemas distribuidos, que a pesar de la simplicidad de sus individuos, presentan una organización social altamente estructurada. Uno de los patrones de comportamiento exhibido por las hormigas es su habilidad para encontrar el camino más corto, para lo cual coordinan su actividad mediante una comunicación indirecta lograda por modificación del medio ambiente usando una sustancia química llamada feromona.

Capítulo 1

20

El modelo ACO (Ant Colony Optimization) es un modelo computacional que ofrece las técnicas algorítmicas más exitosas y ampliamente reconocidas basadas en el comportamiento de las hormigas [46]. La idea básica del modelo ACO es usar una forma de comunicación indirecta artificial (artificial stigmergy) para coordinar sociedades de agentes artificiales para resolver problemas de optimización discretos. Una hormiga artificial en ACO es un procedimiento constructivo estocástico que construye incrementalmente una solución agregando oportunamente componentes a la solución parcial en construcción. Las diferencias de las hormigas artificiales con respecto a las hormigas naturales son: (i) Tienen alguna memoria; (ii) No son completamente ciegas; y, (iii) Viven en un ambiente donde el tiempo es discreto.

1.2.2 Modo de funcionamiento y estructura genérica de la meta-heurística ACO

El modo de operación básico de un algoritmo de ACO es como sigue: las m hormigas (artificiales) de la colonia se mueven, concurrentemente y de manera asíncrona, a través de los estados adyacentes del problema (que puede representarse en forma de grafo). Este movimiento se realiza siguiendo una regla de transición que está basada en la información local disponible en las componentes (nodos). Esta información local incluye la información heurística (dependiente del problema) y memorística (rastros de feromona) para guiar la búsqueda. Al moverse por el representativo del problema, las hormigas construyen incrementalmente soluciones. Opcionalmente, las hormigas pueden depositar feromona cada vez que crucen un arco (conexión) mientras que construyen la solución (actualización en línea paso a paso de los rastros de feromona).

Una vez que cada hormiga ha generado una solución se evalúa ésta y puede depositar una cantidad de feromona que es función de la calidad de su solución (actualización en línea de los rastros de feromona). Esta información guiará la búsqueda de las otras hormigas de la colonia en el futuro.

Es bueno aclarar que la estructura que almacena la feromona está en dependencia del tipo del problema a resolver: para problemas de secuenciación o asignación, la feromona es asociada a los arcos del grafo representativo, por lo que se habla de una matriz de feromona, como se presenta en la mayoría de los problemas. Para problemas donde el orden de los elementos de la solución no es importante se le asocia la feromona a los nodos del grafo, por lo que se utiliza como estructura de almacenamiento un vector de feromona. Estas dos variantes serán ejemplificadas en el capítulo siguiente. En lo adelante, para explicar el funcionamiento genérico de la meta-heurística ACO y el comportamiento de sus algoritmos se utilizará el término de matriz de feromona, sin que se refiera a un tipo de problema en específico.

Los valores iniciales de feromona pueden ser de la siguiente forma:

Capítulo 1

21

• Inicialización aleatoria: donde cada elemento de la matriz es un elemento escogido aleatoriamente con distribución uniforme en el intervalo (0,1).

• Con un valor constante: cada elemento de la matriz es inicializado con el mismo valor, este valor debe de estar en el intervalo (0,1).

• Inicialización dependiendo de una solución (S) calculada por algún otro algoritmo con menor costo computacional; donde cada elemento de la matriz es inicializado con el valor 1/S.

Además, el modo de operación genérico de un algoritmo de ACO incluye dos procedimientos adicionales, la evaporación de los rastros de feromona y las acciones del demonio. La evaporación de feromona la lleva a cabo el entorno y se usa como un mecanismo que evita el estancamiento en la búsqueda y permite que las hormigas busquen y exploren nuevas regiones del espacio. Las acciones del demonio son acciones opcionales -que no tienen un contrapunto natural- para implementar tareas desde una perspectiva global que no pueden llevar a cabo las hormigas por la perspectiva local que ofrecen. Entre las capacidades adicionales que desarrolla las acciones del demonio están por ejemplo: observar la calidad de todas las soluciones generadas y depositar una nueva cantidad de feromona adicional sólo en las transiciones/componentes asociadas a algunas soluciones, o aplicar un procedimiento de búsqueda local a las soluciones generadas por las hormigas antes de actualizar los rastros de feromona. En ambos casos, el demonio reemplaza la actualización en línea a posteriori de feromona y el proceso pasa a llamarse actualización fuera de línea de rastros de feromona.

La estructura de un algoritmo de ACO genérico es como sigue [47, 48]: Procedimiento meta-heurísticaACO; Actividades Programadas

Construir Soluciones de las Hormigas

Actualizar Feromonas

Evaporación de la feromona

Acciones del Demonio (opcional)

Fin de las Actividades Fijas

Fin del procedimiento

Este procedimiento se anida en el siguiente procedimiento iterativo:

P1: Inicializar los valores de feromona

nciclo=1

P2: Repetir

Procedimiento meta-heurísticaACO

nciclo= nciclo+1

Hasta que: criterio de parada

Capítulo 1

22

Los criterios de parada de este proceso iterativo son, entre otros:

- Se alcanza un número máximo de ciclos.

- Se alcanza una solución con la calidad deseada.

- Convergencia a la misma solución (estancamiento o stagnation).

- Se alcanza un tiempo límite o predeterminado de procesamiento.

En cualquier caso, la meta-heurística ACO no es lo suficientemente general como para cubrir la familia completa de algoritmos de hormigas, que pueden definirse (aunque no de manera muy precisa) como métodos aproximados para solucionar problemas combinatorios basados en características del comportamiento genérico de las hormigas naturales. Algunos ejemplos de algoritmos de hormigas que no están incluidos en la meta-heurística ACO son el Sistema de Hormiga Rápido (“Fast Ant System”) [49] y el Sistema de Hormiga Híbrido (“Hybrid Ant System”) [50]. El primero es un algoritmo de construcción que se basa en el modo de operación de una única hormiga y que no utiliza de manera explícita la evaporación de feromona. El segundo consiste en un procedimiento de búsqueda local que hace uso de la información de los rastros de feromona para generar soluciones vecinas.

Observando las aplicaciones actuales de la ACO, podemos identificar algunas directivas sobre como

atacar problemas utilizando esta metaheurística. Estas directivas se pueden resumir en las seis tareas

de diseño que se enumeran a continuación:

1. Representar el problema como un conjunto de componentes y transiciones a través de un

grafo1 que será recorrido por las hormigas para construir soluciones

2. Definir de manera apropiada el significado de los rastros de feromona τ , esto es, el tipo de

decisión que inducen. Éste es un paso crucial en la implementación de un algoritmo de ACO

y, a menudo, una buena definición de los rastros de feromona no es una tarea trivial. De

hecho, normalmente implica tener un buen conocimiento del problema que se quiere

solucionar.

3. Definir de manera apropiada la preferencia heurística de cada decisión que debe tomar una

hormiga mientras construye una solución, es decir, definir la información heurística rsη

1 Remítase al anexo 2 donde se especifica la teoría de grafo utilizada en este trabajo.

Capítulo 1

23

asociada a cada componente o transición. Hay que remarcar que la información heurística es

crucial para un buen rendimiento si no existen o no pueden ser aplicados algoritmos de

búsqueda local.

4. Si es posible, implementar una búsqueda local eficiente para el problema que se desea

solucionar, porque los resultados de muchas aplicaciones de la ACO a problemas de

optimización combinatoria NP-completos demuestran que el mejor rendimiento se alcanza

cuando se complementa con optimizaciones locales [51, 52].

5. Escoger un algoritmo de ACO específico y aplicarlo al problema que hay que solucionar

teniendo en cuenta las características propias de cada uno.

6. Refinar los parámetros del algoritmo de ACO. Un buen punto de partida para la especificación de los valores de los parámetros es usar configuraciones de parámetros que han demostrado ser buenas cuando se aplicaban en el algoritmo de ACO a problemas similares o a una gran variedad de problemas distintos. Otra posible alternativa para evitar el esfuerzo y tiempo necesarios para esta tarea es utilizar procedimientos automáticos de refinamiento de parámetros [53].

1.2.3 Algoritmos de la meta-heurística ACO

En la literatura se han propuesto diversos algoritmos que siguen la meta-heurística ACO. Entre los algoritmos de ACO disponibles para problemas de optimización combinatoria NP-duros, se encuentran el Sistema de Hormigas (Ant System (AS)) [54], el Sistema de Colonia de Hormigas (Ant Colony System (ACS)) [55], el Sistema de Hormigas Max-Min (, Max-Min Ant System) [56], el AS con Ordenación (Rank-Based Ant System) [57], el Sistema de la Mejor-Peor Hormiga (Best-Worst Ant System) [58] entre otros. Muchos investigadores interesados por la originalidad y el rendimiento del modelo ACO, aplicaron la técnica con excelentes resultados a problemas tan diversos como:

- El paradigma del viajante de comercio (Travelling Salesman Problem) [12, 59]; - El problema del ordenamiento secuencial (Sequential Ordering Problem)[60]; - El problema de ruteo de vehículos (Vehicle Routing Problem)[61]; - El problema de asignación cuadrática (Quadratic Assignment Problem) [62]; - Redes de telecomunicaciones (Telecommunications Networks) [63].

Esta técnica comienza a tener la madurez tecnológica adecuada para su utilización en problemas reales, como puede verse por la publicación del libro [64].

Capítulo 1

24

En lo que sigue, presentaremos una pequeña descripción de los algoritmos AS y ACS ya que son los utilizados en nuestro trabajo. El Sistema de Hormigas (Ant System, AS) [54], desarrollado por Dorigo, Maniezzo y Colorni en 1991, fue el primer algoritmo de ACO. Inicialmente, se presentaron 3 variantes distintas: Hormiga-Densidad (Ant-Density), Hormiga-Cantidad (Ant-Quality) y Hormiga-Ciclo (Ant-Cycle), que se diferenciaban en la manera en que se actualizaban los rastros de feromona. En los dos primeros, las hormigas depositaban feromona mientras construían sus soluciones (es decir, aplicaban una actualización en línea paso a paso de feromona), con la diferencia de que la cantidad de feromona depositada en Hormiga-Densidad es constante, mientras que la depositada en Hormiga-Cantidad dependía directamente de la deseabilidad heurística de la transición rsη . Por último, en Hormiga-

Ciclo, la deposición de feromona se lleva a cabo una vez que la solución está completa (actualización en línea a posteriori de feromona). Esta última variante era la que obtenía mejores resultados y es por tanto la que se conoce como AS en la literatura y en el resto de este trabajo. El AS se caracteriza por el hecho de que la actualización de feromona se realiza una vez que todas las hormigas han completado sus soluciones, y se lleva a cabo como sigue: primero, todos los rastros de feromona se reducen en un factor constante, implementándose de esta manera la evaporación de feromona según la expresión 1.2,

( ) ( ]1,0,1 ∈∗−← ptpt ijij (1.2)

donde p se conoce como constante de evaporación y es la encargada de reducir los rastros de feromona para evitar el estancamiento de las soluciones y tij la cantidad de feromona asociada al arco (i, j). A continuación, cada hormiga de la colonia deposita una cantidad de feromona que es función de la calidad de su solución, según expresión 1.3,

kij

kijij Sattt ∈∀Δ+← (1.3)

donde ))(( kk SCft =Δ , es decir, que la cantidad de feromona a depositar en cada arco ( ija ) que

pertenece a la solución ( kS ) de la hormiga k depende totalmente de la calidad ( )( kSC ) de la

solución encontrada por dicha hormiga. Inicialmente, el AS no usaba ninguna acción del demonio, pero es relativamente fácil, por ejemplo, añadir un procedimiento de búsqueda local para refinar las soluciones generadas por las hormigas, esto se verá más adelante. Las soluciones en el AS se construyen como sigue. En cada paso de construcción, una hormiga k escoge ir al siguiente nodo con una probabilidad que se calcula como:

Capítulo 1

25

( ) ( )( ) ( )

ki

Njijij

ijijkij Njsip

ki

∈=∑∈

βα

βα

ητ

ητ

*

* (1.4)

donde kiN es el vecindario alcanzable por la hormiga k cuando se encuentra en el nodo i, los

parámetros alfa (α ) y beta ( β ) controlan el proceso de búsqueda. Para α =0 se tiene una búsqueda

heurística estocástica clásica, mientras que para 0=β solo el valor de la feromona tiene efecto. Un

valor de 1<α lleva a una rápida situación de convergencia (stagnation), kijP es un vector de

probabilidades de visitar cada uno de los nodos de la vecindad ( kiN ) por la hormiga k, ijτ el valor

del elemento i, j en la matriz de feromona y ijη , se denomina función de visibilidad o función

heurística que depende totalmente de las características del problema que se va a resolver. El Sistema de Colonias de Hormigas (Ant Colony System, ACS) [55] es uno de los primeros sucesores del AS que introduce tres modificaciones importantes con respecto a dicho algoritmo de ACO: 1. El ACS usa una regla de transición distinta y más agresiva, denominada regla proporcional

pseudo-aleatoria. Sea k una hormiga situada en el nodo r, [ ]1,00 ∈q un parámetro y q un valor

aleatorio en [0,1], el siguiente nodo i se elige aleatoriamente mediante la siguiente distribución de probabilidad:

si 0qq ≤

⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧ =

= ∈

casosotros

jsiP ijijNjk

ijki

,0

*max,1 βητ (1.5)

si no ( 0qq > ):

( ) ( )( ) ( )

ki

Njijij

ijijkij Njsip

ki

∈=∑∈

βα

βα

ητ

ητ

*

* (1.6)

Como puede observarse, la regla tiene una doble intención: cuando q ≤ q0, explota el conocimiento disponible, eligiendo la mejor opción con respecto a la información heurística y los rastros de feromona. Sin embargo, si q > q0 se aplica una exploración controlada, tal como se hacía en el SH. En resumen, la regla establece un compromiso entre la exploración de nuevas conexiones y la explotación de la información disponible en ese momento.

2. Las hormigas aplican una actualización en línea paso a paso de los rastros de feromona que favorece la generación de soluciones distintas a las encontradas.

Capítulo 1

26

Cada vez que una hormiga viaja por una arista ija , aplica la regla:

0*)1( ttt ijij +−← ϕ (1.7)

donde ]1,0(∈ϕ es un segundo parámetro de decremento de feromona. Como puede verse, la

regla de actualización en línea paso a paso incluye tanto la evaporación de feromona como la deposición de la misma. Ya que la cantidad de feromona depositada es muy pequeña (de hecho, t0 es el valor del rastro de feromona inicial y se escogiese de tal manera que, en la práctica, se corresponda con el límite menor de rastro de feromona, esto es, con la elección de las reglas de actualización de feromona del ACS ningún rastro de feromona puede caer por debajo de t0), la aplicación de esta regla hace que los rastros de feromona entre las conexiones recorridas por las hormigas disminuyan. Así, esto lleva a una técnica de exploración adicional del ACS ya que las conexiones atravesadas por un gran número de hormigas son cada vez menos atractivas para el resto de hormigas que las recorren en la iteración actual, lo que ayuda claramente a que no todas las hormigas sigan el mismo camino.

3. Sólo el demonio (y no las hormigas individualmente) actualiza la feromona, es decir, se realiza una actualización de feromona fuera de línea de los rastros. Para llevarla a cabo, el ACS sólo considera una hormiga concreta, la que generó la mejor solución global, Smejor-global (aunque en algunos trabajos iníciales se consideraba también una actualización basada en la mejor hormiga de la iteración [65], en ACO casi siempre se aplica la actualización por medio de la mejor global). La actualización de la feromona se hace evaporando primero los rastros de feromona en todas las conexiones utilizadas por la mejor hormiga global (es importante recalcar que, en el ACS, la evaporación de feromona sólo se aplica a las conexiones de la solución, que es también la usada para depositar feromona) tal como sigue:

globalmejorijijij Satpt −∈∀−← *)1( (1.8)

A continuación el demonio deposita feromona a los arcos que pertenecen a la mejor solución encontrada hasta el momento usando la regla:

globalmejorijijij Sattt −∈∀Δ+← (1.9)

Donde ))(( globalmejorSCft −=Δ , es decir la cantidad de feromona esta en dependencia de la

calidad de la mejor solución encontrada hasta el momento )( globalmejorSC − .

En general, las soluciones obtenidas con los métodos constructivos y de vida artificial como es el caso de la meta-heurística ACO suelen ser de una calidad moderada, por lo que es razonable aplicarle diversos algoritmos basados en la búsqueda local para mejorarlas.

Capítulo 1

27

1.2.4 Búsqueda Local

Los procedimientos de búsqueda local, también llamados de mejora, se basan en explorar el entorno o vecindad (neighborhood search, VNS) [66, 67] de una solución. Utilizan una operación básica llamada movimiento que, aplicada sobre los diferentes elementos de una solución, proporciona las soluciones de su entorno. Formalmente:

Definición: Sea X el conjunto de soluciones del problema combinatorio. Cada solución x tiene un

conjunto de soluciones asociadas , que denominaremos entorno de x.

Definición: Dada una solución x, cada solución de su entorno, , puede obtenerse

directamente a partir de x mediante una operación llamada movimiento.

Un procedimiento de búsqueda local parte de una solución inicial x0, calcula su entorno N(x0) y escoge una nueva solución x1 en él. Dicho de otro modo, realiza el movimiento m1 que aplicado a x0 da como resultado x1. Este proceso se aplica reiteradamente, describiendo una trayectoria en el espacio de soluciones.

Un procedimiento de búsqueda local queda determinado al especificar un entorno y el criterio de selección de una solución dentro del entorno. La definición de entorno/movimiento, depende en gran medida de la estructura del problema a resolver, así como de la función objetivo. También se pueden definir diferentes criterios para seleccionar una nueva solución del entorno. Uno de los criterios más simples consiste en tomar la solución con mejor evaluación de la función objetivo, siempre que la nueva solución sea mejor que la actual. Este criterio, conocido como Greedy, permite ir mejorando la solución actual mientras se pueda. El algoritmo se detiene cuando la solución no puede ser mejorada. A la solución encontrada se le denomina óptimo local respecto al entorno definido. El óptimo local alcanzado no puede mejorarse mediante el movimiento definido. Sin embargo, el método empleado no permite garantizar, de ningún modo, que sea el óptimo global del problema. Más aún, dada la “miopía” de la búsqueda local, es de esperar que en problemas de cierta dificultad, en general no lo sea.

Pese a la miopía de los métodos de búsqueda local simples, suelen ser muy rápidos y proporcionan soluciones que, en promedio, están relativamente cerca del óptimo global del problema. Además, dichos métodos suelen ser el punto de partida en el diseño de algoritmos meta-heurísticos más complejos.

Existen distintos algoritmos de búsqueda local basados en el intercambio de vecindad entre los que se encuentran: el Algoritmo de Lin y Kernighan [68-71], el Algoritmo de 2-intercambio, de 3-intercambio [72] y mas general el Algoritmo de k-intercambio [73], en este epígrafe veremos con

Capítulo 1

28

mas detalles el Algoritmo de 2-intercambio. Estos algoritmos son muy dependientes del problema que resuelven, por lo que utilizaremos el TSP para describirlos.

El algoritmo 2-intercambio (2-opt) [74] fue propuesto por primera vez por Croes (1958) [75], aunque los movimientos básicos ya fueron sugeridos por Flood (1956) [76]. Este método elimina dos arcos, rompiendo el tour en dos caminos diferentes, que luego son reconectados de otra manera posible. El trabajo de Johnson et al.[77] presenta un estudio sobre la optimización local aplicada al problema del viajante de comercio. Entre los métodos que trata, el 2-opt intenta mejorar un tour específico realizando simples movimientos para convertir un tour en otro, esto es, dado un tour factible, el algoritmo realiza repetidas operaciones de una clase, hasta reducir la longitud de tour actual o hasta que se consiga un tour para el cual ya no exista operaciones posibles que la mejoren. Alternativamente, se puede ver esto como un proceso de búsqueda en la vecindad (neighborhood search), donde cada tour tiene una vecindad asociada de tours adyacentes, esto significa que pueden ser encontrados con un solo movimiento y esto se realiza hasta encontrar uno mejor o hasta que ya no existan mejores. Su comportamiento general se presenta como: Algoritmo 2-opt Inicialización

Considerar un ciclo Hamiltoniano inicial

move=1

Mientras (move=1)

move=0. Etiquetar todos los vértices como no explorados.

Mientras( Queden vértices por explorar)

Seleccionar un vértice i no explorado.

Examinar todos los movimientos 2-opt que incluyan la arista de i

a su sucesor en el ciclo. Si alguno de los movimientos

examinados reduce la longitud del ciclo, realizar el mejor de

todos y hacer

move = 1.

En otro caso etiquetar i como explorado.

Como se puede apreciar este algoritmo parte de una solución factible por lo que puede ser aplicado conjuntamente con algún algoritmo heurístico que le facilite la solución factible inicial. Estudios realizados sobre el efecto de combinar la búsqueda local con la meta-heurística ACO se presentan en [65, 78, 79].

Capítulo 1

29

En nuestro trabajo realizamos un estudio de la aplicación de la búsqueda local a las soluciones encontradas por el algoritmo ACS aplicado al TSP, así como, analizaremos el comportamiento del nuevo modelo con búsqueda local.

1.3 Conclusiones parciales

A partir de la revisión bibliográfica desarrollada para presentar este capítulo se pueden extraer las conclusiones siguientes:

Los problemas de optimización combinatoria caen regularmente en la categoría de problemas en la que se tienen algoritmos para resolverlos pero cuando su dimensión crece estos se vuelven inaplicables computacionalmente; de modo que la aplicación de los métodos heurísticos representa una buena alternativa.

Los algoritmos bioinspirados y en particular la meta-heurística ACO es un modelo muy poderoso para dar solución a esta clase de problemas ya que propone formas muy precisas de emplear la cooperación entre agentes para la solución de problemas de optimización combinatoria.

La cooperación causa fundamental del éxito del modelo ACO trae consigo que la calidad de las soluciones este estrechamente relacionada con la cantidad de agentes que se comuniquen, pero esto a su vez provoca un elevado costo computacional; es decir, a mayor cantidad de cooperación (lograda mediante el incremento de la cantidad de agentes cooperando o aumentando la cantidad de tiempo en que cooperan) mejores soluciones, pero mayor tiempo de ejecución. De modo que resulta conveniente explorar modificaciones al modelo ACO que enfrenten esta contradicción.

Capítulo 2

30

Capítulo 2 Nuevo modelo ACO en dos etapas para resolver Problemas de Optimización Combinatoria En este capítulo se presenta una nueva estrategia de trabajo con la meta-heurística ACO llamada Optimización Basada en Colonias de Hormigas en Dos Etapas (Two Stages Ant Colony Optimization, TS-ACO), la cual propone modificar la estrategia de búsqueda desarrollada por el modelo ACO, esta modificación se basa en dividir el proceso de búsqueda de dos etapas, siendo la primera la encargada de determinar un conjunto de posibles estados iniciales para una segunda etapa que se encargará de dar soluciones concretas al problema en general.

2.1 Optimización basada en Colonias de Hormigas en dos Etapas

En los procesos de búsqueda heurística la determinación del estado inicial desde donde comenzar la misma, ha sido una problemática de interés, pues se ha mostrado que tiene un efecto importante en la solución final. El propósito es poder acercar lo más posible el estado inicial al estado final u objetivo. Por supuesto, es necesario considerar un balance adecuado entre el costo computacional de lograr ese acercamiento y el costo total, no sea que la suma del costo de aproximar el estado inicial al final, más el costo de encontrar la solución desde ese estado inicial “mejorado”, sea mayor que el costo de buscar la solución desde un estado inicial original, además es necesario que en el proceso de acercamiento no se pierda la posibilidad de explorar buenas soluciones.

De modo que el propósito es el siguiente. Sea Ei un estado inicial generado aleatoriamente, u obtenido por cualquier otro método sin un costo computacional significativo, Ei* un estado inicial generado por algún método M que lo acerca al estado final con un costo CM(Ei*) , y sea CCABH(x) el costo computacional de encontrar una solución desde el estado x usando el algoritmo ABH (Algoritmo de Búsqueda Heurística). Entonces el objetivo es que CM(Ei*)+ CCABH(Ei*) < CCABH(Ei).

La nueva forma de trabajo con la meta-heurística ACO, TS-ACO, propone como nueva estrategia de búsqueda hacer una división en dos de la exploración y del espacio de búsqueda, de modo que en la primera etapa se encuentren soluciones preliminares (soluciones parciales) que sirven de estado inicial para el proceso de búsqueda desarrollado en la segunda etapa. Para realizar esta división, primero se determinaron los factores que influyen en el tamaño de la exploración y del espacio de búsqueda, se detectó que el número de hormigas (m), la cantidad de ciclos (nc) y la longitud de alguna solución factible del problema (nn), son los parámetros que definen estos dos factores. Para establecer el tamaño de cada etapa se le introduce al modelo un factor de proporcionalidad (r), el

Capítulo 2

31

cual indica cuanto abarca cada etapa dentro del proceso de búsqueda completo. Este valor está en el intervalo (0,1), 0< r <1.

Por ejemplo, si r=0.3, esto significa que la primera etapa cubrirá con el 30% del tamaño de la exploración, el 30% del espacio de búsqueda completo. En otras palabras, el 30% de la cantidad total de hormigas de la colonia construirá soluciones de longitud igual al 30% del tamaño de la solución real, en el 30% de los ciclos. Después que se termine el proceso de búsqueda de la primera etapa, solo una cantidad de las mejores soluciones parciales encontradas en la primera etapa denotadas por (cs) servirán de punto de partida de las hormigas restantes (m-0.3* m) para la segunda etapa, con el objetivo de completar las soluciones con la exploración del espacio de búsqueda restante, para lo cual se completa con elementos restantes para los (nn-0.3* nn) nodos del grafo que no han sido explorados, en una cantidad de ciclos (nc-0.3* nc). La cantidad de soluciones parciales que pasan de la primera etapa a la segunda son un subconjunto de la cantidad de soluciones encontradas en esta etapa, donde ( )mrcs *≤ . Más genéricamente los parámetros de la primera etapa

se calculan como sigue:

nnrnnncrncmrm

*1*1*1

===

(2.1)

Y para la segunda etapa se calculan como:

1212

12

nnnnnnncncnc

mmm

−=−=−=

(2.2)

Es bueno aclarar que, para poder explicar más claramente el nuevo modelo se asumió que la variable número de ciclos (nc) representa la condición de parada, en el caso de que se utilice otro criterio, como por ejemplo un tiempo máximo de ejecución, puede fácilmente ponerse en dependencia del factor r, para que la primera etapa sea cubierta en un tiempo y la segunda en otro, como se verá en el capítulo 3 en la fase de solución del SCP.

El estado intermedio introducido por la nueva estrategia funciona como estado de entrega de las mejores subsoluciones de la primera etapa para el proceso de búsqueda en la etapa posterior, además, en este estado también se entrega la matriz de feromona utilizada en la primera etapa, de forma tal que la información acumulada por el proceso de búsqueda sea utilizada para guiar la misma en el resto del proceso, más claramente, la feromona es la misma para las dos etapas.

Capítulo 2

32

Modelo general de TS-ACO

Dados los parámetros del Modelo (factor (r), porciento de soluciones a usar (%cs), etc.) P1: Etapa 1.

P1.1: Calcular los parámetros que definen la dimensión de la primera etapa según

expresión 2.1

P1.2: Aplicar cualquier algoritmo de la meta-heurística ACO

P1.3: EI ← las %cs mejores soluciones parciales encontradas en la primera etapa

P2: Etapa 2.

P2.1: Calcular los parámetros para el proceso de búsqueda en la segunda etapa

según expresión 2.2

P2.2: Aplicar algoritmo de ACO utilizando como estados iniciales para las

hormigas en cada ciclo, soluciones parciales seleccionadas aleatoriamente del

conjunto EI

P3: Fin del proceso.

Como se puede apreciar, la elección del factor r debe tener una alta incidencia en el desempeño del algoritmo. Un valor alto de r, es decir, cercano al valor 1, hace que el estado intermedio Ei* se acerque más al estado objetivo, de modo que el valor de CACO(Ei*) debe aumentar y el de CCACO(Ei*) disminuir. Pero, además de este balance entre los costos de CACO(Ei*) y CCACO(Ei*), está la problemática de cuanto se explora el espacio de búsqueda; mientras mayor sea el valor de r el proceso de búsqueda en la segunda etapa disminuye por varias razones: (i) existen menos hormigas trabajando, (ii) la cantidad de ciclos decrece, (iii) y aunque la cantidad de posibles estados iniciales para la segunda etapa debe crecer cuando crezca r, ya esa cantidad está acotada por el resultado de la etapa previa.

De modo que resulta clave estudiar cual debe ser el valor del factor de proporcionalidad r que logre el mejor balance entre las búsquedas en ambas etapas. Este valor debe permitir:

1. Disminuir el valor de CACO(Ei*)+CCACO(Ei*), es decir, el costo computacional del proceso

de búsqueda completo.

2. Obtener buenas soluciones finales.

En aras de mostrar graficamente como se disminuye el tiempo de ejecución en la estrategia de búsqueda del nuevo modelo, presentamos la siguiente figura.

Capítulo 2

33

Figura 2.1 Explicación gráfica para el tiempo de ejecución de los dos modelos

Para probar que con el nuevo modelo se encuentran buenas soluciones a problemas de optimización combinatoria se presenta un estudio experimental en el capítulo 3.

2.2 Aplicación de los algoritmos ACS y TS-ACS al TSP

Para resolver el TSP utilizando ACS [12, 49, 80] y TS-ACS, se construye inicialmente un grafo no dirigido G=(N, A), donde el conjunto de nodos es igual a la cantidad de ciudades que presenta la instancia a resolver, los arcos representan distancias entre cada una de las ciudades, ver figuras 1.1 y 2.2, para este problema es importante el orden en que son visitadas las ciudades, es decir, es un problema de secuenciación, por lo que en este caso se tiene una matriz de feromona, que es lo mismo que asociar la feromona a los arcos del grafo, esta matriz se inicializa mediante algunos de los criterios presentados en el capítulo anterior.

Capítulo 2

34

Figura 2.2 Grafo generado para la instancia del TSP de la figura 1.1, marcado en negrita el tour óptimo desde la ciudad 1

Para este ejemplo, un posible tour calculado por las hormigas sería A:1; 3; 2; 6; 5; 4, cuyo costo es 2+3+1+9+5= 20 más el costo de regresar a la ciudad de partida que es 1 sería igual a 21. Pero el camino anterior no es el camino óptimo, pues existen recorridos muchos más pequeños en costo por ejemplo B:1; 4; 3; 6; 2; 5 cuyo costo es de 14, este recorrido representa el óptimo para este ejemplo.

2.2.1 ACS aplicado al TSP

El proceso comienza posicionando cada una de las hormigas que conforman la colonia en una ciudad escogida aleatoriamente, cada hormiga comienza a moverse por el grafo según las expresiones (1.5) y (1.6), para este problema la función heurística ijij d/1=η , donde dij es la

distancia de la ciudad i a la ciudad j, representada en la matriz de distancia en la posición i, j y la vecindad Ni del nodo i, son las ciudades que no han sido visitadas por la hormiga que está realizando el movimiento, o lo que es lo mismo, la diferencia entre el conjunto total de ciudades y la lista tabú, después la ciudad que fue elegida se introduce en la lista tabú de dicha hormiga, luego se procede a incrementar los valores de feromona con una actualización en línea paso a paso según la expresión 1.7, este proceso es repetido por todas las hormigas de la colonia, cada hormiga termina cuando su

vecindad , en otras palabras, cuando se ha pasado por todas las ciudades. Siempre que se

obtengan soluciones, éstas son evaluadas para tener almacenado el recorrido de menor distancia encontrado hasta el momento (mejor solución global). Cuando cada hormiga de la colonia encontró su solución, se pasa a la evaporación de los rastros de feromona pertenecientes a la mejor solución encontrada hasta el momento según expresión 1.8, además se realiza una actualización de los rastros de feromona asociados a esta solución (actualización global de los rastros de feromona ) según expresión 1.9.

Capítulo 2

35

Todo el proceso explicado anteriormente se ejecuta hasta que se cumpla con alguna de las condiciones de parada.

Descripción del algoritmo en pseudo código.

1. Fase de inicialización

Inicializar contador de ciclos nc

Inicializar total de Hormigas

Inicializar solución global Φ=globalL

Inicializar matriz de feromona t(i, j) = 0t

Cargar matriz de distancia d(i, j)

2. Repetir NC veces

Para cada hormiga

Elegir ciudad origen Repetir para cada hormiga hasta llenar su lista tabúk

Elegir próxima ciudad a ser visitada según ecuaciones

(1.5) y (1.6)

Mover la hormiga a la próxima ciudad

Insertar ciudad seleccionada en tabúk Actualizar feromonas paso a paso según ecuación (1.7)

Repetir para las k hormigas

Aplicar algoritmo de búsqueda local a Lk (opcional)

Calcular costo de la solución (Lk)

Si (Lk < Lglobal)

Actualizar Lglobal con Lk

Actualización global de las feromonas según ecuación (1.8) y (1.9)

3. Imprimir camino más corto Lglobal

2.2.2 TS-ACS aplicado al TSP

Se inicia el proceso calculando la dimensión de la primera etapa según expresión 2.1. El proceso continúa aplicando el algoritmo ACS como se explicó en el epígrafe anterior, solo que en la evaluación de las subsoluciones alcanzadas en esta etapa no se tiene en cuenta el costo de regresar a la ciudad de partida, porque todavía no representan una solución completa.

Cuando termina la primera etapa, se calculan los parámetros para la segunda según expresión 2.2, luego cada hormiga es posicionada de forma aleatoria en uno de los ns mejores subrecorridos encontrados en la primera etapa, es bueno aclarar que, en este momento, las hormigas no comienzan su búsqueda a partir de una ciudad, sino de un subrecorrido. Luego el proceso continúa con la

Capítulo 2

36

aplicación del algoritmo ACS, nótese que en la evaluación de las soluciones encontradas en esta etapa, si se tiene en cuenta el costo de regresar a la ciudad de partida, ya que estas constituyen una solución general del TSP.







Cargar matriz de distancia d(i, j)

2. Primera Etapa

Calcular dimensión según expresión 2.1

3. Repetir nc1 veces

Para cada hormiga de m1

Elegir ciudad origen

Repetir para cada hormiga hasta llenar su lista tabúk, su dimensión es nn1


(1.5) y (1.6)


Insertar ciudad seleccionada en tabúk Actualizar feromonas paso a paso según ecuación (1.7)



Calcular costo de su solución (Lk) sin regresar a la ciudad de

partida

Actualizar EI con las cs mejores soluciones de esta etapa.

Actualización global de los rastros de feromona de la mejor

solución del conjunto EI según ecuación (1.8) y (1.9)

4. Segunda etapa




Elegir subtour de origen, uno de los elementos de EI

Repetir para cada hormiga hasta llenar su lista tabúk


(1.5) y (1.6)


Insertar ciudad seleccionada en tabúk

Capítulo 2

37

Actualizar feromonas paso a paso según ecuación (1.7)



Calcular costo de su solución (Lk)y de regresar a la ciudad de

partida

Si (Lk < Lglobal)


Actualización global de las feromonas según ecuación (1.8) y (1.9)

6. Imprimir camino más corto Lglobal

2.2.3 Efecto de la Búsqueda Local en ACS y TS-ACS aplicados al TSP

Al aplicarle el algoritmo ACS al TSP, las hormigas de la colonia encuentran soluciones factibles al TSP, que son utilizadas como punto de partida para el operador de búsqueda local 2-opt. Este operador modifica cada solución haciendo intercambios en el orden en que fueron visitadas las ciudades, mejorando en algunos casos las soluciones originales. Después que este proceso termina son evaluadas cada una de las soluciones para actualizar la mejor solución alcanzada hasta el momento (mejor solución global). Luego se pasa a la evaporación y actualización de los rastros de feromona pertenecientes a la mejor solución global según expresiones 1.8 y 1.9, este proceso se repite hasta que se detiene el algoritmo ACS.

En el caso de incorporar la búsqueda local 2-opt al algoritmo TS-ACS se puede hacer en dos momentos del modelo:

– En la primera etapa: con el objetivo de mejorar los subcaminos para obtener mejores estados iniciales para la segunda etapa, aunque el costo computacional se eleva un poco, no es tan alentador porque las subsoluciones no son de gran longitud.

– En la segunda etapa: como las soluciones de esta etapa representan una solución del TSP, el hecho de aplicarles la búsqueda local, trae consigo que se puedan encontrar buenas vecindades con costo menor que el alcanzando por las hormigas y con esto una mejor solución global, para este caso, el costo computacional es mucho mayor que el de la variante anterior, pues las longitudes de las soluciones de esta etapa son mayores que en la primera.

Como se pudo apreciar, los algoritmos de búsqueda local, al ligarlos con los algoritmos de la meta-heurística ACO y con el nuevo modelo, sólo se emplean para mejorar las soluciones alcanzadas por las hormigas, es bueno aclarar, que este proceso trae consigo que el costo computacional se eleve, pero este a veces es el precio que hay que pagar por obtener buenas soluciones, por lo que es muy común en las publicaciones actuales encontrarse modelos híbridos entre algoritmos heurísticos y de búsqueda local, en aras de un mejor desempeño.

Capítulo 2

38

2.3 Aplicación de los algoritmos AS y TS-AS al JSSP

Según estudios realizados en [81], el AS es el algoritmo de la meta-heurística ACO que mejores resultados ha alcanzado en la solución del JSSP, por lo que también utilizaremos este algoritmo con la nueva estrategia de búsqueda para resolver este problema.

Una instancia de este problema se puede representar mediante un grafo mixto G = (V, A ∪E) [82]. Cada nodo del conjunto V representa una operación, por ejemplo, el nodo 1 representa la primera operación del trabajo 1, el segundo nodo la segunda operación del primer trabajo y así sucesivamente. En general, el nodo i representa la ( i mod (m+1)) operación del trabajo ( i div (m+1))+1. Cada arco del conjunto A representa una restricción de precedencia (arcos dirigidos) y los arcos del conjunto E representan las restricciones de capacidad (arcos no dirigidos), véase figura 2.3.

Para este problema, al igual que el anterior, es importante el orden en que son procesadas las operaciones en las máquinas, por lo que se trata de un problema clásico de secuenciación, para el cual la feromona es representada como una matriz, esta se inicializa siguiendo algún criterio de los mencionados en el capítulo anterior, para ser más claro, se puede decir que la feromona está asociada a los arcos del grafo representativo.

Una solución para este problema es una secuencia de operaciones ejemplo: A: 1-2-3-5-6-7-4-8, B: 5-6-7-1-2-8-3-4, C: 1-2-5-6-3-4-7-8 y un Scheduling activo para la solución B es construido iterativamente en las tablas siguientes, auxiliarse de la tabla 1.1 de datos.

B:5, este nodo representa la primera operación del trabajo 2 que se ejecutará en la máquina 1

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2

M2

M3

M4

Figura 2.3 Una representación gráfica para 2 tareas y 4 máquinas, de la instancia del problema mostrada en la Tabla 1.1

Capítulo 2

39

B:5-6, el nodo 6 representa la segunda operación del trabajo 2 que se ejecutará en la máquina 4

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2

M2

M3

M4 J2

B:5-6-7, el nodo 7 representa la tercera operación del trabajo 2 que se ejecutará en la máquina 3

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2

M2

M3 J2

M4 J2

B:5-6-7-1, el nodo 1 representa la primera operación del trabajo 1 que se ejecutará en la máquina 2, en este caso, esta operación puede ser procesada paralelamente con la primera operación del trabajo 2 ya que esa máquina está ociosa.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2

M2 J1

M3 J2

M4 J2

B:5-6-7-1-2, el nodo 2 representa la segunda operación del trabajo 1 que se ejecutará en la máquina 1, en este caso, esta operación será ejecutada cuando termine la operación del trabajo 2 y después que termine la del trabajo 1 en la máquina 2.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2 J1

M2 J1

M3 J2

M4 J2

B:5-6-7-1-2-8, el nodo 8 representa la cuarta operación que se ejecutará en la máquina 2, esta operación no puede ejecutarse cuando termine la primera operación del trabajo 1 en la máquina 2, pues se estaría violando las restricciones de orden, ya que esta operación tiene que ser ejecutada después de la última operación del trabajo 2 que ya fue procesada.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2 J1

M2 J1 J2

Capítulo 2

40

M3 J2

M4 J2

B:5-6-7-1-2-8-3, el nodo 3 representa la tercera operación del trabajo 1 que se ejecutará en la máquina 4, para este caso, esta operación comienza después que termine de procesarse en la máquina 4 la operación del trabajo 2.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2 J1

M2 J1 J2

M3 J2

M4 J2 J1

B:5-6-7-1-2-8-3-4, el nodo 4 representa la cuarta operación del trabajo 1 que se ejecutará en la máquina 3, en este caso esta operación será procesada después que termine la operación de su mismo trabajo que se está ejecutando en la máquina 4, porque si comienza cuando termine la operación del trabajo 2 que se está ejecutando en su máquina, se violarían las restricciones de orden ya que la operación anterior de su mismo trabajo no ha terminado. Este sería el makespan activo de solución.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

M1 J2 J1

M2 J1 J2

M3 J2 J1

M4 J2 J1

Tabla 2.1 Makespan activo a partir de la solución B

2.3.1 AS aplicado al JSSP

El proceso de aplicar el algoritmo AS a una instancia del problema JSS comienza posicionando cada hormiga de la colonia de forma aleatoria en una operación de partida, este nodo inicial es escogido del conjunto de las primeras operaciones de cada trabajo nodos 1 y 5 para la figura 2.3. Después, cada hormiga comienza a moverse por los nodos del grafo según expresión 1.4, para este problema la función heurística ( ijη =1/ pj ), donde pj es el tiempo de procesamiento de operación que

representa el nodo j y la vecindad del nodo i (Ni) es el conjunto de las operaciones que no han sido procesadas aún y que cumplen con las restricciones de orden en el nodo i, las operaciones elegidas por cada hormiga se introducen en su lista tabú. Este proceso se repite hasta que cada hormiga haya recorrido todos los nodos del grafo o en otras palabras, se hayan ejecutado todas las operaciones de todos los trabajos, luego los valores de feromona son evaporados una vez, según expresión 1.2 y seguidamente, para la soluciones de cada hormiga, se realiza el incremento de los rastros de

Capítulo 2

41

feromona según la expresión 1.3 que está en dependencia de la calidad de la solución activa encontrada. El algoritmo va a funcionar hasta que se cumpla con alguna condición de parada de las explicadas anteriormente.






Inicializar matriz de feromona t(i, j) = t0

Cargar matriz de orden m1(i, j)

Cargar matriz de tiempo m2(i, j)

2. Repetir NC veces

Para cada hormiga

Elegir operación de origen

Repetir para cada hormiga hasta llenar su lista tabu Elegir próxima operación a ejecutarse según ecuación (1.4)

Mover la hormiga a la próxima operación

Insertar operación seleccionada en tabúk

Evaporar los rastros de feromona según (1.2)


Calcular planificación activa de su solución (Lk)

Incrementar los valores de feromona asociados a Lk según (1.3)

Si (Lk < Lglobal)


3. Imprimir mejor planificación activa Lglobal

2.3.2 TS-AS aplicado al JSSP

Para resolver el JSSP mediante el nuevo modelo, se calcula la dimensión de la primera etapa según expresión 2.1, el proceso continúa aplicándole el algoritmo AS explicado en el epígrafe anterior, con la diferencia de que para este caso la condición de parada de cada hormiga es que haya encontrado un subscheduling de longitud nn1, calculado en la expresión 2.1, luego para cada subsolución se construyen la planificación activa y las ns mejores servirán de punto de partida para la segunda etapa.

La segunda etapa comienza calculando su dimensión según expresión 2.2, seguidamente, cada hormiga de esta etapa es posicionada en un subscheduling de partida escogido al azar dentro de las mejores subsoluciones almacenadas en ns, luego se aplica el algoritmo AS antes descrito y en este

Capítulo 2

42

caso las soluciones encontradas por las hormigas de esta etapa si constituyen soluciones a la instancia del JSSP seleccionada.





Inicializar solución global globalL


Cargar matriz de orden Ma1(i, j)

Cargar matriz de tiempo Ma2(i, j)

2. Primera Etapa




Elegir operación de origen

Repetir para cada hormiga hasta llenar tabúk de cada hormiga, su dimensión es nn1

Elegir próxima operación a ser ejecutada según (1.4)

Mover la hormiga a la próxima operación

Insertar nodo seleccionado en tabúk Evaporar los rastros de feromona según (1.2)


Calcular subplanificación activa de la solución (Lk)

Depositar cantidad de feromona adicional en los arcos de (Lk)

según (1.3)

Actualizar EI con las cs mejores soluciones de esta etapa.

4. Segunda etapa



Para cada hormiga

Elegir subplanificación de origen, uno de los elementos de EI

Repetir para cada hormiga hasta llenar tabúk de cada hormiga Elegir próxima operación a ejecutar según ecuación (1.4)

Mover la hormiga a la operación seleccionada

Insertar operación seleccionada en tabúk Evaporar los rastros de feromona según (1.2)


Calcular planificación activa de su solución (Lk)

Actualizar los valores de feromona asociados a (Lk) según (1.3)

Capítulo 2

43

Si (Lk < Lglobal)


6. Imprimir mejor Scheduling activo encontrado Lglobal

2.4 Aplicación de los algoritmos AS y TS-AS al SCP

Una instancia de este problema puede ser representada como un grafo G = (V, A) donde cada vértice de V representa un elemento H y cada arista de A la precedencia de los nodos, ver figura 2.4.

Figura 2.4 Grafo generado por la instancia de la figura 1.3

Una solución para este problema no consiste en recorrer todos los nodos del grafo, sino en obtener un subrecorrido donde se cubran todos los elementos de S, un ejemplo de posibles soluciones:

A:1; 2; 3; 4 con un costo de 28+34+15+70 =147, B:9; 2; 1 con costo de 44+34+28=106, que para este ejemplo es el cubrimiento óptimo.

Para este problema no es necesario constar con una matriz de feromona como en los ejemplos anteriores, ya que el orden en que serán cubiertos los elementos de S no interesa, en otras palabras, no es un problema de secuenciación, por lo que tenemos un vector de feromona donde cada elemento del vector nos informa lo deseado que ha sido la elección del elemento Hi que lo representa, es decir, la feromona está asociada a los nodos del grafo, este vector se inicializa según algún criterio antes mencionado.

2.4.1 AS aplicado al SCP

El proceso comienza posicionando cada una de las hormigas de la colonia en un elemento de H de forma aleatoria, después cada hormiga comienza a moverse por el grafo según expresión 1.4, para

Capítulo 2

44

este problema la función heurística tomada de [83] es: ijη =ce/ cj ,donde ce representa la cantidad de

elementos de S que son cubiertos por Hj y que no han sido cubiertos hasta el momento y cj es el costo del cubrimiento de Hj y la vecindad (Ni) representa todos los elementos de H que no han sido elegidos, en otras palabras, todos los nodos por los que no se ha pasado. Nótese que pueden existir nodos para los que ijη =0, este el caso de los elementos de H que no han sido visitado, pero no

cubren ninguno de los elementos de S que no han sido cubiertos hasta el momento, para este caso ce=0. Luego el nodo seleccionado es introducido en la lista tabú de la hormiga, este proceso se repita hasta que se haya realizado un cubierto del conjunto S.

Posteriormente los valores de feromona son evaporados una sola vez según expresión 1.2 y seguidamente el proceso continúa incrementando los valores de feromona en los nodos de la solución alcanzada por cada hormiga en dependencia de la calidad de su solución. Este proceso se repite hasta que se cumpla alguna condición de parada mencionada anteriormente.





Inicializar solución global 0=globalL

Inicializar vector de feromona t(j) = t0

Cargar vector de costo Cj

Cargar matriz del cubrimiento m(i, j)

2. Repetir NC veces

Para cada hormiga

Elegir columna de origen

Repetir hasta que cada hormiga tenga un cubrimiento

Para cada hormiga:

Elegir próxima columna para el cubrimiento según ecuación (1.4)

Mover la hormiga a la próxima columna

Insertar columna seleccionada en tabuk Evaporar los rastros de feromona según (1.2)


Calcular costo del cubrimiento de su solución (Lk)

Incrementar los valores de feromona asociados a Lk según (1.3)

Si (Lk < Lglobal)


3. Imprimir mejor cubrimiento Lglobal

Capítulo 2

45

2.4.2 TS-AS al SCP

Al aplicar el nuevo modelo al problema SCP, al igual que en los otros problemas a los que se les ha dado solución en este capítulo, se comienza calculando la dimensión de la primera etapa según expresión 2.1, donde para este problema nn representa el cardinal de S, en otras palabras, las dimensiones de los subcubrimientos de la primera etapa no son más que una parte del conjunto que tiene que ser cubierto, luego se aplica el algoritmo AS explicado anteriormente. Cuando la primera etapa concluye se escogen los ns mejores subcubrimientos para que sirvan de estado inicial en el proceso de búsqueda de la segunda etapa.

La segunda etapa comienza calculando su dimensión según expresión 2.2; luego, cada hormiga de esta etapa escoge aleatoriamente su subcubrimiento inicial de los almacenados en ns, se continúa con la ejecución del algoritmo AS, es bueno aclarar que las soluciones encontradas en esta etapa si representan un cubrimiento completo.





Inicializar solución global 0=globalL

Inicializar vector de feromona t(j) = 0t

Cargar vector de costo Cj

Cargar matriz del cubrimiento m(i, j)

2. Primera Etapa




Elegir columna de origen

Repetir hasta obtener un subcubrimiento de longitud nn1

Para cada hormiga:

Elegir próxima columna para el cubrimiento según (1.4)

Mover la hormiga a la próxima columna

Insertar columna seleccionada en tabúk Evaporar los rastros de feromona según (1.2)


Calcular subcubrimiento de su solución (Lk)

Depositar cantidad de feromona adicional en los arcos de (Lk)

según (1.3)

Actualizar EI con las cs mejores subcubrimientos de esta etapa.

4. Segunda etapa

Capítulo 2

46



Para cada hormiga

Elegir subcubrimiento de origen, uno de los elementos de EI

Repetir hasta conseguir un cubrimiento total de cada hormiga

Para cada hormiga:

Elegir próxima columna para el cubrimiento según ecuación

(1.4)

Mover la hormiga a la columna seleccionada

Insertar columna seleccionada en tabúk Evaporar los rastros de feromona según (1.2)


Calcular cubrimiento de su solución (Lk)

Actualizar los valores de feromona asociados a (Lk) según (1.3)

Si (Lk < Lglobal)


6. Imprimir mejor cubrimiento Lglobal

2.5 Conclusiones parciales

El nuevo modelo TS-ACO introducido en este capítulo propone una mejor estrategia de exploración del espacio de búsqueda que la presentada por ACO, se basa fundamentalmente en hacer una división en la exploración y en el espacio de búsqueda en dos etapas, de forma tal que las soluciones parciales (que corresponden a estados intermedios del problema completo) encontradas en la primera etapa sirven como estados iniciales para la segunda etapa, de esta forma se genera el acercamiento del estado inicial al estado final u objetivo, la dimensión del acercamiento está en dependencia de un factor r (radio) introducido al modelo, otro elemento adicionado al modelo es la variable ns, la cual nos brinda el porciento de soluciones de la primera etapa que servirán como punto de partida en la segunda etapa. Los parámetros que influyen en el costo computacional de la búsqueda realizada por las hormigas (cantidad de hormigas y número de ciclos) se dividen de acuerdo al valor del radio, con lo cual el costo de la búsqueda en ambas etapas se reduce y la suma del costo es menor o igual al costo de una búsqueda completa como se muestra en el Capítulo 3.

Nótese que esta estrategia es aplicable a cualquier algoritmo de la meta-heurística ACO, además es muy flexible si se desea trabajar mezclando algoritmos de dicha meta-heurística, o si se desea trabajar con el mismo algoritmo pero con parámetros diferentes para lograr comportamientos distintos en cada etapa.

Capítulo 3

47

Capítulo 3 Prueba experimental y análisis de los resultados En los últimos años ha existido un creciente interés por el análisis de experimentos en el ámbito de las meta-heurísticas. Este análisis debería evitar una serie de problemas/decisiones que podrían invalidar las conclusiones del estudio. El trabajo de Hooker es pionero en esta línea y muestra un interesante estudio de lo que debemos hacer y no hacer cuando nos planteamos el análisis del comportamiento de una metaheurística sobre un problema [84].

En cuanto al diseño de experimentos, podemos encontrar dos tipos de trabajos, el estudio y diseño de problemas de test y el análisis estadístico de experimentos.

• Diferentes autores han centrado su interés en el diseño de problemas de test que sean adecuados para realizar un estudio comparativo entre algoritmos, como el caso de Whitley y coautores en [85] para el diseño de funciones de test complejas para optimización continua, así como los bancos de instancias de los problemas (TSP, JSSP, SCP) presentados en Or-Library [35].

• Centrados en el análisis estadístico de los resultados, si analizamos los trabajos publicados en revistas especializadas, nos encontramos que la mayoría de los artículos realizan una comparación de resultados basada en el valor medio de un conjunto de ejecuciones sobre un caso concreto. En proporción, pocos trabajos utilizan técnicas estadísticas para comparar los resultados aunque recientemente aumenta su uso y está siendo planteado por parte de muchos revisores. Cuando encontramos estudios estadísticos estos suelen estar basados en la media y la varianza utilizando test paramétricos (ANOVA, t-test, etc).

Para comprobar el comportamiento del nuevo modelo se trazaron dos vías de comparación:

– Costo computacional (tiempo de ejecución): se ejecutaron los dos modelos con los mismos valores de los parámetros que definen el tamaño de la exploración, para observar si el nuevo modelo era capaz de reducir el tiempo de ejecución, conservando la calidad de las soluciones encontradas por el modelo ACO, véanse tablas 3.1 a la 3.4.

– Convergencia: para esta prueba se fijó un tiempo límite de ejecución para los dos algoritmos y se comparó la calidad de las soluciones encontradas en ese tiempo, estos fueron ejecutados con la misma cantidad de hormigas, es bueno aclarar que para este caso no se trabajó con un número de ciclos como condición de parada, sino con el tiempo fijado, esta prueba se realizó al SCP, véase tabla 3.5.

Capítulo 3

48

3.1 Resultados Experimentales

Todos los resultados experimentales obtenidos en este epígrafe fueron desarrollados en una P4 Intel a 2.6 GHz de velocidad, 512 MB de RAM con sistema operativo Linux, la implementación de tales algoritmos se realizó en el lenguaje Java, para lo cual se utilizó el Eclipse como entorno de desarrollo, en todos los casos se realizaron 10 corridas de cada algoritmo.

La tabla 3.1 muestra los resultados alcanzados por los algoritmos ACS y TS-ACS aplicados al TSP, para ambos, los valores de p,φ=0.1, la cantidad de hormigas m=10 y la cantidad de ciclos nc=1000. Los valores β=3 y q0=0.9, se presentan como los mejores valores a partir de estudios realizados y expuestos en el anexo 1, en el estudio se analizaron distintos valores a tomar por los parámetros q0=0.3, 0.6, 0.9 y β=1, 3, 5 para comprobar la influencia de estos en la solución del problema, además de la relación entre ellos. Para todas las pruebas se hizo uso de la variable α=1 en la ecuación (1.5). Con estos resultados se llegó a la conclusión de que los valores a tomar por estos parámetros guardan cierta relación, pues para q0=0.9 los mejores resultados se encuentran para β=3 y para q0=0.3 sería entonces β=5, para todos los casos. Así que a medida que se va aumentando el nivel de explotación del problema se le debe ir dando menor peso en la decisión de movimiento a la feromona, para obtener buenas soluciones.

La columna instancia de la tabla 3.1 representa las bases de datos escogidas de [14], la estructura de los ficheros es como en la figura 1.1, la columna “MS” representa la mejor solución reportada internacionalmente hasta el momento y en algunos casos la solución optima, “ACS” es la mejor solución alcanzada por el algoritmo ACS, “TS-ACS” la mejor solución lograda por el nuevo modelo TS-ACS y el valor del factor r con el cual se alcanzó (se probaron distintos valores de r=0.2, 0.25, 0.3, 0.35, 0.4, 0.5), las columnas “Tiempo” constituyen los tiempos empleados por cada uno de los algoritmos respectivamente.

Instancia MS ACS Tiempo TS-ACS Tiempo

bays29.tsp 2020 2033 1026 2022(0.2) 588

berlin52.tsp 7542 7590 3801 7550(0.2) 1980

st70.tsp 675 722 7632 738(0.25) 4344

rd100.tsp 7910 8386 18140 8351(0.2) 9032

ch150.tsp 6528 6604 54001 6590(0.25) 21391

Capítulo 3

49

kroA200.tsp 29368 31362 112982 29658(0.2) 64829

tsp225.tsp 3919 4285 148351 4295(0.25) 74109

a280.tsp 2579 2604 271179 2593(0.2) 166810

lin318.tsp 42029 43500 398572 43028(0.3) 173437

pcb442.tsp 50778 53465 973212 52303(0.25) 468578

rat783.tsp 8806 8895 5081400 8834(r=0.3) 2460528

Tabla 3.1 Resultados experimentales del los métodos ACS y TS-ACS para el TSP

Los resultados del efecto del operador 2-opt de búsqueda local se muestran en las tablas 3.2 y 3.3, en la primera, en relación con la calidad de las soluciones encontradas y en la segunda con respecto al costo computacional, para todos los casos se trabajó con los mismos parámetros del experimento anterior, la columna “ACS-2opt” muestra los resultados alcanzados por el algoritmo ACS unido al operador 2-opt, “TS-ACS-2opt 1ra etapa” muestra los resultados de aplicar el operador de búsqueda local en la primera etapa del algoritmo TS-ACS y “TS-ACS-2opt 2da etapa” los resultados de TS-ACS más la búsqueda local en la segunda etapa.

Instancia MS ACS-2opt TS-ACS-2opt 1ra etapa

TS-ACS-2opt 2da etapa

bays29.tsp 2020 2028 2045 (0.2) 2020 (0.2)

berlin52.tsp 7542 7564 7563 (0.25) 7542 (0.25)

st70.tsp 675 719 730 (0.25) 722 (0.25)

rd100.tsp 7910 8345 8358 (0.3) 8159 (0.2)

ch150.tsp 6528 6573 6696 (0.3) 6570 (0.2)

kroA200.tsp 29368 31298 31889 (0.2) 29470(0.25)

tsp225.tsp 3919 4115 4204 (0.25) 4102 (0.2)

Capítulo 3

50

a280.tsp 2579 2604 2644 (0.25) 2618 (0.25)

lin318.tsp 42029 43006 43503 (0.3) 42086 (0.2)

pcb442.tsp 50778 52861 53369 (0.3) 51790 (0.2)

rat783.tsp 8806 8855 8904(0.25) 8815(0.3)

Tabla 3.2 Efecto del 2-opt con los algoritmos ACS y TS-ACS para el TSP

La tabla 3.3 muestra el tiempo empleado por los algoritmos para obtener los resultados de la tabla anterior, este tiempo está ilustrado en milisegundos.

Instancia ACS-2opt TS-ACS-2opt

1ra etapa

TS-ACS-2opt

2da etapa

bays29.tsp 1231 606 651

berlin52.tsp 3937 1719 1734

st70.tsp 7851 3609 3687

rd100.tsp 18721 12492 14202

ch150.tsp 57803 21984 31874

kroA200.tsp 123852 66781 74873

tsp225.tsp 155151 76120 78677

a280.tsp 295464 135987 146898

lin318.tsp 430637 172492 190220

pcb442.tsp 1040741 425612 478066

rat783.tsp 5315734 2490555 2983343

Tabla 3.3 Comparación en cuanto a tiempo de ejecución del efecto de la búsqueda local al TSP

Capítulo 3

51

La tabla 3.4 muestra un estudio comparativo entre los algoritmos AS y TS-AS al problema JSS, los valores de los parámetros fueron: α=0.8, β=0.17, p=0.1, extraídos de un estudio realizado en [81], la cantidad de hormigas m=número de operaciones de la instancia y la cantidad de ciclos nc=3000, las instancias mostradas en la columna “Instancia” fueron tomadas de una base internacional OR-Library [86, 35], la estructura de estos ficheros es la siguiente:

Información sobre el creador de la instancia y otros elementos

Cantidad de trabajos, cantidad de máquinas

Matriz de datos, donde las filas representan trabajos y los elementos de las columnas (máquina duración).Ver figura 3.1

Figura 3.1 Estructura de la instancia la01 del JSSP

“MS” la mejor solución reportada hasta el momento, “AS” la mejor solución obtenida por al algoritmo AS, “TS-AS” la mejor solución encontrada por el algoritmo TS-AS y las columnas “Tiempo” representan el tiempo que se demoró el algoritmo representado a su izquierda, este tiempo se midió en milisegundos.

Instancia MS AS Tiempo TS-AS Tiempo

la01 666 666 157502 666(r=0.3) 53513

la02 660 673 144697 672(r=0.2) 74518

la03 597 627 144107 607(r=0.25) 60210

la04 590 611 144455 594(r=0.3) 53044

Capítulo 3

52

la05 593 593 144531 593(r=0.25) 61224

la06 926 926 510077 926(r=0.3) 180915

la07 890 897 509708 890(r=0.25) 224793

la08 863 868 508714 865(r=0.25) 216916

la09 951 951 510802 951(r=0.3) 186744

la10 958 958 508825 958(r=0.25) 178458

la11 1222 1222 1276036 1222(r=0.3) 460834

la12 1039 1039 1269386 1039(r=0.3) 450302

la13 1150 1150 1268055 1150(r=0.3) 462080

la14 1292 1292 1288142 1292(r=0.3) 456755

la15 1207 1251 1271330 1247(r=0.25) 553566

la16 945 978 930177 978(r=0.3) 353844

la17 784 797 927918 800(r=0.2) 510641

la18 848 901 938328 868(r=0.2) 480469

la19 842 892 928723 871(r=0.3) 414511

la20 902 955 933017 936(r=0.3) 354534

Tabla 3.4 Resultados comparativos de los algoritmos AS y TS-AS al JSSP

La tabla 3.5 muestra a continuación los resultados obtenidos al aplicarle los algoritmos AS y TS-AS a las instancias representadas en la columna “Instancia”, las columnas “MS” contienen los mejores resultados obtenidos, en el caso de la primera columna con dicha marca, representa la mejor solución reportada internacionalmente. Las columnas “Filas” y “Columnas” la cantidad de filas y columnas que presentan las instancias, la columna “Tiempo” el tiempo en milisegundos fijado para

Capítulo 3

53

las pruebas de convergencia y las columnas “P” el costo promedio de las 10 corridas para cada instancia. La estructura de un fichero de instancia es la siguiente:

Número de filas (m), Número de columnas (n)

Matriz de datos con el siguiente formato por fila:

Costo de cada columna C (j), j = 1…n, Cantidad de filas que cubre la columna i, Lista de las filas que cubre. Ver figura 3.2

Figure 3.2 Instancia de ejemplo del SCP

Los parámetros usados en los algoritmos fueron obtenidos luego de muchos y largos procesos de pruebas y observaciones, además del estudio bibliográfico desarrollado en [83] finalmente resultaron: nivel de feromona inicial = 0.4, constante de evaporación = 0.1, cantidad de hormigas = 100, para el caso del algoritmo AS en II Etapas el factor de proporcionalidad r = 0.2 fue el que brindó mejores resultados (se probaron además otros valores como 0.25 y 0.3) y el otro parámetro se especifica en la tabla, es el caso del tiempo de ejecución de los algoritmos (que depende de la base de datos). En el caso de alfa (α ) y beta ( β ) se usaron distintos valores en dependencia del tipo de

base de datos también. Para el caso de los ficheros correspondientes a SCP los valores tomados fueron: alfa (α )= 1, beta (β )= 2. En las pruebas efectuadas con las bases de datos de tipo SPP

fueron: alfa (α )= 2, beta (β )= 3. Resulta que los modelos representados en estos ficheros de tipo

SPP tienen muy pocas filas a cubrir como se muestra en la tabla 3.5, luego un conjunto pequeño de columnas ya completaban la solución, y se hizo necesario potenciar más la información tanto heurística como memorística para que la convergencia fuera más rápida, ya que una sola columna de mala calidad que se incluyera en la solución elevaba enormemente el resultado final.

Capítulo 3

54

Instancia Filas Columnas MS Tiempo AS TS-AS

MS P MS P

Scp41 200 1000 429 42000 484 501 475 490 Scp410 200 1000 514 42000 594 618 588 608.3 Scp42 200 1000 512 42000 615 640.7 607 638.8 Scp48 200 1000 492 42000 578 590.9 551 572.7 Scp51 200 2000 253 42000 305 313.1 299 312.4 Scp61 200 1000 138 42000 163 174.2 160 171.7 Scp62 200 1000 146 42000 184 192.5 180 187.2 Scp63 200 1000 145 42000 163 175.8 162 172.6 Spp39 25 667 10080 5000 12357 14189.7 12831 13950 Spp34 20 899 10488 5000 11628 13114.2 10602 12640.2 Spp26 23 771 6796 5000 8200 9294 8052 8673.6 Spp41 17 197 11307 800 12348 14073.1 11580 13017.2 Spp32 19 294 14877 800 15951 17394.6 15675 17018.7

Tabla 3.5 Resultados experimentales para el problema SCP

3.2 Técnicas estadísticas para el análisis de los resultados

Si se observan los valores que se muestran en las tablas de la 3.1 a la 3.4 del epígrafe anterior, se

puede apreciar a simple vista que los resultados que aporta el nuevo modelo no difieren

significativamente de los resultados obtenidos con el modelo original ACO en cuanto a calidad de

soluciones, pero si se perciben diferencias en cuanto a costo computacional (en tiempo) y en el caso

de la observación de los resultados de la tabla 3.5 se puede pregonar que la nueva estrategia de

búsqueda incorporada al modelo ACO logra converger más rápidamente a buenas soluciones que el

modelo original.

Un análisis a simple vista no sería suficiente para probar lo antes dicho, por lo que se utilizaron

técnicas estadísticas para validar los resultados y no dejarlo solamente a la apreciación, este análisis

se realizó utilizando el paquete estadístico SPSS versión 11.0, a partir de los datos del epígrafe 3.1.

Las técnicas estadísticas utilizadas se justifican mediante estudios sobre el uso de tests no paramétricos.

Capítulo 3

55

Las pruebas paramétricas requieren supuestos acerca de la naturaleza o forma de las poblaciones

involucradas. Las pruebas no paramétricas no requieren estos supuestos. Consecuentemente, las

pruebas no paramétricas de hipótesis son frecuentemente llamadas pruebas de libre distribución.

Aunque el término no paramétrico sugiere que la prueba no está basada en un parámetro, hay

algunas pruebas no paramétricas que dependen de un parámetro tal como la media. Las pruebas no

paramétricas, sin embargo, no requieren una distribución particular, de manera que algunas veces

son referidas como pruebas de libre distribución. Aunque libre distribución es una descripción más

exacta, el término no paramétrico es más comúnmente usado. Además, un estudio realizado sobre el

porqué utilizar pruebas no paramétricas en vez de tests paramétricos para el análisis de los

resultados de problemas combinatorios se presenta en [87] así como una excelente descripción de

las técnicas utilizadas.

Para el análisis estadístico para cada caso se escogió el valor promedio de las 10 corridas de cada base de datos y la prueba utilizada fue el test de Friedman, que sirve para comparar J promedios poblacionales cuando se trabaja con muestras relacionadas. La situación experimental que permite resolver esta prueba es similar a la estudiada a propósito del ANOVA de un factor con medidas repetidas para saber si existen diferencias significativas entre los grupos de muestra y el test Wilcoxon par a par, para en caso de diferencias significativas en los grupos, detectar en cuales muestras están las diferencias. En todos los casos las tablas resumen las dos pruebas, donde la primera columna representa los algoritmos utilizados y la columna “Rangos Medios” muestra el ranking del test de Friedman, la letra de superíndice brinda las diferencias significativas par a par encontradas por el test de Wilcoxon según el orden en el abecedario.

Las tablas 3.6 y 3.7 muestran los análisis estadísticos para las soluciones reportadas en la tabla 3.1 para el TSP, en estos casos, el valor del significativo de Monte Carlo del Test de Friedman fue sig= 0.000, por lo que muestra que existen diferencias significativas entre el conjunto total de muestras.

Rangos Medios

MS 1.00a

TS-ACS(r=0.2) 2.6363b

ACS 3.1818b

TS-ACS(r=0.25) 3.5454bc

TS-ACS(r=0.3) 4.4363c

Tabla 3.6 Estadístico para la calidad de las soluciones de la tabla 3.1

Capítulo 3

56

Las tablas 3.8 y 3.9 muestran los resultados estadísticos desarrollados sobre los resultados expuestos en la tabla 3.4 para el JSSP, para el cual se realizaron las mismas pruebas que para el problema anterior, para este caso el valor de la significación de Friedman tuvo valor sig= 0.000.

Rangos Medios MS 1.50a TS-AS-JSSP(0.2) 2.80b TS-AS-JSSP(0.25) 3.10b AS-JSSP 3.45bc TS-AS-JSSP(0.3) 4.15c

Tabla 3.8 Estadístico para la calidad de las soluciones de la tabla 3.4

Rangos Medios TS-AS-JSSP(0.3) 1.00a TS-AS-JSSP(0.25) 1.40ab TS-AS-JSSP(0.2) 2.10b AS-JSSP 4.00c

Tabla 3.9 Estadístico para el costo computacional de la tabla 3.4

La tabla 3.10 muestra el análisis estadístico desarrollado sobre el estudio realizado para el problema SCP mostrado en la tabla 3.5, en este caso la significación del test de Friedman fue 0.000.

Rangos Medios MS 1.00a TS-AS-SCP 2.00b AS-SCP (0.2) 3.00c

Tabla 3.10 Estadístico sobre el estudio realizado en la tabla 3.5

Rangos Medios TS-ACS(r=0.3) 1.18a TS-ACS(r=0.25) 2.18b TS-ACS(r=0.2) 2.82b ACS 3.82c

Tabla 3.7 Estadístico para el costo computacional de las soluciones de la tabla 3.1

Capítulo 3

57

3.3 Conclusiones parciales El comportamiento de los algoritmos ACO es sensible a los valores de los parámetros del modelo. En el caso del Sistema de Colonias de Hormigas (Ant Colony System), dos de los parámetros de mayor incidencia en los resultados alcanzados son los parámetros q0 y β y el estudio presentado en este capítulo sobre estos parámetros muestra la forma de escoger los valores de estos para obtener buenos resultados, esta deducción no ha sido reportada en ningún estudio obtenido en la búsqueda bibliográfica para esta tesis.

A partir de los estudios estadísticos que validan los resultados experimentales realizados al aplicar este nuevo modelo a diversos problemas de optimización combinatoria (Problema del viajero vendedor, Problema de Scheduling, y Problema de Cubrimiento) se puede concluir que el nuevo enfoque para la estrategia ACO tiene un impacto significativo ya que se presenta de forma más eficiente en el proceso de solución; esto fue valorado usando dos vías de comparación (tiempo de ejecución y convergencia), lo cual se fundamenta en:

– Tiempo de ejecución: como se muestra en las tablas 3.2 y 3.5 el nuevo modelo ACO en dos etapas es capaz de encontrar soluciones con calidad semejante a las reportadas por el modelo original ACO, pero estas soluciones son encontradas en un tiempo que representa entre el 40% y 60% menor que el empleado por ACO, como se sabe, esta disminución está en dependencia del acercamiento, o de lo que es lo mismo, del factor r.

– Convergencia: en la tabla 3.6 se puede apreciar que el nuevo modelo es capaz de obtener buenas soluciones más rápidamente que el modelo ACO, en otras palabras, es capaz de encontrar mejores soluciones que el modelo original en un tiempo límite.

Para el factor r en todos los problemas se estudiaron distintos valores 0.2, 0.25, 0.3, 0.35, 0.4, 0.5 en todos los casos los mejores resultados del modelo se encontraron para los valores entre 0.2, 0.25, 0.3, ver tablas desde 3.2 a la 3.6.

También se probó experimentalmente el efecto de la búsqueda local en el nuevo modelo, contrastando con el efecto de este en el modelo original ACO para el TSP, básicamente se obtuvo que:

– Al aplicar la búsqueda local en la primera etapa del nuevo modelo en aras de mejorar los estados iniciales para el proceso de búsqueda en la segunda etapa, no se presentan mejoras en la calidad de las soluciones, aunque el tiempo empleado por esta variante es mucho menor que el que emplea la segunda posibilidad, ya que la dimensión de las soluciones a refinar es menor, por lo que lleva menos intercambios de componentes en la solución.

– Al mejorar las soluciones de la segunda etapa con la aplicación de la búsqueda local se presentan resultados interesantes como:

Capítulo 3

58

- El tiempo de ejecución al aplicar la búsqueda local en la segunda etapa es mucho menor que el tiempo empleado por el modelo original ACO sin búsqueda local e incluyendo la misma.

- Las soluciones encontradas con la aplicación de la búsqueda local 2-opt a la segunda etapa del nuevo modelo obtiene mejores resultados que los presentados por el modelo original con la búsqueda local. Además de comportarse mucho mejor que el modelo ACO sin búsqueda local.

Conclusiones

59

Conclusiones Como resultado de esta investigación se desarrolló una nueva metodología de trabajo con la meta-heurística ACO, que ofrece a los investigadores y desarrolladores en el campo de la optimización combinatoria una herramienta que brinda un mejor rendimiento de los algoritmos basados en colonias de hormigas en la solución de problemas, cumpliéndose de esta forma el objetivo general planteado, ya que:

– Existe un creciente interés por el uso de los algoritmos bioinspirados para la solución de problemas de optimización, principalmente por el comportamiento de la metaheurística ACO ante problemas combinatorios. Sin embargo los principales trabajos reportados en la literatura sobre ACO están dirigidos a la solución de problemas reales, a la búsqueda de nuevas formas de movimiento de las hormigas y en otras maneras de trabajo con los rastros de feromona, estos elementos han sido la base fundamental en el origen de otros algoritmos incorporados a la metaheurística ACO.

– El análisis crítico sobre el comportamiento de la metaheurística ACO arrojó como deficiencia principal el tiempo que emplea este modelo para la solución de problemas, esta deficiencia se debe a la estrategia de exploración del espacio de búsqueda utilizada por ACO, en la cual un conjunto de hormigas se desplaza una cierta cantidad de ciclos por un grafo buscando soluciones de un tamaño determinado, por lo que la calidad de las soluciones está en dependencia del tamaño de la búsqueda o de lo que es lo mismo, de estos parámetros.

– El diseño de la nueva metodología de trabajo con la metaheurística ACO llamada TS-ACO se basa fundamentalmente en proponer una nueva estrategia de exploración del espacio de búsqueda, la cual se basa en dividir en dos etapas este proceso, de forma tal que en la primera etapa se encuentren soluciones parciales que sirven de estado inicial para las hormigas en la segunda etapa. La cantidad de trabajo a realizar por las hormigas y la cantidad de estas en cada etapa se regula por un factor de proporcionalidad r que permite calcular los valores de algunos de los parámetros del algoritmo para cada etapa.

– La validación del modelo TS-ACO se realizó a partir de estudios experimentales desarrollados a problemas de optimización combinatoria (TSP, JSSP, SCP), donde se comprobó que la estrategia de exploración empleada por el nuevo modelo consigue explorar el espacio de búsqueda de forma más eficiente que el modelo original, probándose estadísticamente que es capaz de reducir el tiempo de ejecución entre el 40% y 60% en dependencia de la dimensión de las etapas, sin presentar diferencias significativas en cuanto a calidad de las soluciones obtenidas, además de converger más rápidamente a buenas soluciones mostradas a partir de

Conclusiones

60

otro enfoque de comparación donde se fijó el tiempo de ejecución y de las soluciones obtenidas por los dos modelos se encontraron diferencias significativas que premian el uso del nuevo modelo para la solución de problemas de optimización combinatoria. De esta forma queda validada la hipótesis de investigación que dio paso a este estudio.

Recomendaciones

61

Recomendaciones El estudio realizado no agota este campo de investigación, de modo que existen diversas alternativas de trabajo científico posterior relacionado con esta problemática, entre las cuales se destacan:

Analizar el efecto de dividir el proceso de búsqueda desarrollado por las hormigas en el modelo ACO en 3 o más etapas.

Estudiar el comportamiento del modelo TS-ACO propuesto en la solución de otros problemas de optimización combinatoria.

Estudiar el comportamiento del enfoque propuesto en otras meta-heurísticas, como la Optimización basada en partículas, en la cual también los parámetros cantidad de partículas y número de ciclos influyen en el costo computacional de la búsqueda.

Anexos

62

Anexo1 Estudio experimental para los parámetros β y q0 Base de dato N Mejor

Solución Valor Valor β Solución ACS

bays29.tsp 29 2020 0.3 1 2595 3 2147 5 2057.66667

0.6 1 2141.66667 3 2102.33333 5 2072.66667

0.9 1 2104.66667 3 2052,66667 5 2103.33333

gr24.tsp 24 1272 0.3 1 1512.333333 3 1325 5 1310.666667

0.6 1 1366 3 1300 5 1319.666667

0.9 1 1301 3 1339 5 1349.333333

rd100.tsp 100 7910 0.3 1 16145.66667 3 9628 5 8765.666667

0.6 1 11588.66667 3 8926 5 8716.666667

0.9 1 9030 3 8850.333333 5 8872.333333

gr120.tsp 120 6942 0.3 1 14259.66667 3 9181.333333 5 8254.333333

0.6 1 10020.33333 3 7946.333333 5 7659.333333

0.9 1 7550.333333 3 7443.666667 5 7501.333333

Anexos

63

st70.tsp 70 675 0.3 1 1286.333333 3 841 5 786.3333333

0.6 1 957.6666667 3 802 5 789

0.9 1 797.6666667 3 786.3333333 5 798

tsp225.tsp 70 3919 0.3 1 9504 3 5221 5 4578

0.6 1 6315.666667 3 4682.666667 5 4417

0.9 1 4574.666667 3 4322 5 4328

Anexos

64

Anexo2 Terminología utilizada en la teoría de grafos Definición 2.1. Un seudografo G=(V,A,f) es una terna, donde:

– V≠∅ es el conjunto de nodos, puntos o vértices. – A es el conjunto de aristas.

– f:A VxV∪u,v; u,v∈V

∀a∈A, si f(a)=(u,v) o f(a)=u,v, se dice la arista a conecta los nodos u y v. Definición 2.2. Un seudografo se denomina sencillo (o simple) si no tiene aristas múltiples.

Definición 2.3. Una arista a se dice lazo o bucle si f(a)=(v,v) o f(a)=v,v.

En dependencia de las características de las aristas, existen diferentes tipos de seudografos: Seudografo dirigido, seudografo no dirigido y seudografo mixto.

Definición 2.4. Un seudografo se dice dirigido u orientado si todas sus aristas son dirigidas.

Definición 2.5. Un seudografo se dice no dirigido o no orientado si todas sus aristas son no dirigidas.

Definición 2.6. Un seudografo se dice mixto si tiene aristas dirigidas y aristas no dirigidas.

Definición 2.7. Llamamos grafo a un seudografo sencillo sin lazos o bucles.

ĺndice

I

Índice Introducción ........................................................................................................................................ 7

Capítulo 1 Problemas de Optimización Combinatoria, meta-heurística ACO y algoritmos de Búsqueda Local. ............................................................................................................................... 12

1.1 Problemas de Optimización Combinatoria .............................................................................. 13

1.1.1 Problema del Viajante de Comercio .................................................................................. 13

1.1.2 Secuenciación de Tareas ................................................................................................... 15

1.1.3 Problema del Cubrimiento de Conjuntos .......................................................................... 18

1.2 Vida artificial y algoritmos de Búsqueda Local ....................................................................... 18

1.2.1 Optimización Basada en Colonias de Hormigas ............................................................... 19

1.2.2 Modo de funcionamiento y estructura genérica de la meta-heurística ACO .................... 20

1.2.3 Algoritmos de la meta-heurística ACO ............................................................................. 23

1.2.4 Búsqueda Local ................................................................................................................. 27

1.3 Conclusiones parciales ............................................................................................................. 29

Capítulo 2 Nuevo modelo ACO en dos etapas para resolver Problemas de Optimización Combinatoria .................................................................................................................................... 30

2.1 Optimización basa en Colonias de Hormigas en dos Etapas ................................................... 30

2.2 Aplicación de los algoritmos ACS y TS-ACS al TSP ............................................................ 33

2.2.1 ACS al TSP ....................................................................................................................... 34

2.2.2 TS-ACS al TSP ................................................................................................................. 35

2.2.3 Efecto de la Búsqueda Local en ACS y TS-ACS al TSP .................................................. 37

2.3 Aplicación de los algoritmos AS y TS-AS al JSSP ................................................................. 38

2.3.1 AS al JSSP ......................................................................................................................... 40

2.3.2 TS-AS al JSSP ................................................................................................................... 41

2.4 Aplicación de los algoritmos AS y TS-AS al SCP .................................................................. 43

2.4.1 AS al SCP .......................................................................................................................... 43

2.4.2 TS-AS al SCP .................................................................................................................... 45

ĺndice

II


Capítulo 3 Prueba experimental y análisis de los resultados ...................................................... 47

3.1 Resultados Experimentales ...................................................................................................... 48

3.2 Técnicas estadísticas para el análisis de los resultados ............................................................ 54


Conclusiones ..................................................................................................................................... 59

Recomendaciones ............................................................................................................................. 61

Referencias Bibliográficas ............................................................... ¡Error! Marcador no definido.

Anexo1 Estudio experimental para los parámetros β y q0 ............................................................ 62

Anexo2 Terminología utilizada en la teoría de grafos .................................................................. 64

Abstract

3

Referencias bibliográficas 1. Johnson, M.R.G.a.D.S., Computers and Intractability: A Guide to the Theory of NP-

Completeness. 1979, San Francisco: H. Freeman and Company.

2. A. Díaz, F.G., H.M. Ghaziri, J.L. Gonzalez, M. Laguna, P. Moscato and Tseng, and F.T., Optimización Heurística y Redes Neuronales. 1996, Madrid: Paraninfo.

3. Glover, F., Future Paths for Integer Programming and Links to Artifical Intelligence. Computers and Operations Research, 1986. 13: p. 533–549.

4. Reeves, C.R., Modern Heuristic Techniques for Combinatorial Problems. 1995, UK: Ed. McGraw-Hill.

5. Kelly, I.H.O.a.J.P., Meta-Heuristics: Theory and Applications. 1996, Boston: Ed. Kluwer Academic.

6. Glover, F., Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, 1977. 8: p. 156-166.

7. S. Kirkpatrick, C.D.G., M.P. Vecchi, Optimization by simulated. annealing. Science, 1983. 220(4598): p. 671-680.

8. Resende, T.F.a., A probabilistic heuristic for a computational difficult set covering problems. Operations research letters, 1989. 8: p. 67–71.

9. Goldberg, D.E., Genetic Algorithms in Search. Optimization and Machine Learning. 1998, University of Alabama: Addison-Wesley Publishing Company.

10. Eberhart, J.K.a.R.C. Particle swarm optimization. in on neural networks. 1995. Piscataway, NJ.

11. Stützle, M.D.a.T., ACO Algorithms for the Traveling Salesman Problem. Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications. 1999, EEUU: John Wiley & Sons.

12. Gambardella, D.M.a.L., Ant Colonies for the Traveling Salesman Problem. BioSystems, 1997. 43: p. 73-81.

13. Karp, R., Reducibility among combinatorial problems. Complexity of Computer Computations. 1972, New York: R. Mille and J. Thatcher.

14. Reinelt, G., TSPLIB - A traveling salesman library. ORSA Journal on Computing, 1991. 3: p. 376-384.

15. Johnson D.S., M.L.A., The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization,. 1997, New York,: New York: Wiley.

16. Bfirdossy, I.K., Jinos Jzsa and Andrfis, Improving Spatial and Temporal Discretisation By Simulated Annealing. 2002.

17. Mxico, H.S.-s.a.C.M., Methodology to Parallelize Simulated Annealing and its Application to the Traveling Salesman Problem. 2002.

Abstract

4

18. McGeoch, J.D.S.y., The traveling salesman problem: a case studyin local optimization. Local Search in Combinatorial Optimization. 1997, New York: New York: Wiley.

19. Michael, A., A New Approach to Evolutionary Computation: Segregative Genetic Algorithms (SEGA). 2004.

20. Jose Ignacio Hidalgo, Raaele Perego, Dpto Arquitectura, Computadores, Gambhava, Dr K. Kotecha and Nilesh, A Parallel Hybrid Heuristic for the Solving Precedence Constraint Traveling Salesman Problem using Genetic Algorithm. 2001.

21. Stützle T., G.A., Linke S. y Rüttger M., A Comparison of Nature Inspired Heuristics on the Traveling Salesman Problem, in The Sixth International Conference on Parallel Problem Solving for Nature (PPSN-VI). 2000: Paris – Francia.

22. Liu, B.L.M.a.J., Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal Production Research, 1993. 31(1): p. 59-79.

23. Sadeh. N., F.M.S., Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 1996. 86: p. 1-41.

24. Hentenryck, H.S.a.M.D., Constraint satisfaction using constraint logic programming. Artificial Intelligence, 1992. 58: p. 113-159.

25. R. Varela, C.R.V., J. Puente and C.L. Alonso, Parallel Logic Programming For Problem Solving. International Journal of Parallel Programming, 2000. 28(3): p. 275-319.

26. Johnston, H.M.A.a.M.D. A discrete stochastic neural network algoritm for constraint satisfaction problems. in International Joint Conference on Neural Networks. 1990. San Diego.

27. M. Zweben, E.D., B. Daun, E. Drascher, M. Deale and M. Eskey, Learning to improve constraint-based scheduling. Artificial Intelligence, 1992. 58: p. 271-296.

28. Bayiz, I.S.a.M., Job shop scheduling with beam search. European Journal of Operational Research, 1999. 118: p. 390-412.

29. Reeves, T.Y.a.C.R. Permutation Flowshop Scheduling by Genetic Local Search. in International Conference on Genetic Algorithms in Engineering Systems 1997. GALESIA.

30. Nowicki, E., The Permutation flow shop with buffers: A tabu search approach. European Journal of Operational Research, 1999. 116: p. 205-219.

31. Kolonko, M., Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, 1999. 113: p. 123-136.

32. Bierwirth, C., A Generalized Permutation Approach to Jobshop Scheduling with Genetic Algorithms. OR Spectrum, 1995. 17: p. 87-92.

33. Pesch, U.D.a.E., Evolution based learning in a job shop scheduling environment. Computers & Operations Research, 1995. 22: p. 25-40.

34. Syswerda, G., Schedule Optimizacion Using Genetic Algorithms, in Handbook of Genetic Algorithms, V.N.R. L. Davis, Editor. 1991: New York. p. 332-349.

Abstract

5

35. Beasley, J.E., Or-library: distributing test problems by electronic mail. Journal of the Operations Research Society, 1990. 41(11): p. 1069-1072.

36. Meeran, A.S.J.a., Deterministic jobshop scheduling: Past, present and future. European Journal of Operational Research, 1999. 113: p. 390-434.

37. Olivier, C., On Solving Covering Problems. 1996.

38. Dortmund, T.B., Martin Schutz, Sami Khuri and Informatik Centrum, A Comparative Study of a Penalty Function, a Repair Heuristic, and Stochastic Operators with the Set-Covering Problem. 1995.

39. Marchiori, E., An Iterated Heuristic Algorithm for the Set Covering Problem. 1998.

40. Jiménez, F. Vida Artificial. 1999 [cited; Available from: http://complex.us.es/~jimenez/CA/ac/node19.html.

41. Liekens, A. Alife Online. 2000 [cited; Available from: http://alife.org/.

42. Paolo, E.D. Artificial Life Bibliography of On-line Publications. 2000 [cited; Available from: http://www.cogs.susx.ac.uk/users/ezequiel/alife-page/alife.html.

43. F. Glover and G. Kochenberger, Handbook of Metaheuristics. 2003: Kluwer Academic Publishers.

44. S. Voss, S.M., I.H. Osman and C. Roucairol, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. 1999, Boston, MA: Kluwer Academic Publishers

45. Bonabeau, E., Swarm Intelligence: From natural to artificial systems. 1999: Oxford University Press.

46. T.Stutzle, M.D.a., Ant Colony Optimization. 2004, MIT Press. p. 303-348.

47. Caro, M.D.a.G.D., The Ant Colony Optimization meta-heuristic, in New Ideas in Optimization, M. Hill, Editor. 1999: London UK. p. 11-32.

48. M. Dorigo, G.D.C., and L. M. Gambardella, Ant algorithms for discrete optimization. Artificial Life, 1999. 5(2): p. 137-172.

49. Gambardella, É.D.T.a.L.M., Adaptative memories for the quadratic assigment problem., in DSIA-97. 1997: Lugano, Switzerland,.

50. L. M. Gambardella, È.D.T., and M. Dorigo, Ant colonies for the quadratic assigment problem. Journal of the Operational Research Society, 1999. 50(2): p. 167-176.

51. Caro, M.D.y.G.D., Ant Colony Optimization meta-heuristic, in New Ideas in Optimization, M.D.y.F.G. D. Corne, editores, Editor. 1999: McGraw Hill, London, UK. p. 11-32.

52. Stützle, M.D.y.T., The ant colony optimization metaheuristic: Algorithms, applications and advances, in Handbook of Metaheuristics, e. F. Glover and G. Kochenberger, Editor. 2003, Kluwer Academic Publishers. p. 251-285.

53. M. Birattari, T.S., L. Paquete, y K. Varrentrapp., A racing algorithm for configuring metaheuristics, in GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, e. W.B. Langdon y otros, Editor. 2002, Morgan Kaufmann Publishers: San Francisco, CA, USA. p. 11-18.

Abstract

6

54. M. Dorigo, V.M., and A. Colorni, The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems Man, and Cybernetics, 1996. 26: p. 29-41.

55. Gambardella, M.D.y.L.M., Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.

56. Hoos, T.S.a.H., MAX-MIN Ant System. Future Generation Computer Systems, 2000. 16(8): p. 889-914.

57. B. Bullnheimer, R.F.H.a.C.S., A new rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics, 1999. 7(1): p. 25-38.

58. O. Cordón, I.F.d.V., F. Herrera, and L. Moreno. new ACO model integrating evolutionary computation concepts: The Best-Worst Ant System. in ANTS 2000. 2000. Université Libre de Bruxelles, Belgium,.

59. Dorigo M., M.V.y.C.A., The Ant System: Optimization by a colony of cooperating agents. EEE Transaction on Systems, Man, and Cybernetics-Part B, USA, 1996. 26(1): p. 1-13.

60. Dorigo, L.G.a.M., HAS-SOP: An Hybrid Ant System for the Sequential Ordering Problem, in Technical Report IDSIA11-97. 1997: Lugano - Suiza.

61. Bullnheimer B., H.R.y.S.C. An improved ant system algorithm for the vehicle routing problem. in Annals of Operations Research. 1999: Nonlinear Economic Dynamics and Control.

62. Colorni, V.M.a.A., The Ant System applied to the Quadratic Assignment Problem, in Transactions on Knowdledge and Data Engineering. 1999, IEEE

Estados Unidos.

63. Dorigo, G.D.C.a.M. Mobile Agents for Adaptive Routing. in Proceedings of the 31st Hawaii International Conference on System. 1998. Hawaii.

64. E. Bonabeau, M.D.a.T.T., From Natural to Artificial Swarm Intelligence. 1999, New York: New York: Oxford University Press.

65. Manno-lugano, L.M.a.G., An Ant Colony System Hybridized with a New Local Search. 2000.

66. Nenad, M.a., A Tutorial on Variable Neighborhood Search. 2003.

67. Matthijs, B., Neighborhoods Revisited: An Experimental Investigation into the Effectiveness of Variable Neighborhood Descent for Scheduling. 2001.

68. Keld, H.a., An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. 2000.

69. Kernighan, S.L.a.B.W., An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations research letters, 1973. 21: p. 498-516.

70. McPeak, D.B., Eugene Ingerman, Joshua Levy and Scott, An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP. 2000.

Abstract

7

71. Chris, W., A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem. 2001.

72. Keuthen, K.E., Burke, I. Peter, Cowling and Ralf, Eective Local and Guided Variable. 2003.

73. Freisleben, P.M.a.B., Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming. 2000.

74. Colin, R.a.R., Landscapes, Operators and Heuristic Search. 1997.

75. CROES, G.A., A method for solving traveling salesman problems. Operations research letters, 1958. 6: p. 791-812.

76. FLOOD, M., The traveling-salesman problem. Operations research letters, 1956. 4: p. 61-75.

77. McGeoch, D.S.J.a.L.A. The traveling salesman problem: a case study in local optimization. in Local Search in Combinatorial Optimization. 1999. New York.

78. Ducatelle, J.L.a.F., Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. 2003.

79. Luigi, V.M.a.L.M.G.a.F.D., Ant Colony Optimization. 2004.

80. Gambardella, M.D.a.L.M., Ant Colonies for the Traveling Salesman Problem. 2002.

81. Mario Ventresca, B.a.M.O. Ant Colony Optimization for Job Shop Scheduling Problem. in MISTA 2004. 2004. Spain.

82. Mattfeld, C.D. Evolutionary Search and the Job Shop. in Investigations on Genetic Algorithms for Production Scheduling. 1995.

83. Castro, B.C.a.C., Ant Colonies using Arc Consistency Techniques for the Set Partitioning Problem. LNAI 2006. 4183: p. 45-55.

84. Hooker, J.H., Testing Heuristics: We Heve it All Wrong. Jornal of Heuristics, 1995. 1(1): p. 33-42.

85. D. Whitley, P.G.a.K.M., New Test function and geometric matching. Jornal of Heuristics, 1995. 1(1): p. 77-104.

86. Taillard, E., Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993. 64: p. 278-285.

87. S. García, D.M., M. Lozano and F. Herrera, Un Estudio Experimental sobre el Uso de Test No Paramétricos para Analizar el Comportamiento de los Algoritmos Evolutivos en Problemas de Optimización, in V Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB 07). 2007, Universidad de La Laguna: Puerto de La Cruz, Tenerife.

Optimización Basada en Colonias de Hormigas en Dos Etapas

Documents

Transcript of Optimización Basada en Colonias de Hormigas en Dos Etapas