Genetische Algorithmen und komplexe adaptive Systeme

Von Ralf Keu­per

Die Infor­matik macht hin und wieder Anlei­hen bei der Biolo­gie bzw. der Evo­lu­tion­s­the­o­rie. So auch im Fall der Genetis­chen Algo­rith­men. Für ihren “Vater”, John Hol­land, sind Genetis­che Algo­rith­men Opti­mierung­stech­niken, die auf den Prinzip­i­en der natür­lichen Selek­tion basieren und ver­wen­det wer­den, um effiziente Lösun­gen für kom­plexe Prob­leme zu find­en, wie z. B. die Opti­mierung von Liefer­ket­ten. Der Prozess umfasst mehrere Schritte¹Inside AI:

• Ini­tialpop­u­la­tion: Eine Gruppe poten­zieller Lösun­gen wird erstellt, die unter­schiedliche Routen, Verteilungspläne und Zeit­pläne umfasst.
• Bew­er­tung: Jede Lösung wird anhand eines Fit­nesskri­teri­ums bew­ertet, das Fak­toren wie Lieferzeit und Kosten berück­sichtigt.
• Selek­tion: Die besten Lösun­gen wer­den aus­gewählt, um sie zu kom­binieren.
• Crossover: Teile erfol­gre­ich­er Lösun­gen wer­den kom­biniert, um neue Lösun­gen zu schaf­fen.
• Muta­tion: Zufäl­lige Änderun­gen wer­den vorgenom­men, um Vielfalt zu erzeu­gen.

Dieser Zyk­lus wieder­holt sich über mehrere Gen­er­a­tio­nen, bis eine zufrieden­stel­lende Lösung gefun­den wird oder ein fest­gelegter Zeitraum abge­laufen ist.

Genetis­che Algo­rith­men sind beson­ders effek­tiv bei kom­plex­en Prob­le­men, bei denen eine voll­ständi­ge Analyse aller Möglichkeit­en unprak­tisch ist, wie z. B. beim Trav­el­ing Sales­man Prob­lem (TSP). Sie bieten Vorteile gegenüber klas­sis­chen Opti­mierungsmeth­o­d­en, da sie eine Vielzahl poten­zieller Lösun­gen gener­ieren und sich kon­tinuier­lich verbessern kön­nen.

Trotz ihrer Stärken haben GAs auch Ein­schränkun­gen: Sie garantieren nicht die beste Lösung, erfordern hohe Rechen­res­sourcen und kön­nen manch­mal schw­er zu inter­pretieren sein. Den­noch sind sie ein wertvolles Werkzeug zur Lösung kom­plex­er Prob­leme in ver­schiede­nen Anwen­dun­gen, von Liefer­ket­ten über Finanz­mod­elle bis hin zu Robotik.

Schema-The­o­rem

Mitt der 1960er Jahren for­mulierte Hol­land das sog. »Schema-The­o­rem«, einen Haupt­satz für genetis­che Algo­rith­men.

Wenn es Repro­duk­tion, Cross-over und Muta­tion gibt, wächst fast jedes kom­pak­te Gen-Clus­ter, das über­durch­schnit­tliche Tauglichkeit gewährleis­tet, in der Pop­u­la­tion expo­nen­tiell an²in: Inseln im Chaos. Die Erforschung kom­plex­er Sys­teme .

Mit Schema beze­ich­nete Hol­land jedes spezielle Gen­muster.

Genetis­che Algo­rith­men und das Schema-The­o­rem allein nicht aus­re­ichend 

Hol­land selb­st war mit der Ent­deck­ung der genetis­chen Algo­rith­men noch nicht ganz zufrieden.

Mit dem genetis­chen Algo­rith­mus und dem Schema-The­o­rem war die Evo­lu­tion in ihren Grundzü­gen erfasst, davon war er weit­er­hin überzeugt. Doch wurde er das Gefühl nicht los, dass sein auf dem genetis­chen Algo­rith­mus basieren­des Mod­ell der Evo­lu­tion noch viel zu skelet­thaft war. Irgend etwas fehlte offen­bar ein­er The­o­rie, in der «Organ­is­men» lediglich von einem Pro­gram­mier­er ent­wor­fene Stücke der DNA sind. Was kon­nte ein solche The­o­rie über kom­plexe Lebe­we­sen aus­sagen, die sich in ein­er kom­plex­en Umwelt her­aus­bilden? Nichts. Der genetis­che Algo­rith­mus war für sich allein ein­fach noch kein adap­tives Agens³in: Inseln im Chaos. Die Erforschung kom­plex­er Sys­teme .

com­plex adap­tive sys­tems 

Hol­land gelangte bei seinen Forschun­gen weit­er­hin zu dem Schluss, dass in kom­plex­en Sys­te­men kein dauer­haftes Gle­ichgewicht herrschen kann und die Evo­lu­tion sich nicht an heuris­tis­che Regeln und Leit­fä­den ori­en­tiert. Um zu über­leben, müssen kom­plexe Sys­teme sich an die Verän­derun­gen in ihrer Umwelt anpassen — sie müssen ler­nen. Das brachte ihn und seine Mit­stre­it­er am San­ta Fe Insti­tute auf den Gedanken, solche Sys­teme als kom­plexe, adap­tive Sys­teme zu beze­ich­nen (com­plex adap­tive sys­tems — cas). Eine wichtige Rolle übernehmen dabei Agen­ten.

Viele .. kom­plexe Sys­teme zeigen Kohärenz im Angesicht des Wan­dels. Aber wir kön­nen bere­its einige der Gemein­samkeit­en her­ausar­beit­en. Wir kön­nen zum Beispiel sehen, dass die Kohärenz und das Fortbeste­hen jedes Sys­tems von umfan­gre­ichen Inter­ak­tio­nen, der Aggre­ga­tion ver­schieden­er Ele­mente und der Anpas­sung für das Ler­nen abhän­gen. … Wir wer­den sehen, dass Volk­swirtschaften, das Inter­net und sich entwick­el­nde Embry­onen ähn­liche Her­aus­forderun­gen bieten — Han­dels­bi­lanzen, Com­put­er­viren und Geburts­fehler zum Beispiel — und wir wer­den noch anderen begeg­nen. Auch wenn sich diese kom­plex­en Sys­teme im Detail unter­schei­den, ist die Frage nach der Kohärenz im Wan­del das zen­trale Rät­sel für alle. Dieser gemein­same Fak­tor ist so wichtig, dass wir am San­ta Fe Insti­tute⁴vgl. dazu: Inseln im Chaos. Die Erforschung kom­plex­er Sys­teme diese Sys­teme unter ein­er gemein­samen Über­schrift zusam­men­fassen und sie als kom­plexe adap­tive Sys­teme (cas) beze­ich­nen. Dies ist mehr als nur eine Ter­mi­nolo­gie. Es sig­nal­isiert unsere Intu­ition, dass all­ge­meine Prinzip­i­en das Ver­hal­ten von cas bes­tim­men, Prinzip­i­en, die Wege zur Lösung der damit ver­bun­de­nen Prob­leme aufzeigen (in: Hid­den Order. How Adap­ta­tion builds com­pex­i­ty).

Die Vielfalt der cas ist ein dynamis­ches Muster, das oft beständig und kohärent ist, wie eine ste­hende Welle. Wenn man die Welle stört, z. B. mit einem Stock oder einem Pad­del, erholt sich die Welle schnell wieder, sobald die Störung beseit­igt ist. Ähn­lich ver­hält es sich bei cas: Ein Inter­ak­tion­s­muster, das durch das Ausster­ben von Kom­po­nen­ten gestört wurde, stellt sich oft wieder her, obwohl sich die neuen Agen­ten im Detail von den alten unter­schei­den kön­nen. Es gibt jedoch einen entschei­den­den Unter­schied zwis­chen dem Muster der ste­hen­den Welle und den cas-Mustern: Cas-Muster entwick­eln sich. Die bei cas beobachtete Vielfalt ist das Ergeb­nis fortschre­i­t­en­der Anpas­sun­gen. Jede neue Anpas­sung eröffnet die Möglichkeit für weit­ere Inter­ak­tio­nen und neue Nis­chen (ebd.).