Algoritmos genéticos (ou o cliente é sempre rei - e muitas vezes um tolo)

(versão 2, com erros de digitação corrigidos - espero que todos ...)

Olá Habr!

Agora ele estava sentado, fazendo um protótipo do algoritmo genético para um amigo. Inspirado para compartilhar, e alguns outros pensamentos ...

Dado (pedido pelo cliente): em um determinado reino, o armazém tem 100 células. Os bens estão nele. Como levar a quantidade X para esvaziar todas as células envolvidas até o fim? Bem, você tem um tipo de célula [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] - como discar, digamos, 40

Bem, você pode quebrar, com certeza há algo inteligente, mas você pode resolvê-lo com um algoritmo genético ...


A primeira pergunta: por que secar o cérebro, porque se você passar pela lista, precisará tirar as duas primeiras células para isso - a segunda, no entanto, será o restante. E você não precisa ir muito longe. Mas, para ver, o cliente é um perfeccionista, ele quer que seja como em uma farmácia. Provavelmente em um armazém celular vale seu peso em ouro. Isso acontece

A segunda pergunta: se você a classificar em ordem crescente, certamente poderá deslizar muito mais células ... No nosso exemplo, existem muitas células com menos de dez células. Provavelmente, o cliente também não quer;) Eu também me deparei com essas pessoas: eu sou o chefe aqui. Eles disseram a você - faça, não faça perguntas.

(Bem, não meu cliente, caso contrário eu perderia novamente a fé na mente humana ...)

Bem, que Deus esteja com ele, todo mundo tem suas próprias prioridades ... Então falaremos sobre algoritmos genéticos - de alguma forma precisamos resolver isso ... Vamos escrever em Java.

Para aqueles que nunca ouviram falar sobre eles antes: imite a Mãe Natureza.

1. Comportamentos de codificação
2. Verificamos quão bem cada opção funciona com a ajuda de uma referência adequada
3. A melhor transmissão de seus atributos para a próxima geração

No último passo na natureza, existem dois componentes: cruzamento (troca de caracteres entre as mesmas partes do cromossomo) e mutação (alterações espontâneas no código genético). Olá, ensino médio;)

Provavelmente é tudo. Codificaremos de quais células extrair e das quais não. Temos 100 células, o que significa que nosso cromossomo terá 100 elementos verdadeiros / falsos. Por isso, peguei String, na qual zeros e uns serão escritos. Eles, é claro, serão 100.

A referência é a coisa mais importante nesse processo. A natureza está procurando um nicho, e a natureza do computador procurará um buraco no seu benchmark para enganá-lo e sobreviver. Maravilhoso, honestamente ...

Com tudo isso dito, algo como isto:

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

A idéia é que quanto mais longe estivermos do número desejado 40, pior. Se marcarmos 40, não avançaremos mais no cromossomo, vencemos. Classificaremos, é claro, em ordem crescente - quanto menos pontos de penalidade, melhor.

A primeira geração é criada aleatoriamente:

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

Como o algoritmo genético, de fato, se aproxima do objetivo, mas nem sempre o atinge, é importante limitar o número de gerações.

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

Classifique, deixe o melhor:

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

Criamos e multiplicamos, restauramos o tamanho da população. Ou seja, selecionamos aleatoriamente os pais, combinamos os mesmos sinais (se você tiver sorte - veja a bandeira da troca), modifique (a bandeira da mutação), espere um milagre ...

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

E finalmente: se você se atrapalhar com os parâmetros - muitas mutações, tamanho populacional muito pequeno etc. - Estagnará ou até dará os piores resultados.

A propósito, esse problema já foi resolvido com frequência e as próximas gerações não são necessárias :) Se você quiser complicar a vida do computador, remova esse retorno do benchmark:

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

Isso complicará a tarefa e fará com que o computador sofra um pouco ...

Boa sorte

m_OO_m