Ottimizzatori

I problemi di ottimizzazione che si presentano nella pratica sono spesso tanto complessi da non poterne determinare una soluzione per via analitica.  La complessità è determinata innanzi tutto dal numero di variabili e di vincoli, che definiscono la dimensione del problema; e poi dalla eventuale presenza di funzioni non lineari. La soluzione analitica è possibile solo nel caso di poche variabili e di funzioni estremamente semplici, dunque solo in casi che hanno più valenza didattica che reale.
Nella pratica, per risolvere un problema di ottimizzazione può essere opportuno fare ricorso a un algoritmo iterativo, ossia ad un programma di calcolo che, data una approssimazione corrente xk della soluzione, determina, con una appropriata sequenza di operazioni, una nuova approssimazione xk+1.
Nell’ottimizzazione combinatoria (ossia nei problemi di programmazione matematica con un numero finito di soluzioni ammissibili) sono utilizzati gli algoritmi euristici (o euristiche), cioè algoritmi che forniscono una soluzione ammissibile, non necessariamente ottima, di un problema di ottimizzazione.
Il gruppo EML2  dispone di competenze nell’ambito dell’uso di metaueristiche (ossia di euristiche per la soluzione di problemi NP-difficili) applicate alla soluzione di problemi EM complessi.  È il caso, ad esempio, degli algoritmi genetici e della tabu search, che vengono da noi utilizzati nella pianificazione ottima di reti cellulari al fine di ottenere le combinazioni migliori dei parametri elettrici e di posizionamento delle antenne di una data rete di comunicazione wireless su una data area geografica per garantire elevati standard di comunicazione e ridotte emissioni EM.
Gli ottimizzatori sono utilizzati dal nostro gruppo nelle attività didattiche frontali e nelle attività di ricerca e sviluppo dei progetti: SeGriPlaNet, Genetic Agents…

ALGORITMI GENETICI
Proposti dai primi anni ’70 da John Holland, sfruttano un’analogia con i meccanismi della genetica e dell’evoluzione naturale.
Gli AG sono algoritmi di ottimizzazione e apprendimento automatico basati sull’implementazione artificiale di alcuni principi fondamentali della selezione naturale e della genetica evoluzionistica
Solitamente si basano sulla specifica di tre operazioni di tipo probabilistico su entità definite stringhe (rappresentabili nella maggior parte dei casi come stringhe binarie) contenenti la codifica dei parametri del problema soggetti a ottimizzazione. Tali operazioni sono:
-    riproduzione: generazione/combinazione di nuove stringhe a partire dalla popolazione iniziale per ottenerne di nuove
-    mutazione: alterazione di uno o più caratteri di una stringa
-    crossover: combinazione di porzioni di stringhe preesistenti per ottenerne di nuove
Queste operazioni possono essere combinate: ad esempio è molto comune effettuare una riproduzione tramite crossover.
I passi di un generico algoritmo genetico sono:
1)    inizializzazione della popolazione
2)    selezione dei genitori per la riproduzione e le operazioni da eseguire
3)    esecuzione delle operazioni genetiche per generare una popolazione intermedia e valutare la capacità di sopravvivenza dei membri della popolazione
4)    selezione (sulla base del valore di una opportuna funzione di fitness) dei membri della popolazione che rimarranno nella generazione successiva
5)    Ripetizione dei passi precedenti fino al raggiungimento di un predefinito criterio di arresto

In ambito EM, le ottimizzazioni condotte tramite gli AG sono ormai uno strumento consolidato e molto utile.
Una procedura di ottimizzazione tipica (così come evidenziato in figura) prevede di ottimizzare le posizioni delle BS e i parametri elettrici delle antenne di tali BS sfruttando gli AG

Si inizia discretizzando l’area geografica in esame in una griglia di punti equidistanti fra loro detta griglia dei test point
Si procede poi alla scelta della più adeguata funzione di fitness per il problema in esame
In ogni test point viene calcolato il campo elettrico prodotto da tutte le antenne presenti nell’area e sommato con gli altri contributi di campo che raggiungono quel punto
Si calcola per ogni test point dell’area considerata la funzione di fitness

genetico

TABU SEARCH
La tabu search (=ricerca con tabu) è una metaeuristica per risolvere problemi di ottimizzazione globale, in particolare di ottimizzazione combinatoria. Il metodo consiste nello spostarsi da una soluzione ad un’altra scegliendo la migliore soluzione non proibita nell’intorno della soluzione corrente. Le soluzioni vengono proibite sulla base di certi attributi con lo scopo di evitare cicli e di guidare la ricerca verso regioni inesplorate. Se non ci fossero soluzioni proibite una volta giunti ad un punto di ottimo locale non sarebbe più possibile spostarsi.