namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:knapsack

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

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

Das allgemeine Vorgehen

Eine Population von Individuen wird einer Reihe von Operationen unterworfen:

// ===[ Interface ]========================================
 
struct Population;
void starten  (Population& p);
void vermehren(Population& p);
void mutieren (Population& p);
void auslesen (Population& p);
void bewerten (const Population& p);
bool beenden  (const Population& p);
 
void evolution(Population& p)
{
  starten (p);
  bewerten(p);
  while (!beenden(p))
  {
    vermehren(p);
    mutieren (p);
    auslesen (p);
    bewerten (p);
  }
}

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:

struct Genom;
double fitness (const Genom& g); // Zielfunktion
void   mutieren(Genom& g);
void   kreuzen (const Genom& elter1, const Genom& elter2, 
                      Genom& kind1,        Genom& kind2);

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?

// ===[ Real-World-Problem ]===============================
 
const int MAX_GEGENSTAENDE = 9;
const double MAX_GEWICHT = 10;  // Kinderrucksack :-)

Die Gegenstände werden gewogen und ihr (vermuteter) Nutzwert eingeschätzt:

Gegenstand GewichtGebrauchswertMitnahme
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
const double gewichte[MAX_GEGENSTAENDE] =
{
  0.3, 1.5, 3.0, 0.3, 0.3, 2, 2.5, 1.5 , 1.0
};
 
const int gebrauchswerte[MAX_GEGENSTAENDE] =
{
  6, 5, 1, 7, 3, 5, 2, 4, 1
};
 
// ===[ Codierung ]========================================

Genetische Codierung und Zielvorgabe

Die Entscheidung über die Mitnahme lässt sich in einem binär codierten Genom unterbringen:

const int GENOM_LENGTH = MAX_GEGENSTAENDE;
 
struct Genom
{
  bool base[GENOM_LENGTH];
};

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:

double fitness(const Genom& 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;
}

Genetische Prozesse

Die genetischen Vorgänge sind unabhängig vom konkreten Problem modellierbar. Gene verändern sich durch zufällige Mutation

void mutieren(Genom& g)
{
  int pos = rand() % GENOM_LENGTH;
  g.base[pos] = !g.base[pos];
}

und durch Durchmischung bei der Fortpflanzung. Dabei werden Teile zweier Genome an einer (hier zufällig) ausgewählten Stelle über Kreuz kopiert:

// 1-Point-Crossover (1X)
// 01000:101 => 01000:010
// 11010:010 => 11010:101
 
void kreuzen(const Genom& elter1, const Genom& 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];
  }
}

Die Beschreibung der Population

const int MAX_INDIVIDUEN = 35; // vier reichen auch ...
const int MAX_NACHKOMMEN = 2;
 
struct Population
{
  Genom individuen[MAX_INDIVIDUEN+MAX_NACHKOMMEN];
  int zeit;
};

Gestartet wird mit einer Zufallsbelegung der Genome.

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;
}

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:

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]);
}

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:

void mutieren(Population& p)
{
  int i = rand() % MAX_INDIVIDUEN;
  mutieren(p.individuen[i]);
}

Ob die Individuen sich zu ihrem Vorteil oder Nachteil entwickelt haben, wird festgestellt, wenn sie sich im Wettbewerb durchsetzen müssen:

bool vorteil(const Genom& g1, const Genom& g2)
{
  return fitness(g1) > fitness(g2);
}

Die Darwinsche Evolutionstheorie postuliert das Überleben der am besten angepassten Individuen:

void auslesen(Population& p)
{
  p.zeit++;
  int anzahl = MAX_INDIVIDUEN + MAX_NACHKOMMEN;
  std::sort(p.individuen, p.individuen+anzahl, vorteil); // die besten nach vorn
}

Die Population wird beständig überwacht und bewertet:

double wertung=0, alte_wertung=0;
 
void bewerten(const Population& 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 ...
}

Der evolutionäre Algorithmus endet, wenn - ja wenn??

bool beenden(const Population& 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;
}

Hauptprogramm

Der Evolutionsprozess muss nur noch angestossen werden:

int main()
{
  srand(time(NULL));
 
  Population p;
  evolution(p);
 
  std::cout << "Weiter mit ENTER...";
  std::cin.get();
  return 0;
}

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 …

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]
}

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

anwenden/knapsack.txt · Zuletzt geändert: 2016-12-28 12:35 (Externe Bearbeitung)