Policy Dinamiche per Parametri per il Problema LeadingOnes su Spazi di Stato Estesi

Black-box optimization is a framework for optimizing problems for which a model or function is not explicitly provided or is too complex to be used by direct analytical means. In this context, the use of genetic algorithms is an established way to solve complex real-world problems of different types. A reliable analysis of their performance can be done through the study of the number of evaluations of solution candidates. In recent years, many studies about performance analysis highlighted the role of parameters in evolutionary algorithm's performance, and proposed several solutions to adapt the parameters in order to enhance speed, including the use of reinforcement learning. The limits of this novel approach highlighted the necessity of a deeper understanding of algorithms behavior in new settings. In this thesis, we present an overview of the state of the art in black-box optimization and parameter control, existing theoretical results, and our contributions. We developed and tested a methodology to exploit information from enhanced state spaces in dynamic policies for the specific case of RLS, a randomized local search algorithm with dynamic choice of the search radius. We investigated optimal or close-to-optimal control policies for this algorithm for different scenarios optimizing the LeadingOnes problem. This work offers a foundational example that could inspire broader development of new dynamic parameter policies in enhanced state spaces.

L'ottimizzazione black-box è un framework per l'ottimizzazione di problemi in cui un modello o una funzione non sono esplicitamente forniti oppure sono troppo complessi per essere utilizzati con metodi analitici diretti. In questo contesto, l'uso degli algoritmi genetici rappresenta un approccio consolidato per risolvere problemi reali complessi di varia natura. Un'analisi affidabile delle loro prestazioni può essere condotta studiando il numero di valutazioni di possibili candidati soluzione. Negli ultimi anni, numerosi studi sull'analisi delle prestazioni hanno evidenziato il ruolo cruciale dei parametri nell'efficacia degli algoritmi evolutivi, proponendo diverse strategie per adattarli al fine di migliorare la velocità, tra cui l'uso del reinforcement learning. Tuttavia, i limiti di questo approccio innovativo hanno messo in luce la necessità di una comprensione più approfondita del comportamento degli algoritmi in nuovi contesti. In questa tesi, presentiamo una panoramica dello stato dell'arte nell'ottimizzazione black-box e nel controllo dei parametri, discutendo i risultati teorici esistenti e i nostri contributi. Abbiamo sviluppato e testato una metodologia per sfruttare le informazioni provenienti da spazi di stato estesi nelle policy dinamiche, con particolare riferimento al caso dell'RLS, un algoritmo di ricerca locale randomizzato con scelta dinamica del raggio di ricerca. Abbiamo studiato politicy di controllo dei parametri ottimali o quasi ottimali per questo algoritmo in diversi scenari di ottimizzazione del problema LeadingOnes. Questo lavoro fornisce un esempio fondamentale che potrebbe ispirare un più ampio sviluppo di nuove policy dinamiche per parametri in spazi di stato estesi.