Algoritmos genéticos (o el cliente siempre es el rey, y a menudo un tonto)

(versión 2, con errores tipográficos corregidos, espero que todos ...)

Hola Habr!

Ahora estaba sentado, haciendo un prototipo del algoritmo genético para un amigo. Inspirado a compartirlo, y algunos otros pensamientos ...

Dado (pedido por el cliente): en cierto reino, el almacén tiene 100 celdas. Los bienes están en él. ¿Cómo tomar la cantidad X para vaciar todas las celdas involucradas hasta el final? Bueno, es decir, tienes un 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] - cómo marcar, digamos, 40

Bueno, puedes reventar, seguro que hay algo inteligente, pero puedes resolverlo con un algoritmo genético ...


La primera pregunta: por qué secar sus cerebros, porque si solo revisa la lista, debe tomar de las dos primeras celdas para esto; la segunda, sin embargo, será el resto. Y no tendrás que ir muy lejos. Pero para ver, el cliente es un perfeccionista, quiere que sea como en una farmacia. Probablemente en un almacén de celdas que valga su peso en oro. Sucede

La segunda pregunta: si lo ordena en orden ascendente, entonces seguramente puede deslizar muchas más celdas ... En nuestro ejemplo, hay muchas celdas con menos de diez celdas. Probablemente, el cliente tampoco quiere;) También me encontré con esas personas: soy el jefe aquí. Te dijeron: hazlo, no hagas preguntas.

(Bueno, no es mi cliente, de lo contrario volvería a perder la fe en la mente humana ...)

Bueno, que Dios esté con él, cada uno tiene sus propias prioridades ... Luego hablaremos sobre algoritmos genéticos, de alguna manera debemos resolver esto ... Escribiremos en Java.

Para aquellos que no han oído hablar de ellos antes: imiten a la Madre Naturaleza.

1. Codificar comportamientos
2. Verificamos qué tan bien funciona cada opción con la ayuda de un punto de referencia adecuado
3. La mejor transmisión de sus atributos a la próxima generación.

En el último paso en la naturaleza, hay dos componentes: el cruce (el intercambio de caracteres entre las mismas partes del cromosoma) y la mutación (cambios espontáneos en el código genético). Hola escuela secundaria

Eso es probablemente todo. Codificaremos de qué celdas tomar y de cuáles no. Tenemos 100 células, por lo que nuestro cromosoma será de 100 elementos verdaderos / falsos, para esto tomé una cadena en la que se escribirán ceros y unos. Ellos, por supuesto, serán 100.

El punto de referencia es lo más importante en este proceso. La naturaleza está buscando un nicho, y la naturaleza de la computadora buscará un agujero en su punto de referencia para engañarlo y sobrevivir. Maravilloso, sinceramente ...

Con todo lo dicho, algo como esto:

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

La idea es que cuanto más nos alejemos del número deseado 40, peor. Si tenemos 40, entonces no vamos más allá en el cromosoma, ganamos. Clasificaremos, por supuesto, en orden creciente: cuantos menos puntos de penalización, mejor.

La primera generación se crea al azar:

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

Dado que el algoritmo genético, de hecho, se acerca al objetivo, pero no siempre lo logra, es importante limitar el número de generaciones.

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

Ordenar, dejar lo mejor:

 ... // 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 y multiplicamos, restauramos el tamaño de la población. Es decir, seleccionamos al azar a los padres, combinamos los mismos signos (si tienes suerte, mira la bandera de cambio), mutamos (bandera de mutación), esperamos un milagro ...

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

Y finalmente: si se confunde con los parámetros: demasiadas mutaciones, tamaño de población demasiado pequeño, etc. - se estancará o incluso dará los peores resultados.

Este problema, por cierto, a menudo se resuelve al azar y no se necesitan las próximas generaciones :) Si desea complicar la vida de la computadora, elimine este retorno del punto de referencia:

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

Esto complicará la tarea y hará que la computadora sufra un poco ...

Buena suerte

m_OO_m