namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:knapsack

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.


anwenden:knapsack [2022-09-27 14:24] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== knapsack : Das Rucksack-Problem: Evolution in einem Byte (+ 1 Bit) ======
 +
 +> Sire, dieser Hypothese bedurfte ich nicht.
 +>>---  Pierre Laplace
 +
 +
 +===== Das Rucksackproblem =====
 +Ein Rucksack fasst nur ein bestimmtes Maximalgewicht.
 +Verschiedene Gegenstände mit unterschiedlicher Masse 
 +und mit unterschiedlichem Gebrauchswert stehen zur Auswahl.
 +Welche der Gegenstände sollen eingepackt werden, 
 +um den Gesamtgebrauchswert zu maximieren, 
 +ohne das Gesamtgewicht zu überschreiten?
 +
 +Das Problem gehört zu den NP-vollständigen Problemen,
 +die nicht in polynomialer Zeit gelöst werden können.
 +Um die beste Lösung zu finden, 
 +müssen alle 2 hoch n Packvarianten ausprobiert und bewertet werden.
 +Jeder weitere Gegenstand würde zur Verdopplung der notwendigen Laufzeit führen.
 +
 +Oft reicht jedoch schon eine Lösung in der Nähe des Optimums.
 +
 +===== Genetische Algorithmen =====
 +Die Idee der evolutionären Algorithmen wurde 1975 von
 +[[http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htm|John Holland]]
 +fixiert, nachdem sie in den Sechzigern mehrfach formuliert wurde. 
 +In Anlehnung an die biologische Evolution treten Individuen
 +mit unterschiedlichen Genomen miteinander in den Wettbewerb.
 +Fortpflanzung kombiniert Teile der Eltern-Genome zu neuen Lösungen
 +in den Genomen der Kinder (Kreuzung).
 +Mutationen führen ebenfalls zu Änderungen im Genom.
 +Durch Auslese werden sich die "fittesten" Lösungen durchsetzen.
 +Dazu wird der sich aus dem Genom entwickelnde "Phänotyp" 
 +der einzelnen Individuen mit einer Zielfunktion bewertet.
 +Die Genome der Lösungen werden im Laufe der Zeit immer besser werden.
 +Die Hoffnung ist, eine fast optimale Lösung in kürzerer Zeit
 +als durch erschöpfende Suche zu finden.
 +
 +Ein kleines {{knapsack.cpp|C++-Programm}} demonstriert die Arbeitsweise.
 +Es soll ja Leute geben, die nicht akzeptieren wollen,
 +dass die Darwinsche Idee tatsächlich und so einfach funktioniert...
 +
 +===== Implementation =====
 +<code cpp>
 +//: knapsack.cpp : Rucksack-Problem - R.Richter 2003-04-12
 +// evolutionärer Ansatz - genetischer Algorithmus
 +//////////////////////////////////////////////////////////
 +
 +#include <ctime>     // time(), clock()
 +#include <cstdlib>   // rand()
 +#include <iostream>
 +#include <algorithm> // sort()
 +
 +</code>
 +==== Das allgemeine Vorgehen ====
 +Eine Population von Individuen wird einer Reihe
 +von Operationen unterworfen:
 +
 +<code cpp>
 +// ===[ Interface ]========================================
 +
 +struct Population;
 +void starten  (Population& p);
 +void vermehren(Population& p);
 +void mutieren (Population& p);
 +void auslesen (Population& p);
 +void bewerten (Population const& p);
 +bool beenden  (Population const& p);
 +
 +void evolution(Population& p)
 +{
 +  starten (p);
 +  bewerten(p);
 +  while (!beenden(p))
 +  {
 +    vermehren(p);
 +    mutieren (p);
 +    auslesen (p);
 +    bewerten (p);
 +  }
 +}
 +
 +</code>
 +Diese allgemeine Vorschrift ist für alle 
 +evolutionären Algorithmen charakteristisch [Fogel, S. 151].
 +
 +Die evolutionären Operationen arbeiten mit einzelnen Individuen
 +und deren Genom, ohne hier genau sagen zu müssen,
 +wie dieses Genom aufgebaut ist und was welches Gen bewirkt:
 +
 +<code cpp>
 +struct Genom;
 +double fitness (Genom const& g); // Zielfunktion
 +void   mutieren(Genom& g);
 +void   kreuzen (Genom const& elter1, Genom const& elter2, 
 +                      Genom& kind1,        Genom& kind2);
 +
 +</code>
 +==== Rucksäcke als Individuen ====
 +Der Träger des Rucksackes steht vor folgendem Problem:
 +Welche der folgenden Gegenstände können mitgenommen werden,
 +ohne das Maximalgewicht zu überschreiten?
 +
 +<code cpp>
 +// ===[ Real-World-Problem ]===============================
 +
 +int const MAX_GEGENSTAENDE = 9;
 +double const MAX_GEWICHT = 10;  // Kinderrucksack :-)
 +
 +</code>
 +Die Gegenstände werden gewogen 
 +und ihr (vermuteter) Nutzwert eingeschätzt:
 +
 +|Gegenstand   |Gewicht|Gebrauchswert|Mitnahme|
 +|Taschenlampe |    0.3|            6|   1|
 +|Regenumhang  |    1.5|            5|   1|
 +|Gitarre      |    3.0|            1|   0|
 +|Landkarte    |    0.3|            7|   1|
 +|Schokolade      0.3|            3|   0|
 +|Wasserflasche|    2.0|            5|   1|
 +|Wechselwäsche|    2.5|            2|   0|
 +|Essen        |    1.5|            4|   1|
 +|Kuscheltier  |    1.0|            1|   0|
 +
 +
 +<code cpp>
 +double const gewichte[MAX_GEGENSTAENDE] =
 +{
 +  0.3, 1.5, 3.0, 0.3, 0.3, 2, 2.5, 1.5 , 1.0
 +};
 +
 +int const gebrauchswerte[MAX_GEGENSTAENDE] =
 +{
 +  6, 5, 1, 7, 3, 5, 2, 4, 1
 +};
 +
 +// ===[ Codierung ]========================================
 +
 +</code>
 +==== Genetische Codierung und Zielvorgabe ====
 +Die Entscheidung über die Mitnahme lässt sich 
 +in einem binär codierten Genom unterbringen:
 +
 +<code cpp>
 +int const GENOM_LENGTH = MAX_GEGENSTAENDE;
 +
 +struct Genom
 +{
 +  bool base[GENOM_LENGTH];
 +};
 +
 +</code>
 +Statt Adenin-/Gyanin- und Cytosin-/Thymin-Basenpaaren
 +bei der biologischen Evolution
 +werden nur boolesche Werte gespeichert. 
 +(Die vier Basen könnten in je einem bool-Paar codiert sein.)
 +
 +Mit einer Zielfunktion wird der Wert eines Rucksackes eingeschätzt:
 +
 +<code cpp>
 +double fitness(Genom const& g) // Zielfunktion
 +{
 +  double wert=0, gewicht=2.0; // wiegt auch leer was 
 +  for (int i=0; i < GENOM_LENGTH; i++)
 +  {
 +    gewicht += g.base[i]*gewichte[i];
 +    wert    += g.base[i]*gebrauchswerte[i];
 +  }
 +  if (gewicht > MAX_GEWICHT) wert = 0; // zu schwer
 +  return wert;
 +}
 +
 +</code>
 +==== Genetische Prozesse ====
 +Die genetischen Vorgänge sind unabhängig vom konkreten Problem
 +modellierbar. Gene verändern sich durch zufällige Mutation
 +
 +<code cpp>
 +void mutieren(Genom& g)
 +{
 +  int pos = rand() % GENOM_LENGTH;
 +  g.base[pos] = !g.base[pos];
 +}
 +
 +</code>
 +und durch Durchmischung bei der Fortpflanzung. 
 +Dabei werden Teile zweier Genome an einer (hier zufällig) 
 +ausgewählten Stelle über Kreuz kopiert:
 +
 +<code cpp>
 +// 1-Point-Crossover (1X)
 +// 01000:101 => 01000:010
 +// 11010:010 => 11010:101
 +
 +void kreuzen(Genom const& elter1, Genom const& elter2, 
 +                   Genom& kind1,        Genom& kind2)
 +{
 +  int i, pos = rand() % GENOM_LENGTH;
 +  for (i=0; i < pos; i++)
 +  {
 +    kind1.base[i] = elter1.base[i];
 +    kind2.base[i] = elter2.base[i];
 +  }
 +  for (; i < GENOM_LENGTH; i++)
 +  {
 +    kind1.base[i] = elter2.base[i];
 +    kind2.base[i] = elter1.base[i];
 +  }
 +}
 +
 +</code>
 +==== Die Beschreibung der Population ====
 +<code cpp>
 +int const MAX_INDIVIDUEN = 35; // vier reichen auch ...
 +int const MAX_NACHKOMMEN = 2;
 +
 +struct Population
 +{
 +  Genom individuen[MAX_INDIVIDUEN+MAX_NACHKOMMEN];
 +  int zeit;
 +};
 +
 +</code>
 +Gestartet wird mit einer Zufallsbelegung der Genome.
 +
 +<code cpp>
 +void starten(Population& p)
 +{
 +  for (int i=0; i<MAX_INDIVIDUEN; i++)
 +  {
 +    for (int j=0; j<GENOM_LENGTH; j++)
 +    {
 +      p.individuen[i].base[j] = bool(rand() > RAND_MAX/2);
 +    }
 +  }
 +  p.zeit = 0;
 +}
 +
 +</code>
 +Zur Paarung kommen bevorzugt Individuen,
 +die bezüglich ihrer Umwelt vorteilhaft ausgestattet sind.
 +Nach dem Motto "Traumprinz sucht Traumprinzessin"
 +suchen die Individuen durch die Partnerwahl ("gute Partie"
 +die Chancen ihrer Nachkommenschaft zu verbessern:
 +
 +<code cpp>
 +void vermehren(Population& p)
 +{
 +  double paarungstoleranz = 0.5;  // max. 1.0
 +  int elter1, elter2, kind = MAX_INDIVIDUEN,
 +      grenze = int(paarungstoleranz*MAX_INDIVIDUEN);
 +  do        
 +  {
 +    elter1 = rand() % grenze;
 +    elter2 = rand() % grenze;
 +  } while (elter1 == elter2);
 +
 +  kreuzen(p.individuen[elter1], p.individuen[elter2], 
 +          p.individuen[kind],   p.individuen[kind+1]);
 +}
 +
 +</code>
 +Ein engerer Heiratsmarkt führt zu höherem Selektionsdruck.
 +Gleichzeitig steigt auch die Gefahr, das Optimum zu verfehlen. 
 +Bei unzureichender Durchmischung des Genpools (Inzucht) 
 +setzen sich schnell suboptimale Lösungen durch (deutscher Hochadel).
 +
 +Mutationen betreffen zufällig die Gene einzelner Individuen:
 +
 +<code cpp>
 +void mutieren(Population& p)
 +{
 +  int i = rand() % MAX_INDIVIDUEN;
 +  mutieren(p.individuen[i]);
 +}
 +
 +</code>
 +Ob die Individuen sich zu ihrem Vorteil oder Nachteil entwickelt haben,
 +wird festgestellt, wenn sie sich 
 +im Wettbewerb durchsetzen müssen:
 +
 +<code cpp>
 +bool vorteil(Genom const& g1, Genom const& g2)
 +{
 +  return fitness(g1) > fitness(g2);
 +}
 +
 +</code>
 +Die Darwinsche Evolutionstheorie postuliert das Überleben
 +der am besten angepassten Individuen:
 +
 +<code cpp>
 +void auslesen(Population& p)
 +{
 +  p.zeit++;
 +  int anzahl = MAX_INDIVIDUEN + MAX_NACHKOMMEN;
 +  std::sort(p.individuen, p.individuen+anzahl, vorteil); // die besten nach vorn
 +}
 +
 +</code>
 +Die Population wird beständig überwacht und bewertet:
 +
 +<code cpp>
 +double wertung=0, alte_wertung=0;
 +
 +void bewerten(Population const& p)
 +
 +#ifdef unix        
 +  system("clear");
 +#else  
 +  system("cls");
 +#endif  
 +  std::cout << p.zeit << 
 +          ". Runde\n"
 +          "Fitness\tGenom\n"
 +          "===============================";
 +
 +  alte_wertung = wertung;  
 +  wertung = 0;
 +  for (int i=0; i < MAX_INDIVIDUEN; i++)
 +  {
 +    double fitness_i = fitness(p.individuen[i]);
 +    wertung += fitness_i;
 +
 +    if (i<18) // unsere Besten-Wandtafel
 +    {
 +      std::cout << '\n' << fitness_i << '\t';
 +      for (int j=0; j < GENOM_LENGTH; j++)
 +      {
 +        std::cout << (p.individuen[i].base[j] ? '1':'0');
 +      }
 +    }
 +  }
 +  std::cout << "\n===============================\n"
 +            << wertung << "\tGesamtbewertung " << std::endl;
 +
 +  // void warte_msek(unsigned millisek);
 +  // warte_msek(0); // falls es zu schnell geht ...
 +}
 +
 +</code>
 +Der evolutionäre Algorithmus endet, wenn - ja wenn??
 +
 +<code cpp>
 +bool beenden(Population const& p)
 +{
 +  // maximale Rundenzahl
 +  // oder keine Verbesserung über eine Anzahl von Runden
 +  static int wiederholungen = 0;
 +  if (wertung == alte_wertung)
 +    wiederholungen++;
 +  else
 +    wiederholungen = 0;  
 +
 +  return wiederholungen >= 10 || p.zeit >= 1000;
 +}
 +
 +</code>
 +==== Hauptprogramm ====
 +Der Evolutionsprozess muss nur noch angestossen werden:
 +
 +<code cpp>
 +int main()
 +{
 +  srand(time(NULL));
 +
 +  Population p;
 +  evolution(p);
 +
 +  std::cout << "Weiter mit ENTER...";
 +  std::cin.get();
 +  return 0;
 +}
 +
 +</code>
 +In einer Population von 35 Individuen setzt sich bei 50% Paarungstoleranz
 +nach 70 bis 110 Runden (mit je einer Mutation und zwei Nachkommen)
 +eine genetische Lösung durch und verdrängt alle anderen. 
 +In 80 von 100 Fällen ist die dominante Lösung optimal.
 +Also Gene mixen und ...
 +
 +<code cpp>
 +void warte_msek(unsigned millisek)
 +{
 +  unsigned start = clock();
 +  while ((clock()-start)*CLOCKS_PER_SEC/1000 < millisek)
 +    ; // Heute tue ich, was ich will: Nichts. [Gauloises Blondes]
 +}
 +
 +</code>
 +===== Literatur =====
 +[Fogel] Zbigniew Michalewicz, David B. Fogel: 
 +How to Solve It: Modern Heuristics. Springer (2000).
 +ISBN 3-540-66061-5
 +
 +[Holland]
 +John H. Holland: Genetic Algorithms. 
 +[[http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htm]]
 +
 +
  

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki