Utilizarea Calculatorului

Utilizarea calculatorului

(sintezã lãrgitã a cunostintelor si recomandãri de lucru)

Folosirea calculatoarelor la rezolvarea problemelor de optimizare.

1. Metode generale de optimizare.

Prin optimizare se întelege alegerea dintre mai multe variante candidat a unei solutii ce satisface în cel mai înalt grad un criteriu. Problema optimizarii este o metaproblemã. Ea include mai multe probleme cum ar fi: cea a existentei candidatului optim, a explorabilitãtii multimii candidatilor, a selectabilitãtii unui candidat, a calculabilitãtii criteriului pentru diferiti candidati, a identificãrii unui candidat ce satisface conditia de optimalitate, a verificãrii unicitãtii existentei sale, a identificãrii si a altor candidati ce satisfac conditia de optimalitate, a construibilitãtii multimii tuturor candidatilor optimi, a definirii unei reguli de selectie, a selectãrii celor mai reprezentativi candidati optimi, a evaluãrii consecintelor unei alegeri, a alegerii unui singur candidat dintre cei reprezentativi si adoptarea deciziei, a gestionãrii resurselor implicate în fiecare din problemele precedente. Nu am fãcut decât o enumerare generalã a problemelor conexe privind adoptarea unei hotãrâri. În limbajul curent vorbim de adoptarea unei decizii. Adoptarea „celei mai bune” decizii vom conveni s-o numim, în continuare, optimizare.

Gãsirea valorii optime si a punctelor de realizare a ei (punctelor de optim) este o problemã de programare deschisã pânã în prezent, dacã ne referim la cazul general. Algoritmii folositi se bazeazã fie pe proprietãti de geometrie algebricã fie pe o explorare Branch and Bound. Metodele clasice de optimizare (de gãsire a valorii si a punctelor de optim) pot fi grupate în douã clase mari: metode iterative si metode neiterative (într-un pas). Metodele neiterative folosesc anumite proprietãti (derivabilitate, convexitate, nici ele verificabile în cazul general) ale functiei obiectiv si ale spatiului de cãutare. Metodele iterative, mai des folosite, pornesc cu o aproximare initialã (de regulã aleasã în mod arbitrar) si calculeazã la fiecare pas o nouã aproximare („mai bunã”). Multe din schemele iterative folosesc o discretizare a unui spatiu de cãutare continuu. Metodele iterative pot fi de cãutare directã dacã utilizeazã numai valorile functiei obiectiv sau urcare/coborâre alpinistã dacã reclamã informatii privind valorile derivatei functiei.

Metode iterative de cãutare directã. Aceste metode sunt în general costisitoare din punct de vedere al timpului de calcul (ameliorarea producându-se doar într-un cadru de ghidare).

• Metodele exhaustive iau în considerare toate posibilitãtile de exploatare a spatiului problemei, cãutarea terminându-se la epuizarea tuturor elementelor din acest spatiu. La fiecare pas se pãstreazã solutia ce corespunde celei mai bune valori a functiei obiectiv. Aceste metode sunt ineficiente din cauza timpului de cãutare ce devine prohibitiv chiar pentru probleme relativ simple.

• Procedurile de ameliorare iterativã folosesc un mecanism de generare, printr-o perturbatie a stãrii curente, pentru obtinerea noilor stãri, ce construiesc o "vecinãtare" a stãrii curente. În aceastã vecinãtate sunt incluse toate stãrile ce pot fi atinse din starea curentã printr-o tranzitie. Dacã o stare din vecinãtate induce o ameliorare a functiei criteriu, ea va deveni noua stare a sistemului. Algoritmul se terminã când se obtine o stare pentru care vecinãtatea nu contine o stare mai bunã. Celebrul algoritm simplex din programarea liniarã poate fi inclus în aceastã categorie, fiind un algoritm cu ghidare strictã. Clasa metodelor de optimizare evolutivã trebuie mentionatã tot aici. Vom cãuta nu o solutie ci o populatie de solutii. La fiecare iteratie se creeazã o nouã populatie de solutii în jurul celor mai bune solutii ale iteratiei precedente. Procedurile de ameliorare iterativã neghidate sunt lente si nu foarte eficiente.

Metode iterative alpiniste (de tip gradient). Abordãrile traditionale cer utilizatorului sã cunoascã câte optime sunt cãutate pentru functia ce urmeazã a fi rezolvatã si, în general, unde sunt optimele, astfel încat sã poatã fi fãcutã o bunã ghicire initialã. Totusi, utilizatorul nu poate face decât rareori o ghicire initialã bunã si nu are informatii despre existenta minimelor multiple. În absenta unor astfel de informatii, algoritmii existenti vor converge, în general, cãtre un rãspuns, dar acesta este doar o solutie localã care s-ar putea sã nu fie global-optimalã. Mai mult, chiar optimele globale s-ar putea sã nu fie unice. De asemenea, dacã regiunea din jurul optimului este foarte platã, majoritatea algoritmilor vor prezenta dificultati cu convergenta. În realitate, o astfel de regiune platã, pentru problemele din lumea realã, poate indica existenta unei zone de indiferentã a solutiilor tot atât de bune.

Teoria jocurilor în turism

Veghes Ovidiu 1/7

Metode probabiliste. Ele sunt metode de optimizare evolutivã. La fiecare iteratie se realizeazã schimbãri pseudo aleatoare ale stãrii curente, retinând doar stãrile care amelioreazã starea curentã (în raport cu valoarea functiei obiectiv). Algoritmul de recoacere simulatã (simulated annealing) face parte din acestã categorie. Principiul algoritmului provine prin analogie cu atingerea minimului global al energiei interne a unei bucãti de metal încãlzitã si supusã la un proces controlat de rãcire lentã. Pornind de la starea curentã printr-o procedurã de generare aleatoare este furnizat un nou candidat. „Zburdãlnicia” noului candidat este proportionalã cu diferenta dintre valoarea corespunzãtoare a functiei obiectiv si un parametru global numit „temperaturã”. Când „temperatura este ridicatã” schimbarea este aproape liberã, iar pe mãsurã ce ea „descreste” schimbarea se focalizeazã într-o vecinãtate a stãrii de „energie redusã”. Noul candidat primeste statutul de stare curentã întotdeauna dacã este „mai bun" si în mod aleator în functie de temperaturã si diferenta în calitate dacã este „mai slab". Când nici o ameliorare, pe mãsurã ce „temperatura scade”, nu mai este posibilã am atins „echilibrul termic”. Chiar si algoritmii de recoacere paralelã sau re-recoacere care îmbunãtãtesc viteza de atingere a solutiei nu asigurã o „rãcire” rapidã. Cãutarea tabu are similitudini cu recoacerea simulatã. Pornind de la starea curentã se genereazã mai multi candidati, unul dintre ei devenind noua stare curentã. Se foloseste istoria procesului de cãutare pentru a clasa anumite miscãri ca fiind interzise (tabu). Lista tabu a cãutãrii este dinamicã si integreazã componente de memorie lungã si de memorie de scurtã duratã. Cele douã componente ale memoriei tabu asigurã un echilibru între explorarea spatiului solutiilor (diversificarea cãutãrii) si producerea de optime locale (intensificarea cãutãrii sau explorarea solutiilor deja gãsite). Ea se aplicã pentru probleme discrete de optimizare.