Leveraging machine learning for guiding metaheuristics in combinatorial optimization

L’optimització combinatòria és una branca de l’optimització matemàtica que s’ocupa de problemes l’espai de solucions dels quals és finit, però sovint massa gran per ser explorat exhaustivament. Aquest tipus de problemes apareix en àmbits diversos, com la logística, la bioinformàtica i la planificació. Hi ha dos enfocaments principals per abordar-los: els mètodes exactes, que garanteixen solucions òptimes però no escalen bé, i els mètodes aproximats, que sacrifiquen optimalitat a canvi d’eficiència. Dins dels mètodes aproximats hi trobem el concepte de metaheurístiques, que són marcs generals adaptables a múltiples problemes d’optimització combinatòria. Alguns exemples destacats inclouen l’Optimització per Colònia de Formigues, els Algorismes Genètics i la Cerca Tabú. Recentment, el camp de l’aprenentatge automàtic ha atret una atenció considerable, impulsada pels avenços en computació i nombrosos descobriments. En particular, una aplicació relativament nova i prometedora és la seva integració en algorismes d’optimització combinatòria, especialment en metaheurístiques. En aquest context, l’aprenentatge pot produir-se de manera offline, amb models entrenats abans de l’execució de l’algorisme, o de manera online, amb models que s’actualitzen dinàmicament durant la cerca. Aquesta tesi investiga ambdós paradigmes. En l’àmbit offline, s’introdueix un marc evolutiu per aprendre informació heurística que guiï les metaheurístiques. El marc s’empra en tres escenaris: un algorisme genètic i un algortme beam search aplicats a problemes d’optimització sobre cadenes de caràcters, i l’heurística de Clarke i Wright per a problemes de ruteig de vehicles. En l’àmbit online, es proposen dues noves variants de la metaheurística híbrida Construir, Fusionar, Resoldre, i Adaptar (CMSA). Totes dues integren feedback del solucionador exacte utilitzat en el pas resoldre de CMSA per millorar la construcció de solucions: la primera mitjançant un mecanisme inspirat en l’aprenentatge per reforç, i la segona a través de l’aprenentatge profund, que permet una adaptació més completa durant la cerca.