Genetische Algorithmen (oder der Klient ist immer König - und oft ein Narr)

(Version 2, mit korrigierten Tippfehlern - ich hoffe, dass alle ...)

Hallo Habr!

Jetzt saß er und machte einen Prototyp des genetischen Algorithmus für einen Freund. Inspiriert, davon und einige andere Gedanken zu teilen ...

Gegeben (vom Kunden bestellt): In einem bestimmten Königreich hat das Lager 100 Zellen. Die Ware ist drin. Wie nimmt man die Menge X, um alle beteiligten Zellen bis zum Ende zu leeren? Das heißt, Sie haben einen Zelltyp [34, 10, 32, 32, 33, 41, 44, 4, 28, 23, 22, 28, 29, 14, 28, 15, 38, 49, 30, 24, 18, 9, 15, 8, 17, 9, 2, 7, 30, 29, 29, 2, 28, 23, 19, 4, 15, 30, 38, 3, 14, 21, 43, 50, 29, 14, 17, 12, 25, 15, 23, 28, 47, 38, 29, 7, 36, 45, 25, 6, 25, 11, 10, 1, 19, 37, 24, 27, 50, 12, 1, 1, 44, 22, 48, 13, 46, 49, 11, 33, 29, 4, 19, 33, 12, 3, 47, 27, 26, 45, 40, 37, 21, 2, 8, 41, 5, 1, 9, 5] - wie man beispielsweise 40 wählt

Nun, Sie können pleite gehen, sicher gibt es etwas Kluges, aber Sie können es mit einem genetischen Algorithmus lösen ...


Die erste Frage: Warum trocknen Sie Ihr Gehirn, denn wenn Sie nur die Liste durchgehen, müssen Sie dafür die ersten beiden Zellen entnehmen - die zweite ist jedoch der Rest. Und Sie müssen nicht weit gehen. Aber um zu sehen, der Kunde ist ein Perfektionist, er möchte, dass es wie in einer Apotheke ist. Wahrscheinlich in einem Zelllager, das Gold wert ist. Es passiert.

Die zweite Frage: Wenn Sie es in aufsteigender Reihenfolge sortieren, können Sie sicherlich viel mehr Zellen durchwischen ... In unserem Beispiel gibt es viele Zellen mit weniger als zehn Zellen. Wahrscheinlich will der Kunde auch nicht;) Ich bin auch auf solche Leute gestoßen: Ich bin der Chef hier. Sie sagten dir - mach es, stell keine Fragen.

(Nun, nicht mein Klient, sonst würde ich wieder das Vertrauen in den menschlichen Verstand verlieren ...)

Nun, Gott sei mit ihm, jeder hat seine eigenen Prioritäten ... Dann werden wir über genetische Algorithmen sprechen - wir müssen das irgendwie lösen ... Wir werden in Java schreiben.

Für diejenigen, die noch nie wirklich davon gehört haben: Mutter Natur nachahmen.

1. Verhalten codieren
2. Wir überprüfen anhand eines geeigneten Benchmarks, wie gut jede Option funktioniert
3. Die besten geben ihre Attribute an die nächste Generation weiter

Im letzten Schritt der Natur gibt es zwei Komponenten: Überkreuzen (Austausch von Zeichen zwischen denselben Teilen des Chromosoms) und Mutation (spontane Änderungen des genetischen Codes). Hallo, High School;)

Das ist wahrscheinlich alles. Wir werden codieren, aus welchen Zellen entnommen werden soll und aus welchen nicht. Wir haben 100 Zellen, was bedeutet, dass unser Chromosom aus 100 wahren / falschen Elementen besteht. Dafür habe ich einen String genommen, in den Nullen und Einsen geschrieben werden. Sie werden natürlich 100 sein.

Der Benchmark ist das Wichtigste in diesem Prozess. Die Natur sucht nach einer Nische, und die Computernatur sucht nach einem Loch in Ihrem Benchmark, um es zu täuschen und zu überleben. Wunderbar, ehrlich ...

Nach alledem so etwas:

private static int benchmark(String chromosome, boolean verbose) { int sum = 0; char[] cArr = chromosome.toCharArray(); for (int i = 0; i < cnt_bins; i++) { if (cArr[i] == '1') { sum += stock[i]; if (verbose) System.out.println("storage bin " + i + ":\t+" + stock[i] + "\t= " + sum); } if (sum == target_qty) { return 0; } } return Math.abs(target_qty - sum); } 

Die Idee ist, dass je weiter wir von der gewünschten Zahl 40 entfernt sind, desto schlimmer. Wenn wir 40 Punkte erzielt haben, gehen wir auf dem Chromosom nicht weiter, wir haben gewonnen. Wir werden natürlich in aufsteigender Reihenfolge sortieren - je weniger Strafpunkte, desto besser.

Die erste Generation wird zufällig erstellt:

 // create 1st generation for (int i = 0; i < generation_size; i++) { StringWriter sw = new StringWriter(); for (int j = 0; j < cnt_bins; j++) { // take stock from this bin? sw.append(rnd.nextBoolean() ? "1" : "0"); } chromosomes.add(sw.toString()); sw.close(); } 

Da sich der genetische Algorithmus zwar dem Ziel nähert, es aber nicht immer erreicht, ist es wichtig, die Anzahl der Generationen zu begrenzen.

 for (int generationNo = 0; generationNo < maxGenerationCnt; generationNo++) { // evaluate List<SimpleEntry<String, Integer>> evaluated = new ArrayList<>(); for (int i = 0; i < chromosomes.size(); i++) { evaluated.add( new SimpleEntry<String, Integer>(chromosomes.get(i), benchmark(chromosomes.get(i), false))); } // ...    , .  ... } System.out.println("No solution found after " + maxGenerationCnt + " iterations"); 

Sortieren, das Beste lassen:

 ... // sort evaluated = evaluated.stream().sorted((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())) .collect(Collectors.toList()); System.out.println("Generation " + generationNo + "; Best / last parent / worst: " + evaluated.get(0).getValue() + " / " + evaluated.get(best_size).getValue() + " / " + evaluated.get(evaluated.size() - 1).getValue()); if (evaluated.get(0).getValue() == 0) { System.out.println("Solution found"); benchmark(evaluated.get(0).getKey(), true); System.exit(0); } // leave only the best evaluated = evaluated.subList(0, best_size); ... 

Wir züchten und vermehren uns, stellen die Größe der Population wieder her. Das heißt, wir wählen zufällig Eltern aus, kombinieren die gleichen Zeichen (wenn Sie Glück haben - siehe die Austauschflagge), mutieren (Mutationsflagge), warten auf ein Wunder ...

 // replication List<String> parents = evaluated.stream().map(e -> e.getKey()).collect(Collectors.toList()); chromosomes.clear(); while (chromosomes.size() < generation_size) { int parent1 = rnd.nextInt(evaluated.size()); int parent2 = rnd.nextInt(evaluated.size()); char[] cArr1 = parents.get(parent1).toCharArray(); char[] cArr2 = parents.get(parent2).toCharArray(); for (int i = 0; i < cnt_bins; i++) { boolean exchange = rnd.nextDouble() < exchange_rate; if (exchange) { char c1 = cArr1[i]; char c2 = cArr2[i]; // exchange both values cArr1[i] = c2; cArr2[i] = c1; } // mutation boolean mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr1[i] = rnd.nextBoolean() ? '1' : '0'; } mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr2[i] = rnd.nextBoolean() ? '1' : '0'; } } chromosomes.add(new String(cArr1)); chromosomes.add(new String(cArr2)); } 

Und schließlich: Wenn Sie mit den Parametern verwechseln - zu viele Mutationen, zu kleine Populationsgröße usw. - wird stagnieren oder sogar die schlechtesten Ergebnisse liefern.

Dieses Problem wird übrigens oft schon zufällig gelöst und die nächsten Generationen werden nicht benötigt :) Wenn Sie die Lebensdauer des Computers verkomplizieren möchten, entfernen Sie diese Rückgabe aus dem Benchmark:

 if (sum == target_qty) { return 0; } 

Dies wird die Aufgabe komplizieren und den Computer ein wenig leiden lassen ...

Viel Glück

m_OO_m