[ca] 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.

[en] 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.