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: | ||
+ | |||
+ | > Sire, dieser Hypothese bedurfte ich nicht. | ||
+ | >> | ||
+ | |||
+ | |||
+ | ===== 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:// | ||
+ | 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 " | ||
+ | Dazu wird der sich aus dem Genom entwickelnde " | ||
+ | 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 < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | </ | ||
+ | ==== Das allgemeine Vorgehen ==== | ||
+ | Eine Population von Individuen wird einer Reihe | ||
+ | von Operationen unterworfen: | ||
+ | |||
+ | <code cpp> | ||
+ | // ===[ Interface ]======================================== | ||
+ | |||
+ | struct Population; | ||
+ | void starten | ||
+ | void vermehren(Population& | ||
+ | void mutieren (Population& | ||
+ | void auslesen (Population& | ||
+ | void bewerten (Population const& p); | ||
+ | bool beenden | ||
+ | |||
+ | void evolution(Population& | ||
+ | { | ||
+ | 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: | ||
+ | |||
+ | <code cpp> | ||
+ | struct Genom; | ||
+ | double fitness (Genom const& g); // Zielfunktion | ||
+ | void | ||
+ | void | ||
+ | Genom& kind1, | ||
+ | |||
+ | </ | ||
+ | ==== 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 :-) | ||
+ | |||
+ | </ | ||
+ | Die Gegenstände werden gewogen | ||
+ | und ihr (vermuteter) Nutzwert eingeschätzt: | ||
+ | |||
+ | |Gegenstand | ||
+ | |Taschenlampe | 0.3| 6| 1| | ||
+ | |Regenumhang | ||
+ | |Gitarre | ||
+ | |Landkarte | ||
+ | |Schokolade | ||
+ | |Wasserflasche| | ||
+ | |Wechselwäsche| | ||
+ | |Essen | ||
+ | |Kuscheltier | ||
+ | |||
+ | |||
+ | <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 ]======================================== | ||
+ | |||
+ | </ | ||
+ | ==== 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]; | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Statt Adenin-/ | ||
+ | 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; | ||
+ | for (int i=0; i < GENOM_LENGTH; | ||
+ | { | ||
+ | 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 | ||
+ | |||
+ | <code cpp> | ||
+ | void mutieren(Genom& | ||
+ | { | ||
+ | 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: | ||
+ | |||
+ | <code cpp> | ||
+ | // 1-Point-Crossover (1X) | ||
+ | // 01000:101 => 01000:010 | ||
+ | // 11010:010 => 11010:101 | ||
+ | |||
+ | void kreuzen(Genom const& elter1, Genom const& elter2, | ||
+ | | ||
+ | { | ||
+ | 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; | ||
+ | { | ||
+ | kind1.base[i] = elter2.base[i]; | ||
+ | kind2.base[i] = elter1.base[i]; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ==== 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; | ||
+ | }; | ||
+ | |||
+ | </ | ||
+ | Gestartet wird mit einer Zufallsbelegung der Genome. | ||
+ | |||
+ | <code cpp> | ||
+ | void starten(Population& | ||
+ | { | ||
+ | for (int i=0; i< | ||
+ | { | ||
+ | for (int j=0; j< | ||
+ | { | ||
+ | p.individuen[i].base[j] = bool(rand() > RAND_MAX/ | ||
+ | } | ||
+ | } | ||
+ | p.zeit = 0; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Zur Paarung kommen bevorzugt Individuen, | ||
+ | die bezüglich ihrer Umwelt vorteilhaft ausgestattet sind. | ||
+ | Nach dem Motto " | ||
+ | suchen die Individuen durch die Partnerwahl ("gute Partie" | ||
+ | die Chancen ihrer Nachkommenschaft zu verbessern: | ||
+ | |||
+ | <code cpp> | ||
+ | void vermehren(Population& | ||
+ | { | ||
+ | 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[kind], | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | 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& | ||
+ | { | ||
+ | int i = rand() % MAX_INDIVIDUEN; | ||
+ | mutieren(p.individuen[i]); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Ob die Individuen sich zu ihrem Vorteil oder Nachteil entwickelt haben, | ||
+ | wird festgestellt, | ||
+ | im Wettbewerb durchsetzen müssen: | ||
+ | |||
+ | <code cpp> | ||
+ | bool vorteil(Genom const& g1, Genom const& g2) | ||
+ | { | ||
+ | return fitness(g1) > fitness(g2); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Die Darwinsche Evolutionstheorie postuliert das Überleben | ||
+ | der am besten angepassten Individuen: | ||
+ | |||
+ | <code cpp> | ||
+ | void auslesen(Population& | ||
+ | { | ||
+ | p.zeit++; | ||
+ | int anzahl = MAX_INDIVIDUEN + MAX_NACHKOMMEN; | ||
+ | std:: | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | Die Population wird beständig überwacht und bewertet: | ||
+ | |||
+ | <code cpp> | ||
+ | double wertung=0, alte_wertung=0; | ||
+ | |||
+ | void bewerten(Population const& p) | ||
+ | { | ||
+ | #ifdef unix | ||
+ | system(" | ||
+ | # | ||
+ | system(" | ||
+ | # | ||
+ | std::cout << p.zeit << | ||
+ | ". Runde\n" | ||
+ | " | ||
+ | " | ||
+ | |||
+ | alte_wertung = wertung; | ||
+ | wertung = 0; | ||
+ | for (int i=0; i < MAX_INDIVIDUEN; | ||
+ | { | ||
+ | double fitness_i = fitness(p.individuen[i]); | ||
+ | wertung += fitness_i; | ||
+ | |||
+ | if (i<18) // unsere Besten-Wandtafel | ||
+ | { | ||
+ | std::cout << ' | ||
+ | for (int j=0; j < GENOM_LENGTH; | ||
+ | { | ||
+ | std::cout << (p.individuen[i].base[j] ? ' | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | std::cout << " | ||
+ | << wertung << " | ||
+ | |||
+ | // void warte_msek(unsigned millisek); | ||
+ | // warte_msek(0); | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | 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; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ==== Hauptprogramm ==== | ||
+ | Der Evolutionsprozess muss nur noch angestossen werden: | ||
+ | |||
+ | <code cpp> | ||
+ | int main() | ||
+ | { | ||
+ | srand(time(NULL)); | ||
+ | |||
+ | Population p; | ||
+ | evolution(p); | ||
+ | |||
+ | std::cout << " | ||
+ | std:: | ||
+ | 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 ... | ||
+ | |||
+ | <code cpp> | ||
+ | void warte_msek(unsigned millisek) | ||
+ | { | ||
+ | unsigned start = clock(); | ||
+ | while ((clock()-start)*CLOCKS_PER_SEC/ | ||
+ | ; // Heute tue ich, was ich will: Nichts. [Gauloises Blondes] | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | ===== Literatur ===== | ||
+ | [Fogel] Zbigniew Michalewicz, | ||
+ | How to Solve It: Modern Heuristics. Springer (2000). | ||
+ | ISBN 3-540-66061-5 | ||
+ | |||
+ | [Holland] | ||
+ | John H. Holland: Genetic Algorithms. | ||
+ | [[http:// | ||
+ | |||
+ | |||