Sperimentazione del tabu search per la stima dello sforzo di sviluppo del software

Gli algoritmi genetici, proposti da Holland, simulano il processo dell’evoluzione naturale, applicandolo ai problemi di ottimizzazione. Quando si applica una tecnica di ottimizzazione all’ingegneria del software, come quella degli algoritmi genetici, ci si riferisce in particolare al cosiddetto “Search-Based Software Engineering”.
Il principio di base dell’evoluzione naturale riguarda la sopravvivenza di individui, che dovrebbero riprodursi tra di loro dando vita ad una nuova popolazione di individui. L’accoppiamento tra individui avviene generando nuovi individui, che mantengono, con una certa probabilità, determinate caratteristiche dei loro genitori. Solo alcuni individui però, partecipano al processo di riproduzione. Un individuo inoltre, può essere soggetto a mutazione, ossia alla variazione di alcune sue componenti genetiche. La riproduzione continua fino a generare intere generazioni di individui.
Per il nostro scopo, un algoritmo genetico inizialmente crea una popolazione di individui che solitamente sono scelti a caso, ossia un insieme di possibili soluzioni. In realtà la rappresentazione di una soluzione è detta cromosoma, e consiste in una stringa binaria di lunghezza fissa. Per ogni cromosoma della popolazione ne viene stabilita la bontà, attraverso il valore di una funzione di fitness. Lo scopo di questa funzione è proprio quello di valutare la qualità di una soluzione. Successivamente, per creare una nuova popolazione di individui si applica una serie di operatori genetici, ossia la selezione, il crossover e la mutazione (in tale ordine rispettivamente). La selezione implica la scelta di quei cromosomi della popolazione affinché essi possano riprodursi. In effetti, migliore è il valore del fitness di un cromosoma, maggiore sarà la probabilità che tale cromosoma sia scelto. Il crossover invece impone che, con una certa probabilità, due cromosomi simulino un accoppiamento, generando così nuove soluzioni. La mutazione fa si che, con una certa probabilità, il valore di un cromosoma venga cambiato.
Una volta applicati i tre operatori genetici, viene stabilito il valore di fitness per ogni cromosoma, e successivamente si da luogo ad una nuova generazione di individui, combinando in qualche modo la vecchia popolazione con quella nuova ottenuta in seguito all’applicazione degli operatori. Sono possibili diverse combinazioni, ad esempio prendendo un certo numero di cromosomi della nuova popolazione (eventualmente quelli che hanno il miglior valore di fitness) e combinandoli con i restanti cromosomi della vecchia popolazione.
A questo punto, si valuta un criterio d’arresto: se è soddisfatto, l’algoritmo genetico termina e restituisce il cromosoma col miglior valore di fitness. Altrimenti, si ripete il processo andando a riapplicare gli operatori a partire dalla selezione, come descritto in precedenza. Ci sono vari criteri d’arresto che possono essere applicati. Ad esempio, si può scegliere di fermarsi quando si raggiungono n iterazioni, oppure quando il valore della funzione di fitness non si migliora per k volte consecutive.