Migliore struttura dei dati per Genetic Algorithm in C ++?

Question

ho bisogno di implementare un algoritmo genetico personalizzato per il mio problema (progetto del college), e la prima versione era esso codificato come una matrice di brevi (bit per cromosoma x dimensione della popolazione).

E 'stata una cattiva progettazione, dal momento che sto dichiarando una breve, ma solo con i "0" e "1" valori ... ma era solo un prototipo e ha funzionato come previsto, e ora è il momento per me di sviluppare una nuova versione migliorata. Le prestazioni sono importanti qui, ma la semplicità è anche apprezzato.

Ho fatto una ricerca in giro e si avvicinò con:

per il cromosoma: - classe String (come "0.100.100,01 mille") - Array di bool - Vector (vettori sembra essere ottimizzato per bool) - bitset (suona il più naturale)

e per la popolazione: - C Array [] - Foto - Coda

Sono propenso a prendere vettore per chromossome e la matrice per il pop, ma vorrei il parere chiunque con esperienza in materia.

Grazie in anticipo!

Answer 1

Sto cercando di indovinare che si desidera accesso casuale alla popolazione e ai geni. Tu dici che le prestazioni sono importanti, che io interpreto come velocità di esecuzione. Quindi probabilmente stai best off utilizzando un vector<> per i cromosomi e un vector<char> per i geni. La ragione di vector<char> è che bitset<> e vector<bool> sono ottimizzati per il consumo di memoria, e sono quindi lento. vector<char> vi darà maggiore velocità al costo della memoria x8 (assumendo char = byte sul sistema). Quindi, se volete la velocità, andare con vector<char>. Se il consumo di memoria è fondamentale, quindi utilizzare vector<bool> o bitset<>. bitset<> potrebbe sembrare una scelta naturale qui, tuttavia, tenere presente che è templato il numero di bit, il che significa che a) il numero di geni deve essere fissato e noto al momento della compilazione (che immagino è un grande no -no), e b) se si utilizzano diverse dimensioni, si finisce con una copia per dimensioni bitset di ciascuno dei metodi bitset che usate (anche se inlining potrebbe negare questo), vale a dire, il codice gonfiare. Nel complesso, direi vector<bool> è meglio per voi se non si vuole vector<char>.

Se siete preoccupati per l'estetica del vector<char> si poteva typedef char gene; e quindi utilizzare vector<gene>, che sembra più naturale.

Un string è proprio come un vector<char> ma più ingombrante.

Answer 2

In particolare per rispondere alla tua domanda. Io non sono esattamente sicuro di quello che sei suggerimento. Lei parla di array e la classe stringa. Stai parlando di classi container STL dove si può avere una coda, bitset, vettore, lista collegata ecc vorrei suggerire un vettore per la popolazione (cosa più vicina ad una matrice C c'è) e un bitset per voi se siete cromosoma preoccupato per la capacità di memoria. Altrimenti come si sta già utilizzando un vettore di stringa representaion del vostro DNA. ( "10.110.110")

Per idee e un buon strumento di dilettarsi. Consigliamo di scaricare e inizialmente usa questa libreria. Funziona con i principali compilatori. Funziona su varianti di UNIX. Ha tutto il codice sorgente.

Tutta la roba quadro è fatto per voi e si impara molto. In seguito si potrebbe scrivere il proprio codice da zero o ereditare da queste classi. È possibile utilizzarli anche nel codice commerciale, se si vuole.

Perché sono gli oggetti che si possono cambiare representaion del vostro DNA facilmente da interi a reali alle strutture di alberi per le matrici di bit ecc ecc.

C'è sempre imparando cura coinvolti, ma ne vale la pena.

Io lo uso per generare migliaia di reti neurali poi estirpare con una semplice funzione di fitness per poi correre per davvero.

Galib

http://lancet.mit.edu/ga/

Answer 3

Supponendo che si desidera codificare da soli (se si vuole un kingchris biblioteca esterno sembra avere una buona lì) in realtà dipende da che tipo di manipolazione che devi fare. Per ottenere il maggior successo per il dollaro in termini di memoria, è possibile utilizzare qualsiasi tipo intero e insieme / manipolare i singoli bit tramite bitmasks ecc Ora questo approccio probabilmente non ottimale in termini di facilità di utilizzo ... L'esempio stringa sopra funzionerebbe ok, però ancora una volta la sua non è significativamente diverso da quello dei pantaloncini, qui si sta ora solo rappresentando uno '0' o '1' con un valore a 8 bit al contrario di valore a 16 bit. Inoltre, ancora una volta a seconda della manipolazione, il caso della stringa sarà probabilmente rivelarsi unwieldly. Quindi, se potesse dare qualche informazione in più sull'algoritmo potremmo forse dare più feedback. Mi piace il bit individuali come parte di un intero (un bitset), ma se non siete abituati a maschere, turni, e tutta quella roba buona non può essere giusto per voi.

Answer 4

Suggerisco a scrivere una classe per ogni membro della popolazione, che semplifica notevolmente le cose, dal momento che è possibile mantenere tutte le funzioni importanti membri nello stesso luogo ben avvolto con i dati effettivi.

Se avete bisogno di un "array di Caccio" Io suggerisco di usare un int o più interi (quindi utilizzare la maschera e un po 'le operazioni di saggi per l'accesso (modificare / Flip) ogni bit) a seconda del numero dei tuoi cromosomi.

Io di solito usato una sorta di classe di raccolta per la popolazione, in quanto solo una serie di membri di popolazione non consente di aggiungere semplicemente alla vostra popolazione. Vorrei suggerire attuare una sorta di elenco dinamico (se si ha familiarità con ArrayList allora che è un buon esempio).

ho avuto grande successo con algoritmi genetici con la ricetta di cui sopra. Se si prepara la classe membro correttamente può davvero semplificare le cose e permette di concentrarsi sulla codifica algoritmi genetici meglio invece di preoccuparsi di vostre strutture di dati.