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

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