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

Привет!

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

Дано (клиент заказал): в некоем царстве складе есть 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] сушить, ведь если просто идти по списку, по для этого надо взять из первых двух ячеек — во второй, правда, окажется остаток. И ходить далеко не надо будет. Но видать, клиент перфекционист, хочет, чтоб было, как в аптеке. Наверное, в складе ячейки на вес золота. Бывает.

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

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

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

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

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

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

Вот, пожалуй, и всё. Кодировать будем, из каких ячеек брать, а из каких нет. У нас 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));
			}

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

Автор: m_OO_m

Источник ^[2]