Хабрахабр

Генетические алгоритмы (или Клиент всегда король — и часто дурак)

Привет, Хабр!

Навеяло поделиться оным, да и некоторыми другими мыслями… Сейчас вот сидел, делал для товарища прототип генетического алгоритма.

В нем товар лежит. Дано (клиент заказал): в некоем царстве складе есть 100 ячеек. Ну то есть, есть у вас типа ячейки [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] — как набрать, скажем, 40 Как взять количество Х так, чтобы опустошить все задействованные ячейки до конца?

Ну можно перебором, наверняка есть что-то умное, а можно генетическим алгоритмом это решить…

И ходить далеко не надо будет. Первый вопрос: а чего мозги сушить, ведь если просто идти по списку, по для этого надо взять из первых двух ячеек — во второй, правда, окажется остаток. Наверное, в складе ячейки на вес золота. Но видать, клиент перфекционист, хочет, чтоб было, как в аптеке. Бывает.

Наверное, тоже не хочет клиент 😉 Мне тоже такие попадались: я тут начальник. Второй вопрос: а если отсортировать по возрастающей, то наверняка можно повычистить гораздо больше ячеек… В нашем примере полно ячеек с количеством меньше десяти. Тебе сказали — делай, вопросов не задавай.

(Хорошо, не мой клиент, а то б я в очередной раз веру в человеческий разум потерял...)

Ну да Бог с ним, у каждого свои приоритеты… Тогда про генетические алгоритмы поговорим — надо ж это как-то решать… Писать будем на Яве.

Для тех, кто про них раньше толком не слышал: имитируем Мать Природу.

  1. Кодируем варианты поведения
  2. Проверяем, насколько хорошо работает каждый вариант с помощью подходящего бенчмарка
  3. Самые лучшие передают свои признаки следующему поколению

Привет, средняя школа 😉 В последнем шаге в природе есть две составляющие: кроссинг-овер (обмен признаками между одинаковыми участками хромосомы) и мутация (спонтанное изменения генетического кода).

Кодировать будем, из каких ячеек брать, а из каких нет. Вот, пожалуй, и всё. Их, понятно, будет 100. У нас 100 ячеек, значит наша хромосома будет из 100 элементов true/false, я для этого взял String, в котором будут записаны ноли и единицы.

Природа ищет нишу, а компьютерная природа будет искать дыру в вашем бенчмарке, чтобы обдурить его и выжить. Бенчмарк — важнейшая вещь в этом процессе. Диву даешься, честное слово…

С учетом всего сказанного, примерно так:

private static int benchmark(String chromosome, boolean verbose) if (sum == target_qty) { return 0; } } return Math.abs(target_qty - sum);
}

Если набрали 40 — дальше во хромосоме не идем, мы победили. Идея — чем дальше мы от искомого числа 40, тем хуже. Сортировать будем, понятно, по возрастающей — чем меньше штравных очков, тем лучше.

Первое поколение создаем случайно:

// 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))); } // ... тут будет остальной код, см. ниже ...
}
System.out.println("No solution found after " + maxGenerationCnt + " iterations");

Отсортируем, оставим лучшие:

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

То есть, выбираем родителей случайным образом, комбинируем одинаковые признаки (если повезет — см. Плодимся и размножаемся, восстанавливаем размер популяции. флаг exchange), мутируем (флаг mutation), ждем чуда…

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

Ну и вот вам чудо:

Target value: 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]
Generation 0; Best / last parent / worst: 705 / 991 / 1580
Generation 1; Best / last parent / worst: 576 / 846 / 1175
Generation 2; Best / last parent / worst: 451 / 722 / 1108
Generation 3; Best / last parent / worst: 0 / 613 / 904
Solution found
storage bin 7: +4 = 4
storage bin 10: +22 = 26
storage bin 13: +14 = 40

А вот и весь код

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

— будет топтаться на месте или даже давать все худшие результаты. Ну и в завернешие: если намутить с параметрами — слишком много мутаций, слишком маленький размер популяции и т.п.

Задачка эта, кстати, часто решается уже случайным образом и следующие поколения не нужны 🙂 Если хотите усложнить компьютеру жизнь — уберите вот этот return из бенчмарка:

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

Это усложнит задачу и заставит комп помучиться немного…

Удачи,

m_OO_m

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»