Algoritmo genetico per il problema del set covering

Negli ultimi anni, gli algoritmi genetici sono diventati sempre più comuni per risolvere i complessi problemi di ottimizzazione come quelle di scheduling o di timetabling. Il metodo generale nel passato doveva direttamente ottimizzare i problemi con una procedura genetica accoppiata spesso con una fase di post-ottimizzazione, dove entrambe le fasi erano orientate verso l'abbassamento del costo delle soluzioni. Il nuovo metodo presentato qui ,tratto da un U. Aickelin (Faculty of Computer Studies and Mathematics, University of the West of England, Frenchay Campus, ColdharbourLane, Bristol BS16 1QY, UK) in un articolo intitolato: “An indirect genetic algorithm for set covering problems” è diverso in due punti. In primo luogo, una procedura separata di decodifica, con i parametri forniti dalla procedura genetica, risolve il problema reale. In secondo luogo, lo scopo dell’ottimizzazione del decodificatore non è quello di realizzare soluzioni di basso costo. Le buone soluzioni sono trovate attraverso una fase di post-ottimizzazione (hill-climbing). Anche se suona complicato, questo metodo facilita realmente l’algoritmo dividendolo in tre componenti separate. I componenti stessi sono relativamente diretti ed autonomi, permettendo il loro uso per altri problemi. Quindi, questo metodo è particolarmente adatto per persone che hanno conoscenza approfondita del problema da ottimizzare ma che non conoscono il calcolo evolutivo, perché soltanto le parti non-evolutive devono essere cambiate per affrontare il nuovo problema. Il metodo si è sviluppato dall'osservazione che non ha senso, in generale, includere i vincoli nell'algoritmo genetico. Questo è uno dei loro svantaggi più grandi, poiché non li rende prontamente applicabili alla maggior parte dei problemi reali di ottimizzazione. Alcuni metodi per occuparsi dei vincoli esistono, sono essenzialmente funzioni di riparazione e di penalty. Tuttavia, la loro applicazione è successiva al problema specifico. Nell'approccio modulare, i problemi che coinvolgono i vincoli sono risolti dal modulo del decodificatore, che libera l'algoritmo genetico della gestione dei vincoli. L’ algoritmo sviluppa in primo luogo un metodo veloce, elastico e modulare per la soluzione dei problemi di set covering e, secondo, sviluppa un metodo per soddisfare i vincoli. In questa sede si usa un metodo modulare tri-fase. In primo luogo, la procedura genetica trova la permutazione 'migliore' delle righe e buoni parametri per la fase due. La procedura del decodificatore, un semplice euristico, assegna buone colonne alle righe trovate dall'algoritmo genetico. Infine un post-hill-climber ottimizza tutte le soluzioni. Prima di analizzare nel dettaglio l’algoritmo nei primi capitoli verrà presentata un breve excursus sull’origine degli algoritmi genetici, la terminologia usata in questo ambito la loro rappresentazione classica e i problemi che si posso incontrare affrontando l’argomento. Negli ultimi capitoli verranno invece presentati, innanzitutto, il problema del set covering e successivamente l’algoritmo da me implementato con le relative spiegazioni di ogni funzione usata e tabelle che illustrano i risultati da me ottenuti.