Codierung

Nun stellt sich nach dem vorigen Abschnitt unmittelbar die Frage, wie man den genetischen Code im Computer nachbilden soll, bzw. wie man die biologischen Vorgänge der Selektion  , der Mutation   und des Crossover   am besten auf bestehende Probleme anpaßt. (Es sei an dieser Stelle nochmals erwähnt, daß hier nicht die Natur nachgeahmt werden soll, d.h. es sollen in diesen Anwendungen keine wie immer gearteten biologischen Vorgänge simuliert werden. Vielmehr wird versucht, die Strategie die die Natur selbst anwendet um Anpassungen vorzunehmen, zu übernehmen und auf eigene Probleme anzuwenden. Der Gedanke, der dahinter steckt, ist: Prinzipien, die in der Natur Optimierungsarbeit leisten, sollten dies auch im mathematischen Sinne tun.)

Die Art der Repräsentation des Gens die wir für die Umsetzung im Computer wählen ist zweifellos willkürlich - allerdings nicht bedingungslos! Immerhin sollte eine Codierung gewählt werden, auf deren Basis sich die aus der Genetik kopierten Strategien möglichst gut verwirklichen lassen. In der Praxis hat sich im wesentlichen eine Möglichkeit durchgesetzt, die auch von John Holland mathematisch fundiert wurde (schema theorem, beschrieben in Lucasius et.al., 1992): An Stelle des genetischen Codes im biologischen Sinne, tritt eine Binärzahl   mit prinzipiell beliebiger Länge. D.h. wir definieren unser Computergen als eine Folge einer bestimmten Anzahl von 0 und 1. Mit diesem Gen werden dann, wie im nächsten Kapitel beschrieben wird, die Operationen Mutation und Crossover durchgeführt.

Nun stellt sich folgerichtig das nächste Problem: im Modell liegen üblicherweise mehrere Parameter, mit dem Definitionsbereich der reelle Zahlen vor, deren Optimum gefunden werden soll. Innerhalb des Algorithmus arbeiten wir aber, wie eben beschrieben, nur mit dem binären Gen. D.h. das Gen muß diese Parameter in irgendeiner Weise in eineindeutiger Form repräsentieren. Diese Problematik ist in der Tat, wie viele Versuche zeigen (Vankeerberghen et.al., 1995; Zitat Doktorarbeit .. Zitat Hollander) ein sehr fundamentales Problem. Bei ungünstiger Wahl der Codierung kann die Leistungsfähigkeit des gesamten Algorithmus in Frage gestellt werden! Ich will nun die zwei wichtigsten Möglichkeiten, die Abbildung vorzunehmen, beschreiben, ausgehend von mehreren reellen Parametern.

Zunächst muß die reelle Zahl, die durch den Parameter ausgedrückt wird, in eine natürliche Zahl umgeformt werden, das geschieht üblicherweise durch folgende Transformation

wobei den transformierten Parameter darstellt und n die Anzahl der zu berücksichtigenden Dezimalstellen. Dieser transformierte Parameter ist aus dem Definitionsbereich der natürlichen Zahlen, kann also ohne weiteres in eine binäre Zahl   umgerechnet werden. Dieser Vorgang wird für alle zu optimierenden Parameter wiederholt. Die binären Parameter werden nun in einer Folge aneinandergereiht. Diese Reihe wird jetzt als Gen definiert, der Repräsentant des ganzen Parametersatzes (siehe auch Abb.).

  
Abbildung: Binäre Transformation eines Parametersatzes eines mathematischen Modelles in ein Gen

Allerdings zeigt sich in der Praxis, daß diese Form der Codierung nicht optimal ist, da im binären Parameter logischerweise jedem Bit ein anderes Gewicht zukommt. Ein Invertieren des niederwertigsten Bits verursacht eine Veränderung des Parameters um den Wert 1, des zweiten Bits um 2, der dritten um 4, des n-ten um . Das ist normalerweise nicht wünschenswert. So wende ich in dieser Arbeit anstelle des Binärcodes den Graycode   an, der zwar auch über eine Stelligkeit   verfügt, die sich aber bei weitem nicht so unangenehm äußert, wie die des binären Codes. Das Prinzip der Transformation bleibt allerdings das gleiche. Auch in den folgenden Operationen ändert sich nichts, das Gen liegt auch hier in Form von 0 und 1 vor.

Selbstverständlich müssen die Parameter, bevor sie wieder in das Modell eingesetzt werden, rücktransformiert werden. D.h. innerhalb des GA wird nur mit den binären oder gray codierten Parametern gearbeitet, extern - also in den Modellen - natürlich mit den reellen Parametern!