// 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 )