An Algorithmic Framework for Making Use of Negative Learning in Ant Colony Optimization

Abstract

L'optimització amb colònies de formigues (ACO) és una metaheurística que s'inspira en la naturalesa. ACO explota la capacitat que tenen les formigues per a trobar rutes curtes, entre el formiguer i la font d'aliments, utilitzant dos mecanismes: la construcció de solucions i l'actualització de feromones. Igual que les formigues trien la ruta en funció de la concentració de feromones, l'algorisme ACO fa servir valors de feromones, a més d'informació greedy, per a construir diverses solucions en cada iteració. Posteriorment, l'algorisme fa servir algunes de les millors solucions construïdes per a actualitzar el seu model de feromones com una manera d'emular la dinàmica dels rastres de feromones de les formigues durant la cerca d'aliments. Aquest model de feromones condueix la cerca cap a àrees pròximes a la solució utilitzada per a l'actualització. Per tant, podem dir que aquest algorisme d'optimització utilitza un mecanisme d'\emph{aprenentatge positiu}, com ho fan la majoria de metaheurísticas.

Se sap per experiència que l'aprenentatge negatiu, juntament amb el mecanisme d'aprenentatge positiu, juga un paper vital en el comportament dels eixams d'animals i en l'evolució dins de les espècies i entre espècies, així com en la història humana. Diversos treballs han intentat millorar els algorismes ACO existents integrant mecanismes d'aprenentatge negatiu. No obstant això, la majoria d'aquestes implementacions no han produït cap millora significativa sobre l'algorisme ACO estàndard.

La nostra proposta d'aprenentatge negatiu per a ACO empra diverses característiques no contemplades en implementacions anteriors. El nostre aprenentatge negatiu ACO identifica solucions dolentes (o components d'una solució dolenta) comparant les solucions generades en una iteració ACO amb la solució generada per un component algorítmic addicional. Qualsevol component d'una solució que es trobi en una iteració de ACO però que no sigui present en la solució generada pel component algorítmic addicional es considera un component de solució de baixa qualitat i el seu valor de feromona negatiu s'incrementa. Per tant, és menys probable que aquest component se seleccioni en les iteracions successives. Una altra característica nova és que l'algorisme baseline ACO genera una subinstància que consta dels components comuns trobats en totes les iteracions. Posteriorment, l'algorisme de base passa aquesta subinstància al component algorítmic addicional. Per tant, el component algorítmic considera una instància més petita formada per components que, presumiblement, són d'alta qualitat.

En aquesta tesi, utilitzem amb èxit diversos algorismes d'optimització com a opcions per al component algorítmic addicional en les nostres implementacions ACO amb aprenentatge negatiu i resolem diversos problemes d'optimització (el problema de la motxilla multidimensional, el problema del conjunt dominant mínim, el problema de la màxima satisfactibilitat, el problema del conjunt dominant mínim amb capacitats i el problema del conjunt dominant mínim amb influència positiva). Els resultats experimentals mostren que les nostres variants ACO amb aprenentatge negatiu són millors que l'algorisme ACO de base i els altres algorismes d'optimització utilitzats internament en les nostres variants ACO amb aprenentatge negatiu. Clarament, aquesta és una fita que cap altra implementació d'aprenentatge negatiu ACO ha assolit anteriorment. D'altra banda, comparem les nostres variants amb quatre propostes ACO amb aprenentatge negatiu, representatives de la literatura, per al problema de la motxilla multidimensional i el problema del conjunt dominant mínim. La comparació mostra que, globalment, les nostres variants ACO amb aprenentatge negatiu funcionen significativament millor que aquests competidors. A més, trobem que ACOnegplus---la nostra millor variant ACO amb aprenentatge negatiu en general---sempre és competitiva amb els millors algorismes per a cadascun dels problemes d'optimització considerats. De fet, ACOnegplus és actualment l'algorisme més competitiu per al problema del conjunt dominant mínim amb influència positiva. D'aquesta manera, hem demostrat l'aplicabilitat general i l'efectivitat de la nostra proposta ACO amb aprenentatge negatiu.

La Optimización con colonias de hormigas (ACO) es una metaheurística inspirada en la naturaleza. ACO explota la capacidad que tienen las hormigas para encontrar rutas cortas, entre el hormiguero y la fuente de alimentos, utilizando dos mecanismos: la construcción de soluciones y la actualización de feromonas. Al igual que las hormigas eligen la ruta en función de la concentración de feromonas, el algoritmo ACO utiliza valores de feromonas, además de información greedy, para construir varias soluciones en cada iteración. Posteriormente, el algoritmo usa algunas de las mejores soluciones construidas para actualizar su modelo de feromonas como una forma de emular la dinámica de los rastros de feromonas de las hormigas durante la búsqueda de alimentos. Este modelo de feromonas conduce la búsqueda hacia áreas cercanas a la solución utilizada para la actualización. Por lo tanto, podemos decir que este algoritmo de optimización utiliza un mecanismo de aprendizaje positivo, como lo hacen la mayoría de metaheurísticas.

Se sabe que el aprendizaje negativo, junto con el mecanismo de aprendizaje positivo, juega un papel vital en el comportamiento de los enjambres de animales y en la evolución dentro de las especies y entre especies, así como en la historia humana. Varios trabajos han intentado mejorar los algoritmos ACO existentes integrando mecanismos de aprendizaje negativo. Sin embargo, la mayoría de estas implementaciones no han producido ninguna mejora significativa sobre el algoritmo ACO estándar.

Nuestra propuesta de aprendizaje negativo para ACO emplea varias características no contempladas en implementaciones anteriores. Nuestro aprendizaje negativo ACO identifica soluciones malas (o componentes de una solución mala) comparando las soluciones generadas en una iteración ACO con la solución generada por un componente algorítmico adicional. Cualquier componente de una solución que se encuentre en una iteración de ACO pero que no esté presente en la solución generada por el componente algorítmico adicional se considera un componente de solución de baja calidad y su valor de feromona negativo se incrementa. Por tanto, es menos probable que este componente se seleccione en las iteraciones sucesivas. Otra característica novedosa es que el algoritmo baseline ACO genera una subinstancia que consta de los componentes comunes encontrados en todas las iteraciones. Posteriormente, el algoritmo de base pasa esta subinstancia al componente algorítmico adicional. Por lo tanto, el componente algorítmico considera una instancia más pequeña formada por componentes que, presumiblemente, son de alta calidad.

En esta tesis, utilizamos con éxito varios algoritmos de optimización como opciones para el componente algorítmico adicional en nuestras implementaciones ACO con aprendizaje negativo y resolvemos varios problemas de optimización (problema de la mochila multidimensional, problema del conjunto dominante mínimo, problema de la máxima satisfactibilidad, problema del conjunto dominante mínimo con capacidades, problema del conjunto dominante mínimo con influencia positiva). Los resultados experimentales muestran que nuestras variantes ACO con aprendizaje negativo son mejores que el algoritmo ACO de base y los otros algoritmos de optimización utilizados internamente en nuestras variantes algorítmicas. Claramente, este es un logro que ninguna otra implementación de aprendizaje negativo ACO ha obtenido anteriormente. Por otro lado, comparamos nuestras variantes con cuatro propuestas ACO con aprendizaje negativo, representativas de la literatura, para el problema de la mochila multidimensional y el problema del conjunto dominante mínimo. La comparación muestra que, globalmente, nuestras variantes ACO con aprendizaje negativo funcionan significativamente mejor que estos competidores. Además, encontramos que ACOnegplus---nuestra mejor variante algorítmica---siempre es competitiva con los mejores algoritmos para cada uno de los problemas considerados. De hecho, ACOnegplus es actualmente el algoritmo más competitivo para el problema del conjunto dominante mínimo con influencia positiva. De esta manera, hemos demostrado la aplicabilidad general y la efectividad de nuestra propuesta algorítmica.

Ant Colony Optimization (ACO) is a metaheuristic that took its inspiration from nature. This algorithm imitates the ants' capability in finding short routes between their nest and food sources by using two mechanisms: solution construction and pheromone update. Similar to the real ants that choose their route based on its pheromone concentration, the ACO algorithm makes use of pheromone values, in addition to greedy information, to construct several solutions at each iteration. Subsequently, the algorithm uses some of the good ones of the constructed solutions to update its pheromone model as a way to emulate the dynamics of the pheromone trails during the ants' foraging activities. This pheromone model will bias the search towards areas in the proximity of the solutions used for updating. Hence, we can say that this optimization algorithm uses a positive learning mechanism, as most metaheuristics do.

Observations showed that negative learning, in addition to the positive learning mechanism, also plays a vital role in animal swarm behavior, the species and inter-species evolution, as well as the human history. Several works tried to improve existing ACO algorithms by integrating negative learning mechanisms. However, most of these implementations did not produce any consistent improvement over the standard ACO algorithm.

Our negative learning ACO proposal employs several features not considered in previous implementations. Unlike the previous approaches that identify the negative learning information by a function that searches for worse solutions or simply by choosing the worst solution in an iteration for updating the pheromone values, our negative learning ACO identifies bad solutions (or bad solution components) by comparing the solutions produced in an ACO iteration to the solution generated by an additional algorithmic component. Any solution component found in an ACO iteration but not present in the solution generated by the additional algorithmic component is considered a bad solution component. As a consequence, its negative pheromone value is increased. Consequently, this component will be less likely to be selected in the next iterations. We developed another novel feature to support this negative information identification mechanism. The baseline ACO algorithm generates a sub-instance that consists of solution components found in each of its iterations. Subsequently, the baseline algorithm feeds the sub-instance to the additional algorithmic component. Hence, the algorithmic component works on a problem instance that is smaller in size and consists of presumably high-quality solution components.

We successfully used several optimization algorithms (CPLEX, MAX-MIN Ant System, and the MaxSAT solvers SATlike and SlsMcs) as options for the additional algorithmic component in our negative learning ACO applications to several optimization problems (Multi Dimensional Knapsack Problem, Minimum Dominating Set problem, Maximum Satisfiability problem, Capacitated Minimum Dominating Set problem, and Minimum Positive Influence Dominating Set problem). The results show that our negative learning ACO variants improve consistently over the baseline ACO algorithm and over the other optimization algorithms used internally in our negative learning ACO variants. Clearly, this is an achievement that no other negative learning ACO proposal obtained in their implementations. We also compared them to four representative negative learning ACO proposals from the literature in our application to the Multi Dimensional Knapsack Problem and Minimum Dominating Set problem. The comparison shows that, globally, our negative learning ACO variants perform significantly better than these competitors. Moreover, we found that ACOnegplus---our overall-best negative learning ACO variant---always performs competitively with the state-of-the-art algorithms in each considered optimization problem. In fact, ACOnegplus is currently the state-of-the-art algorithm for the Minimum Positive Influence Dominating Set problem. This way, we proved the general applicability and the effectiveness of our negative learning ACO proposal.