Quali sono le differenze tra la ricottura simulata e algoritmi genetici?

Question

Quali sono le differenze rilevanti, in termini di casi di prestazioni e, tra di ricottura simulata (con ricerca di fagioli) e gli algoritmi genetici?

So che SA può essere pensato come GA in cui la dimensione della popolazione è una sola, ma non so la differenza fondamentale tra i due.

Inoltre, sto cercando di pensare a una situazione in cui SA sorpasserà GA GA o sorpasserà SA. Solo un semplice esempio che vi aiuterà a capire sarà sufficiente.

Answer 1

Bene a rigor di termini, queste due cose -. simulato ricottura (SA) e algoritmi genetici non sono né gli algoritmi, né è il loro scopo 'data mining'

Entrambi sono meta-euristiche - un paio di livelli di cui sopra 'algoritmo' sulla scala di astrazione. In altre parole, entrambi i termini si riferiscono a metafore alto livello - uno preso in prestito dalla metallurgia e l'altro dalla biologia evoluzionistica. Nella tassonomia meta-euristica, SA è un metodo singolo Stato e GA è un metodo popolazione (in una sotto-classe con PSO, ACO, et al, di solito denominata biologicamente ispirati meta-euristiche ).

Queste due meta-euristiche vengono utilizzati per risolvere problemi di ottimizzazione, in particolare (ma non esclusivamente) in combinatoria di ottimizzazione (alias programmazione a vincoli soddisfazione ). ottimizzazione combinatoria riferisce all'ottimizzazione scegliendo tra un insieme di elementi discreti - in altre parole, non v'è alcuna funzione continua per minimizzare. Il problema dello zaino, problema del commesso viaggiatore, il taglio stock problema - sono tutti problemi di ottimizzazione combinatoria

.

La connessione al data mining è che il nucleo di molti (la maggior parte?) Sotto la supervisione macchina di apprendimento algoritmi (ML) è la soluzione di un problema di ottimizzazione -. (Multi-layer Perceptron e Support Vector Machines per esempio)

Qualsiasi tecnica soluzione per risolvere i problemi della protezione, indipendentemente dell'algoritmo, consisterà essenzialmente di questi passaggi (che sono tipicamente codificati come un unico blocco all'interno di un ciclo ricorsivo):

1. codificare i dettagli dominio-specifici in una funzione di costo (è il minimizzazione graduale del valore restituito da questa funzione che costituisce una 'soluzione' al c / o problema);

2. valutare la funzione di costo di passaggio in un 'ipotesi' iniziale (per iniziare iterazione);

3. in base al valore restituito dal funzione di costo, generare una successiva soluzione candidata (o più di uno, a seconda della meta-euristica) al costo funzione;

4. valutare ogni soluzione candidato passando in un set argomento, la funzione di costo;

5. procedura di ripetizione (iii) e (iv) fino o qualche criterio di convergenza è soddisfatto o un numero massimo di iterazioni viene raggiunto.

meta-euristiche sono diretti alla fase (iii) di cui sopra; quindi, SA e GA differiscono nel modo di generare soluzioni candidate per la valutazione della funzione di costo. In altre parole, questo è il luogo per cercare di capire come questi due meta-euristiche differiscono.

Informalmente, l'essenza di un algoritmo diretto alla soluzione di ottimizzazione combinatoria è il modo in cui gestisce una soluzione candidato il cui valore restituito dalla funzione di costo è peggio di quello attuale migliore soluzione candidata (quello che restituisce il valore più basso dalla funzione di costo). Il modo più semplice per un algoritmo di ottimizzazione per gestire una tale soluzione candidato è di rifiutare a titolo definitivo - questo è ciò che l'algoritmo di hill climbing fa. Ma facendo questo, semplice arrampicata collina sarà sempre perdere una soluzione migliore separata dalla soluzione corrente da una collina. In altre parole, un algoritmo di ottimizzazione sofisticato deve includere una tecnica per (temporaneamente) accettare una soluzione candidata peggio (cioè, in salita dal) la migliore soluzione attuale, perché una soluzione ancora migliore di quella attuale potrebbe trovarsi lungo un percorso attraverso quel peggio soluzione.

---

Così come SA e GA generano soluzioni candidate?

L'essenza della SA è di solito espressa in termini di probabilità che una soluzione più elevato costo candidato sarà accettata (l'intera espressione all'interno della doppia parentesi è un esponente:

p = e((-highCost - lowCost)/temperature)

O in python:

p = pow(math.e, (-hiCost - loCost) / T)

Il termine 'temperatura' è una variabile il cui valore durante decadimenti progresso della ottimizzazione - e di conseguenza, la probabilità che SA volontà acCEPT una soluzione peggiore diminuisce all'aumentare numero iterazione.

In altre parole, quando l'algoritmo inizia iterazione, T è molto grande, che, come si può vedere, fa sì che l'algoritmo di muoversi ad ogni soluzione candidata di recente creazione, sia meglio o peggio la migliore soluzione attuale - vale a dire, sta facendo un random walk nello spazio di soluzione. Come numero di iterazioni aumenta (cioè come raffredda temperatura) ricerca dell'algoritmo dello spazio soluzione diventa meno permissive, sino a T = 0, il comportamento è identico ad un algoritmo semplice in salita (cioè solo soluzioni meglio della corrente migliore soluzione sono accettati).

Algoritmi Genetici sono molto diversi. Per prima cosa - e questa è una grande cosa - non genera un'unica soluzione candidato ma un intero 'la popolazione di loro'. Funziona in questo modo: GA chiama la funzione di costo per ogni utente (soluzione candidata) della popolazione. E poi li colloca, dal migliore al peggiore, ordinata dal valore restituito dalla funzione di costo ( 'migliore' ha il valore più basso). Da questi valori classificati (e le loro corrispondenti soluzioni candidati) si crea la popolazione successiva. I nuovi membri della popolazione sono creati essenzialmente uno dei tre modi. La prima è di solito indicato come 'elitarismo' e in pratica di solito si riferisce al solo prendendo le soluzioni candidate massima ordinati e li passa direttamente attraverso - non modificato - alla generazione successiva. Gli altri due modi che i nuovi membri della popolazione sono di solito indicati come 'mutazione' e 'incrocio'. Mutazione solito comporta un cambiamento in un elemento in un vettore soluzione candidata dalla popolazione corrente per creare un vettore soluzione nella nuova popolazione, ad esempio, [4, 5, 1, 0, 2] => [4, 5, 2, 0 , 2]. Il risultato dell'operazione di crossover è simile a ciò che accadrebbe se i vettori potrebbero fare sesso -.. Cioè, un nuovo vettore bambino i cui elementi sono costituiti da alcuni da ciascuno dei due genitori

Quindi, queste sono le differenze tra algoritmiche GA e SA. Che dire delle differenze di prestazioni?

In pratica: (le mie osservazioni sono limitati a problemi di ottimizzazione combinatoria) GA batte quasi sempre SA (restituisce un valore inferiore 'migliore' di ritorno dalla funzione di costo - vale a dire, un valore prossimo al minimo globale della soluzione spazio), ma ad un costo di calcolo più elevata. Per quanto ne so, i libri di testo e pubblicazioni tecniche recitano la stessa conclusione a risoluzione.

, ma qui è la cosa: GA è intrinsecamente parallelizzabile; per di più, è banale a farlo perché l'individuo che compongono ciascuna popolazione non hanno bisogno di scambiare messaggi "agenti ricerca" - vale a dire, lavorano in modo indipendente l'uno dall'altro. Ovviamente questo significa GA calcolo possono essere distribuiti , il che significa , in pratica, è possibile ottenere risultati molto migliori (più vicino al minimo globale) e la performance migliore (la velocità di esecuzione).

In quali circostanze potrebbe sovraperformare SA GA? Lo scenario generale penso che sarebbe quei problemi di ottimizzazione che hanno un piccolo spazio soluzione in modo che il risultato da SA e GA sono praticamente la stessa, ma il contesto di esecuzione (ad esempio, centinaia di problemi simili eseguiti in modalità batch) favorisce l'algoritmo più veloce (che dovrebbe essere sempre SA).

Answer 2

E 'veramente difficile confrontare i due da quando sono stati ispirati da diversi domini ..

un algoritmo genetico mantiene una popolazione di possibili soluzioni, e ad ogni passo, seleziona i coppie di soluzione possibile, li (crossover) combina, e applica alcune modifiche casuali (mutazione). L'algoritmo si basa l'idea di "sopravvivenza del più adatto", dove il processo di selezione è effettuata secondo un criterio di fitness (di solito in problemi di ottimizzazione è semplicemente il valore della funzione obiettivo valutata utilizzando la soluzione attuale). Il crossover è fatto nella speranza che due buone soluzioni, se combinati, possono dare ancora migliore soluzione.

D'altra parte, Simulated Annealing ascolti un'unica soluzione nello spazio delle possibili soluzioni, e ad ogni iterazione considera se spostare a una soluzione vicina o soggiorno in quello corrente secondo alcuni probabilità (che decade nel tempo). Questo è diverso da una ricerca euristica (diciamo ricerca greedy), in quanto non soffre di problemi di ottimo locale dal momento che può scollare i casi in cui tutte le soluzioni sono vicini peggiore di quello attuale.

Answer 3

sono lontano da un esperto di questi algoritmi, ma cercherò di dare una mano.

Penso che la più grande differenza tra i due è l'idea di crossover GA e in modo che qualsiasi esempio di un compito di apprendimento che è più adatto a GA di SA sta per dipendere da quanto mezzo di attraversamento in quella situazione e come viene implementato .

L'idea di crossover è che si può per significato combinare due soluzioni per la produzione di uno migliore. Penso che questo ha senso solo se le soluzioni ad un problema sono strutturati in qualche modo. Potevo immaginare, per esempio, in multi-classe di classificazione prendere due (o più) classificatori che sono bravi a classificare un particolare classe e la loro combinazione con il voto per fare un classificatore molto meglio. Un altro esempio potrebbe essere genetica di programmazione, in cui la soluzione può essere espresso come un albero, ma lo trovo difficile da trovare con un buon esempio in cui è possibile combinare due programmi per creare uno migliore.

Credo che sia difficile trovare una ragione convincente per uno sopra l'altro, perché davvero sono algoritmi molto simili, forse essendo stato sviluppato da molto diversi punti di partenza.