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

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

Дано (клиент заказал): в некоем царстве складе есть 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 элементов 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