kramann.info
© Guido Kramann

Login: Passwort:










Robuste Systemintegration
1 Grundlagen
..1.1 Newton
....1.1.1 LinearSchwinger
....1.1.2 Daempfung
....1.1.4 ODE
....1.1.5 Saaluebung
..1.2 NewtonEuler
....1.2.1 Traegheitsmomente
....1.2.2 Modellgleichungen
....1.2.3 Einfachpendel
..1.3 Scilab
....1.3.1 Erste_Schritte
....1.3.2 Skripte
....1.3.3 Funktionen
..1.4 Laplace
....1.4.1 Eigenwerte
....1.4.2 PT1
..1.5 Regleroptimierung
....1.5.1 Guetefunktion
....1.5.2 Heuristiken
....1.5.3 Scilab
..1.6 Einstellregeln
....1.6.1 Totzeit
....1.6.2 Methode1
....1.6.3 Methode2
....1.6.4 Scilab
..1.7 Zustandsregler
..1.8 Polvorgabe
..1.8 Polvorgabe_alt
..1.9 Beobachter
....1.9.1 Haengependel
..1.10 Daempfungsgrad
..1.11 Processing
....1.11.1 Installation
....1.11.2 Erste_Schritte
....1.11.3 Mechatronik
....1.11.4 Bibliotheken
....1.11.5 Uebung
....1.11.6 Snippets
......1.11.6.1 Dateioperationen
......1.11.6.2 Bilder
......1.11.6.3 GUI
......1.11.6.4 Text
......1.11.6.5 PDF
......1.11.6.8 Maus
......1.11.6.10 Zeit
......1.11.6.13 Animation
......1.11.6.15 Simulation
....1.11.7 Referenzen
..1.12 Breakout
2 Beispiel
3 Beispielloesung
4 Praxis
5 javasci
6 Fehlertoleranz1
7 Reglerentwurf
..7.1 Sprungantwort
..7.2 Messdaten
..7.3 Systemidentifikation
..7.4 Polvorgabe
..7.5 Beobachter
..7.6 Robuster_Entwurf
..7.7 SIL
8 Systementwicklung
9 Arduino
..9.1 Lauflicht
..9.2 Taster
..9.3 Sensor
..9.12 Motor_PWM1
..9.13 Motor_PWM2_seriell
..9.14 Motor_PWM3_analogWrite
..9.15 Scheduler
..9.20 AV
..9.21 Mikrofon
..9.22 Universal
....9.22.1 Laborplatine
....9.22.2 LED_Leiste
....9.22.3 Motortreiber
....9.22.4 Sensoreingaenge
....9.22.5 Taster
....9.22.6 Tests
....9.22.7 Mikrofon
....9.22.8 Lautsprecher
....9.22.9 Fahrgestell
..9.23 Zauberkiste
..9.24 OOP
....9.24.1 Uebungen
..9.25 AVneu
....9.25.1 Tests
..9.26 DA_Wandler
..9.27 CompBoard
....9.27.1 Tastenmatrix
....9.27.2 ASCIIDisplay
..9.28 CTC
..9.29 Tonerzeugung
10 EvoFuzzy
..10.1 Fuzzy
....10.1.1 Fuzzylogik
....10.1.2 FuzzyRegler
....10.1.3 Uebung9
....10.1.5 Softwareentwicklung
......10.1.5.1 AgileSoftwareentwicklung
......10.1.5.2 FuzzyRegler
......10.1.5.3 Uebung
....10.1.6 Umsetzung
......10.1.6.1 FuzzyRegler
......10.1.6.2 Simulation
......10.1.6.3 Optimierung
......10.1.6.4 Uebung
....10.1.7 Haengependel
......10.1.7.1 Haengependel
......10.1.7.2 Simulation
......10.1.7.3 FuzzyRegler
......10.1.7.4 Optimierer
......10.1.7.5 Genetisch
....10.1.8 Information
....10.1.9 Energie
..10.2 Optimierung
....10.2.1 Gradientenverfahren
....10.2.2 Heuristiken
....10.2.3 ModifizierteG
....10.2.4 optim
..10.3 Genalgorithmus
..10.4 NeuronaleNetze
....10.4.1 Neuron
....10.4.2 Backpropagation
....10.4.3 Umsetzung
....10.4.4 Winkelerkennung
..10.5 RiccatiRegler
11 Agentensysteme
12 Simulation
20 Massnahmen
21 Kalmanfilter
..21.1 Vorarbeit
..21.2 Minimalversion
..21.3 Beispiel
30 Dreirad
31 Gleiter
..31.1 Fehlertoleranz
80 Vorlesung_2014_10_01
81 Vorlesung_2014_10_08
82 Vorlesung_2014_10_15
83 Vorlesung_2014_10_22
84 Vorlesung_2014_10_29
kramann.info
© Guido Kramann

Login: Passwort:




Entwicklung allgemein anwendbarer C++ Klassen zur Implementierung eines genetischen Algorithmus

vorlesung_2014_01_07.zip - Quelltexte / Projekte zur Vorlesung vom 7.1.2014.
einachser007optimiert.zip (16.01.2014)

Das Konzept

  • DNA-Objekte enthalten Gen-Elemente.
  • Die Beschaffenheit der Gen-Elemente in einer DNA bestimmt die Ausprägung der daraus erzeugten Individuen
  • Die Individuen werden in einer Umwelt einzeln gestestet und bewertet.
  • In einem Selektionsprozeß werden aus einigen DNA, deren Individuen die besten waren, durch Rekombination neue DNA gebildet, daraus wieder zu testende Individuen usw.
  • Werden beispielsweise zu Beginn 100 zufällige DNA erzeugt, so werden die 10 besten daraus genommen und behalten. Die verbleibenden 90 für die nächste Generation entstehen durch Rekombination der 10 besten.
  • Um zu vermeiden, dass der Optimierungsprozeß in einem lokalen Maximum steckenbleibt, werden die aus dem Rekombinationsprozeß gewonnenen DNA einer Mutation unterzogen, d.h. einer zufälligen leichten Veränderung.
  • Unterschied zu realem Evolutionsprozeß: Eine DNA (Genotyp) ist in der Realität Ursache für viele Individuen (Phenotyp) und nicht nur wir hier für eines.
Schema für die Optimierung mittels eines genetischen Algorithmus.

Bild 0-1: Schema für die Optimierung mittels eines genetischen Algorithmus.

Zuordnung in einem einfachen Beispiel

  • In einem sehr einfachen Beispiel wird die Gradientenfunktion f(x,y) = x^3-4x+y^3-16y als "Umwelt" angesehen, in denen Individuen in Form von Zahlenpaaren x,y "getestet" werden.
  • Die fittesten Individuen, liefern einen möglichst kleinen Wert für f(x,y), bzw. einen möglichst großen für -f(x,y), was eher dem entspricht, dass die Fitness möglichst groß sein soll.
  • Generiert werden die Individuen aus Bitfolgen in der DNA, denen die Gene entsprechen:

Die DNA

  • Die DNA enthält die Gene.
  • Typischerweise enthalten sie die Parameter für unserern Individuen-Konstruktor.
  • Bei unserem Beispiel sollten das eigentlich zwei double-Zahlen x und y sein.
  • Es hat sich aber herausgestellt, dass die Optimierung besser funktioniert, wenn man einen Integer-ähnlichen Typ, z.B. long int nimmt und diesen in eine double-Zahl umrechnet.
  • Denn bei der Mutation wird zufällig ein Bit geändert, das in dem Speicherbereich liegt, der von den Parametern belegt wird.
  • Eine Integer-Zahl ist einfach binär in diesem Speicher kodiert, während eine double-Zahl etwas komplexer aus Vorzeichen, Mantisse und Exponent zusammengesetzt ist.
  • Eine Bitänderung in einem double-Speicherbereich erzeugt recht unvorhersehbare Ergebnisse, die Bitänderung in einem Integer-Speicherbereich führt zu besseren Ergebnissen.
  • Die folgenden Klasse mit Namen DNA ermöglicht es, DNA-Objekte mit einem beliebig großen Array beliebiger Integer-ähnlicher Datentypen zu bilden.
  • Dies gelingt durch Verwendung eines Template-Klassen-Mechanismus, bei dem erst bei Erstellung eines Objektes, der Datentyp in die Schablone eingetragen wird.
  • Mit Schablone ist hier jede Stelle in der Klasse gemeint, wo "meinDATENTYP" steht.
  • Um die Bit-Mutationen durchführen zu können, wird ein zweites Array aus unsigned char-Elementen bebildet, für das kein neuer Speicher allokiert wird, sondern dessen Beginn auf den Beginn des anderen Arrays gesetzt wird.
  • Diesen Abbildungsvorgang und das Messen der Speichergröße, erledigt die Methode init().
  • Um wirklich Speicher für die "Gene" zuallokieren, muß init() auch wirklich aufgerufen werden. Der leere Konstruktor macht dies noch nicht.
  • Zu Beginn des Optimierungsprozesses werden einmal die 100 DNA-Objekte gebildet.
  • Es werden aber nicht bei jeder Generation erneut 100 Objekte neu gebildet, sondern die "Gene" (das Array) der alten DNA werden angepaßt.
  • Um zu Beginn das Array mit Zufallszahlen zu füllen, gibt es die Methode zufall().
  • Um dagegen gezielt Anfangswerte für die Parameter-Arrays vorgeben zu können, z.B. in einem äquidistanten Raster, gibt es die Methode setze().
  • Um für die Mutation ein zufälliges Bit aus dem Speicherbereich auszuwählen und dieses zu flippen, gibt es die Methode mutation.
  • Um bei dem Selektionsprozeß die 10 Besten zu merken, werden deren Gen-Inhalte in einem Hilfs-DNA-Array der Länge 10 zwischengespeichert. Dieser Kopiervorgang kann mit Hilfe der Methode kopieren() erfolgen.
  • Um aus zwei der besten DNA (z.B. dna1 und dna2) ein neues Exemplar zu erzeugen, das teilweise aus der einen und teilweise aus der anderen DNA besteht, wird folgender Weg beschritten:
  • Für jedes Bit des hinter dem Parameter-Array liegenden Speicher, wird für die neue DNA durch Zufall entschieden, ob es aus dna1 oder dna2 heraus genommen wird. Dies erledigt die Methode rekombinieren.
  • Zur besseren Ergebniskontrolle wurden noch zwei Methoden zum Anzeigen der DNA-Inhalte ergänzt: zeigen() zur Darstellung der Zahlenwerte und zeigenBinaer() zur byteweisen Darstellung der einzelnen Bits des die Zahlenarrays repräsentierenden Speicherbereichs.
UML-Klassendiagramm zur Klasse DNA in der Datei DNA.h.

Bild 0-2: UML-Klassendiagramm zur Klasse DNA in der Datei DNA.h.

  • Zur Verdeutlichung, wie die Methoden der Klasse DNA eingesetzt werden, sind sie nachfolgend in dem Optimierungsschema an der entsprechenden Stelle eingetragen.
Wann wird welche Methode aus DNA eingesetzt?

Bild 0-3: Wann wird welche Methode aus DNA eingesetzt?

  • Das Dev-Cpp-Projekt mit dem nachfolgenden Code ist in folgendem .zip-File enthalten:
test_genalgorithmus9_beispiel.zip - Enthält nachfolgende Dateien in einem Dev-Cpp-Projekt.
  • Es folgt nun zunächst der Quellcode der zentralen Klasse DNA im File DNA.h:
template <typename meinDATENTYP>
class DNA
{
    public:
        int anzahl;
        int anzahl_byte;
        int anzahl_bits;
        meinDATENTYP* x;
        unsigned char* b;
        DNA()
        {
        }
        DNA(int anzahl)
        {
            init(anzahl);
        }
        void init(int anzahl)
        {
            this->anzahl = anzahl;
            x = new meinDATENTYP[anzahl+1];
            b = (unsigned char*)&x[0];
            anzahl_byte = (int)( (unsigned char*)&x[anzahl] - (unsigned char*)&x[0] );
            anzahl_bits = anzahl_byte*8;
        }
        void zufall()
        {
            for(int i=0;i<anzahl_byte;i++)
                b[i]=Zufall::zahl(0,255);
        }
        void setze(int nummer, meinDATENTYP wert)
        {
            x[nummer] = wert;
        }
        void mutation()
        {
            int bit_nummer = Zufall::zahl(0,7);
            int byte_nummer = Zufall::zahl(0,anzahl_byte-1);
            if( (b[byte_nummer] & (1<<bit_nummer))>0 )
                 b[byte_nummer] &= 255 - (1<<bit_nummer);
            else
                 b[byte_nummer] |= (1<<bit_nummer);
        }
        void kopieren(DNA<meinDATENTYP>* dna)
        {
            for(int i=0;i<anzahl_byte;i++)
                 b[i] = dna->b[i];
        }
        void rekombinieren(DNA<meinDATENTYP>* dna1, DNA<meinDATENTYP>* dna2)
        {
            for(int i=0;i<anzahl_byte;i++)
            {
                for(int k=0;k<8;k++)
                {
                    if(Zufall::zahl(0,1)==0)
                    {
                        if(  (dna1->b[i] & (1<<k)) > 0 )
                            b[i] |= (1<<k);
                        else
                            b[i] &= 255 - (1<<k);
                    }
                    else
                    {
                        if(  (dna2->b[i] & (1<<k)) > 0 )
                            b[i] |= (1<<k);
                        else
                            b[i] &= 255 - (1<<k);
                    }
                }
            }
        }
        void zeigen()
        {
            cout<<endl;
            for(int i=0;i<anzahl;i++)
                cout<<i<<".: "<<x[i]<<endl;
        }
        void zeigenBinaer()
        {
            int aufteilung = anzahl_byte/anzahl;
            cout<<endl;
            for(int i=0;i<anzahl_byte;i++)
            {
                cout<<endl;
                if(i>0 && i%aufteilung==0)
                    cout<<endl;
                for(int k=0;k<8;k++)
                {
                        if(  (b[i] & (1<<k)) > 0 )
                            cout<<1;
                        else
                            cout<<0;
                }
            }
            cout<<endl;
        }
}; 

Code 0-1: DNA.h - Klasse mit den "Genen" (Array mit Elementen vom Typ "meinDATENTYP") und Methoden zur Manipulation der Gene.

  • In der Methode zufall wird eine statische Methode aus einer Klasse Zufall benutzt.
  • Diese Klasse Zufall befindet sich in der Datei Zufall.h und verwendet die Standard-C-methode rand() zur Generierung von Zufallszahlen.
  • Zur Initialisierung des Startwertes, kann sowohl eine echte Zufallszahl durch Verwendung von time() benutzt werden, oder die Null.
  • Letzteres macht beispielsweise Sinn, wenn man während der Entwicklung Verbesserungen im Algorithmus sehen will und bei jedem Programmlauf die gleichen "Zufallswerte" haben will.
class Zufall
{
    public:
        static void initialisieren_pseudo()
        {
            srand(0);
        }
        static void initialisieren_zeit()
        {
            srand(time(NULL));
        }
        static int zahl(int von, int bis)
        {
            return rand()%(bis-von+1) + von;
        }
};

Code 0-2: Zufall.h - Klasse mit der Methode zahl() zur Generierung von Zufallszahlen im geschlossenen Intervall [von,bis].

  • "Gen-gesteuert" können Individuen generiert werden.
  • Dies wird Programmier-technisch so gelöst, dass einer Generierungsmethode einer Klasse, die die Individuen repräsentiert, die in der Umwelt leben sollen, ein Zeiger auf ein DNA-Objekt übergeben wird.
  • Die Generierungsmethode der Individuum-Klasse, wertet die in dem DNA-Objekt gespeicherten Parameter aus und passt aus dieser Information das bestehende Modell-Objekt an.
  • Der Individuum-Klasse entspräche in einem aufwändigeren Beispiel die Modell-Klasse, also die Klasse, die ein System von Differentialgleichungen repräsentiert, deren Parameter über den Konstruktoer, bzw. die übergebene DNA, eingestellt werden.
  • Der Umwelt-Klasse entspräche in dem aufwändigeren Beispiel der Integrator zuzüglich eines Konstruktes, das den Datenaustausch zwischen Umwelt und Individuen und zwischen den Individuen vornimmt (Kollisionen vor allem).
  • In unserem einfachen Beispiel dagegen, werden in der Individuum-Klasse lediglich die beiden double-Zahlen x und y generiert.
  • Das "Leben" in der "Umwelt" ist hier keine Simulation, sondern lediglich das Einsetzen von x und y in eine Gleichung, die direkt die Fitness ergibt.
  • In einer aufwändigeren Umwelt, würde das Individuum-Modell richtig simuliert werden und als Fitness beispielsweise die Dauer genommen werden, die verstreicht, bis eine erste Kollision mit der Umwelt oder einem anderen Individuum auftritt.
  • Bei diesem aufwändigerem Fall wäre dem Umstand Rechnung zu tragen, dass nicht unbedingt das "gute" Individuum "Schuld" an einer Kollision trägt, sondern ev. ein ungebärdiges "schlechteres"/weniger fittes.
  • Nachfolgend sind nun die Quellcodes der Klassen Umwelt aus dem File Umwelt.h und Individuum aus dem File Individuum.h abgebildet.
  • Der Methodenname "regeneriereIndividuum()" in Individuum.h ist mit Bedacht gewählt, da wie bei DNA zu Beginn 100 Individuen generiert werden, die dann immer wieder geändert werden, statt in jeder Generation neue Objekte zu erzeugen (und damit Speicherallokierungen anzustoßen, deren Verwaltung zu Problemen führen könnte nach z.B. 10000 Generationen!).
class Individuum
{
    public:
        double x,y;
        void regeneriereIndividuum(DNA<long int>* dna)
        {
            x = 0.000001*(double)(dna->x[0]);
            y = 0.000001*(double)(dna->x[1]);
        }
};

Code 0-3: Individuum.h - Wertepaar x,y wird durch eine als Zeiger übergebene DNA manipuliert.

  • Die Umwelt-Klasse repräsentiert die Potentialfunktion:
class Umwelt
{
    public:
        double testeFitness(Individuum* ind)
        {
            double f = -(ind->x*ind->x*ind->x-4.0*ind->x+ind->y*ind->y*ind->y-16.0*ind->y);
            //Um ein Weglaufen in ein globales Maximum im Unendlichen zu vermeiden, Funktionsränder "abschneiden":
            if(ind->x<-100.0 || ind->x>100.0 || ind->y<-100.0 || ind->y>100.0)
                f = -100.0;
            return f;
        }
};

Code 0-4: Umwelt.h - dient dazu Individuen zu testen und deren Fitness zu bestimmen.

  • Das Hauptprogramm steuert die Selektion von Generation zu generation:
  • Es läuft in folgender Weise ab:
Ablaufschema für das Hauptprogramm, Teilbezeichnungen, wie in nachfolgendem Quellcode.

Bild 0-4: Ablaufschema für das Hauptprogramm, Teilbezeichnungen, wie in nachfolgendem Quellcode.

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;
#include "Zufall.h"
#include "DNA.h"
#include "Individuum.h"
#include "Umwelt.h"
#define ANZAHL_DNA 100
#define ANZAHL_BESTE 10
int main(int argc, char *argv[])
{
    //Teil 1:
    int anzahl_mutationen=10;
    DNA<long int> dna[ANZAHL_DNA];
    Individuum ind[ANZAHL_DNA];
    double fit,fit_alt;
    double besten_fitness[ANZAHL_BESTE];
    int besten_index[ANZAHL_BESTE];
    DNA<long int> besten_dna[ANZAHL_BESTE];
    Umwelt umwelt;
    //Teil 2:
    for(int i=0;i<ANZAHL_DNA;i++)
        dna[i].init(2);
    for(int i=0;i<ANZAHL_BESTE;i++)
        besten_dna[i].init(2);
    for(int i=0;i<100;i++)
    {
        dna[i].x[0] = 10000*(i%10);
        dna[i].x[1] = 10000*(i/10);
    }
    //Teil 3:
    ind[0].regeneriereIndividuum(&dna[0]);
    fit = umwelt.testeFitness(&ind[0]);    
    for(int p=0;p<ANZAHL_BESTE;p++)
    {
        besten_fitness[p]=fit;
        besten_index[p]=0;
    }
    //Teil 4:
    for(int generation=0;generation<100;generation++)
    {
        //Teil 4.1
        for(int i=0;i<ANZAHL_DNA;i++)
        {
            ind[i].regeneriereIndividuum(&dna[i]);
            fit = umwelt.testeFitness(&ind[i]);    
            if(fit>=besten_fitness[0])
            {
                for(int p=ANZAHL_BESTE-1;p>=1;p--)
                {
                    besten_fitness[p]=besten_fitness[p-1];
                    besten_index[p]=besten_index[p-1];
                }
                besten_fitness[0]=fit;
                besten_index[0]=i;
            }
        }
        //Teil 4.2
        if(generation%1==0)
        {
            cout<<"Gener. Nr."<<generation;
            printf(" Groesste Fitn.: %8.8f",besten_fitness[0]);
//            cout<<" Groesste Fitness:"<<besten_fitness[0];
//            cout<<" bei Individuum x="<<ind[besten_index[0]].x<<" y="<<ind[besten_index[0]].y<<endl;
            printf(" bei Indiv. x=%8.8f y=%8.8f\n",ind[besten_index[0]].x,ind[besten_index[0]].y);
        }
        //Teil 4.3
        for(int k=0;k<ANZAHL_BESTE;k++)
            besten_dna[k].kopieren(&dna[besten_index[k]]);
        for(int k=0;k<ANZAHL_BESTE;k++)
            dna[k].kopieren(&besten_dna[k]);
        for(int k=ANZAHL_BESTE;k<ANZAHL_DNA;k++)
            dna[k].rekombinieren(&dna[rand()%ANZAHL_BESTE],&dna[rand()%ANZAHL_BESTE]);
        for(int k=ANZAHL_BESTE;k<ANZAHL_DNA;k++)
            for(int p=0;p<anzahl_mutationen;p++)
                dna[k].mutation();
        //Teil 4.4
        if( fit_alt+0.001>fit  )
        {
            anzahl_mutationen*=2;
            anzahl_mutationen%=32;
        }
        else
        {
            anzahl_mutationen/=2;
            if(anzahl_mutationen<2)
                anzahl_mutationen=2;
        }
        fit_alt = fit;
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

Code 0-5: genalgorithmus.cpp - Hauptprogramm.