Сейчас вот сидел, делал для товарища прототип генетического алгоритма. Навеяло поделиться оным, да и некоторыми другими мыслями…
Дано (клиент заказал): в некоем царстве складе есть 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
Ну можно перебором, наверняка есть что-то умное, а можно генетическим алгоритмом это решить…
Первый вопрос: а чего мозги сушить, ведь если просто идти по списку, по для этого надо взять из первых двух ячеек — во второй, правда, окажется остаток. И ходить далеко не надо будет. Но видать, клиент перфекционист, хочет, чтоб было, как в аптеке. Наверное, в складе ячейки на вес золота. Бывает.
Второй вопрос: а если отсортировать по возрастающей, то наверняка можно повычистить гораздо больше ячеек… В нашем примере полно ячеек с количеством меньше десяти. Наверное, тоже не хочет клиент ;) Мне тоже такие попадались: я тут начальник. Тебе сказали — делай, вопросов не задавай.
(Хорошо, не мой клиент, а то б я в очередной раз веру в человеческий разум потерял...)
Ну да Бог с ним, у каждого свои приоритеты… Тогда про генетические алгоритмы поговорим — надо ж это как-то решать… Писать будем на Яве.
Для тех, кто про них раньше толком не слышал: имитируем Мать Природу.
- Кодируем варианты поведения
- Проверяем, насколько хорошо работает каждый вариант с помощью подходящего бенчмарка
- Самые лучшие передают свои признаки следующему поколению
В последнем шаге в природе есть две составляющие: кроссинг-овер (обмен признаками между одинаковыми участками хромосомы) и мутация (спонтанное изменения генетического кода). Привет, средняя школа ;)
Вот, пожалуй, и всё. Кодировать будем, из каких ячеек брать, а из каких нет. У нас 100 ячеек, значит наша хромосома будет из 100 элементов true/false, я для этого взял String, в котором будут записаны ноли и единицы. Их, понятно, будет 100.
Бенчмарк — важнейшая вещь в этом процессе. Природа ищет нишу, а компьютерная природа будет искать дыру в вашем бенчмарке, чтобы обдурить его и выжить. Диву даешься, честное слово…
С учетом всего сказанного, примерно так:
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);
}
Идея — чем дальше мы от искомого числа 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
Комментариев нет:
Отправить комментарий