Codierung von genetischen Algorithmen

Binäre Codierung

Bei Genetischen Algorithmen wird die Binäre Codierung eingesetzt !

• ein Chromosom wird als binärerer Vektor dargestellt
• ein Gen ist eine Position im Vektor oder eine zusammenhängende Sequenz von Positionen
• ein Allel ist der Wert eines Gens

Reelle Codierung Binäre Codierung

Reelle Codierung	Binäre Codierung
kompakt	universell, breit
einfache Optimierung bei reellen Parametern	einfache Optimierung bei diskreten Parametern
hoher Speicherbedarf (32 - 64 Bit/Gen)	geringer Speicherbedarf
Verarbeitung langsam (floating Point)	Verarbeitung schnell (Shift Operationen)

Probleme der Binären Codierung

Positionsabhängigkeit der Codierung

Beispiel:

6 entspricht dem Vektor 0110

7 entspricht dem Vektor 0111

8 entspricht dem Vektor 1000

Um von einer 6 auf eine 7 zu kommen, muß nur 1 Gen verändert werden, um von einer 7 auf eine 8 zu kommen, müssen 4 Gene verändert werden, beide Male ändert sich aber der Wert des Chromosoms nur um 1.

Lösung:

GRAY-CODE

6 = 0101

7 = 0100

8 = 1100

Um auf eine nachfolgende Zahl zu kommen muß jeweils nur ein Gen verändert werden

Unterschiedliche Gewichtung der Positionen

Beispiel:

Gegeben sei ein binärer Vektor dessen dezimaler Wert 1025 entspricht: 10000000001. Ändert sich nun die 11.Position, d.h. der Vektor wäre dann 00000000001 (=1 Dec) ergibt das eine Veränderung um den Wert 1024, wechselt hingegen nur die 1.Position: 10000000000 (=1024 Dec) erhält man eine Veränderung um den Wert 1, beide Male wird jedoch nur ein Gen verändert.

Lösung:

Die Mutationswahrscheinlichkeit eines Gens muß von seinem Gewicht (also seiner Position) abhängig sein.