Căutare Tabu
Căutarea Tabu (sau căutare tabu ) este o tehnică meta-euristică utilizată pentru soluționarea a numeroase probleme de optimizare , inclusiv probleme de planificare și rutare , probleme de grafic și programare întreagă .
Principiile de funcționare
Căutarea Tabu reprezintă o evoluție a „metodei descendente” clasice ( adică „cea mai abruptă coborâre” sau a pantei maxime, cunoscută și sub numele de metoda gradientului), adică, utilizată pentru a găsi minimul unei funcții reale f pe un set S (soluții spațiale). Această metodologie clasică constă în pornirea de la o soluție inițială și efectuarea unei serii de „mișcări” care conduc la o nouă soluție în vecinătatea (sau setul de adiacență) a soluției curente, în care funcția obiectivă f capătă o valoare mai mică a valoarea actuala. Dezavantajul metodei de coborâre este că, dacă în setul de adiacență nu există soluții „mai bune” decât cea curentă, căutarea se oprește. Soluția optimă identificată prin metoda de coborâre este, prin urmare, asociată cu un minim local al spațiului soluției, care este adesea foarte departe, în special în ceea ce privește calitatea, de soluția optimă globală.
Tehnica Tabu Search a fost propusă de Fred Glover ca o modalitate de a continua căutarea dincolo de minimele locale. În primul rând, pentru a scăpa de „capcana” minimelor locale, Căutarea Tabu permite „înrăutățirea mișcărilor”. Totuși, procedând astfel, riscați să reveniți la minimul local imediat după aceea, dacă nu cumva preveniți mișcările făcute recent. Prin urmare, conceptul fundamental al Căutării Tabu constă în a face „interzis” sau, precis, „tabu”, ultimele mișcări efectuate în calea căutării, astfel încât algoritmul să nu-și poată urmări pașii și să cadă înapoi în minimul local. Caracteristica de bază a Căutării Tabu este, prin urmare, utilizarea sistematică a memoriei : pentru a crește eficiența procesului de căutare, nu doar informațiile locale sunt urmărite (cum ar fi valoarea curentă a funcției obiective), ci și unele informații referitoare la traseu călătorit. Aceste informații sunt utilizate pentru a ghida trecerea de la soluția curentă la următoarea soluție, care va fi aleasă în cadrul setului de adiacență.
fundal
În forma sa actuală, Căutarea Tabu a fost propusă de Fred W. Glover . Idei similare au fost, de asemenea, schițate în același timp de P. Hansen, în timp ce conceptul fundamental al utilizării interdicțiilor pentru a încuraja diversificarea cercetării apare în diferite lucrări anterioare, de exemplu în algoritmul Kernighan-Lin pentru partiționarea graficului.
Numeroasele experimente de calcul efectuate arată că Tabu Search este acum o tehnică de optimizare stabilită, care poate concura cu aproape toate metodele cunoscute și că, datorită flexibilității sale, poate învinge multe dintre procedurile clasice de optimizare. Împreună cu recurgerea simulată și algoritmii genetici , Tabu Search a fost indicată de Comitetul pentru următoarea decadă de cercetare operațională ca o tehnică extrem de promițătoare pentru tratamentul viitor al aplicațiilor practice. Demonstrația formală a convergenței asimptotice în Căutarea Tabu poate fi obținută prin modificări stocastice. Recent, U. Faigle și W. Kern au propus o versiune probabilistică a Căutării Tabu care converge aproape sigur către un optim global. Astfel de rezultate teoretice, deși interesante, sunt destul de irelevante pentru aplicațiile practice. Scopul Căutării Tabu, ca și alte tehnici euristice, este de a găsi rapid soluții bune la probleme care deseori nu permit determinarea soluțiilor optime într-un timp rezonabil (de exemplu , probleme dificile NP ).
Bibliografie
- Glover, F. și M. Laguna. (1997). Căutare Tabu . Kluwer, Norwell, MA.
- Glover, F. „Căutare Tabu - Partea I”, ORSA Journal on Computing 1989 1 : 3, 190-206.
- Glover, F. „Tabu Search - Part II”, ORSA Journal on Computing 1990 2 : 1, 4-32.
- Cvijovic, D.; Klinowski, J. „Căutare tabu - o abordare a problemei minime multiple”. Știință 1995 267 , 664-666.
- Greco Francesca; O LUCRU HIBRIDĂ CĂUTARE ADAPTIVĂ RANDOMIZATĂ HEURISTICĂ PENTRU A REZOLVA PROBLEMA DIAL-A-RIDE. , Research Gate, 2008.
linkuri externe
- ( RO ) Introducere în Căutarea Tabu , pe ifi.uio.no.
- ( RO ) Site-ul de căutare reactivă , pe reactive-search.org . Adus la 10 august 2006 (arhivat din original la 2 iunie 2010) .
- ( EN ) Conferința LION despre tehnici de învățare și optimizare inteligentă , pe intelligent-optimization.org . Adus la 22 decembrie 2010 (arhivat din original la 8 noiembrie 2010) .
- ( RO ) Site-ul web al Companiei de căutare reactivă - O companie de software care implementează aceste tehnici , pe reactive-search.com .
- ( EN ) Roberto Battiti, Mauro Brunato și Franco Mascia Reactive Search and Intelligent Optimization , pe reactive-search.org . Adus la 22 decembrie 2010 (arhivat din original la 16 martie 2012) .
