Metodo di confronto e contrasto Monte-Carlo ed algoritmi evolutivi

Question

Qual è il rapporto tra lo Monte-Carlo Method e lo Evolutionary Algorithms? A prima vista sembrano essere metodi di simulazione non correlati utilizzati per risolvere problemi complessi. Per quali tipi di problemi è più adatto? Possono risolvere lo stesso insieme di problemi? Qual è la relazione tra i due (se ce n'è uno)?

Answer 1

"Monte Carlo" è, secondo la mia esperienza, un termine molto sovraccarico. Le persone sembrano usarlo per qualsiasi tecnica che utilizza un generatore di numeri casuali (ottimizzazione globale, analisi degli scenari (Google "Excel Monte Carlo simulazione"), integrazione stocastica (the Pi calculation che tutti usano per dimostrare MC). Credo, perché hai citato algoritmi evolutivi nella tua domanda, stai parlando delle tecniche Monte Carlo per l'ottimizzazione matematica: hai una sorta di funzione fitness con diversi parametri di input e vuoi minimizzare (o massimizzare) quella funzione

Se la tua funzione è ben educata (esiste un unico minimo globale che arriverà a prescindere dagli input con cui inizi), quindi è meglio utilizzare una determinata tecnica di minimizzazione come il metodo del gradiente coniugato. Molte tecniche di classificazione di apprendimento automatico implicano la ricerca di parametri che riducono al minimo piazze errore per un iperpiano rispetto ad un set di allenamento. La funzione che viene ridotta al minimo in questo caso è un parabaloide liscio, ben educato nello spazio n-dimensionale. Calcola il gradiente e rotola in discesa. Vai tranquillo.

Se, tuttavia, i parametri di input sono discreti (o se la funzione di fitness ha interruzioni), non è più possibile calcolare con precisione i gradienti. Questo può accadere se la tua funzione fitness viene calcolata utilizzando dati tabulari per una o più variabili (se la variabile X è inferiore a 0,5 usa questa tabella altrimenti usa quella tabella). In alternativa, potresti avere un programma che hai ricevuto dalla NASA composto da 20 moduli scritti da diversi team che esegui come lavoro batch. Lo fornite con input e sputa un numero (si pensi alla scatola nera). A seconda dei parametri di input che si iniziano con si può finire in un minimo falso. Le tecniche di ottimizzazione globale tentano di risolvere questi tipi di problemi.

Algoritmi evolutivi formano una classe di tecniche global optimization. Le tecniche di ottimizzazione globale in genere prevedono una sorta di "scalata in salita" (accettando una configurazione con una funzione di fitness più alta (peggio)). L'arrampicata in salita comporta in genere casualità/stocasticità/monte-carlo-ness. In generale, queste tecniche hanno maggiori probabilità di accettare configurazioni meno ottimali nelle fasi iniziali e, con il progredire dell'ottimizzazione, sono meno propense ad accettare configurazioni inferiori.

Gli algoritmi evolutivi sono liberamente basati su analogie evolutive. La ricottura simulata si basa su analogie con ricottura nei metalli. Anche le tecniche di sciame di particelle sono ispirate ai sistemi biologici. In tutti i casi dovresti confrontare i risultati con un campionamento casuale semplice (ad es. "Monte carlo") di configurazioni ... questo spesso darà risultati equivalenti.

Il mio consiglio è di iniziare utilizzando una tecnica basata su gradiente deterministico poiché in genere richiedono valutazioni di funzione molto inferiori rispetto alle tecniche stocastico/monte-carlo. Quando senti i passi dello zoccolo, pensa che i cavalli non siano zebre. Esegui l'ottimizzazione da diversi punti di partenza diversi e, a meno che tu non abbia a che fare con un problema particolarmente sgradevole, dovresti ottenere all'incirca lo stesso minimo. In caso contrario, si potrebbero avere zebre e si dovrebbe prendere in considerazione l'utilizzo di un metodo di ottimizzazione globale.

Answer 2

beh, penso che i metodi Monte Carlo sia il nome generico di questi metodi che utilizza numeri casuali per risolvere problemi di ottimizzazione. In questo modo, anche gli algoritmi evolutivi sono un tipo di metodi Monte Carlo se usano numeri casuali (e in effetti lo fanno).

Altri metodi Monte Carlo sono: metropoli, Wang-Landau, tempera parallelo, ecc

Otoh, metodi evolutivi utilizzano preso in prestito dalla natura, come mutazione 'tecniche', cross-over, ecc