O metaheuristică este un algoritm de optimizare pentru rezolvarea problemelor de optimizare dificilă (adesea din domeniile cercetării operaționale , ingineriei sau AI ) pentru care nu există o metodă clasică cea mai eficientă cunoscută.
Metaheuristica este, în general , algoritmi stochastici iterați , care progresează către un optim global, adică extremul global al unei funcții , prin eșantionarea unei funcții obiective . Se comportă ca niște algoritmi de căutare, încercând să învețe caracteristicile unei probleme pentru a găsi o aproximare a celei mai bune soluții (într-un mod similar cu algoritmii de aproximare ).
Există o serie de metaheuristici diferite, variind de la căutare locală simplă până la algoritmi complecși de căutare globală. Cu toate acestea, aceste metode utilizează un nivel ridicat de abstractizare, permițându-le să fie adaptate la o gamă largă de probleme diferite.
Vorbim de meta , din grecescul μετά „dincolo” (înțelegeți aici „la un nivel superior”), euristic , din grecescul εὑρίσκειν / heuriskein , care înseamnă „a găsi”. Într-adevăr, acești algoritmi sunt intenționați să fie metode generice care pot optimiza o gamă largă de probleme diferite, fără a necesita modificări profunde în algoritmul utilizat.
O terminologie ușor diferită consideră că meta-euristica este o formă de algoritmi de optimizare stocastică, hibridizată cu căutare locală. Prin urmare, termenul meta este luat în sensul că algoritmii pot grupa mai multe euristici . Această definiție se găsește în special în literatura despre algoritmi evolutivi, unde este utilizată pentru a denota o specializare. În contextul primei terminologii, un algoritm evolutiv hibridizat cu o căutare locală va fi mai degrabă denumit algoritm memetic .
Metaeuristici sunt adesea inspirate de sistemele naturale, ele sunt luate în fizică (caz de recoacere simulate ) în biologia de evoluție (cazul algoritmilor genetici ) sau în etologie (cazul algoritmilor colonii de furnici sau optimizare roi de particule ).
Scopul unui metaheuristic este de a rezolva o anumită problemă de optimizare : caută un obiect matematic (o permutare , un vector etc.) care minimizează (sau maximizează) o funcție obiectivă , care descrie calitatea unei soluții la problemă. .
Setul de soluții posibile formează spațiul de cercetare . Spațiul de căutare este cel puțin delimitat, dar poate fi limitat și de un set de constrângeri .
Metaheuristica manipulează una sau mai multe soluții, în căutarea soluției optime , a celei mai bune probleme. Iterațiile succesive ar trebui să permită trecerea de la o soluție de calitate slabă la soluția optimă. Algoritmul se oprește după ce a atins un criteriu de oprire , constând în general în atingerea timpului de execuție alocat sau într-o precizie solicitată.
O soluție sau un set de soluții este uneori numit un stat pe care metaheuristic a evoluat prin intermediul a tranzițiile sau a mișcării . Dacă o nouă soluție este construită dintr-o soluție existentă, aceasta este vecina ei . Alegerea cartierului și structura datelor care îl reprezintă pot fi cruciale.
Când o soluție este asociată cu o singură valoare, se vorbește despre o problemă cu un singur obiectiv , când este asociată cu mai multe valori, cu o problemă cu mai multe obiective (sau cu mai multe criterii ). În acest din urmă caz, căutăm un set de non-dominate de soluții (de „ Pareto față “), soluții , printre care noi nu putem decide dacă o soluție este mai bună decât alta, nici una fiind în mod sistematic inferior celorlalți asupra tuturor obiectivelor.
În unele cazuri, scopul dorit este în mod explicit de a găsi un set de optime „satisfăcătoare”. Algoritmul trebuie să găsească apoi toate soluțiile de bună calitate, fără a se limita neapărat la singurul optim: vorbim de metode multimodale .
Metaheuristica nu necesită cunoștințe speciale despre problema optimizată pentru a funcționa, faptul de a putea asocia una (sau mai multe) valori cu o soluție este singura informație necesară.
În practică, acestea ar trebui utilizate numai pentru probleme care nu pot fi optimizate prin metode matematice. Utilizate în locul euristicilor specializate, acestea arată în general performanțe mai slabe.
Metaheuristica este adesea utilizată în optimizarea combinatorie , dar le întâlnim și pentru probleme continue sau mixte (probleme variabile discrete și continue).
Anumite metaheuristici sunt teoretic „ convergente ” în anumite condiții. Se garantează apoi că optimul global se va găsi într-un timp finit, probabilitatea de a face acest lucru crește asimptotic cu timpul. Această garanție echivalează cu a considera că algoritmul se comportă în cel mai rău caz ca o căutare aleatorie pură (probabilitatea de a încerca toate soluțiile tindând la 1). Cu toate acestea, condițiile necesare sunt rareori verificate în aplicațiile reale. În practică, condiția principală a convergenței este de a considera că algoritmul este ergodic (că poate ajunge la orice soluție cu fiecare mișcare), dar suntem adesea mulțumiți de o cvasi- ergodicitate (dacă metaheuristica poate ajunge la orice soluție într-un număr finit a mișcărilor).
În general, metaheuristica se învârte în jurul mai multor noțiuni:
Apropierea unei soluții este un subset de soluții la care se poate ajunge printr-o serie de transformări date. Prin extensie, termenul „vecinătate” denotă uneori ansamblul transformărilor avute în vedere.
Un cartier simplu pentru problema vânzătorului călător va fi, de exemplu, setul de soluții pe care este posibil să le construim permutând două orașe într-o soluție dată.
Noțiunea de vecinătate este, fără îndoială, principiul general cel mai utilizat pentru proiectarea euristicii. Pentru problemele combinatorii, vecinătatea are un impact important asupra comportamentului metaheuristicii, în timp ce pentru problemele continue, însăși noțiunea de vecinătate este mai dificil de definit.
Deși există foarte puține rezultate teoretice privind potrivirea dintre un vecinătate și o anumită problemă discretă, poate fi posibil să se calculeze indicatori empirici, cum ar fi rugozitatea . Cele mai clasice tehnici referitoare la definirea unui vecinătate se învârt în jurul noțiunilor de permutații , lanțuri de ejecție și optimizări parțiale.
Intensificarea, diversificarea, învățareaDiversificarea (sau explorare, sinonim folosit aproape interschimbabil în literatura de algoritmi evolutivi) înseamnă procesul de culegere a informațiilor privind problema optimizată. De intensificare (sau de exploatare) urmărește să utilizeze informațiile colectate deja pentru a defini și a naviga interesante zone ale spațiului de cercetare . Memoria este mediul de învățare, care permite algoritmul să ia în considerare numai zonele în care este probabil ca optimul global să fie găsit, evitându -se astfel valori maxime locale.
Metaheuristica progresează iterativ, alternând faze de intensificare, diversificare și învățare sau prin amestecarea mai apropiată a acestor noțiuni. Starea de pornire este adesea aleasă în mod aleatoriu, algoritmul rulând apoi până la atingerea unui criteriu de oprire.
Noțiunile de intensificare și diversificare sunt preponderente în concepția metaheuristicii, care trebuie să găsească un echilibru delicat între aceste două dinamici de cercetare. Prin urmare, cele două concepte nu sunt contradictorii, ci complementare și există multe strategii care combină ambele aspecte.
Cele mai clasice metaheuristici sunt cele bazate pe noțiunea desigur. În această perspectivă, algoritmul face ca o singură soluție să evolueze pe spațiul de căutare la fiecare iterație. Noțiunea de vecinătate este, prin urmare, esențială.
Cele mai cunoscute din această clasă sunt recoacerea simulată , căutarea cu tabuuri , căutarea în vecinătate variabilă , metoda GRASP sau chiar efectele sonore . Aceste metode pot fi comparate cu metoda clasică de alpinism.
În această clasificare, cealaltă abordare folosește noțiunea de populație. Metaheuristica manipulează un set de soluții în paralel, la fiecare iterație.
Putem cita algoritmi genetici , optimizarea prin roiuri de particule , algoritmi de colonii de furnici .
Granița este uneori estompată între aceste două clase. Astfel putem considera că o recoacere simulată în care temperatura scade în etape are o structură a populației. De fapt, în acest caz, un set de puncte este tratat la fiecare nivel, este pur și simplu o chestiune a unei anumite metode de eșantionare.
Metaheuristicile își folosesc istoricul căutărilor pentru a ghida optimizarea în iterațiile ulterioare.
În cel mai simplu caz, acestea se limitează la luarea în considerare a stării căutării la o iterație dată pentru a determina următoarea iterație: este apoi un proces de decizie markovian și vom vorbi despre o metodă fără memorie . Acesta este cazul majorității metodelor de căutare locale.
Multe metaheuristici folosesc o memorie mai evoluată, fie pe termen scurt (soluții vizitate recent, de exemplu), fie pe termen lung (memorarea unui set de parametri sintetici care descriu cercetarea).
Majoritatea metaheuristicilor folosesc funcția obiectivă așa cum este și își schimbă comportamentul optim de căutare. Cu toate acestea, unii algoritmi, cum ar fi căutarea locală ghidată , modifică reprezentarea problemei, încorporând informațiile colectate în timpul căutării, direct în cadrul funcției obiective.
Prin urmare, este posibil să se clasifice metaheuristicile în funcție de faptul dacă utilizează o funcție statică obiectiv (care rămâne neschimbată pe tot parcursul optimizării) sau dinamică (când funcția obiectiv este modificată în timpul căutării).
Majoritatea metaheuristicilor utilizate în contextul problemelor de optimizare combinatorie utilizează o singură structură de vecinătate. Cu toate acestea, metodele precum căutarea în vecinătate variabilă vă permit să modificați structura în timpul căutării.
Considerând metaheuristica ca metode iterative folosind o eșantionare a funcției obiective ca bază de învățare (o definiție mai potrivită mai ales metaheuristicii populației) apare problema alegerii eșantionării.
În marea majoritate a cazurilor, acest eșantionare se face în mod aleatoriu și, prin urmare, poate fi descris printr- o distribuție de probabilitate . Există apoi trei clase de metaheuristică, în funcție de abordarea utilizată pentru a manipula această distribuție.
Prima clasă este cea a metodelor implicite , unde distribuția probabilității nu este cunoscută a priori . Acesta este cazul, de exemplu, cu algoritmii genetici, unde alegerea eșantionării între două iterații nu urmează o lege dată, ci este o funcție a regulilor locale.
În schimb, putem clasifica metodele explicite , care utilizează o distribuție de probabilitate aleasă la fiecare iterație. Acesta este cazul algoritmilor de estimare a distribuției.
În această clasificare, recoacerea simulată ocupă un loc special, deoarece se poate considera că eșantionează funcția obiectivă folosind-o direct ca distribuție de probabilitate (cele mai bune soluții având o probabilitate mai mare de a fi desenate). Prin urmare, nu este nici explicit, nici implicit, ci mai degrabă „direct”.
Uneori găsim o clasificare care prezintă algoritmii optimizărilor stochastice ca fiind „ evolutivi ” (sau „evolutivi”) sau nu. Algoritmul va fi considerată ca făcând parte din clasa de algoritmi evolutivi manipuleaza o populație prin intermediul a operatorilor , în conformitate cu unele algoritm general.
Acest mod de prezentare a metaheuristicii are o nomenclatură adaptată: vom vorbi de operatori pentru orice acțiune care modifică starea uneia sau mai multor soluții. Un operator care construiește o nouă soluție va fi numit generator , în timp ce un operator care modifică o soluție existentă va fi numit mutator .
În această perspectivă, structura generală a algoritmilor evolutivi leagă etapele de selecție , reproducere (sau încrucișare ), mutație și în cele din urmă înlocuire . Fiecare pas folosește operatori mai mult sau mai puțin specifici.
Vorbim de hibridizare atunci când metaheuristica considerată este compusă din mai multe metode care împart sarcinile de cercetare. Taxonomia metaheuristicii hibride se împarte în două părți: o clasificare ierarhică și o clasificare plană . Clasificarea se aplică atât metodelor deterministe, cât și metaheuristice.
Clasificarea ierarhică se bazează pe nivelul (scăzut sau ridicat) al hibridizării și pe aplicarea acesteia (în releu sau simultan). În hibridizarea la nivel scăzut , o funcție dată a unui metaheuristic (de exemplu, mutație într-un algoritm evolutiv) este înlocuită de un alt metaheuristic (de exemplu, căutare cu tabu). În cazul nivelului ridicat , funcționarea internă „normală” a metaheuristicii nu este modificată. Într-o hibridizare cu releu , metaheuristica este lansată una după alta, fiecare luând ca intrare ieșirea produsă de cea anterioară. În concurență (sau coevoluție ), fiecare algoritm folosește o serie de agenți care cooperează împreună.
Această primă clasificare identifică patru clase generale:
A doua parte identifică mai multe criterii care pot caracteriza hibridizările:
Aceste categorii diferite pot fi combinate, clasificarea ierarhică fiind cea mai generală.
Metaheuristicile sunt adesea folosite pentru ușurința de programare și manipulare. Sunt într-adevăr ușor de adaptat la orice tip de problemă de optimizare. Cu toate acestea, acestea sunt folosite cel mai judicios în probleme dificile de optimizare , unde metodele de optimizare mai clasice (metodele deterministe, în special) își arată limitele.
În general, putem considera că problemele cu următoarele caracteristici sunt destul de favorabile utilizării metaheuristicii:
Pentru a testa o metaheuristică, un prim pas este utilizarea funcțiilor matematice special concepute. Algoritmii sunt evaluați pe baza unui set de funcții, mai mult sau mai puțin dificile, apoi comparate între ele.
Deoarece metaheuristica este în general stocastică, testele trebuie, în principiu, repetate de mai multe ori și apoi exploatate prin metode statistice . Cu toate acestea, această practică rămâne relativ neobișnuită în literatura de specialitate.
Într-un număr special al revistei științifice European Journal of Operational Research , dedicat aplicațiilor metaheuristicii, redactorii au menționat că majoritatea celor 20 de articole publicate erau în două domenii: probleme de programare și logistică . Cele mai utilizate metode aparțin familiei de algoritmi evolutivi , adesea hibridizate cu metode de căutare locale .
Câteva exemple de probleme concrete, optimizate prin metaheuristică:
Deoarece metaheuristica este foarte generală, ele pot fi adaptate la orice tip de problemă de optimizare care poate fi redusă la o „cutie neagră”. Ele sunt adesea mai puțin puternice decât metodele exacte pentru anumite tipuri de probleme. De asemenea, acestea nu garantează descoperirea optimului global într-un timp finit. Cu toate acestea, un număr mare de probleme reale nu pot fi optimizate eficient prin abordări pur matematice , astfel încât metaheuristica poate fi utilizată cu profit.
Noțiunea de eficiență se referă, în general, la două obiective contradictorii: viteza și precizia . Viteza este adesea măsurată în numărul de evaluări ale funcției obiective, care este de cele mai multe ori partea cea mai intensă din punct de vedere al calculului. Precizia se referă la distanța dintre optimul găsit de metaheuristică și optimul real, fie din punctul de vedere al soluției, fie de cel al valorii. Foarte des, un algoritm rapid este imprecis și invers.
De obicei, trebuie făcută o alegere cu privire la criteriul de oprire adecvat. Se utilizează adesea o serie de evaluări sau un timp alocat, dar se poate alege, de asemenea, să se ajungă la o anumită valoare a funcției obiective (scopul fiind acela de a găsi o soluție asociată). De asemenea, este posibil să alegeți criterii în funcție de comportamentul algoritmului, cum ar fi o dispersie minimă a populației de puncte sau un parametru intern adecvat. În orice caz, alegerea criteriului de oprire va influența calitatea optimizării.
Utilizarea metaheuristicii poate părea relativ simplă, la prima vedere, dar este adesea necesară adaptarea algoritmului la problema optimizată. În primul rând, în principal în contextul optimizării combinatorii , alegerea reprezentării soluțiilor manipulate poate fi crucială. Apoi, majoritatea metaheuristicilor au parametri a căror ajustare nu este neapărat banală. În cele din urmă, obținerea unei bune performanțe implică în general o etapă de adaptare a diferiților pași ai algoritmului (inițializarea, în special). În practică, numai cunoștințele și experiența utilizatorului pot gestiona aceste probleme.
Se admite că, dintr-un punct de vedere foarte general, niciun metaheuristic nu este cu adevărat mai bun decât altul. Într-adevăr, un metaheurist nu poate pretinde că este mai eficient în toate problemele, deși unele instanțe (adică algoritmul în sine, dar și o alegere a parametrilor și o implementare dată) pot fi mai potrivite decât altele pentru anumite clase de probleme. Această constatare este descrisă de teorema prânzului gratuit .
În analiza finală, este uneori posibil ca alegerea reprezentării soluțiilor, sau mai general a metodelor asociate metaheuristicii, să aibă o influență mai mare asupra performanțelor decât tipul de algoritm în sine. Cu toate acestea, în practică, metaheuristica se dovedește a fi mai puternică decât metodele de căutare exhaustive sau de căutare pur aleatorii.
Cele mai cunoscute metaheuristici sunt:
Există un număr foarte mare de alte metaheuristici, mai mult sau mai puțin cunoscute:
Deoarece cercetarea în domeniu este foarte activă, este imposibil să se producă o listă exhaustivă a diferitelor metaheuristici de optimizare. Literatura de specialitate arată un număr mare de variante și hibridizări între metode, în special în cazul algoritmilor evolutivi.
Metaheuristica, prin natura lor flexibilă, se pretează în special extensiilor. Astfel putem găsi adaptări pentru probleme mai complexe decât optimizarea cu un singur obiectiv:
Site-uri generaliste
Software și cadre