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

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

}