Euristică

În optimizarea matematică și în informatică, o euristică (din grecescul εὑρίσκω, „găsesc, descopăr”) este o tehnică concepută pentru rezolvarea mai rapidă a problemelor^⁠(d) atunci când metodele clasice sunt prea lente pentru a găsi o soluție exactă sau aproximativă sau când metodele clasice nu găsesc vreo soluție exactă într-un spațiu de căutare. Aceasta se realizează renunțând la optimitate, la completitate, acuratețe sau precizie în favoarea vitezei. Într-un fel, poate fi considerată o scurtătură.

O funcție euristică, numită și simplu euristică, este o funcție care ierarhizează alternativele în algoritmii de căutare^⁠(d) la fiecare pas de ramificare pe baza informațiilor disponibile pentru a decide ce ramură să urmeze. De exemplu, poate aproxima soluția exactă.^[1]

Definiție și motivație

Obiectivul unei euristici este de a produce o soluție într-un interval de timp rezonabil, care este suficient de bună pentru a rezolva problema în cauză. Este posibil ca această soluție să nu fie cea mai bună dintre toate soluțiile la această problemă sau poate pur și simplu să aproximeze soluția exactă. Dar este încă valoroasă, deoarece găsirea ei nu necesită un timp prohibitiv de lung.

Euristicile pot produce rezultate de la sine sau pot fi utilizate împreună cu algoritmi de optimizare pentru a le îmbunătăți eficiența (de exemplu, pot fi utilizate pentru a genera seeduri bune).

Rezultatele din informatica teoretică despre NP-tărie fac ca euristica să fie singura opțiune viabilă pentru o varietate de probleme complexe de optimizare care trebuie rezolvate în mod obișnuit în aplicațiile din lumea reală.

Euristica stă la baza întregului domeniu al inteligenței artificiale și al simulării pe calculator a gândirii, deoarece pot fi utilizate în situații în care nu există algoritmi cunoscuți.^[2]

Compromisuri

Printre criteriile pe care se fac compromisuri pentru a decide dacă se utilizează o euristică pentru rezolvarea unei anumite probleme se numără următoarele:

Optimalitate: Când există mai multe soluții pentru o anumită problemă, garantează euristica că va fi găsită cea mai bună soluție? Este chiar necesar să găsim cea mai bună soluție?
Completitudine: Când există mai multe soluții pentru o anumită problemă, euristica le poate găsi pe toate? Chiar avem nevoie de toate soluțiile? Multe euristici sunt menite doar să găsească o singură soluție.
Acuratețe și precizie: poate euristica să ofere un interval de încredere^⁠(d) pentru soluția pretinsă? Ștacheta de eroare pe o soluție este cumva nerezonabil de mare?
Timp de execuție : Este aceasta cea mai cunoscută euristică pentru rezolvarea acestui tip de problemă? Unele euristici converg mai repede decât altele. Unele euristici sunt doar puțin mai rapide decât metodele clasice, caz în care overheadul la calcularea euristicii ar putea avea un impact negativ.

În unele cazuri, decizia dacă soluția găsită de euristică este suficient de bună poate fi una dificilă, deoarece teoria care stă la baza euristicii nu este foarte elaborată.

Exemple

Problemă mai simplă

O modalitate de a obține câștigul de performanță de calcul așteptat de la o euristică constă în rezolvarea unei probleme mai simple a cărei soluție este și o soluție a problemei inițiale.

Problema comis-voiajorului

Un exemplu de aproximare este descris de Jon Bentley^⁠(d) pentru rezolvarea problemei comis-voiajorului (PCV):

„Se dă o listă de orașe și distanțele dintre fiecare pereche de orașe. Care este cel mai scurt traseu posibil care vizitează fiecare oraș exact o dată și se întoarce la orașul de origine?”

astfel încât să se selecteze ordinea de trasare folosind un plotter. Se știe că PCV este NP-hard, astfel încât o soluție optimă chiar și pentru o problemă de dimensiune medie este dificil de rezolvat. Se poate folosi în schimb algoritmul greedy pentru a oferi o soluție bună, dar nu optimă (este o aproximare a rezultatului optim) într-un timp rezonabil de scurt. Algoritmul euristic greedy spune să se aleagă ceea ce este în prezent cel mai bun pas următor, indiferent dacă aceasta împiedică (sau chiar face imposibili) pașii buni de mai târziu. Este o euristică în sensul că în practică este o soluție suficient de bună, în timp ce în teorie se știe că există soluții mai bune (și chiar, în unele cazuri, teoria indică și cât de mai bune).^[3]

Căutare

Un alt exemplu de euristică care face un algoritm mai rapid apare în anumite probleme de căutare. Inițial, euristica încearcă toate posibilitățile la fiecare pas, cum ar fi algoritmul de căutare pe întregul spațiu. Dar poate opri căutarea în orice moment dacă posibilitatea actuală este deja mai rea decât cea mai bună soluție deja găsită. În astfel de probleme de căutare, o euristică poate fi folosită pentru a încerca mai întâi alegerile bune, astfel încât căile proaste să poată fi eliminate din timp (vezi alpha-beta pruning^⁠(d)). În cazul algoritmilor de căutare best-first^⁠(d) cum ar fi căutarea A*^⁠(d), euristica îmbunătățește convergența algoritmului, menținând în același timp corectitudinea acestuia atâta timp cât euristica este admisibilă^⁠(d).

Newell și Simon: ipoteza căutării euristice

În discursul lor de acceptare a Premiului Turing, Allen Newell și Herbert A. Simon au discutat ipoteza căutării euristice: un sistem de simboluri fizice va genera și modifica în mod repetat structurile-simbol cunoscute până când structura creată se potrivește cu structura soluției. Fiecare pas următor depinde de pasul dinainte, astfel căutarea euristică învață ce căi să urmeze și pe care să le ignore, măsurând cât de aproape este pasul curent de soluție. Prin urmare, unele posibilități nu vor fi niciodată generate, deoarece sunt măsurate ca fiind mai puțin probabil să finalizeze soluția.

O metodă euristică își poate îndeplini sarcina folosind arbori de căutare. Cu toate acestea, în loc să genereze toate ramificările posibile, o euristică selectează ramificări mai susceptibile de a produce rezultate decât alte ramuri. Este selectivă la fiecare punct de decizie, alegând ramificări care sunt mai susceptibile de a produce soluții.^[4]

Software antivirus

Software-ul antivirus utilizează adesea reguli euristice pentru detectarea virușilor și a altor forme de malware. Scanarea euristică caută coduri și/sau modele de comportament comune unei clase sau familii de viruși, cu seturi diferite de reguli pentru viruși diferiți. Dacă se constată că un fișier sau un proces de execuție conține modele de cod care se potrivesc și/sau efectuează acel set de activități, atunci scanerul deduce că fișierul este infectat. Cea mai avansată parte a scanării euristice bazate pe comportament este că poate funcționa împotriva virușilor polimorfi^⁠(d) foarte randomizați, care nu pot fi detectați cu ușurință prin metode mai simple de scanare a șirurilor. Scanarea euristică are potențialul de a detecta viruși viitori fără a necesita ca virusul să fie mai întâi detectat în altă parte, trimis la dezvoltatorul scanerului de viruși, analizat și o actualizare de detectare pentru scaner furnizată utilizatorilor scanerului.

Capcane

Unele euristici se sprijină pe baze teoretice solide; ele sunt fie derivate de sus în jos din teorie, fie s-a ajuns la ele pe baza datelor experimentale sau reale. Altele sunt doar reguli empirice^⁠(d) bazate pe observație sau experiență din lumea reală, fără niciun fel de teorie. Acestea din urmă sunt expuși unui număr mai mare de capcane.

Atunci când o euristică este refolosită în diverse contexte deoarece s-a văzut că „funcționează” într-un context, fără a se fi demonstrat matematic că îndeplinește un anumit set de cerințe, este posibil ca setul de date actual să fie neapărat reprezentativ pentru seturile de date viitoare (vezi: Overfitting^⁠(d)) și acele pretinse „soluții” se dovedesc a nu fi mai bune decât zgomotul.

Analiza statistică^⁠(d) poate fi efectuată atunci când se utilizează euristica pentru a estima probabilitatea unor rezultate incorecte. Pentru a utiliza o euristică pentru rezolvarea unei probleme de căutare^⁠(d) sau a unei probleme a rucsacului, este necesar să se verifice dacă euristica este admisibilă^⁠(d). Dată o funcție euristică $h(v_{i},v_{g})$ menită să aproximeze distanța optimă reală $d^{\star }(v_{i},v_{g})$ până la nodul-țintă $v_{g}$ într-un graf orientat $G$ conținând în total $n$ noduri etichetate $v_{0},v_{1},\cdots ,v_{n}$ , „admisibil” înseamnă aproximativ că euristica subestimează costul drumului până la țintă sau în mod formal că $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ pentru orice $(v_{i},v_{g})$ unde ${i,g}\in [0,1,...,n]$ .

Dacă o euristică nu este admisibilă, atunci s-ar putea să nu ajungă niciodată la țintă, să ajungă într-un punct mort al grafului $G$ , sau să intre în ciclu infinit între două noduri $v_{i}$ și $v_{j}$ unde ${i,j}\neq g$ .

Etimologie

Cuvântul „euristică” a intrat în uz la începutul secolului al XIX-lea. Este format neregulat din cuvântul grecesc heuriskein, care înseamnă „a găsi”.^[5]

Note

^ Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3.
^ Apter, Michael J. (1970). The Computer Simulation of Behaviour. London: Hutchinson & Co. p. 83. ISBN 9781351021005.
^ Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. p. 11.
^ Allen Newell and Herbert A. Simon (1976). „Computer Science as Empirical Inquiry: Symbols and Search” (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022.
^ „Definition of heuristic in English”. Oxford University Press. Arhivat din original la 23 octombrie 2016. Accesat în 22 octombrie 2016.

[1] Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. p. 3.

[2] Apter, Michael J. (1970). The Computer Simulation of Behaviour. London: Hutchinson & Co. p. 83. ISBN 9781351021005.

[3] Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. p. 11.

[4] Allen Newell and Herbert A. Simon (1976). „Computer Science as Empirical Inquiry: Symbols and Search” (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022.

[5] „Definition of heuristic in English”. Oxford University Press. Arhivat din original la 23 octombrie 2016. Accesat în 22 octombrie 2016.

[1]

[2]

[3]

[4]

[5]