Per un problema di massimizzazione, la probabilità può essere definita come minimo tra 1 ed .
Come risulta evidente, se U1 > U0 la probabilità è sempre pari ad 1.
Viceversa, se U1<U0 la probabilità cambia in funzione del parametro T, chiamato ―temperatura‖: all‘aumentare di T, aumenta la ―tolleranza‖ rispetto all‘accettazione provvisoria di un bundle meno buono, e quindi la probabilità che esso venga scelto. Man mano che T si ―raffredda‖, è sempre più difficile passare da una soluzione migliore ad una peggiore, ostacolando conseguentemente l‘uscita dagli ottimi locali. Infatti senza quest‘accorgimento le soluzioni con utilità meno desiderabili di quella in esame non verrebbero mai scelte; questo comporterebbe la scelta del primo ottimo locale trovato e la fine di ogni ricerca.
L‘andamento della temperatura viene stabilito attraverso una schedula apposita, che in genere la fa diminuire in maniera più o meno costante in funzione del tempo o del numero di iterazioni svolte dal programma. Un raffreddamento troppo rapido può portare a risultati largamente sub-ottimali, mentre uno molto lento non rispetterebbe l‘esigenza di individuare una soluzione ―buona‖ in tempi brevi. Alcuni teoremi (Häggström, 2002) dimostrano che se la temperatura scende in modo sufficientemente lento verso 0, allora la probabilità di individuare l‘ottimo globale tende a 1 per n ∞ . Sfortunatamente, il significato di ―sufficientemente lento‖ dipende dal problema cui si applica la schedula. Inoltre Häggström (2002) evidenzia come le schedule che permettono di rispettare tali teoremi sono spesso troppo lente (si veda la Tabella 6.1, formula I), ragion per cui si preferisce individuarne sperimentalmente altre, che convergono più rapidamente.
165
E‘ anche possibile mantenere la temperatura costante per tutta la durata della sperimentazione, dando all‘algoritmo un criterio d‘arresto basato sul tempo trascorso o sul numero di iterazioni svolte. Recentemente è stato anche proposto un meccanismo di ―riscaldamento‖ della temperatura: quando l‘algoritmo sembra arenato in un ottimo, la temperatura viene rialzata a livelli gradualmente più bassi, al fine da promuovere una più accurata esplorazione (Taheri & Zomaya, 2007). Diversi autori hanno anche proposto sistemi di raffreddamento adattativi, basati sui cambiamenti di ―energia‖ (è questo il nome che in metafora viene data alla grandezza che in questo lavoro descrive l‘utilità) tra la soluzione visitate. Per esempio Azizi e Zolfaghari (2004) propongono la seguente regola:
Con δ parametro calcolato sperimentalmente e pari alla deviazione standard delle soluzioni visitate.
Seguono alcuni esempi di cooling schedule non adattativi individuati in letteratura:
Regola Riferimento Caratteristiche
(I)
* d=0 ** d=1
* (Il-Kwon & Ju-Jang, 1996)
**(Geman & Geman, 1984)
La temperatura si dimezza in una decina di iterazioni, indipendentemente dal valore di partenza, per poi scendere molto lentamente (quasi asintoticamente) fino a 0. Si ritiene che questa sia l‘unica schedula in grado di garantire l‘ottimalità dell‘output per n∞ (Bolte & Thonemann, 1996).
166
Regola Riferimento Caratteristiche
(II)
* **
*(Laarhoven & Aarts, 1987)
**(Romeo & Sangiovanni-Vincentelli, 1985)
E‘ probabilmente la più semplice tra le schedule proposte in letteratura, e anche la più utilizzata, spesso con valori di α molto vicini ad 1. Katayama & Narihisa (2001), per esempio, utilizzano α=0,99. Wah e Wang (2007), invece, per un problema di BQP vincolato, scelgono 0,8.
(III)
C costante
(Johnson, Aragon, McGeoch, & Schevon, 1989)
Analogo a (II), con la differenza che il coefficiente moltiplicativo diminuisce con il numero di iterazioni, invece di rimanere costante nel tempo.
(IV) (Wilhelm & Ward, 1987) Inizialmente decresce meno
rapidamente della (I), stabilizzandosi però su un livello più basso di temperatura per poi continuare scendere molto lentamente (quasi asintoticamente) fino a 0.
(V) (Kirkpatrick, Gelatti, & Vecchi, Optimization by Simulated Annealing, 1983)
Introdotta dai primi utilizzatori del SA a scopi di ottimizzazione, la schedula lineare è stata da allora molto utilizzata, ha il difetto di non interrompere per costruzione il raffreddamento a Tn=0.
(VI)
Con α<1
(Nourani & Andresen, 1998)
La schedula esponenziale è tra le più veloci a raffreddare la temperatura, è tra le più rare ad essere utilizzata nella letteratura censita.
167
Si propone, in aggiunta alle schedule di raffreddamento, la seguente (VII):
con n pari al numero di iterazioni svolte dall‘algoritmo e α=10.
In Figura 6.2 si mostrano gli andamenti delle funzioni finora indicate con T0 fissato pari a 100, e i parametri indicati nella legenda. Si è stabilito di scegliere tra queste sulla base di due criteri:
Rapidità di convergenza a 0 (iterazioni): χ t.c. Tχ<0,001
Rapidità di raffreddamento:
E‘ evidente che una maggiore rapidità di convergenza indica una schedula maggiormente efficiente (poiché restituisce una soluzione in tempi più brevi), ma potenzialmente meno efficace (poiché l‘algoritmo, funzionando per un numero minore di iterazioni, rischia di più di arenarsi in un ottimo locale. A parità di iterazioni, minore è il ∆T tra il passo n ed il passo n+1, più è efficace l‘algoritmo, poiché consente più facilmente l‘uscita da ottimi locali.
168 T0=1 T0=50 T0=100 T0=200 T0=500 T0=1000 χ χ Χ χ χ χ (VII) ~ 7 4 128 3'592.7 225 12'467 399 43'831 866 235'036 1571 846'786 (I) ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ (II) α=0,9 ~ 66 10 103 500.0 110 1'000 116 2'000 125 5'000 132 10'000 (III) C=100 ~ 33 9 41 471.0 43 843 44 1'185 45 4'713 46 9'427 (IV) α=0,0001 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ (V) α=0,005 ~ 19 13 140 4'665.0 199 13'234 282 37'514 446 148'573 526 403'726 (VI) α=0,005 ~ 36 12 45 582.0 47 1'163 48 2'627 50 5'817 51 11'633
Tabella 6.2 – Valori di χ e , per diversi valori di T0, applicati ai sette modelli di raffreddamento analizzati
Figura 6.3 – Rapporto tra χ e
La Figura 6.3 illustra l‘andamento del rapporto tra χ e per alcuni valori di riferimento di T0. Si
nota che le curve tendono a differenziarsi tra loro soprattutto in prossimità delle alte temperature, mostrando invece rapporti sostanzialmente simili per temperature sotto i 100 gradi. In questo lavoro si sperimenteranno, oltre alla nuova schedula proposta (VII), quella avente il rapporto più basso (II) e quella caratterizzata dal rapporto più alto (V). Con i parametri indicati, fatta eccezione per la (II), per la quale verrà anche considerato α=0,99 (IIbis) in modo da replicare la schedula utilizzata da Katayama e Narihisa (2001) per un problema di binary quadratic programming.
0 100 200 300 400 500 600 700 800 1 50 100 200 500 1.000 (VII) (II) α=0,9 (III) C=100 (V) α=0,005 (VI) α=0,005
169
Un altro elemento critico nel tuning del Simulated Annealing è – ovviamente – la scelta di T0.
Laarhoven e Aarts(1987) suggeriscono di determinare tale valore in modo da permettere nelle prime iterazioni qualsiasi transizione di stato, ovvero –nel caso in esame – che renda per ogni
bundle 1 e 0. Katayama e Narihisa (2001) scelgono invece T0=0.3*n (con n pari al numero di
variabili) per un problema di binary quadratic programming, valore proposto anche in precedenza (Alkhamis, Hasan, & Ahmed, 1998). Tale metodo per il calcolo della temperatura di partenza è stato riproposto nelle simulazioni relative alla schedula (IIbis)
Kirkpatrick (1984) suggerisce invece di ricorrere ad una regola empirica basata sul tasso di accettazione delle transizioni: se minore di un valore x0 prestabilito (gli autori utilizzano 0,8),
suggeriscono di raddoppiare T0 finché il tasso non supera x0. Con un ragionamento analogo Johnson
et al. (1987, citato in Laarhoven & Aarts, 1987) propongono di determinare T0 con la seguente
formula:
Con ad indicare la differenza di utilità media per un campione di transizioni possibili estratte casualmente.
Sono state testate diverse temperature di raffreddamento, in modo da rendere Tf=0 con f pari
all‘ultima iterazione tale da mantenere il tempo di attesa per la computazione tollerabile per un acquirente online. E‘ intuitivo come f cambi significativamente in funzione della capacità di calcolo, del numero di prodotti, della dimensione del bundle da proporre e della sparsity della matrice delle sinergie.
Per quanto riguarda il criterio di arresto dell‘algoritmo, si fa in genere riferimento ad un valore di Tn stabilito a priori (Laarhoven & Aarts, 1987), oppure ad un numero di iterazioni n (Davis, 1987), o ancora ad un contatore che indichi quando l‘algoritmo è ―bloccato‖ in un ottimo (Wilhelm & Ward, 1987) in ragione della temperatura raggiunta (ovvero se per un determinato numero di volte consecutivei l‘algoritmo restituisce la stessa soluzione), altri ancora ricorrono infine ad algoritmi genetici (Bolte & Thonemann, 1996) che generano dinamicamente la schedula.
i
Per esempio, se la soluzione rimane inalterata dopo dieci cicli di ―raffreddamento‖ si termina l’algoritmo (Katayama & Narihisa, 2001).
170
6.5.2 Ant Colony Optimization
L‘Ant Colony Optimization (Dorigo & Stützle, 2004) è un metodo di ottimizzazione ispirato dal comportamento delle formiche (in inglese, ―ant‖) osservato in natura. In particolare, esso fa riferimento alla tecnica con la quale gli insetti procacciano il cibo, comunicando indirettamente tra loro lasciando piccole quantità di una sostanza chimica (il feromone) sulla via da loro percorsa tra il formicaio e il cibo. La paternità del metodo va riconosciuta all‘italiano Marco Dorigo e ad alcuni suoi colleghi del Politecnico di Milano, che pubblicarono i primi studi a riguardo all‘inizio degli anni ‘90 (Dorigo, 1992; Dorigo, Maniezzo, & Colorni, 1996).
Le formiche si muovono in maniera casuale nelle vicinanze del formicaio, seguendo preferenzialmente l‘odore di feromone lasciato dalle altreii
. In particolare, se una formica trova del cibo, ne valuta qualità e quantità e poi ne porta una porzione nel formicaio. Nel tornare lascia una traccia di feromone di intensità proporzionale a quantità e qualità stimate. In questo modo permette alle compagne di individuare a loro volta la via per il cibo. E‘ stato osservato che questa tecnica permette alle formiche di determinare con esattezza il cammino minimo tra formicaio e fonte di cibo (Deneubourg, Aron, Goss, & Pasteels, 1990). E‘ intuitivo che maggiore è il quantitativo di feromone depositato, maggiore è il numero di formiche che seguono il percorso e che depositano ulteriore feromone. Si instaura quindi un ciclo di feedback positivo (Dorigo, Maniezzo, & Colorni, 1996). Il feromone rilasciato dalle formiche ha una durata limitata, poiché tende ad evaporare col tempo, fenomeno che permette di bloccare il loop positivo man mano che la fonte di cibo si esaurisce.
Cordon et al. (2002) suggeriscono di adottare la seguente procedura per affrontare un problema di ottimizzazioni attraverso l‘Ant Colony Optimization:
1. Rappresentare il problema nella forma di componenti e transizioni indicate da un grafo pesato che deve essere percorso dalle formiche per individuare le soluzioni.
2. Definire adeguatamente il livello di feromone τrs nell‘arco che unisce i nodi r ed s.
3. Determinare la preferenza (heuristic information) ηrs ―a priori‖ che la formica ha nel percorrere l‘arco rs. Tali valori sono di cruciale importanza poiché permettono di customizzare l‘algoritmo al meglio per le specificità note del problema in esame.
ii
Le formiche sono insetti quasi ciechi. Una formica da sola alla ricerca di cibo segue percorsi che ritenuti sostanzialmente casuali. Quando una formica incontra una traccia di feromone può scegliere con una probabilità molto alta di seguire tale traccia, o meno.
171
4. Se possibile, implementare un algoritmo di ricerca locale efficace per il problema di cui si sta cercando la soluzione.
5. Scegliere uno specifico algoritmo ACO e applicarlo al problema da risolvere.
6. Scegliere i parametri per l‘algoritmo, iniziando da quelli che hanno mostrato di funzionare bene per problemi simili ed eventualmente ricorrendo a procedure automatiche per la rifinitura dei parametri(Birattari, Stutzle, Paquete, & Varrentrapp, 2002).
L‘algoritmo, nella sua forma più generica, funziona come segue:
A. Il livello di feromone τi associato ad ogni variabile viene impostato pari ad una
costante c>0 per ogni i.
Viene stabilito il numero A di agenti (formiche) B. Per ogni agente j da 1 ad A
i. determinare le componenti della sua soluzione, scelte sulla base della probabilità P(τ, η)
ii. Deposita feromone in base alle componenti scelte e al risultato conseguito.
C. Aggiorna il livello di feromone con 0<ρ≤1.
D. Calcola l’utilità della migliore soluzione trovata