Algoritmi genetici paralleli per la soluzione del TSP

Il lavoro descritto in questo rapporto riguarda 10 studio, il progetto e l'implernentazione su una macchina ad elevato parallelismo, un multicomputer nCUBE2 con 128 nodi di elaborazione, di alqorittn i genetici. 11 problema usato come caso di studio e il classico problema del commesso viaggiatore (TSP), che per la sua semplicita formale ben si presta ad essere usato come benchmark per la valutazione di euristiche. Allo scopo di effettuare uno studio preliminare sui diversi algoritmi genetici descritti in letteratura, sono stati dapprirna implementati e valutati AG sequenziali standard. Tali implementazioni hanno anche perrnesso di scegliere gli operatori genetici piu promettenti ed ottimizzare il 101'0 funzionamento per il caso di studio trattato. Sono stati quindi implementati e valutati AG paralleli a grana fine e a grana grossa al variare di alcuni parametri. Per I'algoritrno genetico a grana fine si eadottata una tecnica di mapping della popolazione sui processori che ha perruesso di rendere indipendente la dimensione della popolazione dal numero di nodi dell'elaboratore usato.