Un Algoritmo Immunologico Ibrido per Estrarre Informazioni da Reti Complesse

In the field of optimization, interest in hybrid metaheuristics has grown significantly over the last years, obtaining good results not only for classical optimization problems but also for real-life applications. Combinations of algorithms such as metaheuristics, mathematical programming, constraint programming and machine learning techniques have provided very powerful search algorithms. In this thesis work, some contributions are presented to the study and analysis of hybrid metaheuristics to address combinatorial optimization problems on graphs. For many combinatorial optimization problems, there is no prior information about the characteristics of the problem or the properties of the landscape. Consequently, my research has focused on the study and design of a general-purpose framework that combines metaheuristics with local search procedures and/or reinforcement learning to solve combinatorial optimization problems. Two complex problems have been analysed: the Feedback Vertex Set on graphs and the problem of Community Detection on complex networks. The feedback vertex set has been analyzed using a hybrid immunological algorithm, in which the random exploration of the search space is contained by a local search procedure, that tries to exploit the obtained solution with the purpose to solve sub-instances of the original problem. The problem of community detection is a classical clustering problem that arises from complex network analysis. In this case, two approaches have been developed. The first is a fully random search algorithm driven by stochastic operators designed for the problem of community detection. The second approach is guided by a greedy local search procedure, which locally maximizes the objective function. In addition, an in depth analysis has been conducted to investigate how the position of local search can influence the performance of the algorithm, in terms of exploration of the search space and solution quality. Finally, a generic framework for grouping problems has been designed. Generally, a grouping problem aims to group a set of given items into a fixed or variable number of groups while respecting some specific requirements. Typical examples of grouping problems are graph colouring and data clustering. The proposed framework combines a population-based greedy metaheuristic with reinforcement learning techniques. This algorithm aims to exploit a learning component to extract useful information on the problem considered starting from a set of high-quality solutions, to guide the search consciously.

Nel campo dell'ottimizzazione, l'interesse per le metaeuristiche ibride è cresciuto in modo significativo negli ultimi anni, ottenendo buoni risultati non solo per i classici problemi di ottimizzazione, ma anche per applicazioni reali. L'unione di approcci come metaeuristiche, mathematical programming, programmazione con vincoli e tecniche di machine learning hanno fornito algoritmi di ricerca molto potenti. In questo lavoro di tesi, vengono presentati alcuni contributi per lo studio e l'analisi di metaeuristiche ibride per affrontare problemi di ottimizzazione combinatoria sui grafi. Per molti problemi di ottimizzazione combinatoria, non ci sono informazioni preliminari sulle caratteristiche del problema o sulle proprietà dello spazio di ricerca. Di conseguenza, la mia ricerca si è concentrata sullo studio e la progettazione di un framework general-purpose che combina le metaeuristiche con procedure di ricerca locali e/o di reinforcement learning per risolvere problemi di ottimizzazione combinatoria. Sono stati analizzati due problemi complessi: il Feedback Vertex Set sui grafi e il problema della Community Detection su reti complesse. Il Feedback Vertex Set è stato analizzato utilizzando un algoritmo immunologico ibrido, in cui l'esplorazione casuale dello spazio di ricerca è contenuta da una procedura di ricerca locale, che cerca di sfruttare le soluzioni ottenute con lo scopo di risolvere sotto-istanze del problema originale. Il problema del rilevamento di comunità è un classico problema di clustering che deriva dalla Complex Network Analysis. In questo caso, sono stati sviluppati due approcci. Il primo è un algoritmo di ricerca completamente casuale guidato da operatori stocastici progettati per il problema della community detection. Il secondo approccio è guidato da una procedura di ricerca locale greedy, che massimizza localmente la funzione obiettivo. Inoltre, è stata condotta un'analisi approfondita per indagare come la posizione della ricerca locale possa influenzare le prestazioni dell'algoritmo, in termini di esplorazione dello spazio di ricerca e qualità della soluzione. Infine, è stato progettato un framework per i problemi di grouping. In generale, un problema di grouping mira a raggruppare una serie di elementi in un numero fissato o variabile di gruppi, rispettando alcuni requisiti specifici. Esempi tipici di problemi di raggruppamento sono la colorazione dei grafi e il clustering. Il framework proposto combina una metaeuristica basata sulla popolazione greedy con tecniche di reinforcement learning. Questo algoritmo mira a sfruttare una componente di apprendimento per estrarre informazioni utili sul problema considerato a partire da un insieme di soluzioni ad alta qualità, per guidare la ricerca consapevolmente.