Perché usiamo la codifica binaria quando sembra così inefficiente?

Scegliere il modo giusto per rappresentare il genotipo è abbastanza importante quando si utilizza un algoritmo genetico. Ci sono molti modi per farlo, il binario è uno di questi.

Il motivo per cui si potrebbe pensare che il binario sia più utilizzato è perché è più semplice da implementare e spesso utilizzato in contesti accademici. Ma nel mondo reale, un sacco di lavoro va nella creazione di una corretta rappresentazione del genotipo per risolvere esattamente i problemi che stai descrivendo.

C'è anche qualche bagaglio storico. Il binario può essere reso abbastanza efficiente dal punto di vista dello spazio, quindi dovrebbe essere usato nei momenti in cui la memoria era difficile da trovare. Quindi sarebbe una buona scelta quando gli algoritmi genetici furono esplorati per la prima volta, il che era più o meno quando i computer divennero più accademicamente disponibili. Ma questo non è davvero un problema ora, quando si ha accesso a gigabyte di memoria e il problema principale è spesso il tempo necessario per calcolare l'idoneità, non la quantità di memoria che il genotipo richiede.

Altri dettagli su wikipedia .

Finding a suitable representation of the problem domain for a chromosome is an important consideration, as a good representation will make the search easier by limiting the search space; similarly, a poorer representation will allow a larger search space. The mutation operator and crossover operator employed by the genetic algorithm must also take into account the chromosome's design.

Come altri hanno già detto, il binario è utile per una manipolazione efficiente della rappresentazione. È stato anche sottolineato che la codifica della rappresentazione è importante.

Per riunire questi due aspetti, vorrei offrire un rappresentante del tuo esempio di lunghezza 5 che dovrebbe darti un'idea di come la rappresentazione può influire sull'efficienza.

Quindi, stiamo cercando una rappresentazione binaria per d o d o d dove d è in (0-9) e o è in (+ - x /) .

Iniziamo osservando che ci sono 4 operatori in o , quindi potremmo codificare ciascuno in 2 bit.

In secondo luogo, stai cercando una rappresentazione decimale codificata binaria per d . Notiamo che ci sono 3 numeri decimali. Se dovessimo codificare questi insieme, troveremmo che abbiamo 10 ^ 3 (1000) combinazioni che possono essere codificate in 10 bit (2 ^ 10 = 1024). Ci sono ben note codifiche di BCD per 3 numeri, ad es. Codifica Chen-Ho che utilizza effettivamente 10 bit.

Quindi, per questa rappresentazione di esempio, potremmo codificare come 3 decimali usando Chen-Ho più 2 operatori a 2 bit. Questo ci darebbe un'efficienza di codifica di 1000/1024 (x1x1) ~ = 97,7%. Un po 'meglio dell'1% nella codifica del candidato.

Questa codifica non è perfetta, ovviamente. In particolare, non si adatta banalmente a sequenze arbitrarie. Ma si spera che dia un senso di come la rappresentazione della codifica possa influenzare marcatamente l'efficienza della codifica.

Abbiamo usato ASCII per risolvere una serie di problemi nella mia classe AI, quindi non è che usiamo sempre binari.

L'uso della codifica binaria è solo un modo economico per ridurre al minimo le probabilità di produrre cromosomi privi di significato. Se hai 15 simboli 4 bit casuali hanno una probabilità 15/16 di essere significativi. 8 hanno una probabilità di 15/256.

Se non ti piace dover decodificare il binario, l'intero problema può essere evitato essendo un po 'più intelligente su ciò che si randomizza (muta) in primo luogo. Fai questo e puoi lavorare in ASCII con la stessa efficienza di binario.

Alcune spiegazioni degli algoritmi genetici si applicano al binario solo perché non vogliono distrarti con gli shenanigans di codifica ASCII. Ci sono molti modi per codificare. Non c'è motivo di pensare che il binario perfettamente imballato sia sempre il migliore. O (1/2 n) è ancora solo O (n). Fai attenzione alle micro-ottimizzazioni.

Enconding binario è:

1. (spesso) il più efficiente in termini di memoria in quanto la maggior parte dei geni può essere espressa come singolo booleano,
2. il più efficiente per i più popolari algoritmi di crossover (richiedono pochissime operazioni di algebra booleana).