VII. Parametri di GA Crossover e mutazione probabilità ci sono due parametri fondamentali di GA - probabilità di crossover e di probabilità di mutazione. probabilità Crossover dice quanto spesso verrà eseguita crossover. Se non c'è crossover progenie è copia esatta dei genitori. Se vi è un crossover, progenie è composto da parti di genitori cromosoma. Se la probabilità di crossover è 100. allora tutto progenie è fatta da crossover. Se è 0. tutto nuova generazione è composto da copie esatte di cromosomi da popolazione anziana (ma questo non significa che la nuova generazione è lo stesso). Crossover è realizzato nella speranza che i nuovi cromosomi avranno buone parti di vecchi cromosomi e magari i nuovi cromosomi sarà migliore. Tuttavia è bene lasciare una parte della popolazione sopravvive alla generazione successiva. probabilità di mutazione dice quanto spesso saranno parti del cromosoma mutato. Se non vi è alcuna mutazione, progenie viene presa dopo attraversamento (o copiare) senza alcuna variazione. Se viene eseguita mutazione, parte del cromosoma è cambiato. Se la probabilità di mutazione è di 100. intero cromosoma è cambiato, se è 0. nulla è cambiato. La mutazione è fatto per evitare di cadere in GA estremo locale, ma non dovrebbe verificarsi molto spesso, perché poi GA sarà infatti il cambiamento di ricerca casuale. Altri parametri Ci sono anche alcuni altri parametri di GA. Un parametro importante è la dimensione della popolazione. La dimensione della popolazione dice quanti cromosomi sono della popolazione (in una sola generazione). Se ci sono troppo pochi cromosomi, GA ha un paio di possibilità per eseguire di crossover e solo una piccola parte di spazio di ricerca è esplorato. D'altro canto, se vi sono troppi cromosomi, GA rallenta. La ricerca mostra che dopo un certo limite (che dipende principalmente codifica e il problema) non è utile per aumentare la dimensione della popolazione, perché non fa risolvere il problema più velocemente. Alcune raccomandazioni per tutti i parametri possono essere trovati in uno dei seguenti capitoli. Esempio Qui potete vedere l'esempio simile a quello precedente. Ma qui si può provare a cambiare di crossover e la mutazione probabilità. È anche possibile controllare elitarismo. Sul grafico qui sotto potete vedere le prestazioni di GA. Il rosso è la soluzione migliore, il blu è il valore medio (fitness) di tutta la popolazione. Prova a modificare i parametri e guarda come si comporta GA. Ecco applet, ma il tuo browser non supporta Java. Se volete vedere le applet, si prega di verificare i requisiti del browser. Domanda: Se si tenta di aumentare la probabilità di mutazione a 100, GA inizia a comportarsi in modo molto strano, quasi come se la probabilità di mutazione è 0. Sapete perché, è possibile utilizzare un suggerimento e se ancora non lo so, guardi soluzione genetica algoritmi sono stati inventati per imitare alcuni dei processi osservati in evoluzione naturale. Molte persone, biologi compresi, si trovano stupito che la vita al livello di complessità che osserviamo potrebbe si sono evoluti nel tempo relativamente breve suggerito dai reperti fossili. L'idea con GA è di usare questo potere di evoluzione per risolvere problemi di ottimizzazione. Il padre del Algorithm originale genetica era John Holland che lo ha inventato nei primi anni 1970. Qual è algoritmi genetici algoritmi genetici (GA) sono adattivo algoritmo di ricerca euristica basata sulle idee evolutive della selezione naturale e della genetica. Come tali rappresentano un intelligente sfruttamento di una ricerca casuale utilizzato per risolvere problemi di ottimizzazione. Anche se randomizzato, gas sono affatto casuale, invece sfruttano le informazioni storiche per dirigere la ricerca nella regione della migliore performance all'interno dello spazio di ricerca. Le tecniche di base del gas sono progettati per simulare i processi nei sistemi naturali necessarie per l'evoluzione, specialmente quelli seguire i principi stabiliti prima da Charles Darwin della sopravvivenza del più forte .. Dal momento che in natura, la concorrenza tra gli individui per le risorse scarse risultati del più forte individui che dominano su quelli più deboli. Perché Algoritmi Genetici È meglio che AI convenzionale che è più robusto. A differenza dei sistemi IA vecchi, non si rompono facilmente anche se gli ingressi leggermente modificati, o in presenza di rumore ragionevole. Inoltre, nella ricerca di un grande stato-spazio, multi-modale dello spazio degli stati, o n-dimensionale di superficie, un algoritmo genetico può offrire notevoli vantaggi rispetto alle più ricerca tipica delle tecniche di ottimizzazione. (Programmazione lineare, euristica, in profondità, respiro prima, e la prassi.) Algoritmi Genetici Panoramica GA simulare la sopravvivenza del più forte tra gli individui oltre generazione consecutiva per risolvere un problema. Ogni generazione è costituito da una popolazione di stringhe di caratteri che sono analoghe a cromosoma che vediamo nel nostro DNA. Ciascun individuo rappresenta un punto in uno spazio di ricerca e una possibile soluzione. Gli individui nella popolazione vengono poi fatti passare attraverso un processo di evoluzione. GA si basano su una analogia con la struttura genetica e il comportamento dei cromosomi all'interno di una popolazione di individui che utilizzano le seguenti basi: individui di una popolazione competono per le risorse e compagni. Quegli individui di maggior successo in ogni gara produrranno più figli di quelle persone che svolgono male. I geni da buoni individui si propagano in tutta la popolazione in modo che due buoni genitori a volte produrre prole che sono meglio di entrambi i genitori. Così ogni generazione diventerà più adatti al loro ambiente. Ricerca Spazio Una popolazione di individualsare viene mantenuta entro spazio di ricerca per un GA, ciascuno dei quali rappresenta una possibile soluzione di un problema. Ogni individuo è codificato come un vettore lunghezza finita di componenti o variabili, in termini di qualche alfabeto, di solito l'alfabeto binario. Per continuare l'analogia genetica questi individui sono paragonati ai cromosomi e le variabili sono analoghi ai geni. Così un cromosoma (soluzione) è composto da vari geni (variabili). Un punteggio fitness è assegnato a ogni soluzione che rappresenta la capacità di un individuo di competere. è richiesta l'individuo con il punteggio di forma fisica ottimale (o in generale nei pressi ottimale). Il GA intende utilizzare allevamento selettivo delle soluzioni per produrre prole meglio dei genitori combinando informazioni dai cromosomi. Il GA mantiene una popolazione di n cromosomi (soluzioni) con valori di fitness associati. I genitori sono selezionati per accoppiarsi, sulla base della loro idoneità, producendo prole attraverso un piano riproduttivo. Soluzioni Di conseguenza altamente fit sono date maggiori opportunità di riprodurre, in modo che i figli ereditano le caratteristiche di ciascun genitore. Come genitori si accoppiano e producono prole, camera deve essere fatta per i nuovi arrivati in quanto la popolazione è mantenuta a una dimensione statica. Gli individui nella popolazione muoiono e vengono sostituite dalle nuove soluzioni, creando alla fine una nuova generazione, una volta tutte le opportunità di accoppiamento nella popolazione anziana sono state esaurite. In questo modo si spera che nel succedersi delle generazioni soluzioni migliori prosperano mentre le soluzioni meno in forma muoiono. Le nuove generazioni di soluzioni sono prodotte contenente, in media, più buoni geni di una tipica soluzione in una generazione precedente. Ogni generazione successiva conterrà più buone soluzioni parziali rispetto alle generazioni precedenti. Alla fine, una volta che la popolazione è convergente e non è la produzione di prole sensibilmente diversi da quelli nelle generazioni precedenti, lo stesso algoritmo si dice che abbia la convergenza a un insieme di soluzioni al problema in questione. Dettagli di implementazione basata sulla selezione naturale dopo una popolazione iniziale viene generato in modo casuale, l'algoritmo evolve il tramite tre operatori: selezione che equivale alla sopravvivenza del crossover più forte che rappresenta l'accoppiamento tra individui mutazione che introduce modifiche casuali. 1. Selezione operatore idea chiave: dare prefrence agli individui migliori, permettendo loro di passare i loro geni alla generazione successiva. La bontà di ogni individuo dipende dalla sua forma fisica. Fitness può essere determinata da una funzione obiettivo o un giudizio soggettivo. 2. Crossover Operatore Primo fattore distinto di GA da altre tecniche di ottimizzazione Due individui sono scelti dalla popolazione utilizzando l'operatore di selezione Un sito incrociato lungo le stringhe di bit è scelto a caso i valori delle due stringhe vengono scambiati fino a questo punto Se S1000000 e s2111111 e il punto di crossover è 2 allora S1110000 e s2001111 I due nuovi figli creato da questo accoppiamento sono messi nella prossima generazione della popolazione per ricombinare porzioni di buone persone, questo processo rischia di creare ancora migliori individui 3. la mutazione operatore con qualche basso probabilità, una parte dei nuovi individui avranno alcuni dei loro bit capovolto. Il suo scopo è quello di mantenere la diversità nella popolazione e inibire convergenza prematura. La mutazione da sola induce una passeggiata casuale attraverso la mutazione spazio di ricerca e selezione (senza crossover) di creare un parallelo, rumore-tolerant, in salita algoritmi di effetti di operatori genetici Utilizzo di selezione solo tenderanno a riempire la popolazione con le copie del miglior individuo dal popolazione Uso degli operatori di selezione e di crossover tenderà a causare gli algoritmi a convergere su una soluzione buona, ma non ottimale Utilizzando mutazione da sola induce una passeggiata casuale attraverso lo spazio di ricerca. Utilizzando la selezione e la mutazione crea un Parrallel, rumore-tolerant, collina arrampicata algoritmo algoritmi di inizializzazione in modo casuale popolazione (t) determinare l'idoneità fisica della popolazione (t) ripetere selezionare genitori da parte della popolazione (t) eseguire crossover genitori creando popolazione (t1) eseguire mutazione popolazione (t1) determinare l'idoneità fisica della popolazione (t1) fino migliore individuale è abbastanza buono Nel comma precedente è stato affermato che tramite le operazioni di selezione, incrocio, e la mutazione GA convergeranno nel succedersi delle generazioni verso il globale (o quasi globale) optium. perché questi semplice operazione dovrebbe produrre un veloce, utili e robusti techiques è dovuto al fatto che il gas combinano direzione e la possibilità nella ricerca in modo efficace ed efficiente. Poiché la popolazione contiene implicitamente molte più informazioni che semplicemente i punteggi individuali della palestra, gas combinare la buona informazione nascosta in una soluzione con buone informazioni da un'altra soluzione per la produzione di nuove soluzioni con buona indormation ereditato da entrambi i genitori, inevitabilmente (si spera) che porta towrads ottimalità. La capacità dell'algoritmo di esplorare e sfruttare contemporaneamente, una crescente quantità di giustificazione teorica, e l'applicazione di successo per i problemi del mondo reale rafforza la conclusione che il gas sono un potente robusta tecnica, l'ottimizzazione. Un'introduzione al Algoritmi Genetici. MIT Press a cura di algoritmi genetici Melanie Mitchell in ingegneria e informatica a cura di G. inverno. et al .. Fondazioni c1995 di algoritmi genetici a cura di Gregory J. E. Rawlins. c1991 per l 'applicabilità di algoritmi genetici, si prega di fare riferimento al mio partner, Chun s article. Genetic Algoritmi in Plain English Lo scopo di questo tutorial è quello di spiegare gli algoritmi genetici sufficientemente per poter essere in grado di usarli nei vostri progetti. Si tratta di un stripped-down to-the-bare-essenziali tipo di tutorial. Im non intenzione di andare in una grande quantità di profondità e Im non andare a spaventare quelli di voi con ansia per la matematica gettando le equazioni del male a voi ogni poche frasi. Infatti, Im non andare a buttare qualsiasi equazioni brutte su di te a tutti non in questo particolare esercitazione in ogni caso. ltsmilegt Questo tutorial è stato progettato per essere letto attraverso due volte. quindi non preoccupatevi se poco ha senso la prima volta che si studia di esso. (Un lettore, Daniel, ha gentilmente tradotto questo tutorial in tedesco. Lo si può trovare qui.) (Un altro lettore, David Lewin, ha tradotto il tutorial in francese. Lo si può trovare qui.) In primo luogo, una lezione di biologia Ogni organismo ha un insieme di regole, un progetto per così dire, descrivendo come tale organismo è costruita dai piccoli mattoni della vita. Queste regole sono codificati nei geni di un organismo, che a loro volta sono collegati insieme in lunghe stringhe chiamate cromosomi. Ogni gene rappresenta un tratto specifico dell'organismo, come il colore degli occhi o il colore dei capelli, e ha diverse impostazioni diverse. Ad esempio, le impostazioni per un gene colore dei capelli può essere biondo, nero o color rame. Questi geni e le loro impostazioni sono solitamente denominati come il genotipo organismi. L'espressione fisica del genotipo - l'organismo stesso - si chiama il fenotipo. Quando due organismi si accoppiano condividono i loro geni. La prole risultante può finire per avere la metà dei geni di un genitore e metà dall'altra. Questo processo è chiamato ricombinazione. Molto raramente un gene può essere mutato. Normalmente questo gene mutato non influenzerà lo sviluppo del fenotipo, ma molto raramente si sarà espressa nell'organismo come una nuova caratteristica. La vita sulla terra è evoluto per essere in quanto è attraverso i processi di selezione naturale, ricombinazione e mutazione. Per illustrare come questi processi lavorano insieme per produrre la vasta gamma di flora e fauna che condividiamo il nostro pianeta con lasciate che vi dica un po 'di storia. C'era una volta viveva una specie di creature chiamate Hooters. Hooters era evoluta interamente entro i confini bui di un vasto sistema di grotte nascoste nel profondo delle viscere di una catena montuosa. Theyd ha avuto una vita facile, sentire e odorare intorno alle pareti della grotta umide per le alghe hanno tanto amato da mangiare, trasudano tra le rocce e, al momento dell'accoppiamento, ascoltando attentamente i fischi delle altre Hooters. Non c'erano predatori nelle grotte, era solo il Hooters, le alghe e la lumaca amichevole occasionale, in modo che il Hooters non ha mai avuto nulla da temere (tranne forse l'occasionale Hooter temperato male). Un fiume sotterraneo scorreva attraverso il sistema di grotte e l'acqua continuamente gocciolava attraverso la tabella di acqua portando con sé i nutrienti fresche le alghe prosperato così c'era sempre un sacco di mangiare e bere. Tuttavia, anche se Hooters potevano sentire e ascoltare bene non hanno mai avuto alcuna necessità di occhi nel buio passo delle grotte e di conseguenza erano completamente cieco. Questo non sembrava riguardare una delle Hooters e anche se tutti avevano una balena di un tempo sgranocchiare via e clacson nel buio. Poi un giorno un terremoto ha causato una parte del sistema di grotte al collasso e per la prima volta in molti millenni l'Hooters sentiva il calore del sole sulla loro pelle e l'elasticità morbida di muschio sotto i loro piedi. Alcuni Hooters audace assaggiato il muschio e ha scoperto che si trattava di mangiare anche meglio di alghe grotta. quotOooooooooohquot che fischiarono tra un boccone di muschio e prontamente ma ho inghiottito dalle aquile predoni che avevano volato per vedere che cosa tutto il trambusto era circa. Per un po 'sembrava che il Hooters può essere cacciato fino all'estinzione, anche se per gli piaceva mangiare il muschio non avrebbero mai potuto dire se l'aquila volava sopra. Non solo, hanno potuto anche dire se sono stati nascosti sotto una roccia o no a meno che non era abbastanza basso da raggiungere per i loro antenne. Ogni giorno molti Hooters sarebbe inciampare fuori dalle grotte con il dolce profumo di muschio nelle loro narici solo per essere rapidamente portato via e mangiati da un'aquila. La loro situazione sembrava triste davvero. Fortunatamente, nel corso degli anni, la popolazione di Hooters era cresciuto fino a essere enorme nella sicurezza delle grotte e abbastanza di loro sono stati superstiti di accoppiarsi - dopo tutto, un'aquila può solo mangiare così tanto. Un giorno, una nidiata di Hooters è nato che ha condiviso un gene mutato cellule della pelle. Questo particolare gene è stato responsabile per lo sviluppo delle cellule della pelle sulla fronte. Durante lo sviluppo del bambino Hooters, quando le loro cellule cresciute dalle istruzioni geni mutati erano leggermente sensibile alla luce. Ogni nuovo Hooter bambino potrebbe percepire se qualcosa stava bloccando la luce per la sua fronte o meno. Quando questi piccolo bambino Hooters è cresciuto in Hooters più grandi e si avventurò nella luce di mangiare il muschio si potrebbe dire se qualcosa è stato piombando in testa o no. Così questi Hooters è cresciuto fino ad avere un po 'migliore possibilità di sopravvivenza rispetto ai loro cugini completamente ciechi. E perché avevano una migliore possibilità di sopravvivenza, hanno riprodotto molto di più, quindi, passando il nuovo gene delle cellule della pelle sensibile alla luce per la loro prole. Dopo un brevissimo mentre la popolazione divenne dominato dalla Hooters con questo leggero vantaggio. Ora lascia zip qualche migliaio di generazioni nel futuro. Se si estrapolare questo processo più moltissimi anni e che coinvolgono un sacco di piccole mutazioni che avvengono nei geni delle cellule della pelle è facile immaginare un processo in cui una cellula sensibile alla luce può diventare un grumo di cellule sensibili alla luce, e quindi come le cellule interne del ciuffo possono mutare per indurire in una piccola lente di un'area a forma, che aiuterebbe a raccogliere la luce e concentrarsi in un unico luogo. La sua non è troppo difficile immaginare una mutazione che dà origine a due di queste aree di raccolta della luce elargendo così la visione binoculare sui Hooters. Questo sarebbe un enorme vantaggio rispetto ai loro cugini Cyclopsian come Hooters sarebbe ora in grado di valutare le distanze in modo accurato e hanno una maggiore campo visivo. Come si può vedere i processi di selezione naturale - la sopravvivenza del più forte - e la mutazione del gene hanno ruoli molto potenti per giocare nell'evoluzione di un organismo. Ma come funziona la ricombinazione in forma nello schema delle cose bene per dimostrare che ho bisogno di raccontare alcune altre Hooters. A circa lo stesso tempo le Hooters con le cellule sensibili alla luce sono stati amoreggiare in giro per il muschio e prendere in giro le aquile, un'altra nidiata di Hooters era nato che ha condiviso un gene mutato che ha colpito la loro clacson. Questa mutazione ha dato luogo a una sirena leggermente più grande rispetto ai loro cugini, e perché era più grande che potrebbe ora spasso su lunghe distanze. Questa si è rivelata utile nel popolazione in rapida diminuzione a causa delle Hooters con le Hooters più grandi potevano chiamare i potenziali compagni situati lontano. Non solo, ma le Hooters femminile ha cominciato a mostrare una leggera preferenza per i maschi con hooters più grandi. Il risultato di questo, naturalmente, è che il più dotati Hooters si trovava una migliore possibilità di accoppiamento di qualsiasi non così bene Hooters. In un periodo di tempo, grandi hooters divenne prevalente nella popolazione. Poi un bel giorno un Hooter femminile con il gene per le cellule della pelle sensibili alla luce incontrato un Hooter maschio con il gene per la produzione di grandi hooters. Si innamorarono, e poco dopo hanno prodotto una nidiata di bambino bella Hooters. Ora, perché i bambini cromosomi erano una ricombinazione di entrambi i genitori cromosomi, alcuni dei bambini hanno condiviso entrambi i geni speciali e cresciuto, non solo per avere le cellule della pelle sensibili alla luce, ma enorme hooters troppo Questi nuovi prole erano estremamente bene ad evitare le aquile e riproducendo così il processo di evoluzione cominciò a favorire loro e ancora una volta questo nuovo tipo perfezionato di Hooter divenne dominante nella popolazione. E così via. E così via. Gli algoritmi genetici sono un modo di risolvere i problemi imitando gli stessi processi di madre natura utilizza. Essi utilizzano la stessa combinazione di selezione, ricombinazione e mutazione di evolvere una soluzione ad un problema. Neat eh Girare pagina per scoprire esattamente come il suo fare.
No comments:
Post a Comment