🙂 🐰 👨🏼‍🔧 Algorithmes génétiques (ou le client est toujours roi

(version 2, avec fautes de frappe corrigées - j'espère que tout le monde ...)

Bonjour, Habr!

Maintenant, il était assis, faisant un prototype de l'algorithme génétique pour un ami. Inspiré de partager cela, et quelques autres pensées ...

Étant donné (client commandé): dans un certain ~~royaume, l'~~ entrepôt a 100 cellules. Les marchandises sont dedans. Comment prendre la quantité X pour vider à terme toutes les cellules concernées? Eh bien, c'est-à-dire que vous avez un type de cellule [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] - comment composer, disons, 40

Eh bien, vous pouvez casser, c'est sûr qu'il y a quelque chose d'intelligent, mais vous pouvez le résoudre avec un algorithme génétique ...

La première question: pourquoi sécher votre cerveau, car si vous parcourez simplement la liste, vous devez prendre les deux premières cellules pour cela - la seconde, cependant, sera le reste. Et vous n'aurez pas à aller loin. Mais pour voir, le client est un perfectionniste, il veut que ce soit comme dans une pharmacie. Probablement dans un entrepôt cellulaire qui vaut son pesant d'or. Ça arrive.

Deuxième question: si vous le triez par ordre croissant, vous pouvez sûrement faire glisser beaucoup plus de cellules ... Dans notre exemple, il y a beaucoup de cellules avec moins de dix cellules. Probablement, le client ne veut pas non plus;) J'ai aussi rencontré de telles personnes: je suis le patron ici. Ils vous ont dit - faites-le, ne posez pas de questions.

(Eh bien, pas mon client, sinon je perdrais encore une fois confiance dans l'esprit humain ...)

Eh bien, Dieu soit avec lui, chacun a ses propres priorités ... Ensuite, nous parlerons des algorithmes génétiques - nous devons en quelque sorte résoudre cela ... Nous écrirons en Java.

Pour ceux qui n'en ont pas vraiment entendu parler auparavant: imitez Mère Nature.

Encoder les comportements
Nous vérifions le fonctionnement de chaque option à l'aide d'un benchmark approprié
Les meilleurs transmettent leurs attributs à la prochaine génération

Dans la dernière étape de la nature, il y a deux composantes: le croisement (l'échange de caractères entre les mêmes parties du chromosome) et la mutation (changements spontanés du code génétique). Salut, lycée;)

C’est probablement tout. Nous allons coder les cellules à prendre et celles qui ne le seront pas. Nous avons 100 cellules, donc notre chromosome sera composé de 100 éléments vrais / faux, pour cela j'ai pris une chaîne dans laquelle des zéros et des uns seront écrits. Ils seront bien sûr 100.

L'indice de référence est l'élément le plus important de ce processus. La nature cherche une niche, et la nature informatique cherchera un trou dans votre référence pour la tromper et survivre. Merveilleusement, honnêtement ...

Cela dit, quelque chose comme ça:

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

L'idée est que plus nous nous éloignons du nombre souhaité 40, pire c'est. Si nous en avons 40, alors nous n'allons pas plus loin sur le chromosome, nous avons gagné. Nous allons bien sûr trier par ordre croissant - moins il y a de points de pénalité, mieux c'est.

La première génération est créée au hasard:

 // 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(); }

Étant donné que l'algorithme génétique se rapproche en fait de l'objectif, mais ne l'atteint pas toujours, il est important de limiter le nombre de générations.

 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");

Trier, laisser le meilleur:

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

Nous nous reproduisons et nous multiplions, restaurons la taille de la population. Autrement dit, nous sélectionnons au hasard les parents, combinons les mêmes signes (si vous avez de la chance - voir le drapeau d'échange), mutez (drapeau de mutation), attendez un miracle ...

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

Eh bien, voici un miracle pour vous:

Valeur cible: 40
Stock: [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]
Génération 0; Meilleur / dernier parent / pire: 705/991/1580
Génération 1; Meilleur / dernier parent / pire: 576/846/1175
Génération 2; Meilleur / dernier parent / pire: 451/722/1108
Génération 3; Meilleur / dernier parent / pire: 0/613/904
Solution trouvée
bac de stockage 7: +4 = 4
bac de stockage 10: +22 = 26
bac de stockage 13: +14 = 40

Et voici tout le code

 package ypk; import java.io.IOException; import java.io.StringWriter; import java.util.AbstractMap.SimpleEntry; import java.util.stream.Collectors; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; public class YPK { private static int generation_size = 1000; private static int best_size = 200; private static int cnt_bins = 100; private static int max_stock = 50; private static double exchange_rate = .2; private static double mutation_rate = .01; private static Random rnd = new Random(); private static int target_qty = rnd.nextInt(cnt_bins * max_stock / 5); // some quantity private static List<String> chromosomes = new ArrayList<>(); private static int maxGenerationCnt = 20; private static int[] stock = new int[cnt_bins]; public static void main(String[] args) throws IOException { System.out.println("Target value: " + target_qty); // create sample stock stock = new int[cnt_bins]; for (int i = 0; i < cnt_bins; i++) { stock[i] = rnd.nextInt(max_stock) + 1; } System.out.println("Stock: " + Arrays.toString(stock)); // 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(); } 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))); } // 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); // 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)); } } System.out.println("No solution found after " + maxGenerationCnt + " iterations"); } 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); } }

Et enfin: si vous vous embrouillez avec les paramètres - trop de mutations, trop petite taille de population, etc. - va stagner ou même donner les pires résultats.

Soit dit en passant, ce problème est souvent résolu au hasard et les générations suivantes ne sont pas nécessaires :) Si vous voulez compliquer la vie de l'ordinateur, supprimez ce retour de la référence:

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

Cela compliquera la tâche et fera un peu souffrir l'ordinateur ...

Bonne chance

m_OO_m

Algorithmes génétiques (ou le client est toujours roi - et souvent un idiot)

More articles: