Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.


Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

EURISTICHE

informatica



EURISTICHE


Chiamiamo metodi euristici quelli che (contrariamente ai metodi approssimati) non danno nessuna garanzia a-priori sul valore di R(x,y).


RAGIONI PER SCEGLIERE UN' EURISTICA


  • La soluzione deve essere ottenuta rapidamente e non sono disponibili metodi approssimati efficaci
  • Istanza troppo grande per essere formulata come problema di PLI (o di MIP) di dimensione ragionevole
  • Difficile formulare il problema come problema di PLI (o di MIP) perché troppo complicato
  • Branch-and-Bound (o Branch-and-Cut) non arriva a trovare soluzioni in tempi di calcolo ragionevoli
  • L' esperienza dice che un certo metodo euristico fornisce buone soluzioni, mentre i metodi esatti sono inefficaci

Distinguiamo fra euristiche COSTRUTTIVE (ad 313f55d esempio il metodo GREEDY) e euristiche DI SCAMBIO (dette anche di RICERCA LOCALE)




Sia F l' insieme delle soluzioni ammissibili s di un generico problema di ottimizzazione combinatoria e c(s) la sua funzione costo e supponiamo, senza perdere in generalità, che si tratti di un problema di minimo:


min


1-INTORNI


Un intorno N(s) associa ad ogni soluzione ammissibile s un sottoinsieme di soluzioni ammissibili "vicine" (cioè uno degli elementi dell' insieme potenza 2F di F). Si suppone che N sia "esplorabile" efficientemente. Ciò equivale a supporre l' esistenza di un algoritmo che chiamiamo IMPR(s) (per "improvement") e che fornisce efficientemente (ciò equivale il più delle volte, come sappiamo, a dire che IMPR è polinomiale) una soluzione t in N(s) tale che c(t) è minore di c(s), se tale soluzione esiste, mentre fornisce 0 se ciò non è possibile. Spesso t è una soluzione di N(s) diversa da s con valore più  basso possibile della funzione obbiettivo.



GENERAL_LOCAL_SEARCH(N):


begin

generare una soluzione ammissibile s in F ;

while IMPR(s) 0 do s := IMPR(s) ;

return s

end


COSE DA DECIDERE:


  • come generare il primo s
  • come scegliere un "buon" intorno N
  • se vale la pena di ripetere la procedura magari partendo da soluzioni ammissibili generate a caso in F

ALCUNE EURISTICHE MOLTO NOTE


  • Randomised Repeated Trials (Prove Ripetute Casualizzate)
  • Greedy Randomised Adaptive Search Procedure (GRASP)
  • Simulated Annealing (SA)
  • Algoritmi Genetici (GA)
  • Ricerca con Tabu (Tabu Search, TS)
  • Sampling-and-Clustering (SC)
  • Metodi di Soglia (Threshold Method, TM)
  • Exploring Tabu Search (X-TS)
  • Ant System (AS)
  • Ant Colony Optimisation (ACO)
  • Granular Tabu Search (GTS)

Si distinguono euristiche a molti agenti (ad esempio GA, AS, ACO) e ad agente singolo (GRASP, SA, TS).


Vedremo brevemente solo alcune delle più famose.


2-SIMULATED ANNEALING SEMPLIFICATO


SIMANN :


M := 0 ;

q := temperatura iniziale ;

genera soluzione iniziale i ;

x := i ;

repeat

repeat

GENERA (a caso) j in N(i) ;

if D = c(j) - c(i) 0 then i := j else

if exp(-D q) > RANDOM(0,1) then i := j ;

if c(i) < c(x) then x := i

until in EQUILIBRIO ;

AGGIORNA q

M := M+1 ;

until q q-finale v M=K

return x


N.B. In maiuscolo le subroutine che è necessario assegnare.


ESEMPIO DI SEMPLICE STRATEGIA


temperatura iniziale = avg (Dc+) / ln (1/co

q-finale tra 6 e 50

aggiornamento di q: f(q) := 0.95 q


ORIGINE  Metodi Monte-Carlo per simulare il processo di formazione di cristalli a partire da un prodotto fuso abbassando molto lentamente la temperatura al fine di ottenere lo stato cristallino ad energia più bassa (Metropolis et al. 1953)


Se associamo ad ogni soluzione s ammissibile di F un vertice di un grafo e lo connettiamo ai vertici rappresentanti soluzioni di N(s) otteniamo un grafo H (talmente grande da essere solo immaginato). Indichiamo con d(x) il grado di un vertice di H e con D una stima per eccesso del suo grado massimo.


Il seguente algoritmo genera una passeggiata casuale su H partendo da un generico vertice x:


1. con probabilità ½ resta nel vertice x ;

2. seleziona y in F casualmente secondo la distribuzione seguente


Pr(y) =

3. con probabilità min x := y ;

4. go to 1


N.B. a 1 è un parametro: l' algoritmo sopra riportato è per un problema di minimo, mentre nel caso di massimo invece di a bisogna usare 1/a


Sia MC (a) la catena di Markof ottenuta con questo algoritmo: si noti che tale processo accetta di spostarsi in una soluzione migliorante con probabilità 1, mentre si sposta su soluzioni peggioranti con probabilità che dipende da a


decrescente di c(x), e quindi favorisce le soluzioni migliori (per problemi di massimo sarebbe monotona crescente dato che a è sostituito da 1/a


Algoritmo di Metropolis: simulare MC(a) per T iterazioni partendo da una soluzione ammissibile arbitraria e fornire in uscita la miglior soluzione trovata durante la simulazione.


L' algoritmo di Simulated Annealing si può considerare come un algoritmo di Metropolis dove a viene fatto variare secondo uno schema assegnato durante la simulazione, ottenendo una catena di Markof non-omogenea MC(a(t)). Ciò che abbiamo chiamato "temperatura" e indicato con q in SIMANN non è altro che 1/a


N.B. A quanto si sa non esiste prova che SIMANN sia migliore del più semplice algoritmo di Metropolis se a è scelto in maniera ottimale.


2-ALGORITMO GENETICO (Holland 1975)


GENALG:


t := 1 ;

inizializza una popolazione POP(t) con N soluzioni Pi(t) ;

while condizione di fine non soddisfatta do

for i := 1 to N do calcola la fitness fi = f(Pi(t)) ;

for i := 1 to N do

Pi(t+1) := una soluzione Pj(t) scelta a caso in POP(t) con probabilità pj = fj/Sk=1,.,nfk ;

CROSS(POP(t+1))

MUT(POP(t+1)) ;

t := t+1

end while



3-RICERCA CON TABU (Glover 1989)


IDEA: esplorare in N(s) escludendo alcuni movimenti dichiarati "tabu" per evitare di ciclare e guidare la ricerca verso regioni non ancora esplorate dell' insieme F. Un precursore di questo metodo può ritenersi quello di Kernigham-Lin. I metodi basati sulla ricerca con tabu sono risultati spesso tra i più efficaci.


Sia T la lista di mosse tabu e l la sua lunghezza, detta tabu tenure, spesso variabile dinamicamente intorno ad un valore centrale preferenziale.


Le restrizioni dettate da T possono essere violate quando un movimento che sarebbe tabu fornisce una soluzione migliore della migliore soluzione fin ora trovata (criterio di aspirazione).  


Caratteristiche importanti delle mosse utilizzate per esplorare un intorno N(s) tenendo conto della lista di mosse tabu T:


Efficienza: (importante in tutti i metodi di ricerca locale) la miglior soluzione in N(s) raggiungibile deve essere trovata rapidamente e deve essere semplice memorizzare la mossa corrispondente in T

Recentezza: quante iterazioni fa si è richiesto di usare la stessa mossa; su questa caratteristica si basa la possibilità di variare dinamicamente l

Frequenza: la frequenza con la quale una certa mossa viene richiesta è indicazione della sua "appetibilità" ed è utilizzata per intensificare la ricerca in zone promettenti di F

Qualità: il miglioramento della funzione obbiettivo ottenuto  





Privacy




Articolo informazione


Hits: 2871
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2024