Università degli studi Roma Tre

Facoltà di Scienze Matematiche Fisiche e Naturali Corso di Laurea in Matematica

Sintesi della Tesi di Laurea in Matematica di

Luca Rapposelli

Algoritmi genetici applicati a problemi di partizionamento su alberi

Relatore Prof. Marco Liverani

Anno Accademico 2002/2003 Ottobre 2003

Classificazione AMS: 68R01, 68R10, 68T01, 68T05, 68T20, 90C27

Parole chiave: algoritmi genetici, ottimizzazione discreta, grafi, alberi, partizionamento

In questo lavoro ci proponiamo di studiare i problemi di partizionamento di grafi visti come particolari problemi di ottimizzazione: il problema viene definito sulla base di una funzione obiettivo da massimizzare o minimizzare, calcolata sulle componenti della partizione del grafo. Per risolvere tali problemi abbiamo utilizzato la tecnica degli algoritmi genetici e nel caso specifico abbiamo analizzato il problema di partizionamento di alberi. Naturalmente, trattandosi della suddivisione in componenti di un albero con un numero finito di vertici, il nostro è un problema di ottimizzazione discreta (ottimizzazione combinatoria) per la cui soluzione sono state verificate una serie di tecniche algoritmiche classiche. Il contributo originale presente in questo lavoro è costituito dall’utilizzo degli algoritmi genetici per affrontare e risolvere il problema di ottimizzazione combinatoria del partizionamento di un albero.

Il partizionamento di grafi è un problema di ottimizzazione che ritroviamo in tantissime applicazioni, anche molto eterogenee: ad esempio dai problemi di analisi dei campioni elettorali o di segmentazione del mercato per studi di marketing, alla riduzione del numero di colori per il miglioramento del contrasto nelle immagini grafiche al computer, dai problemi di dimensionamento di apparati per reti di telecomunicazione a più generici problemi di cluster analysis in statistica, e in molti altri ambiti.

Il problema di partizionamento che abbiamo preso in considerazione in questa tesi rientra nella classe più generale dei cosiddetti problemi di equipartizione di un grafo, ossia problemi di partizionamento che mirano a definire una suddivisione in componenti il più possibile simili fra loro, o per le quali la differenza sia minima. La misura della maggiore o minore distanza tra due componenti diverse della stessa partizione ci viene fornita in generale dal peso delle componenti, calcolato come somma dei pesi associati ai vertici della componente stessa.

Sia G = (V, E) un grafo, con V = {v_{1}, v_{2}, …, v_{n}}. Una partizione in p componenti del grafo G la indicheremo con π = {C_{1}, C_{2}, …, C_{p}}, dove C_{j} = {v_{i_{1}}, …, v_{i_{k}}} è una generica componente della partizione. Naturalmente risulta

C_{i} ∩ C_{j} = ∅, ∀i, j = 1, …, p, i ≠ j

e inoltre

∪_{j=1}^{p}C_{j} = V (G).

In alcuni problemi può essere richiesto che la p-partizione del grafo sia effettuata costruendo p componenti connesse: in questo modo si introducono dei vincoli molto forti per la costruzione della soluzione ottima; d’altra parte tali vincoli sono insiti nei problemi pratici in cui il partizionamento di grafi trova applicazione. Il vincolo della connessione delle componenti della partizione è strettamente legato alla particolare topologia del grafo che si sta considerando: ad esempio se il grafo è un albero, allora anche le componenti connesse di una sua partizione saranno alberi ed il numero di tagli che è necessario compiere sugli spigoli dell’albero per ottenere le p componenti connesse, è fissato ed è pari a p − 1.

Indicando con w_{i}, i = 1, …, n, il peso associato agli elementi dell’insieme da partizionare (vertici del grafo), si vuole individuare una partizione tale da rendere il più omogeneo possibile il peso delle diverse componenti C_{1}, …, C_{p} della partizione. Con W (C_{k}) = ∑_{v_{i}∈C_{k}} w_{i} indichiamo, come abbiamo già detto, il peso della componente k-esima; indicheremo invece con

μ = \frac{1}{p} ∑_{k=1}^{p} W (C_{k})

il peso medio ideale di una componente della p-partizione. Possiamo allora definire i seguenti problemi di ottimizzazione:

• Norma L_{1}: si vuole minimizzare la funzione obiettivo

f(π) = ∑_{k=1}^{p} |W (C_{k}) − μ|

• Norma L_{2}: si vuole minimizzare la funzione obiettivo

f(π) = ∑_{k=1}^{p} (W (C_{k}) − μ)^{2}

• Norma L_{∞}: si vuole minimizzare la funzione obiettivo

f(π) = max_{k=1,...,p} |W (C_{k}) − μ|

• Min-max: si vuole minimizzare la funzione obiettivo

f(π) = max_{k=1,...,p} W (C_{k})

• Max-min: si vuole massimizzare la funzione obiettivo

f(π) = min_{k=1,...,p} W (C_{k})

• Massima partizione limitata dal basso: si vuole trovare una partizione dell’insieme in modo tale da massimizzare il numero di componenti connesse C_{k}, con il vincolo che W (C_{k}) ≥ L, ∀k.

• Minima partizione dominata dall’alto: si vuole trovare una partizione nel minimo numero di componenti connesse C_{k} tali che W (C_{k}) ≤ U, ∀k.

Indicheremo con Π(G) l’insieme di tutte le partizioni del grafo G, mentre con Π_{A}(G) ⊆ Π(G) indicheremo l’insieme delle partizioni ammissibili di G per un determinato problema; ad esempio se il problema richiede che le componenti della partizione siano dei sottografi connessi, allora una partizione di G che contenga una componente non connessa non sarà una partizione ammissibile di G. Sia p un intero tale che 1 ≤ p ≤ n. Una p-partizione connessa π di G è una partizione di V in p sottoinsiemi C_{1}, …, C_{p} tali che ogni C_{k} induca un sottografo connesso di G. Con Π_{p}(G) indicheremo l’insieme di tutte le p-partizioni connesse di G.

Indicheremo inoltre con w_{i} il peso associato al vertice v_{i} di G. Il peso di una certa componente C_{j} della partizione π di G sarà dunque espresso come

W (C_{j}) = ∑_{h=i_{1}}^{i_{k}} w_{h}.

Gli algoritmi genetici, ispirandosi all’evoluzione biologica, risolvono numerosi problemi di ricerca e di ottimizzazione. Come abbiamo già detto, nel nostro caso li abbiamo impiegati per risolvere problemi di ottimizzazione legati al partizionamento di un grafo, ed è abbastanza naturale passare dalla formulazione di un problema di ottimizzazione alla soluzione con la tecnica degli algoritmi genetici. In natura il patrimonio genetico di un essere vivente è rappresentato dai cromosomi del DNA: delle concatenazioni di geni con cui sono codificate le caratteristiche distintive di ogni individuo. Nell’evoluzione biologica è proprio la combinazione dei cromosomi che consente di produrre nuovi individui che, ereditando solo parzialmente il codice genetico dei propri genitori, saranno dotati di maggiore o minore probabilità di “sopravvivenza”. L’evoluzione di una specie porta dunque a rendere più probabile il propagarsi di una configurazione cromosomica che ottimizza la “funzione sopravvivenza” di un individuo di quella specie: gli individui più “idonei” a sopravvivere nel contesto ambientale in cui sono stati inseriti avranno una maggiore aspettativa di vita e dunque maggiori probabilità di riprodursi e di generare discendenti che ereditando il loro patrimonio genetico siano altrettanto idonei a sopravvivere.

Il funzionamento degli algoritmi genetici ricalca questo processo evolutivo: se si riesce a rappresentare le soluzioni del problema da ottimizzare con delle stringhe assimilabili a dei cromosomi e se si può codificare la funzione obiettivo da ottimizzare come una misura dell’idoneità del cromosoma, allora applicando le operazioni che regolano l’evoluzione dei cromosomi in natura, si può far evolvere la soluzione del problema di ottimizzazione fino a raggiungere l’ottimo cercato. Dunque lo schema con cui sono costruiti gli algoritmi genetici è il seguente: si codifica il problema in una stringa chiamata cromosoma, si definisce una funzione del cromosoma chiamata idoneità e tramite delle operazioni applicate al cromosoma stesso, che sono la selezione, l’incrocio e la mutazione, si tenta di massimizzare la funzione idoneità. Nel caso di un problema di ottimizzazione le soluzioni ammissibili vengono codificate in stringhe che rappresentano i cromosomi della popolazione su cui opera l’algoritmo genetico applicando le tre operazioni citate precedentemente. La funzione di ottimizzazione c : F → ℝ viene trasformata nella funzione idoneità da massimizzare.

Un algoritmo genetico si articola nei seguenti passi:

1. Genera casualmente una popolazione di n cromosomi di lunghezza l

2. Calcola la funzione idoneità per ogni cromosoma

3. Ripeti, finché non sono stati creati n discendenti, le seguenti operazioni:

(a) Seleziona casualmente due cromosomi in modo da privilegiare i cromosomi con un alto valore della funzione idoneità

(b) Con una probabilità p_{c} incrocia i due cromosomi; se questo incrocio non avviene i due cromosomi rimangono invariati.

(c) Con una probabilità p_{m} muta i due cromosomi; se non succede lascia i cromosomi invariati.

4. sostituisci la vecchia popolazione di cromosomi con quella appena generata.

5. Vai al passo 2 se la condizione di stop non è verificata.

6. Stampa la migliore soluzione individuata durante l’esecuzione dell’algoritmo

Spieghiamo brevemente le operazioni fondamentali che un algoritmo genetico compie.

La codifica consiste nel costruire un modello con cui rappresentare le configurazioni del nostro sistema (lo spazio delle soluzioni) mediante delle stringhe (i cromosomi) i cui elementi (geni) potranno essere valori binari oppure dei numeri reali.

Ogni algoritmo genetico ha bisogno di una funzione chiamata funzione idoneità, che assegna ad ogni cromosoma un valore che dipende dalla capacità del cromosoma di risolvere il problema, ed è definita come:

f : C → ℝ

dove C è l’insieme dei cromosomi, e la funzione associa ad ogni cromosoma un numero reale. La funzione idoneità ha un ruolo molto importante nella selezione dei cromosomi, infatti misura la qualità della soluzione rappresentata da un certo cromosoma ed in base a questo valore tale cromosoma avrà una maggiore probabilità di sopravvivere.

La selezione consiste nello scegliere gli individui in una popolazione per creare la generazione successiva. Lo scopo è quello di far emergere gli individui con la più alta funzione idoneità, in modo che nella generazione successiva, la popolazione possa avere una maggiore idoneità media. Un metodo efficiente per selezionare i cromosomi è la selezione proporzionale all’idoneità. Questa selezione assegna ad ogni individuo una certa probabilità di essere estratto e questa probabilità è data dalla formula:

p_{s} = \frac{f(c, t)}{\overline{f}(t)}

cioè l’idoneità dell’individuo f(c, t) divisa per l’idoneità media della popolazione \overline{f}(t).

Dopo aver selezionato gli N genitori l’operazione successiva è quella dell’incrocio. Consiste nel prendere due individui, dopo averli selezionati, e scambiare tra loro i geni in modo da formare due nuovi cromosomi chiamati figli.

Per comprendere meglio questa operazione descriviamo il metodo più semplice per incrociare due cromosomi chiamato l’incrocio con un solo punto di taglio. Il funzionamento è il seguente: si sceglie casualmente il punto in cui dividere i due cromosomi genitori e si ricombinano le quattro parti così ottenute dai due genitori per formare i due cromosomi figli. Il primo cromosoma figlio è costituito della prima parte del cromosoma genitore A e dalla seconda parte del genitore B, mentre il secondo figlio è formato dalla prima parte del genitore B e dalla seconda parte del genitore A.

Genitori  Figli
Cromosoma A aaaa aaaaa aaaa bbbbb
Cromosoma B bbbb bbbbb bbbb aaaaa

Tabella 1: Incrocio con un solo punto di taglio

La mutazione è una delle operazioni che permette di introdurre variazioni che assicurano, ad una popolazione di cromosomi, di esplorare nelle fasi iniziali una porzione più grande dello spazio delle soluzioni, ed in particolare di non rimanere ferma in un determinato stato. Cioè, dopo un certo tempo di esecuzione, l’algoritmo potrebbe trovarsi in una condizione in cui i cromosomi della popolazione sono tutti uguali o simili. L’operazione di incrocio in questo caso non introdurrebbe nessuna variazione e quindi un modo per uscire da questa situazione di stallo è quella di applicare la mutazione.

Il metodo più semplice di mutazione è chiamato mutazione uniforme che consiste nel cambiare il valore di un gene ad un cromosoma. In questa operazione viene scelto casualmente un gene del cromosoma da mutare e al gene scelto viene cambiato valore. Ad esempio utilizzando la codifica binaria se il valore del gene è 1 allora dopo la mutazione il valore diventerà 0, o viceversa.

Ritornando al problema che ci siamo proposti di risolvere in questa tesi, diamo brevemente un’idea di come partizionare un albero utilizzando un algoritmo genetico, e in particolare come questo avviene utilizzando la norma L_{∞} come funzione obiettivo del problema di ottimizzazione.

Nel nostro problema abbiamo utilizzato una codifica binaria per rappresentare i cromosomi della popolazione. Nella nostra codifica ogni gene del cromosoma rappresenta un arco dell’albero e dunque la totalità degli archi forma il cromosoma; il valore 0 di un gene corrisponde ad un arco senza un taglio, mentre il valore 1 corrisponde ad un punto di taglio.

Nella Figura 1 è riprodotto un albero a cui è stato imposta l’orientazione naturale degli spigoli, una volta definito il vertice 0 come radice. L’orientazione naturale, che può essere facilmente calcolata con una visita dell’albero a partire dalla radice, ci permette così di identificare ogni spigolo con lo stesso indice del vertice su cui lo spigolo entra.

[figure: 0; 1; 1; 2; 3; 4; 4; 5; 5; 2; 3]

Figura 1: Esempio di albero partizionato in tre componenti connesse

In riferimento alla partizione rappresentata in Figura 1, la codifica del cromosoma corrispondente è la seguente:

a_{1} = 0, a_{2} = 1, a_{3} = 1, a_{4} = 0, a_{5} = 0

ossia a = 01100.

La funzione idoneità scelta è la seguente:

f : π → \frac{1}{max_{k=1,...,p} |W (C_{k}) − μ|}

che esprime la funzione obiettivo del problema di ottimizzazione del partizionamento del grafo con norma L_{∞}.

Nel nostro lavoro abbiamo adattato le operazioni di incrocio e mutazione in modo che i cromosomi generati da queste operazioni rappresentino solo delle partizioni ammissibili.

Riportiamo di seguito un esperimento significativo condotto su un albero di 100 vertici, con un numero di partizioni pari a 10. Il peso dei vertici è compreso tra 1 e 10. I parametri di funzionamento che abbiamo scelto sono i seguenti: il numero cromosomi è 200, le generazioni sono 100, la probabilità di mutazione è pari a 0.01 con lo spostamento di massimo tre tagli per ogni cromosoma; l’incrocio è uniforme con una probabiltà di incrocio pari a p_{c} = 1. Il valore minimo del partizionamento è stato trovato alla quattordicesima generazione ed è pari a 24. Il grafico della Figura 2 rappresenta questo test. Il grafico rappresenta la media della funzione idoneità calcolata per ogni generazione di cromosomi e possiamo osservare come questa media cresca di generazione in generazione, fino ad arrivare al valore ottimo.

Da questo esperimento possiamo trarre alcune conclusioni: questi algoritmi risolvono in modo approssimato i problemi di ottimizzazione NP-completi, e sono un metodo molto efficiente per risolvere diversi problemi di ottimizzazione di cui non si conosce un buon algoritmo che risolva il problema in breve tempo.

Figura 2: asse x generazioni, asse y medie della funzione idoneità

Concludiamo questa breve introduzione descrivendo dettagliatamente il contenuto dei capitoli.

Nel primo capitolo abbiamo definito i problemi di ottimizzazione, ed abbiamo presentato i principali metodi di soluzione dei problemi di ottimizzazione. Infine abbiamo esposto un metodo per risolvere un problema di ottimizzazione con la tecnica degli algoritmi genetici.

Il secondo capitolo fornisce un’analisi dettagliata degli algoritmi genetici. Abbiamo iniziato il capitolo introducendo i principali vocaboli e definizioni di un algoritmo genetico confrontandoli con la terminologia informatica, poi, utilizzando un semplice algoritmo genetico abbiamo spiegato il suo funzionamento e presentato i vari tipi di codifica che traducono il problema iniziale. Inoltre, abbiamo descritto le operazioni di selezione, di incrocio e di mutazione che un algoritmo genetico compie per trovare la soluzione ottima. Di seguito abbiamo dimostrato il Teorema degli schemi che sta alla base della teoria degli algoritmi genetici ed abbiamo descritto il modello di Vose e Nix che considera un algoritmo genetico come una catena di Markov.

Nel terzo capitolo abbiamo descritto il problema di ottimizzazione generale del partizionamento di un grafo. Dopo aver dato alcuni cenni sui contesti a cui è possibile applicare questo genere di problema, proporremo una schematizzazione, se pur parziale, del problema stesso, al fine di individuare gli aspetti fondamentali del problema stesso e focalizzare l’attenzione su alcuni casi che ad oggi si sono rivelati particolarmente difficili da risolvere con i metodi tradizionali dell’ottimizzazione discreta.

Nel quarto capitolo utilizzando la teoria esposta nei capitoli precedenti, abbiamo costruito un metodo per risolvere i problemi di p-partizionamento di alberi in componenti connesse. In quest’ultimo capitolo descriviamo un tecnica innovativa per codificare il problema del partizionamento e spieghiamo le diverse operazioni da compiere per ottenere la soluzione ottima. Inoltre abbiamo esteso questa metodologia al problema più generale del partizionamento di grafi. Come conclusione del capitolo abbiamo riportato i risultati ottenuti attraverso l’implementazione di questo metodo su alcuni casi di esempio.

In appendice sono riportati i listati commentati del programma che implementa l’algoritmo genetico descritto nel quarto capitolo per il partizionamento di alberi pesati. Inoltre sono presenti i listati dei programmi che ci sono serviti per generare in modo casuale alberi e per calcolare in modo esaustivo la soluzione ottima dei problemi di partizionamento, al fine di poter compiere delle verifiche sulla bontà della soluzione prodotta dall’algoritmo genetico. L’esecuzione del programma che implementa la ricerca esaustiva della soluzione (e che dunque produce sicuramente una soluzione ottima) ha richiesto in alcuni casi anche un’intera giornata di elaborazione su una macchina piuttosto potente, a fronte dei pochi secondi di elaborazione richiesti dal programma che implementa l’algoritmo genetico.

Bibliografia

[1] John H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, Mich., 1975. An introductory analysis with applications to biology, control, and artificial intelligence.

[2] Melanie Mitchell. Introduzione agli algoritmi genetici. MIT Press, 1996.

[3] David E. Goldberg. Genetic Algorithms in Search, Optimization, and, Machine Learning. Addison-Weslet publishing company, inc, 1989.

[4] M. Garey and D. S. Johnson. Computer and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979.

[5] G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi. Teoria e Progetto di algoritmi fondamentali. Franco Angeli Editore, 1988.

[6] Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization - Algorithms and Complexity. Dover Publications, Inc., 1998.

[7] Paolo Baldi. Calcolo delle probabilità e statistica. McGraw-Hill, 1992.

[8] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to algorithms. The MIT Electrical Engineering and Computer Science Series. MIT Press, Cambridge, MA, 1990.

[9] Marco Liverani, Aurora Morgana, Bruno Simeone, and Giovanni Storchi. Path equipartition in the Chebyshev norm. European J. Oper. Res., 123(2):428–436, 2000. Advances in theory and practice of combinatorial optimization (Puerto de la Cruz, 1997).

[10] Enzo Aparo and Bruno Simeone. Un algoritmo di equipartizione e il suo impiego in un problema di contrasto ottico. Ricerca operativa, 6:1–12, 1973.

[11] Michael Schroder. Balanced tree partitioning.

[12] Mario Lucertini, Yehoshua Perl, and Bruno Simeone. Most uniform path partitioning and its use in image processing. Discrete Appl. Math., 42(2-3):227–256, 1993. Combinatorial structures and algorithms.

[13] Ronald I. Becker, Stephen R. Schach, and Yehoshua Perl. A shifting algorithm for min-max tree partitioning. J. Assoc. Comput. Mach., 29(1):58–67, 1982.

[14] Yehoshua Perl and Stephen R. Schach. Max-min tree partitioning. J. Assoc. Comput. Mach., 28(1):5–15, 1981.

[15] Thang Nguyen Bui and Byung Ro Moon. Genetic algorithm and graph partitioning. IEEE Trans. Comput., 45(7):841–855, 1996.

[16] Allen E. Nix and Michael D. Vose. Modeling genetic algorithms with Markov chains. Ann. Math. Artificial Intelligence, 5(1):79–88, 1992.

[17] Michael D. Vose and Gunar E. Liepins. Punctuated equilibria in genetic search. Complex Systems, 5(1):31–44, 1991.

[18] Michael D. Vose. Generalizing the notion of schema in genetic algorithms. Artificial Intelligence, 50(3):385–396, 1991.

[19] Yijia Cao and Lilian Cao. Controlled Markov chain optimization of genetic algorithms. In Computational intelligence (Dortmund, 1999), volume 1625 of Lecture Notes in Comput. Sci., pages 186–196. Springer, Berlin, 1999.

[20] Raphaël Cerf. A new genetic algorithm. Ann. Appl. Probab., 6(3):778– 817, 1996.

[21] Nicole Drechsler, Wolfgang Günther, and Rolf Drechsler. Efficient graph coloring by evolutionary algorithms. In Computational intelligence (Dortmund, 1999), volume 1625 of Lecture Notes in Comput. Sci., pages 30–39. Springer, Berlin, 1999.