5.4.2 Lösung mithilfe eines genetischen Algorithmus

// Time-stamp: "04.05.03 05:42 gen_dose.cpp klaus@wachtler.de"
//
// Findet eine (fast) optimale Lösung der Aufgabenstellung
// "Blechdose eines bestimmten Volumens mit kleinster Oberfläche"
// mithilfe eines genetischen Algorithmus.
//
// Da eine Gleitkommazahl einerseits als Durchmesser, aber andererseits
// als Erbinformation mit 32 Bit verwendet wird, kann dieses Programm
// nur auf Rechnern mit 32-Bit-Darstellung für eine float und
// 4 Byte für eine int verwendet werden.
//
// Weiterhin ist es nur auf GNU-Systemen lauffähig, weil eine
// nicht standardisierte Funktion
//    int isnan(double)
// verwendet wird, um eine Gleitkommazahl auf Gültigkeit zu testen.
//
// Die Gene eines Lebewesens bestehen aus einer Gleitkommazahl,
// die den Durchmesser der Dose in cm repräsentiert (32 bit als float).
//
// Dieses Programm ist keineswegs auf Effektivität getrimmt;
// es soll nur das Prinzip verdeutlichen.
//
// Kompilieren und starten unter Linux:
// g++ -Wall gen_dose.cpp -o gen_dose && gen_dose
//
//
// Änderungen:
//
// 04.05.2003 kw  Kommentare korrigiert

#include <cfloat>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

#define PI  3.1415926534

// liefert mit der übergebenen Wahrscheinlichkeit true, sonst false:
bool vielleicht_ja( double wahrscheinlichkeit )
{
  return rand() < (int)( wahrscheinlichkeit*RAND_MAX );
}

// liefert eine Zufallszahl zwischen 0 und (modwas-1)
int randmod( int modwas )
{
  return rand()%modwas;
}

// die Standardfunktion rand() liefert üblicherweise nicht 32 Bit
// lange Zufallswerte, sondern typischerweise 16...31 Bit, die mit
// Nullen zu einer int aufgefüllt werden (je nach RAND_MAX).
// Die folgende Funktion liefert dagegen volle 32 zufällige Bit
// (falls RAND_MAX zumindest 255 ist):
unsigned irand()
{
  return (rand()<<24) ^ (rand()<<16) ^ (rand()<<8) ^ rand();
}


#define WRSCH_MUTATION       0.01 // Wahrscheinlichkeit einer Mutation
#define GENZAHL_MUTATION     1    // Höchstzahl mutierter Gene
#define WRSCH_REKOMBINATION  0.4  // Wahrscheinlichkeit einer Rekombination
#define ANZAHL_LEBEWESEN     200  // Größe des Genpools

// Datentyp für die Gene:
typedef union { float d; unsigned igen; } gen_t;

// Datentyp für ein Lebewesen:
// Seine Gene (gen_t) sowie gleich ein Wert für die
// Zielfunktion; dann braucht diese nicht so oft neu berechnet
// zu werden:
typedef struct { gen_t gen; double fitness; } wesen_t;

// erstellt anhand eines übergebenen Gens eine Bewertung des
// Lebewesens: hoher Wert="guter Junge", niedriger Wert="untauglich".
// Diese Zielfunktion ist einfach der negative Wert der
// Dosenoberfläche.
double Zielfunktion( const gen_t &gen )
{
  const double Volumen = 850;  // eine Dose Tomatenmark, [ml] bzw. [cm^3]
  double durchmesser = gen.d;  // Durchmesser [cm] holen

  // negativer Durchmesser? Ist Unfug -> sehr untauglich
  if( isnan( durchmesser ) || durchmesser<=0.0 )
  {
    return -DBL_MAX;  // schlechter gehts nicht!
  }

  // Aus Durchmesser [cm] und Volumen [cm^3] die Höhe [cm] berechnen:
  double hoehe = Volumen/(durchmesser*durchmesser*PI/4.0);
  // Die Fläche der Dose ist 2*Kreisfläche + Zylinder:
  double flaeche     // [cm^2]
    = ( 2.0*durchmesser*durchmesser*PI/4.0   // 2*Kreisfläche
        +
        durchmesser*PI*hoehe                 // Zylinderfläche
        );
  return -flaeche;  // zu maximierender Wert
}

// Initialisiert die Lebewesen mehr oder weniger sinnvoll:
void init_wesen( wesen_t wesen[], size_t n_wesen )
{
  for( size_t i=0; i<n_wesen; i++ )
  {
    wesen[i].gen.igen = irand();  // zufälliger Wert in der Ursuppe
    wesen[i].fitness  = Zielfunktion( wesen[i].gen );
  }
}

// listet alle Wesen mit ihrer Tauglichkeit:
void zeige_population( wesen_t wesen[], size_t n_wesen )
{
  //// Ausgabe aller Lebewesen:
  //for( size_t i=0; i<n_wesen; i++ )
  //{
  //  printf( "[%3u] 0x%08x/%15.4g => %15.4g\n",
  //          i,
  //          wesen[i].gen.igen,
  //          wesen[i].gen.d,
  //          wesen[i].fitness
  //          );
  //}

  // Ausgabe des besten Werts und des Durchschnitts der 5 besten:
  double dSchnitt = 0.0;
  for( size_t i=( n_wesen>5 ? n_wesen-6 : 0 ); i<n_wesen; i++ )
  {
    dSchnitt += wesen[i].gen.d;
  }
  dSchnitt /= 5.0;
  printf( "%20.8g %20.8g\n", wesen[n_wesen-1].gen.d, dSchnitt );
}

// Vergleichsfunktion für bsearch() und qsort() für wesen_t
// anhand ihrer fitness:
int vergleiche_wesen( const void *p1, const void *p2 )
{
  if( ((wesen_t*)p1)->fitness-((wesen_t*)p2)->fitness < 0.0 )
  {
    return -1;
  }
  else if( ((wesen_t*)p1)->fitness-((wesen_t*)p2)->fitness > 0.0 )
  {
    return +1;
  }
  else
  {
    return 0;
  }
}

// sortiert die Wesen anhand ihrer Tauglichkeit
void sortiere_wesen( wesen_t wesen[], size_t n_wesen )
{
  qsort( wesen, n_wesen, sizeof(wesen_t), vergleiche_wesen );
}

// Hier wird "Lieber Gott" gespielt:
// Die Population erlebt einen Schritt der Evolution.
void evolution( wesen_t wesen[], size_t n_wesen )
{
  // Vorgehensweise:
  // Jedes Wesen des "besseren Drittels" wird mit einer
  // Wahrscheinlichkeit von WRSCH_REKOMBINATION mit einem beliebigen
  // anderen kombiniert; die beiden entstehenden neuen
  // (mit vertauschter Herkunft jedes Gens) ersetzen jeweils ein
  // Wesen aus den schlechteren zwei Dritteln.
  // Alle Wesen mutieren außerdem mit einer
  // Wahrscheinlichkeit WRSCH_MUTATION. Falls das der Fall ist,
  // werden etwa GENZAHL_MUTATION Gene gekippt.

  size_t n_wesen_1_3 = n_wesen*1/3;  // etwa 1/3 von n_wesen
  size_t n_wesen_2_3 = n_wesen*2/3;  // etwa 2/3 von n_wesen

  // Schleife über alle Wesen:
  for( size_t iWesen=0; iWesen<n_wesen; iWesen++ )
  {
    // besseres Drittel?
    if( iWesen>n_wesen_2_3 )
    {
      // Rekombination?
      if( vielleicht_ja( WRSCH_REKOMBINATION ) )
      {
        // wesen[iWesen] soll rekombiniert werden (cross over).

        // Mit welchem?
        unsigned iWesen2 = rand()%n_wesen;

        // Aber bitte nicht mit sich selbst:
        if( iWesen==iWesen2 )
        {
          --iWesen2;
        }

        // Bitmuster, anhand dessen entschieden wird,
        // welches Gen von iWesen zum ersten Kind kommt (falls Bit=1)
        // oder von iWesen2 (falls 0); jeweils das andere geht
        // zum zweiten Kind:
        unsigned muster = irand();

        // hier kommen die Kinder hin: es wird jeweils ein Kind
        // im unteren Drittel und eines in den unteren zwei Dritteln
        // abgelegt, indem dort ein je Lebewesen ins Gras beißt
        // (waren ja sowieso nicht die besten => Selektion):
        int   iNeu1 = iWesen%n_wesen_1_3;
        int   iNeu2 = iWesen2%n_wesen_2_3;

        //printf( "cross over (%3d,%3d)->(%3d,%3d); muster=0x%08x\n",
        //        iWesen,
        //        iWesen2,
        //        iNeu1,
        //        iNeu2,
        //        muster
        //        );

        // das erste Kind bekommt die Gene von iWesen, falls das
        // entsprechende Bit in muster gesetzt ist; sonst von iWesen2:
        wesen[iNeu1].gen.igen
          = ( ( wesen[iWesen].gen.igen&muster )     // Bits aus iWesen
              |
              ( wesen[iWesen2].gen.igen&(~muster) ) // Bits aus iWesen2
              );
        // Tauglichkeit neu berechnen:
        wesen[iNeu1].fitness = Zielfunktion( wesen[iNeu1].gen );


        // das zweite Kind bekommt die Gene von iWesen2, falls das
        // entsprechende Bit in muster gesetzt ist; sonst von iWesen:
        wesen[iNeu2].gen.igen
          = ( ( wesen[iWesen2].gen.igen&muster )    // Bits aus iWesen2
              |
              ( wesen[iWesen].gen.igen&(~muster) )  // Bits aus iWesen
              );
        // Tauglichkeit neu berechnen:
        wesen[iNeu2].fitness = Zielfunktion( wesen[iNeu2].gen );


      } // Rekombination

    } // besseres Drittel

    // Mutation?
    if( vielleicht_ja( WRSCH_MUTATION ) )
    {
      int AnzahlMutierterGene = randmod( GENZAHL_MUTATION );
      if( AnzahlMutierterGene<1 )
      {
        AnzahlMutierterGene = 1;
      }

      unsigned maske = 0;

      for( int i=0; i<AnzahlMutierterGene; i++ )
      {
        // Eine Bitnummer bestimmen, und das entsprechende
        // Bit in maske setzen:
        maske |= 1<<randmod( 32 );
      }

      // printf( "Mutation von %d mit maske 0x%08x\n", iWesen, maske );

      wesen[iWesen].gen.igen ^= maske;
      wesen[iWesen].fitness = Zielfunktion( wesen[iWesen].gen );

    } // Mutation

  } // Schleife über alle Wesen

}


int main( int nargs, char **args )
{
  // Die Lebewesen:
  wesen_t    wesen[ANZAHL_LEBEWESEN];

  init_wesen( wesen, ANZAHL_LEBEWESEN );
  sortiere_wesen( wesen, ANZAHL_LEBEWESEN );

  unsigned anzahl_schritte;
  if( nargs>1 )
  {
    // Argument übergeben; daraus die Anzahl Schritte lesen:
    anzahl_schritte = strtoul( args[1], NULL, 0 );
  }
  else
  {
    // keine Argumente, also abfragen:
    printf( "Schrittzahl:\n" );
    scanf( "%u", &anzahl_schritte );
  }

  for( unsigned iEvolutionsschritt=0;
       iEvolutionsschritt<anzahl_schritte;
       iEvolutionsschritt++
       )
  {
    // printf( "\nEvolutiunsschritt %d\n\n", iEvolutionsschritt );
    evolution( wesen, ANZAHL_LEBEWESEN );
    sortiere_wesen( wesen, ANZAHL_LEBEWESEN );
    zeige_population( wesen, ANZAHL_LEBEWESEN );
  }

  return 0;
} // main( int nargs, char **args )

Abbildung 5.3: Variation Wahrscheinlichkeit Rekomb. (Mut.=0.01)

Abbildung 5.4: Variation Wahrscheinlichkeit Rekomb. (Mut.=0.05)

Abbildung 5.5: Variation Wahrscheinlichkeit Rekomb. (Mut.=0.10)