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

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