Quali sono buoni esempi di algoritmi genetici/soluzioni di programmazione genetica?[Chiuso]

StackOverflow https://stackoverflow.com/questions/1538235

Domanda

Algoritmi genetici (GA) e programmazione genetica (GP) sono interessanti aree di ricerca.

Mi piacerebbe sapere quali problemi specifici hai risolto utilizzando GA/GP e quali librerie/framework hai utilizzato se non ne hai creato uno tuo.

Domande:

  • Quali problemi hai utilizzato GA/GP per risolvere?
  • Quali librerie/framework hai utilizzato?

Sto cercando esperienze di prima mano, quindi per favore non rispondere a meno che tu non le abbia.

È stato utile?

Soluzione

non i compiti a casa.

Il mio primo lavoro come programmatore professionista (1995) era la scrittura di un sistema di trading automatico basato genetico-algoritmo per i futures S & P500. L'applicazione è stata scritta in Visual Basic 3 [!] E non ho idea di come ho fatto nulla allora, dal momento che VB3 non aveva nemmeno le classi.

L'applicazione avviata con una popolazione di stringhe generate in modo casuale a lunghezza fissa (la parte "gene"), ciascuno dei quali corrispondeva ad una forma specifica nei dati prezzo minuto per minuto delle future S & P500, nonché un ordine specifico (comprare o vendere) e stop-loss e stop-profit quantità. Ogni stringa (o "gene") ha avuto le sue prestazioni profitto valutati da una corsa attraverso 3 anni di dati storici; ogni volta che la "forma" specificato abbinato i dati storici, ho assunto l'acquisto corrispondente o ordine di vendita e valutato il risultato del commercio. Ho aggiunto l'avvertenza che ogni gene iniziato con una quantità fissa di denaro e potrebbe quindi potenzialmente andare rotto e rimossa dal pool genetico interamente.

Dopo ogni valutazione di una popolazione, i sopravvissuti sono stati incrociati casualmente (da bit appena miscelazione da due genitori), con la probabilità di un gene essere selezionato come genitore essendo proporzionale al profitto ha prodotto. Ho anche aggiunto la possibilità di mutazioni puntiformi per rendere le cose un po '. Dopo poche centinaia di generazioni di questo, ho finito con una popolazione di geni che potrebbero trasformare $ 5000 in una media di circa 10000 $ con nessuna possibilità di morte / brokeness (sui dati storici, ovviamente).

Purtroppo, non ho mai avuto la possibilità di utilizzare questo sistema vivo, dal momento che il mio capo ha perso quasi $ 100.000 in meno di 3 mesi di negoziazione in modo tradizionale, e ha perso la sua volontà di continuare con il progetto. Col senno di poi, credo che il sistema avrebbe fatto enormi profitti - non perché stavo necessariamente facendo qualcosa di giusto, ma perché la popolazione di geni che ho prodotto è capitato di essere sbilanciata verso ordini di acquisto (in contrapposizione a vendere gli ordini) di circa un 5: 1 ratio. E come sappiamo con la nostra 20/20 senno di poi, il mercato è andato un po 'dopo il 1995.

Altri suggerimenti

Ho fatto un po 'di creature che vivevano in questo piccolo mondo. Avevano un cervello rete neurale che ha ricevuto alcuni input dal mondo e l'uscita era un vettore per il movimento tra le altre azioni. I loro cervelli sono stati i "geni".

Il programma è iniziato con una popolazione casuale di creature con cervelli casuali. Gli ingressi e neuroni uscita erano statica ma ciò che era tra non era.

L'ambiente conteneva cibo e pericoli. Il cibo aumento di energia e quando si ha abbastanza energia, si può accoppiarsi. I pericoli potrebbero ridurre l'energia e se l'energia è stata dello 0, sono morti.

Alla fine le creature si sono evoluti per spostare tutto il mondo e trovare cibo ed evitare i pericoli.

Ho quindi deciso di fare un piccolo esperimento. Ho dato il cervello creatura un neurone di output chiamato "bocca" e di un neurone di input chiamato "orecchio". Iniziato corso e sono rimasto sorpreso di scoprire che si sono evoluti per ottimizzare lo spazio e ciascuna rispettiva creatura sarebbe rimasto nella rispettiva parte (il cibo è stato posto in modo casuale). Hanno imparato a cooperare tra loro e non entrare in ogni modo altri. C'erano sempre le eccezioni.

Poi ho provato qualcosa di interessante. I creature morte sarebbero diventati cibo. Provate ad indovinare cosa è successo! Due tipi di creature evolute, quelle che hanno attaccato come in sciami, e quelli che erano ad alto evitamento.

Allora, qual è la lezione qui? Dei mezzi di comunicazione di cooperazione. Non appena si introduce un elemento in cui ferire un altro significa che si guadagna qualcosa, poi la cooperazione è distrutta.

Mi chiedo come questo riflette sul sistema del libero mercato e il capitalismo. Voglio dire, se le aziende possono danneggiare la loro concorrenza e farla franca , quindi il suo chiaro faranno tutto quanto in loro potere per ferire la concorrenza.

Modifica:

L'ho scritto in C ++ utilizzando non quadri. Ha scritto la mia rete neurale e il codice GA. Eric, grazie per dicendo che è plausibile. La gente di solito non credono nei poteri del GA (anche se i limiti sono evidenti) fino a quando hanno giocato con esso. GA è semplice ma non semplicistico.

Per gli scettici, reti neurali hanno dimostrato di essere in grado di simulare qualsiasi funzione se hanno più di uno strato. GA è un modo piuttosto semplice da navigare uno spazio soluzione di trovare minimo locale e potenzialmente globale. Combinare GA con reti neurali e si dispone di un buon modo per trovare le funzioni che trovano soluzioni approssimate per problemi generici. Perché utilizziamo reti neurali, allora stiamo ottimizzando la funzione per alcuni input, non alcuni input ad una funzione come altri stanno utilizzando GA

Ecco il codice demo per l'esempio di sopravvivenza: http: //www.mempko .com / darcs / neurale / demo / mangiatori / Costruire istruzioni:

  • Installa darcs, libboost, liballegro, gcc, cmake, rendono
  • darcs clone --lazy http://www.mempko.com/darcs/neural/
  • cd neural
  • cmake .
  • make
  • cd demos/eaters
  • ./eaters

Eaters Schermata

Nel gennaio del 2004, sono stato contattato da Philips nuove tecnologie di visualizzazione che stavano creando l'elettronica per la prima e-ink mai commerciale, il Sony Librie, che era stato rilasciato solo in Giappone, anni prima Amazon Kindle e gli altri ha colpito il mercato negli Stati Uniti un Europa.

Gli ingegneri di Philips hanno avuto un grosso problema. Pochi mesi prima che il prodotto avrebbe dovuto colpire il mercato, che stavano ancora ricevendo ghosting sullo schermo quando si cambia pagine. Il problema era i driver 200 che sono stati la creazione del campo elettrostatico. Ognuno di questi piloti hanno avuto una certa tensione che doveva essere situato proprio tra zero e 1000 mV o qualcosa di simile. Ma se è stato modificato uno di loro, sarebbe cambiato tutto.

Quindi, ottimizzare la tensione di ogni conducente era singolarmente fuori questione. Il numero di possibili combinazioni di valori era in miliardi, e ci sono voluti circa 1 minuto per una macchina fotografica speciale per valutare una singola combinazione. Gli ingegneri avevano provato molte tecniche di ottimizzazione standard, ma nulla sarebbe venuto vicino.

L'ingegnere capo mi ha contattato perché avevo precedentemente rilasciato una libreria di programmazione genetica alla comunità open-source. Mi ha chiesto se GP / GA del avrebbe aiutato e se potessi essere coinvolto. L'ho fatto, e per circa un mese abbiamo lavorato insieme, me la scrittura e la messa a punto della biblioteca GA, su dati sintetici, e l'integrandolo nel loro sistema. Poi, un fine settimana hanno lasciato correre dal vivo con la cosa reale.

Il seguente Lunedi ho ottenuto queste email incandescente da lui e il loro progettista hardware, di come nessuno poteva credere che i risultati sorprendenti GA trovato. Era questo. Nello stesso anno il prodotto ha colpito il mercato.

Non ho pagato un centesimo per questo, ma ho ottenuto 'vantarsi' diritti. Hanno detto che fin dall'inizio erano già fuori budget, quindi sapevo cosa la trattativa era prima ho iniziato a lavorare su di esso. Ed è una grande storia per le applicazioni di gas. :)

Ho utilizzato un GA per ottimizzare l'assegnazione dei posti al mio ricevimento di nozze.80 ospiti su 10 tavoli.La funzione di valutazione si basava sul mantenere le persone con i loro appuntamenti, mettere insieme le persone con qualcosa in comune e tenere le persone con punti di vista estremamente opposti in tavoli separati.

L'ho eseguito diverse volte.Ogni volta ho ottenuto nove buoni tavoli e uno con tutte le palline dispari.Alla fine, mia moglie ha assegnato i posti a sedere.

Il mio ottimizzatore da venditore ambulante ha utilizzato una nuova mappatura dei cromosomi rispetto all'itinerario, che ha reso banale l'allevamento e la mutazione dei cromosomi senza alcun rischio di generare tour non validi.

Aggiornamento:Perché un paio di persone hanno chiesto come...

Inizia con una serie di ospiti (o città) in un ordine arbitrario ma coerente, ad esempio in ordine alfabetico.Chiamatela la soluzione di riferimento.Pensa all'indice di un ospite come al numero del suo posto.

Invece di provare a codificare questo ordinamento direttamente nel cromosoma, codifichiamo le istruzioni per trasformare la soluzione di riferimento in una nuova soluzione.Nello specifico, trattiamo i cromosomi come elenchi di indici nell'array da scambiare.Per decodificare un cromosoma, iniziamo con la soluzione di riferimento e applichiamo tutti gli scambi indicati dal cromosoma.Lo scambio di due voci nell'array risulta sempre in una soluzione valida:ogni ospite (o città) appare comunque esattamente una volta.

Pertanto i cromosomi possono essere generati, mutati e incrociati in modo casuale con altri e produrranno sempre una soluzione valida.

Ho usato algoritmi genetici (come pure alcune tecniche correlate) per determinare le migliori impostazioni per un sistema di gestione del rischio che ha cercato di mantenere gli agricoltori d'oro di usare carte di credito rubate per pagare MMO. Il sistema prenderebbe in diverse migliaia di operazioni con valori "noti" (frode o meno) e capire che cosa la migliore combinazione di impostazioni è stato quello di individuare correttamente le transazioni fraudolente senza avere troppi falsi positivi.

Abbiamo avuto i dati su diverse decine (booleano) caratteristiche di un'operazione, ognuno dei quali è stato dato un valore e sommati. Se il totale era superiore ad una soglia, l'operazione è stata frode. Il GA creerebbe un gran numero di gruppi casuali di valori, valutarle contro un corpus di dati noti, selezionare quelli che hanno ottenuto il migliore (sia il rilevamento delle frodi e limitando il numero di falsi positivi), poi croce razza il meglio alcuni da ogni generazione per la produzione di una nuova generazione di candidati. Dopo un certo numero di generazioni il miglior set di punteggio di valori è stato considerato il vincitore.

Creare il corpus di dati noti per testare contro era il tallone d'Achille del sistema. Se avete aspettato per chargeback, eravate diversi mesi alle spalle quando si cerca di rispondere ai truffatori, così qualcuno avrebbe dovuto rivedere manualmente un gran numero di transazioni per costruire quel corpus di dati senza dover aspettare troppo a lungo.

Questo ha finito per identificare la stragrande maggioranza della frode che è entrato, ma non riusciva a farlo sotto l'1% sulle voci più frode incline (dato che il 90% delle transazioni in entrata potrebbe essere la frode, che stava facendo abbastanza bene).

Ho fatto tutto questo utilizzando Perl. Una corsa del software su un abbastanza vecchia scatola di linux prenderebbe 1-2 ore per l'esecuzione (20 minuti per caricare i dati su un collegamento WAN, il resto del tempo trascorso scricchiolio). La dimensione di ogni data generazione è stata limitata dalla RAM disponibile. Mi piacerebbe correre più e più volte con lievi modifiche ai parametri, alla ricerca di un buon set di risultati particolarmente.

Tutto sommato è evitato alcune delle gaffe che è venuto con il tentativo di modificare manualmente i valori relativi di decine di indicatori di frode, e coerentemente si avvicinò con soluzioni migliori di quanto ho potuto creare a mano. AFAIK, è ancora in uso (circa 3 anni dopo l'ho scritto).

Calcio Tipping. Ho costruito un sistema di GA per prevedere la settimana in settimana risultato dei giochi nella AFL (Aussie Rules Football).

Alcuni anni fa mi sono stufato del pool di lavoro di calcio di serie, ognuno stava solo andando on-line e prendere le scelte da qualche opinionista nella stampa. Così, ho pensato che non poteva essere troppo difficile da battere un gruppo di major giornalismo televisivo, giusto? Il mio primo pensiero è stato quello di prendere i risultati di Massey Valutazioni e poi rivelare alla fine della stagione mia strategia dopo aver vinto fama e gloria. Tuttavia, per ragioni non ho mai scoperto Massey non tiene AFL. Il cinico in me crede che sia perché il risultato di ogni partita AFL ha praticamente diventato casualità, ma le mie lamentele delle recenti modifiche delle regole appartengono in un forum diverso.

Il sistema sostanzialmente considerato forza offensivo, forza difensiva, vantaggio campo di casa, una settimana all'altra miglioramento (o mancanza) e la velocità di modifiche a ciascuna di esse. Questo ha creato un insieme di equazioni polinomiali per ogni squadra nel corso della stagione. Il vincitore e il punteggio per ogni partita per una determinata data potrebbe essere calcolate. L'obiettivo era quello di trovare il set di coefficienti che la maggior parte strettamente allineato l'esito di tutti i giochi del passato e l'uso che insieme per prevedere la prossima settimana di gioco.

In pratica, il sistema sarebbe trovare soluzioni che previsto con precisione oltre il 90% dei risultati del gioco del passato. Sarebbe poi scegliere con successo circa il 60-80% dei giochi per la settimana prossima (che è la settimana non nel training set).

Il risultato: appena sopra mezzo al gruppo. Nessun grande premio in denaro, né un sistema che potrei usare per battere Vegas. E 'stato divertente però.

Ho costruito tutto da zero, nessun quadro utilizzato.

Così come alcuni dei problemi più comuni, come il commesso viaggiatore e di una variazione su di Roger Alsing programma Mona Lisa , ho anche scritto un solutore evolutivo Sudoku (che ha richiesto un po 'più di pensiero originale da parte mia, e non solo ri-attuazione di qualcun altro idea). Ci sono algoritmi più affidabili per risolvere Sudoku, ma l'approccio evolutivo funziona abbastanza bene.

In questi ultimi giorni ho giocato in giro con un programma evolutivo di trovare "ponti freddo" per il poker dopo aver visto questo articolo su Reddit. Non è del tutto soddisfacente al momento, ma penso di poter migliorare.

mia quadro che uso per algoritmi evolutivi.

Ho sviluppato un GA birra fatta in casa per un sistema di profilo di superficie laser 3D la mia azienda ha sviluppato per il settore del trasporto merci nel 1992. Il sistema invocata 3 triangolazione dimensionale e utilizzato uno scanner a linea laser personalizzato, una macchina fotografica 512x512 (con cattura hw personalizzato). La distanza tra la fotocamera e il laser è stato mai sta per essere preciso e il punto focale delle telecamere non dovesse essere trovato nel 256.256 posizione che ti aspettavi di essere!

E 'stato un incubo per cercare di risolvere i parametri di calibrazione utilizzando geometria standard e simulato risolvendo l'equazione stile ricottura.

L'algoritmo genetico è stata montata in una serata e ho creato un cubo di calibrazione per testarlo su. Sapevo le dimensioni del cubo ad alta precisione e quindi l'idea era che la mia GA possa evolvere un insieme di parametri triangolazione personalizzati per ogni unità di scansione in grado di superare le variazioni di produzione.

Il trucco ha funzionato a meraviglia. Ero sbalordito a dir poco! Entro circa 10 generazioni mio cubo 'virtuale' (generato dalla scansione crudo e ricreato dai parametri di calibrazione) in realtà sembrava un cubo! Dopo circa 50 generazioni ho avuto la taratura di cui avevo bisogno.

Il suo spesso difficile da ottenere una combinazione esatta di colore quando si prevede di dipingere la vostra casa. Spesso, avete un po 'di colore in mente, ma non è uno dei colori, il venditore vi mostra.

Ieri, il mio prof che è un ricercatore GA accennato circa una storia vera in Germania (mi dispiace, non ho ulteriori riferimenti, sì, lo può trovare fuori se uno richieste a). Questo ragazzo (chiamiamolo di colore ragazzo ) consente di passare da porta a porta per aiutare le persone a trovare il codice colore esatto (in RGB ) che sarebbe l'armadio per ciò che il cliente aveva in mente. Ecco come lo avrebbe fatto:

di colore ragazzo utilizzato per trasportare con sé un programma software che ha usato GA. Ha usato per iniziare con 4 colors- diverso ogni codificato come un cromosoma codificato (il cui valore decodificato sarebbe un valore RGB). Il consumatore sceglie 1 dei 4 colori (che è il più vicino a cui lui / lei ha in mente). Il programma dovrebbe quindi assegnare la massima Fitness per che individuale e passare alla prossima generazione con mutazione / Crossover . I passaggi di cui sopra sarebbero ripetuti fino al consumatore aveva trovato il colore esatto e quindi color ragazzo utilizzati per dirgli la combinazione RGB!

Con l'assegnazione di massima idoneità al colore chiude a ciò che il consumatore ha in mente, il programma color ragazzo s 'è in aumento le possibilità di convergere al colore, il consumatore ha in mente esattamente. L'ho trovato abbastanza divertente!

Ora che ho un -1, se si sta progettando per ulteriori -1 di, pls. chiarire il motivo per farlo!

Come parte del mio corso di laurea CompSci, ci hanno assegnato il problema di trovare bandiere JVM ottimali per la ricerca macchina virtuale Jikes. Questa è stata valutata utilizzando la suite di benchmark Dicappo che restituisce un tempo per la console. Ho scritto un alogirthm gentic distribuita che commutato questi flag per migliorare il tempo di esecuzione della suite di benchmark, anche se ci sono voluti giorni per correre per compensare il jitter hardware influisce sui risultati. L'unico problema è stato che non ha adeguatamente conoscere la teoria del compilatore (che era l'intento della cessione).

avrei potuto seminato la popolazione iniziale con i exisiting bandiere di default, ma la cosa interessante è che l'algoritmo ha trovato una configurazione molto simile al livello di ottimizzazione O3 (ma in realtà era più veloce in molti test).

Modifica:. Inoltre ho scritto il mio quadro algoritmo genetico in Python per l'assegnazione, e appena usato i comandi popen per eseguire i vari parametri di riferimento, anche se non era un incarico valutata avrei guardato pyEvolve

Prima di tutto, "Programmazione Genetica" di Jonathan Koza ( su Amazon ) è più o meno il libro sulle tecniche di algoritmo / programmazione genetici ed evolutivi, con molti esempi. Consiglio vivamente di estrarlo.

Per quanto riguarda il mio uso di un algoritmo genetico, ho usato un (casa coltivata) algoritmo genetico di sviluppare un algoritmo di sciame per un / scenario di distruzione di raccolta oggetto (scopo pratico potrebbe essere stata l'eliminazione di un campo minato). Ecco un link la carta . La parte più interessante di quello che ho fatto è stata la funzione di fitness multi-messa in scena, che era una necessità in quanto le semplici funzioni di fitness non hanno fornito informazioni sufficienti per l'algoritmo genetico per differenziare a sufficienza tra i membri della popolazione.

Un paio di settimane fa, ho proposto una soluzione su SO utilizzando algoritmi genetici per risolvere un problema di aspetto grafico. Si tratta di un esempio di un problema di ottimizzazione vincolata.

Inoltre, nella zona di machine learning, ho implementato un quadro regole di classificazione GA-based in C / C ++ da zero.
Ho anche usato GA in un progetto di esempio per la formazione Reti Neurali Artificiali (ANN), in opposizione per usare la famosa backpropagation algoritmo .

In aggiunta, e come parte della mia ricerca di laurea, ho usato GA in allenamento Hidden Markov Models come un ulteriore approccio alla EM-based Baum-Welch algoritmo (in C / C ++ di nuovo).

Sono parte di una squadra di indagare l'uso di Evolutionary Computation (CE) per correggere automaticamente errori in programmi esistenti. Abbiamo riparato con successo una serie di bug reali in progetti di software del mondo reale (vedi homepage di questo progetto ).

Abbiamo due applicazioni di questa tecnica di riparazione CE.

  • La prima ( codice e le informazioni di riproduzione disponibili attraverso la pagina del progetto ) evolve l'albero sintattico astratto analizzati da programmi C esistenti e viene implementata in OCaml utilizzando il nostro proprio motore EC personalizzato.

  • Il secondo ( codice e le informazioni di riproduzione disponibili attraverso la pagina del progetto ), il mio contributo personale al progetto, si evolve l'assembly x86 o bytecode Java compilato da programmi scritti in un certo numero di linguaggi di programmazione. Questa applicazione è implementata in Clojure e utilizza anche il proprio personalizzato costruito il motore EC.

Un bel aspetto del calcolo evolutivo è la semplicità della tecnica permette di scrivere le proprie implementazioni personalizzate senza troppe difficoltà. Per un buon liberamente disponibile testo introduttivo sulla programmazione genetica vedere la Field Guide di Programmazione Genetica .

Un collega ed io stiamo lavorando su una soluzione per il carico di merci su camion utilizzando i vari criteri nostra società richiede. Ho lavorato su una soluzione algoritmo genetico, mentre lui sta usando un ramo e legato con la potatura aggressivo. Siamo ancora in fase di implementazione di questa soluzione, ma finora, stiamo ottenendo buoni risultati.

Alcuni anni fa ho usato ga di ottimizzare ASR grammatiche (Automatic Speech Recognition) per i tassi di riconoscimento migliori. Ho iniziato con abbastanza semplici liste di scelte (dove la ga stava testando combinazioni di possibili termini per ogni slot) e lavorato la mia strada fino a grammatiche più aperti e complessi. Fitness è stato determinato misurando separazione tra termini / sequenze sotto un tipo di funzione fonetica distanza. Ho anche sperimentato con fare variazioni debolmente equivalenti su una grammatica per trovare uno che ha compilato per una rappresentazione più compatta (alla fine sono andato con un algoritmo diretta, ed è drasticamente aumentato la dimensione del "linguaggio" che potremmo usare in applicazioni) .

Più recentemente ho loro utilizzato come ipotesi predefinito contro cui verificare la qualità delle soluzioni generate da vari algoritmi. Questo ha categorizzazione in gran parte coinvolti e diversi tipi di problemi di montaggio (vale a dire creare una "regola" che spiega una serie di scelte fatte da revisori nel corso di un set di dati (s)).

Ho fatto un quadro completo GA denominato "GALAB", per risolvere molti problemi:

  • Individuazione ANT GSM (BTS) per diminuire la sovrapposizione e posizioni vuote.
  • pianificazione del progetto vincolo delle risorse.
  • creazione quadro evolutivo. ( Evopic )
  • problema del commesso viaggiatore.
  • N-Queen & N-Color problemi.
  • del cavaliere del tour e zaino problemi.
  • Magic Square e puzzle di Sudoku.
  • compressione stringa, sulla base di problema superstringhe.
  • problema 2D Imballaggio.
  • piccolo artificiale APP vita.
  • di puzzle Rubik.

Una volta ho usato un GA per ottimizzare una funzione di hash per gli indirizzi di memoria. Gli indirizzi erano 4K o 8K dimensioni di pagina, in modo da hanno mostrato una certa prevedibilità nel modello di bit dell'indirizzo (bit meno significativi tutti a zero; bit di mezza incrementare regolarmente, ecc) La funzione di hash originale era "grosso" - tendeva a raggrupparsi colpi su ogni terzo secchio di hash. Il migliorato algoritmo ha avuto una distribuzione quasi perfetta.

Non so se i compiti conta ...

Durante i miei studi abbiamo implementato il nostro programma per risolvere il problema del commesso viaggiatore.

L'idea era di fare un confronto a diversi criteri (difficoltà per mappare il problema, prestazioni, ecc) e abbiamo anche usato altre tecniche come simulato ricottura .

Ha funzionato abbastanza bene, ma ci sono voluti un po 'per capire come fare la fase di 'riproduzione' correttamente: modellare il problema a portata di mano in qualcosa di adatto per la programmazione genetica davvero mi ha colpito come la parte più difficile ...

E 'stato un corso interessante dal momento che anche dilettato con le reti neurali e simili.

Mi piacerebbe sapere se qualcuno ha usato questo tipo di programmazione in codice 'produzione'.

ho costruito un semplice GA per estrarre modelli utili fuori dello spettro delle frequenze della musica come è stato riprodotto. L'uscita è stato utilizzato per guidare effetti grafici in un plug-in winamp.

  • Input: alcuni fotogrammi FFT (immaginate una matrice 2D di carri)
  • uscita: valore float singolo (somma ponderata degli input), thresholded a 0,0 o 1,0
  • I geni: pesi di input
  • funzione fitness. Combinazione di duty cycle, durata dell'impulso e BPM all'interno del campo sensibile

Ho avuto un paio di GA sintonizzati per diverse parti dello spettro, nonché diversi limiti di BPM, in modo che non tendono a convergere verso lo stesso schema. Le uscite dalla parte superiore 4 da ogni popolazione sono state inviate al motore di rendering.

Un interessante effetto collaterale è che la forma fisica media in tutta la popolazione era un buon indicatore per i cambiamenti nella musica, anche se in genere sono voluti 4-5 secondi per capirlo.

Come parte della mia tesi ho scritto un framework generico Java per i multi-obiettivo mPOEMS algoritmo di ottimizzazione (ottimizzazione multiobiettivo prototipo con gradini di miglioramento evoluti), che è un GA utilizzando concetti evolutivi. È generico in modo che tutte le parti problema indipendenti sono stati separati dalle parti problema-dipendente, e un'interfaccia è povided utilizzare il quadro con aggiungendo solo le parti problema-dipendente. Così chi vuole utilizzare l'algoritmo non deve cominciare da zero, e facilita lavorare molto.

È possibile trovare il codice qui .

Le soluzioni che si possono trovare con questo algoritmo sono stati confrontati in un lavoro scientifico con algoritmi state-of-the-art SPEA-2 e NSGA, ed è stato dimostrato che l'algoritmo esibisce paragonabile o, meglio ancora, a seconda delle metriche si prende per misurare le prestazioni, e soprattutto in funzione della ottimizzazione-problema che si sta cercando su.

Si può trovare qui .

Inoltre, come parte della mia tesi e la prova di lavoro ho applicato questo quadro di riferimento per il problema di selezione dei progetti si trovano in gestione del portafoglio. Si tratta di selezionare i progetti che aggiungono il maggior valore per l'azienda, sostenere la maggior parte della strategia della società o sostenere qualsiasi altro obiettivo arbitrario. Per esempio. selezione di un certo numero di progetti da una categoria specifica, o la massimizzazione delle sinergie progettuali, ...

La mia tesi che si applica questo quadro di riferimento per il problema di selezione dei progetti: http://www.ub.tuwien.ac.at/dipl/2008 /AC05038968.pdf

Dopo che ho lavorato in un reparto di gestione del portafoglio in una delle aziende Fortune 500, dove hanno usato un software commerciale che si applica anche una GA all'ottimizzazione problema / portafoglio di selezione dei progetti.

Ulteriori risorse:

La documentazione del quadro: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

carta mPOEMS presentazione: http://portal.acm.org/citation.cfm?id=1792634.1792653

In realtà con un po 'di entusiasmo chiunque potrebbe facilmente adattare il codice del framework generico per un problema di ottimizzazione multi-obiettivo arbitrario.

Al lavoro ho avuto il seguente problema: dato compiti M e N DSP, quale fosse il modo migliore per assegnare compiti a DSP? "Migliore" è stata definita come "minimizzare il carico del DSP più caricato". C'erano diversi tipi di attività, e vari tipi di attività ha avuto varie ramificazioni di prestazioni a seconda di dove sono stati assegnati, in modo codificato l'insieme di incarichi di lavoro-a-DSP come una "stringa di DNA" e poi utilizzato un algoritmo genetico per "razza" il miglior stringa di assegnazione che ho potuto.

Ha funzionato abbastanza bene (molto meglio del mio metodo precedente, che era quello di valutare ogni possibile combinazione ... sulle dimensioni del problema non banali, ci sarebbero voluti anni per completare!), L'unico problema era che non c'era modo per capire se la soluzione ottimale è stato raggiunto o meno. Si potrebbe decidere solo se la corrente "best effort" era abbastanza buono, e farlo funzionare più a lungo per vedere se si poteva fare di meglio.

C'è stato un concorso su codechef.com (grande sito a proposito, concorsi di programmazione mensile) dove si doveva risolvere un sudoku unsolveable (uno dovrebbe avvicinarsi il più possibile con il minor numero sbagliato collumns / file / etc possibile).

quello che vorrei fare, è stato quello di creare prima un sudoku perfetto e quindi sovrascrivere i campi, che sono state date. Da questa bella buona base su che ho usato programmazione genetica per migliorare la mia soluzione.

Non riuscivo a pensare ad un approccio deterministico, in questo caso, perché il sudoku era 300x300 e di ricerca avrebbe preso troppo tempo.

ho usato un semplice algoritmo genetico per ottimizzare il rapporto segnale-rumore di un'onda che è stato rappresentato come una stringa binaria. Lanciando i bit di un certo modo di diversi milioni di generazioni sono stato in grado di produrre una trasformazione che ha provocato un segnale più alto rapporto rumore di quell'onda. L'algoritmo avrebbe potuto essere anche "Simulated Annealing", ma non è stato utilizzato in questo caso. Al loro centro, algoritmi genetici sono semplici, e questo era circa semplice di un caso d'uso che ho visto, quindi non mi utilizzano un quadro per la realizzazione e la selezione generazione - soltanto un seme casuale e il rapporto segnale-rumore funzioni a portata di mano.

In un seminario nella scuola, abbiamo sviluppare un'applicazione per generare musica basata in modalità musicale. Il programma è stato costruito in Java e l'output era un file midi con la canzone. Noi utilizzando distinti aproachs di GA per generare la musica. Penso che questo programma può essere utile per esplorare nuove composizioni.

in undergrad, abbiamo usato NERO (una combinazione di reti neurali e algoritmi genetici) per insegnare i robot in-game per prendere decisioni intelligenti. E 'stato abbastanza freddo.

Ho sviluppato una simulazione basata altalena multithread di navigazione del robot attraverso una serie di terreni randomizzato griglia di fonti di cibo e miniere e sviluppato una strategia basata algoritmo genetico di esplorare l'ottimizzazione del comportamento robotico e la sopravvivenza dei geni più adatti per un cromosoma robotica. Questo è stato fatto con la creazione di grafici e la mappatura di ogni ciclo di iterazione.

Da allora ho sviluppato ancora di più il comportamento di gioco. Un esempio di applicazione che di recente costruzione per me è stato un algoritmo genetico per la soluzione del problema uomo di vendita di viaggio nel percorso ritrovamento nel Regno Unito, tenendo conto di inizio e di obiettivo gli Stati, nonché uno / più punti di connessione, ritardi, cancellazioni, lavori di costruzione, Ora di punta, scioperi pubblici, tra considerazione più veloce vs percorsi più economici. Poi fornendo una raccomandazione equilibrato per il percorso da seguire in un dato giorno.

In generale, la mia strategia è di usare POJO representaton base di geni, allora mi candido implementazioni di interfacce specifiche per la selezione, la mutazione, le strategie di crossover, e il punto di criteri. La mia funzione di fitness poi diventa sostanzialmente un complesso piuttosto sulla base della strategia e dei criteri che ho bisogno di applicare come misura euristica.

Inoltre ho esaminato l'applicazione di algoritmi genetici in test automatizzati al codice con cicli di mutazione sistematici in cui l'algoritmo capisce la logica e cerca di stabilire un bug report con raccomandazioni per correzioni di codice. In sostanza, un modo per ottimizzare il mio codice e fornire raccomandazioni per il miglioramento, nonché un modo di automatizzare la scoperta di nuovo codice programmatico. Ho anche cercato di applicare gli algoritmi genetici per la produzione musicale, tra le altre applicazioni.

In generale, trovo strategie evolutive come la maggior parte delle strategie metaeuristica / ottimizzazione globale, sono lenti ad imparare in un primo momento, ma iniziare a raccogliere le soluzioni diventano sempre più vicino alla stato obiettivo e finché la vostra funzione di fitness e euristiche sono ben allineato per la produzione che la convergenza all'interno del vostro spazio di ricerca.

Una volta ho provato a fare un giocatore del computer per il gioco del Go, basata esclusivamente sulla programmazione genetica. Ogni programma sarà trattato come una funzione di valutazione per una sequenza di movimenti. I programmi prodotti non erano molto buone, però, anche su una tavola 3x4 piuttosto diminuitive.

Ho usato Perl, e codificato tutto da solo. Vorrei fare cose in modo diverso oggi.

Dopo aver letto L'orologiaio cieco , ero interessato al programma pascal Dawkins ha detto che aveva sviluppato per creare modelli di organismi che potrebbero evolvere nel tempo. Ero interessato abbastanza per scrivere il mio utilizzando Swarm . Non ho fatto tutta la grafica critter fantasia ha fatto, ma i miei '' cromosomi tratti controllati che hanno interessato la capacità degli organismi di sopravvivere. Vivevano in un mondo semplice e potrebbe slug fuori uno contro l'altro e il loro ambiente.

Gli organismi vivere o morire in parte dovuto al caso, ma anche sulla base come effettivamente hanno adattato al loro ambiente locale, come ben si consumavano sostanze nutritive e con quanto successo hanno riprodotto. E 'stato divertente, ma anche più prove a mia moglie che io sono un geek.

E 'stato qualche tempo fa, ma ho tirato un GA per evolvere ciò che erano in effetti kernel di elaborazione delle immagini per rimuovere le tracce di raggi cosmici dal Telescopio Spaziale Hubble (HST) le immagini. L'approccio standard è quello di prendere esposizioni multiple con il telescopio e mantenere solo la roba che è lo stesso in tutte le immagini. Poiché il tempo HST è così prezioso, io sono un appassionato di astronomia, e aveva da poco partecipato al Congresso il calcolo evolutivo, ho pensato di usare un GA per ripulire singole esposizioni.

I soggetti erano in forma di alberi che hanno un'area di pixel 3x3 come input, eseguite alcuni calcoli, e prodotto una decisione in merito a se e come modificare il pixel centrale. Fitness è stato valutato confrontando l'uscita con un'immagine ripulito in modo tradizionale (cioè esposizioni accatastamento).

E 'in realtà una sorta di lavorato, ma non abbastanza bene per giustificare quanto sopra l'approccio originale. Se non fossi stato con limitazioni di tempo per la mia tesi, ho potuto ampliato la genetica bin parti disponibili per l'algoritmo. Sono abbastanza sicuro che avrei potuto migliorare in modo significativo.

librerie utilizzate:. Se ricordo bene, IRAF e cfitsio per l'elaborazione dei dati immagini astronomiche e I / O

Ho sperimentato con GA nella mia giovinezza. Ho scritto un simulatore in Python che ha funzionato come segue.

I geni codificati i pesi di una rete neurale.

Gli ingressi della rete neurale sono stati "antenne" che ha rilevato tocca. Valori più alti significava molto vicino e 0 non significava toccare.

Le uscite sono a due "ruote". Se entrambe le ruote è andato avanti, il ragazzo è andato avanti. Se le ruote erano in direzioni opposte, il ragazzo si voltò. La forza dell'uscita determinata la velocità della ruota che gira.

Un semplice labirinto è stata generata. E 'stato molto semplice - stupido persino. Non è stato l'inizio nella parte inferiore dello schermo e un obiettivo in alto, con quattro pareti in mezzo. Ogni parete aveva uno spazio tolto in modo casuale, quindi c'era sempre un percorso.

Ho iniziato ragazzi casuali (ho pensato a loro come insetti) alla partenza. Non appena un ragazzo ha raggiunto è stato raggiunto l'obiettivo, o un limite di tempo, l'idoneità è stato calcolato. E 'stato inversamente proporzionale alla distanza alla meta in quel momento.

Ho poi li accoppiati e "allevato" loro per creare la prossima generazione. La probabilità di essere stati scelti per essere allevati era proporzionale alla sua forma fisica. A volte questo significa che uno è stato allevato con se stesso più volte se avesse un altissimo idoneità relativa.

ho pensato che sarebbe sviluppare un comportamento "muro abbracciare sinistra", ma mi è sempre sembrato di seguire qualcosa di meno ottimale. In ogni esperimento, gli insetti convergevano per un modello a spirale. Avrebbero spirale verso l'esterno fino a toccare un muro a destra. Avevano seguono tale, poi quando hanno ottenuto al gap, avrebbero spirale verso il basso (dal gap) e dintorni. Farebbero un giro di 270 gradi a sinistra, poi di solito penetri nello spazio. Questo li otterrebbe attraverso la maggioranza delle mura, e spesso a raggiungere l'obiettivo.

Una caratteristica ho aggiunto è stato quello di mettere in un vettore di colore nei geni per monitorare parentela tra gli individui. Dopo un paio di generazioni, sarebbero tutti dello stesso colore, che mi dicono che dovrebbe avere una migliore strategia di allevamento.

Ho cercato di convincerli a sviluppare una strategia migliore. Ho complicato la rete neurale - l'aggiunta di una memoria e tutto. Non ha aiutato. Ho sempre visto la stessa strategia.

Ho provato varie cose come avere pool genici separati che solo ricombinati dopo 100 generazioni. Ma nulla li spingerebbe ad una strategia migliore. Forse era impossibile.

Un'altra cosa interessante è graficamente la forma fisica nel tempo. Ci sono stati modelli precisi, come l'idoneità massima scendendo prima che sarebbe salito. Non ho mai visto un discorso un'evoluzione libro su questa possibilità.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top