È necessario mappare numeri interi a bit in un algoritmo genetico?

8

Da quanto ho letto, gli algoritmi genetici sono di solito (sempre?) applicati ai cromosomi dei bit. Quindi se un problema comporta il massimizzare una funzione che prende valori interi, i numeri interi vengono prima codificati come bit.

Questa mappatura è necessaria? Sembra che tu possa prendere i cromosomi degli interi e applicare direttamente il crossover e la mutazione. Quindi, se ho una funzione che richiede 35 ingressi interi, posso semplicemente applicare gli operatori genetici a questi numeri interi, anziché sui bit 35xB (dove B è il numero di bit necessari per codificare un intero). C'è un motivo per non farlo?

Forse l'algoritmo ne risentirebbe perché il problema è definito in modo più rozzo (cioè un problema può essere definito con cromosomi più brevi se non stiamo usando bit), ma sono curioso di sapere se qualcuno ha una risposta migliore.

    
posta itzy 06.08.2013 - 19:22
fonte

4 risposte

9

Codificare i valori come bit non è necessario. Guarda 2d box car (non sprecare troppo tempo su di esso) per un esempio in cui il il crossover viene eseguito su valori interi (float). Intere "assemblee" sono incrociate, questo aggiunge alla riconoscibilità della fonte (parte dell'estetica del gioco), ma lo fa in modo che le variazioni tra un dato cromosoma e i suoi genitori siano più limitate.

Il motivo per considerare l'utilizzo di bit anziché di interi ha a che fare con l'intervallo di dati con cui il pool viene seminato. Avere 35 numeri interi significa che l'attraversamento può avvenire solo su 35 valori presi come valori interi. avere 1120 bit (35 * 32 bit interi) dà una granularità più fine (si consideri il tradizionale lavoro sugli algoritmi genetici su ATCG - non interi "valori" di amminoacidi o proteine).

Avere bit consente di avere mutazioni 'più pulite' (capovolgere un po ') e crossover che prende la parte superiore di un intero e la parte inferiore di un altro. Entrambe queste cose aiutano ad aumentare la potenziale varietà di prole.

Considera il cromosoma di soli due byte (stiamo facendo byte anziché interi per renderlo più facile da vedere):

chromosome 1: 0xA3 0xB2
chromosome 2: 0x12 0x34

L'incrocio tra questi due cromosomi può avvenire solo in posti limitati. Finirai con:

chromosome 1': 0x12 0xB2
chromosome 2': 0xA3 0x34

Se questo è stato fatto come bit, invece:

chromosome 1: 1010001110110010
chromosome 2: 0001001000110100
                    ^   ^     

Ora puoi selezionare i siti di ^ per dare il crossover:

chromosome 1': 1010001000110010
chromosome 2': 0001001110110100
                     ^   ^     

Questo fornisce un modello più ricco con più varianti possibili tra due cromosomi.

    
risposta data 06.08.2013 - 21:03
fonte
3

Se hai un crossover e muti, sei nel business. Il tipo sottostante non ha importanza. Ho visto GA su strutture di grafici in cui il crossover e il mutato operano direttamente sui grafici, aggiungendo o combinando i nodi.

In realtà, di solito codifico tutto in caratteri e quindi fornisco crossover e muta a livello di byte, piuttosto che su bit. Aggiungere una maschera di bit per portarlo a livello di bit non è difficile, ma la vita è troppo breve.

    
risposta data 20.03.2014 - 09:56
fonte
0

La mappatura non è necessaria.

Evoluzione differenziale (DE) è un "sottoinsieme" di grande successo dello spazio più ampio di algoritmi.

Il primo grande cambiamento è che DE è usando numeri reali reali / interi invece di stringhe di bit (in genere numeri reali per l'ottimizzazione numerica, numeri interi in altri campi).

In ogni caso è bello poter rappresentare le cose come numeri reali.

È un modo per utilizzare le risorse del computer in modo efficiente e rende trasparenti input e output per l'utente: i parametri possono essere immessi, manipolati ed emessi come numeri ordinari senza essere mai riformattati come geni con una rappresentazione binaria diversa.

Per il problema di essere "definito in modo più rude" , DE adotta gli operatori di mutazione / crossover modificati che fanno uso della differenza tra due o più vettori interi / reali nella popolazione per creare un nuovo vettore (ad esempio aggiungendo alcune proporzioni casuali della differenza a uno dei vettori esistenti, più una piccola quantità di rumore casuale).

Da Evoluzione differenziale - Un approccio pratico all'ottimizzazione globale

    
risposta data 27.09.2014 - 16:22
fonte
0

In GA tutti i cromosomi sono solitamente rappresentati come stringhe di bit. Puoi avere delle eccezioni, ma per ora dimentichiamolo.

Un cromosoma è una possibile soluzione al tuo problema, quindi se la tua soluzione è un numero intero, deve avere una rappresentazione binaria che funzioni dalle operazioni genetiche. Fortunatamente, i numeri interi hanno già questa rappresentazione binaria (in effetti, sono * sono stringhe di bit nativi), quindi non devi fare nulla, basta applicare gli operatori sugli individui della tua popolazione lungo l'evoluzione processo.

    
risposta data 06.08.2013 - 21:03
fonte

Leggi altre domande sui tag