Tehnici Informatice de Optimizare

Introducere

Multe probleme combinatorice nu pot fi rezolvate exact prin utilizarea rezonabilã a timpului de procesare şi a spaţiului chiar şi atunci când numãrul variabilelor este relative mic.

Tabu search a fost introdusa de Glover ca o tehnica pentru determinarea unui optim local.Ideea de baza este de a interzice anumite directii de cautare la o iteratie prezenta pentru a evita ciclarile, dar in acelasi timp sa poti continua dintr-un punct de optim local.Aceasta strategie poate fi folositoare la orice tehnica de imbunatatire locala.O abordare similara a fost dezvoltata independent si de Hansen.

Formulare QAP

În forma ei simplã QAP poate fi descrisa in forma:

Sa se gaseasca asignarea optimala a N obiecte pentru N locatii, pentru minimizarea cumulative a fluxurilor si distantele de timp intre fiecare 2 locatii.Mai exact, daca fip este fluxul dintre obiectele i si p, si daca djq este distant dintre locatiile j si q, problema poate fi scrisa sub forma:

a.i.

, pentru orice i

, pentru orice j

xij=0 sau 1.

Variabila xij este diferita de zero daca obiectul i este asignat locatiei j si pentru zero obiectul j este asignat locatiei i.Functia care trebuie optimizata este patratica si neconvexa (exista un numar de optime locale) si un set fezabil este un set de permutari.

O formulare echivalenta a problemei este aceea de a minimize

peste un set al tuturor permutarilor a elementelor [1,…,n].

Cand una dintre matricile in functie de obiectivul QAP este restrictionata sa inceapa o matrice de permutare ciclica, rezulta un QAP redus la un TSP.Cu toate ca TSP este un caz special al QAP, problemele au fost studiate separate si exista un numar de metode euristice diferite pentru fiecare.

Adaptare a Tabu Search pentru QAP

In sectiunea I elementele ale metodologiei TS sunt definite si este prezentat algoritmul Tabu-Navigation pentru QAP. Rezultatelecomputationale ale sectiunii I sunt descrise in sectiunea II.Rezultatele obtinute sunt comparate cu cele din literature.Experimentele computationale sunt efectuate in scopul de a evalua valorile parametrilor ca lungimea listei tabu si numarul maxim de iteratii.Strategia de a schimba aceste valori in timpul executiei algoritmului este de a explora toate posibilitatile.Utilizarea unor criteria de aspiratie pentru suprascrierea lui tabu status si o strategie pe termen lung a memoriei pentru selectarea inteligenta a unor noi puncte de restartare a cautarii, sunt de asmenea testate.Concluzii finale sunt date in sectiunea III.

Algoritmul Tabu-Navigation pentru QAP

Un numar de metode pentru QAP constau in doua faze: construire si imbunatatire. Rezultate ale unei astfel de metode este data in West utilizand Heider N-step, un algoritm de cautare in faza de constructive cu 2 variabile si toate schimburile de perechi in faza de imbunatatire.Algoritmul se opreste cand nici o schimbare nu ofera o imbunatatire, cand un optim local este atins.Studiul incorporeaza TS in faza de imbunatatire prin continuarea cautarii chiar daca sa gasit un optim local.

Urmatoarele definitii descriu elementele TS adaptate pentru Glover.

1. O mutare este o tranzitie de la o permutare la alta.

2. Un atribut al unei mutari in acest caz este o pereche neordonata (i,j) a obiectelor care isi schimba locatiile.In contrast cu implementarea TS pentru alte problem, atributul unei mutari in cazul QAP este destul de simpla reflectand faptul ca seturile fezabile sunt seturi neconstranse al tuturor permutarilor.

3. Valoarea unei mutari este diferenta dintre valorile functiei obiectiv dupa si inainte de mutare.Daca aceasta valoare este negative, mutarea ofera o imbunatatire.

4. Cea mai buna functie de mutare este aceea care identifica o pereche (ibest,jbest) pentru care valoarea mutarii este cea mai mica.Domeniul celei mai bune functii de mutare este subsetul tuturor perechilor(i,j)(Acest subset este denumit setul mutarilor admisibile.).Cea mai buna mutare nu trebuie sa fie una de imbunatatire.

5. O lista tabu a perechilor (i,j) a lungimii lui tabu_size este construita si actualizata in timpul fazei de imbunatatire a algoritmului.Daca o pereche (i,j) apartine listei tabu pentru o iteratie data, nu este permis sa se efectueze schimbari a obiectelor i si j la acea iteratie.La inceputul fazei de imbunatatire lista tabu este goala.Aceasta este apoi construita in tabu_size la iteratii consecutive si actualizata circular in iteratii urmatoare.