Quasi-optimale Problemlösungen durch Anwendung genetischer Algorithmen

Seid fruchtbar und vermehret euch!

Quasi-optimale Problemlösungen durch Anwendung genetischer Algorithmen

Lassen Sie sich von der relativ wissenschaftlich klingenden zweiten Überschrift nicht irreführen - in Wirklichkeit sind genetische Algorithmen nicht so schwer zu verstehen. Man kann sie dazu einsetzen, für NP-vollständige (das sind Problemstellungen, für die es keinen Lösungsalgorithmus gibt) oder zumindest schwierige Probleme näherungsweise möglichst gute Lösungen zu finden, wofür auch in diesem Artikel ein Beispiel gegeben werden soll. In der Praxis wurden und werden ähnliche Algorithmen beispielsweise zur Mustererkennung (siehe dazu auch [2] und [3]) mit gewissem Erfolg eingesetzt. Für besonders Interessierte sei an dieser Stelle auch auf [5] als weiterführende Literatur hingewiesen.

In diesem Artikel wollen wir uns allerdings auf etwas Einfacheres beschränken, nämlich die Reaktionen von sogenannten ELEKs (nach [1]: endliche, lebende Klümpchen) auf eine vorgegebene, sich periodisch wiederholende Umweltfolge. Diese Eleks entsprechen dem, was Informatiker einen endlichen Automaten nennen. Ein solcher Gegenstand besitzt eine endliche Anzahl verschiedener Zustände, die er je nach Eingangssignal wechselt, wobei er auch selbst Signale ausgibt. Ein einfaches Elek mit sechs Zuständen ist in Bild 1 etwa so dargestellt, wie es auch mein Programm am Ende einer Simulation am Bildschirm zeigt. Wie die Zahlenpaare zu verstehen sind, ist in dieser Abbildung ebenfalls erklärt.

Um am Ende des Programmlaufs schließlich ein ideales Elek vorliegen zu haben, ist eine Reihe von Vorgängen notwendig: Einerseits züchtet man per Zufall bessere Prognostiker, andererseits aber läßt man auch schlechte Eleks zugrundegehen und ersetzt sie durch erfolgreichere Nachkommen.

Ersteres läßt sich einfach dadurch realisieren, daß man sich ein „kosmisches Teilchen“ vorstellt, das einen Teil des "Chromosoms" verändert, das heißt, ihn mit einem Zufallswert ersetzt. Das zweite Verfahren könnte man am ehesten noch als Paarung bezeichnen, die zwischen dem besten Elek und einem durch Zufall ausgewählten anderen stattfindet. Die Methode des sogenannten Crossing-over, die weiter unten noch genauer beschrieben wird, ist wegen ihrer Einfachheit dafür besonders gut geeignet. Genau wie Dewdney stand ich ihr anfänglich eher skeptisch gegenüber, doch scheint sie sich in der Praxis tatsächlich ganz gut zu bewähren.

Für diesen „Fortpflanzungsprozeß“ ist vor allem die Variable "Paarungsschwelle” von Bedeutung, mit der man die Häufigkeit von Paarungen regulieren kann. Sie wird vor jedem Crossing-over mit einer Zufallszahl verglichen: die Paarung findet nur dann statt, wenn diese größer ist als die angegebene Paarungsschwelle. Das bedeutet, daß bei einem Wert von 0 (fast) immer, bei 1 nie ein neues Elek entstehen kann. Wird zu selten gepaart, dauert die Evolution meist unerträglich lange, andernfalls geht wiederum die "Artenvielfalt" verloren, da dann zu viele gute Prognostiker vorhanden sind.

Abb. 1
Abb. 2

Für Programmierer: DAS LISTING

Meine Simulation wurde übrigens durch [1] angeregt: dort ist allerdings kein fertiges Programmlisting vorhanden, viel mehr wird ein solches nur in seinen Grundzügen beschrieben, was aber leider etwas umständlich geschieht. Aus diesem Grund stimmen auch vor allem die dortigen Daten- und Feldstrukturen teilweise nicht mit meiner Version überein. Diese Tatsache macht sie schneller und auch - so hoffe ich jedenfalls - leichter verständlich. Außerdem habe ich den Variablen bzw. den Konstanten bezeichnende Namen gegeben, so daß sie wohl kaum einer näheren Erklärung bedürfen.

Näher eingehen möchte ich allerdings auf den Aufbau eines Elek-Arrays. Es besteht aus (gedachten) Zahlenpaaren, von denen der erste Wert das Ausgabesignal, also entweder 0 oder 1, enthält und der zweite den Index der zwei Zahlenpaare, von denen eines nach der Ausgabe in Abhängigkeit vom Umweltsignal angesprungen wird. Das Programm verwendet folglich immer den Wert als neuen Index, auf den der alte Index gezeigt hat. (Das Prinzip ist zur besseren Verständlichkeit in Bild 1 grafisch dargestellt.)

Nun aber zu den einzelnen Routinen: Die Funktion rnd, die ja vielen noch aus dem alten ST-Basic bekannt sein dürfte, liefert mit Hilfe einer Funktion des XBIOS eine Zufallszahl zwischen 0 und 1.

Die Prozedur Schoepfung weist den einzelnen Eleks per Zufallszahlengenerator ihre Ausgabesignale sowie die Zustände zu, in die sie nach der Ausgabe übergehen.

Die Prozedur Grafik_Init zeichnet, wie unschwer am Namen zu erkennen ist, das Hintergrundbild mit einer Linieneinteilung in 10-Prozent-Schritten, was alles mit reiner Line-A-Grafik geschieht.

In der Prozedur Simulation wird nun gerechnet. Zuerst werden die Vorhersagen der einzelnen Eleks mit der Umwelt verglichen; dabei sucht das Programm auch gleichzeitig das schlechteste und das beste Elek. Anschließend werden je nach gewählter Darstellungsart entweder diese beiden Werte umgerechnet und auf dem Bildschirm als vertikale Linie gezeichnet, oder die Erfolgsquoten jedes Eleks wer den einzeln in der Grafik dargestellt. Daraufhin wird nun ein zufällig ausgewählter Wert (es kann dies sowohl ein Signal als auch eine Adresse sein) eines zufällig ausgewählten Eleks sinngemäß verändert. Bevor schließlich weiter nach dem besten Prognostiker gesucht wird, wird irgendein Elek mit dem besten gepaart, was in dem Programm so vor sich geht, daß ein zufällig gewählter Ausschnitt des Chromosoms jenes Eleks durch den entsprechenden Teil aus dem besten Elek ersetzt wird, indem einfach der betroffene Array-Ausschnitt kopiert wird.

Beendet wird die Berechnung erst, wenn ein Elek die gesamte Umweltfolge richtig vorhersagen kann. Zum Abschluß werden dann noch die ganze Umweltfolge, die Anzahl der Durchgänge und das Chromosom des besten Prognostikers ausgegeben.

Das Hauptprogramm behandelt schließlich die Eingabe aller Werte, die Überprüfung und periodische Erweiterung der Umweltfolge sowie die Aufrufe der einzelnen Unterprogramme.

Die vielen mysteriösen write (chr(27)....) sind, nebenbei bemerkt, bloß Steuersequenzen für das VT52, dienen also zur Bildschirmmanipulation. Es gibt hier zahlreiche Codes, so daß ich alle, die diese noch nicht genau kennen, auf [4] verweisen möchte, da es wohl den Rah men des Artikels sprengen würde, deren Funktionsweisen zu erklären.

Für Praktiker: DIE BEDIENUNG

Nach aufmerksamem Studium dieses Artikels sollte es Ihnen keine allzu großen Schwierigkeiten mehr bereiten, das Programm zu bedienen, da es ohnehin immer “sagt", welche Werte es gerade benötigt. Gesondert hinweisen möchte ich nur auf die Tatsache, daß mit Taste... immer [Return] gemeint ist.

Scheint außerdem das Programm endlos nach einem optimalen Elek zu suchen, können Sie es mit [Control]+[C] stoppen; es kehrt dann sofort zum Desktop zurück, nachdem die aktuelle Bildschirmseite fertig dargestellt wurde. Drücken Sie [Control]+[S], so haben Sie die Möglichkeit, die fertige Grafik vor dem Umspringen längere Zeit zu betrachten, um danach [Control]+[Q] fortzufahren.

Für Kreative: ERWEITERUNGEN

Da mein Programm nur den Lösungsweg verdeutlichen soll, sind noch eine ganze Menge von Erweiterungsmöglichkeiten für Sie offen. Beispielsweise wäre es interessant, Eleks auf nichtperiodische Umweltfolgen anzusetzen oder auf solche, die sich gelegentlich nur geringfügig ändern. Sie können allerdings auch mehrere Eleks gleichzeitig paaren bzw. von einem kosmischen Teilchen verändern lassen. Auch eine statistische Auswertung der Ergebnisse oder die Beantwortung der Frage, wie lang die längste Periode ist, die ein Elek mit n Zuständen herausfinden kann, könnte überraschende Schlüsse zulassen. Oder findet sich vielleicht jemand, dem es gelingt, das Programm so umzuschreiben, daß es auch Umweltfolgen mit mehreren verschiedenen Signalen - also beispiels weise allen Ziffern von 0 bis 9 - verarbeiten kann?

Sie sehen also: Innovation und Kreativität sind wieder einmal gefragt. Ich bin schon gespannt, von Ihren Ideen und Erfahrungen zu hören. Doch Vorsicht! Wer sich mit diesem Thema einmal eingehend beschäftigt hat, der kommt nicht mehr so schnell davon los. Denn es gibt in der Tat eine ungeheuer große Vielfalt zu erforschen und zu entdecken; um sich davon zu überzeugen, brauchen Sie nur einen Blick auf Bild 2 zu werfen....

Literatur: [1] Sonderheft “Computer Kurzweil" Spektrum der Wissenschaft S 74ff. - A.K.Dewdney

[2] "Computer Kurzweil“
Reihe “Verständliche Forschung"
Spektrum der Wissenschaft

[3] ST-Computer 11/87
“Elemente der künstlichen Intelligenz - Teil 7“
S. 124ff. - K Sarnow

[4] Atari ST Programmierpraxis - ST Pascal
Markt & Technik
hsd. S 93ff. - P.Wollschlaeger

[5] Artificial Intelligence through Simulated Evolution
Lawrence J. Fogel u.a.
John Wiley & Sons Inc.. 1966


(***********************************************)
(* Simulation der Evolution einer Elek-Ursuppe *)
(*                                             *) 
(* Version 2.6  fertiggestellt: 1989-07-01     *)
(* Autor: Stefan Winkler / (c) MAXON Computer  *)
(* erstellt mit ST-Pascal plus V1.20 von CCD   *)
(***********************************************)


program elek_simulation; 

const
    max_zustaende = 25; 
    max_eleks = 150;

type
    elek_type = array [1..100] of integer;
                        (* 100 = 4*max_zustaende *)

var
    i,zustaende,eleks,umweltlaenge,grafik_flag, abstand : integer;
    paarungsschwelle real;
    umw,umwstr : string [255];
    umwelt : array [1..255] of integer;
    elek : array [1..max_eleks] of elek_type;
    y0pos,y1pos : array [1..max_eleks] of long_integer;

function rnd : real;
    (* gibt Zufallszahl zwischen 0 und 1 zurück *)
        function random : integer;
            xbios (17);
begin
    rnd:=abs(random)/32770;
end;



procedure schoepfung;
(* initialisiert Eleks mit Zufallswerten *)
var
    i,j : integer;
begin
    for i:=1 to eleks do
    begin
        j:=1;
        repeat
            elek[i][j]:=round(rnd);
            elek[i][j+1]:=shl(trunc(rnd*zustaende)+1,2)-2;
            j:=j+2;
        until j>shl(zustaende,2);
    end;
end;

procedure grafik_init;
(* zeichnet 10-Prozent-Linien *)
var
    pat,i : integer;
begin
    write(chr(27), 'E');
    pat:=$AAAA;
    for i:=1 to 9 do
        hline(0,i*40,639,1,0,0,0,2,pat,0);
    pat:=$FFFF;
    hline(0,0,639,0,0,0,0,0,pat,0);
    hline(0,200,639,0,0,0,0,0,pat,0);
end;

procedure simulation;
var
    i,el,pos,zust,min_elek,max_elek,richtig,swap,manfang,ende,xpos : integer;
    durchgang,minimum,maximum : long_integer;
    c : char;
begin
    for i:=1 to eleks do
        y0pos[i]:=399;
    grafik_init;
    durchgang:=0;
    repeat
        durchgang:=durchgang+1;
        maximum:=0;
        minimum:=umweltlaenge;
        for el:=1 to eleks do
        begin
            zust:=2;
            richtig:=0;
(* Vergleich des Outputs mit der Umwelt: *)
            for i:=1 to umweltlaenge do 
            begin
                if umwelt[i]=elek[el][zust-1] then 
                    richtig:=richtig+l;
                zust:=elek[el][zust]+shl(umwelt[i],1); 
            end;
            y1pos[el]:=richtig;
            if richtig>maximum then 
            begin
                max_elek:=el;
                maximum:=richtig; 
            end
            else
                if richtig<minimum then
                    minimum:=richtig; 
        end;
(* hier wird das Ergebnis dargestellt: *) 
        xpos:=int((durchgang*abstand)mod 640); 
        if grafik_flag=1 then
        begin
            if durchgang mod 640=0 then 
                grafik_init;
            line(xpos,int(400-(maximum*400)div umweltlaenge),
                 xpos,int(400-(minimum*400)div umweltlaenge),
                 0,0,0,0,$FFFF,2);
        end 
        else
        begin
            if xpos=0 then
                xpos:=640;
            for i:=1 to eleks do
                y1pos[i]:=400-(y1pos[i]*400)div umweltlaenge;
            for i:=1 to eleks do 
                line(xpos-abstand,int(y0pos[i]),xpos,
                    int(y1pos[i]),0,0,0,0,$FFFF,0); 
            if xpos=640 then
                grafik_init; 
            y0pos:=y1pos;
        end;
(* jetzt werden einige Eleks verändert... *)
        if maximum<umweltlaenge then
        begin
(* zuerst das "kosmische Teilchen": *)
            el:=trunc(rnd*eleks)+1; 
            pos:=trunc(rnd*zustaende*4)+1; 
            if pos mod 2=0 then
                elek[el][pos]:=(trunc(rnd*zustaende*2)+1)*2
            else 
                elek[el][pos]:=1-elek[el][pos];
(* nun die Paarung: *)
            if rnd>paarungsschwelle then 
            begin
                repeat 
                    el:=trunc(rnd*eleks)+1;
                until el<>max_elek;
                anfang:=trunc(rnd*zustaende*4)+1; 
                ende:=trunc(rnd*zustaende*4)+1; 
                if anfang>ende then
                begin
                    swap:=ende; 
                    ende:=anfang; 
                    anfang:=swap;
                end;
                for i:=anfang to ende do
                    elek[el][i]:=elek[max_elek][i]; 
            end;
        end;
    until maximum=umweltlaenge;
    write(chr(27),'Y',chr(56),chr(32),' Taste...'); 
    read(c);
(* zum Abschluß noch einige Informationen: *) 
    writeln;
    writeln(chr(27),'EUmweltfolge : '); 
    writeln(umwstr);
    writeln;
    writeln('nach ',durchgang,' Durchgängen'); 
    writeln('konnte folgendes Elek diese Umweltfolge richtig voraussagen : '); 
    writeln;
    write(' Taste...');
    read(c);
    writeln(chr(27),'ESignal:   0                 1'); 
    writeln;
    i:=1; 
    repeat
        write(i div 4+1:3,':   (',elek[max_elek][i]:2,',',
                                 (elek[max_elek][1+1]+2)div 4:3,')');
        i:=i+2;
        writeln('   (',elek[max elek][i]:2,',',(elek[max_elek)[i+1]+2)div 4:3,')');
        i:=i+2;
    until i>zustaende*4; 
    write(chr(27),'Y',chr(37),chr(80),' Taste...'); 
    read(c);
    write(chr(27),'Y',chr(37),chr(80));
end;

begin
    write(chr(27),'b',chr(0),chr(27),'c',chr(1),chr(27),'E');
    write('Version 2.6',chr(27),'Y',chr(32),chr(101),chr(189),' Juli 1989'); 
    writeln(chr(27),'Y',chr(34),chr(59),'+-------------------+');
    writeln(chr(27),'Y',chr(35),chr(59),'| Elek - Simulation |');
    writeln(chr(27),'Y',chr(36),chr(59),'+-------------------+');
    writeln;
    writeln;
    write('Anzahl der möglichen Zustände (1..',max_zustaende,') : '); 
    readln(zustaende);
    write('Anzahl der Eleks (1..',max_eleks, ') :'); 
    readln(eleks);
    write('einzelne Eleks oder nur bestes und schlechtestes darstellen (0/1): ');
    readln(grafik_flag);
    if grafik_flag=0 then
    begin
        write('Anzahl übersprungener Pixel(sinnvoll:2,4,5,8,10,16,20,32,40,64): '); 
        readln(abstand);
    end 
    else
        abstand:=1;
    write('Paarungsschwelle (0-immer..1-nie) : ');
    readln(paarungsschwelle);
    write('Länge der Umweltfolge (1..255) : ');
    readln(umweltlaenge);
    writeln;
    writeln('Umweltfolge (wird auf obige Länge periodisch ergänzt) :');
    readln(umw); 
    write(chr(27),'E',chr(27),'f',eleks:4,' Eleks werden erschaffen...');
(* nur Nullen und Einsen in Umweltfolge: *)
    for i:=1 to length(umw) do
        if not (umw[i] in ['O','1']) then
            delete(umw,i,1); 
    if length(umw)<1 then
        umw:='1'; 
    umwstr:='';
(* periodisch erweitern: *)
    for i:=1 to (umweltlaenge div length(umw)) do
        umwstr:=concat(umwstr,umw);
    for i:=1 to (umweltlaenge mod length(umw)) do
        umwstr:=concat(umwstr,umw[i]); 
    for i:=1 to umweltlaenge do
        umwelt[i]:=ord(umwstr[i])-48; 
    schoepfung;
    simulation;
end.

Stefan Winkler
Aus: ST-Computer 05 / 1990, Seite 146

Links

Copyright-Bestimmungen: siehe Über diese Seite