Genetic algorithms (or the Client is always king - and often a fool)

(version 2, with corrected typos - I hope that everyone ...)



Hello, Habr!



Now he was sitting, making a prototype of the genetic algorithm for a friend. Inspired to share thereof, and some other thoughts ...



Given (customer ordered): in a certain kingdom, the warehouse has 100 cells. It contains the goods. How to take the quantity X so as to empty all involved cells to the end? Well, that is, you have a cell type [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] - how to dial, say, 40



Well, you can bust, for sure there is something smart, but you can solve it with a genetic algorithm ...





The first question: why dry your brains, because if you just go through the list, you need to take from the first two cells for this - the second, however, will be the remainder. And you won’t have to go far. But to see, the client is a perfectionist, he wants it to be like in a pharmacy. Probably in a cell warehouse worth its weight in gold. It happens.



The second question: if you sort it in ascending order, then you can surely swipe a lot more cells ... In our example, there are a lot of cells with less than ten cells. Probably, the client also does not want;) I also came across such people: I’m the boss here. They told you - do it, do not ask questions.



(Well, not my client, otherwise I would once again lose faith in the human mind ...)



Well, God be with him, everyone has their own priorities ... Then we'll talk about genetic algorithms - we must somehow solve this ... We will write in Java.



For those who have not really heard about them before: imitate Mother Nature.

1. Encode Behaviors
2. We check how well each option works with a suitable benchmark
3. The best pass on their attributes to the next generation

In the last step in nature, there are two components: crossing over (the exchange of characters between the same parts of the chromosome) and mutation (spontaneous changes in the genetic code). Hi, high school;)



That’s probably all. We will code from which cells to take, and from which not. We have 100 cells, which means our chromosome will be of 100 true / false elements, for this I took String, in which zeros and ones will be written. Of course, there will be 100 of them.



The benchmark is the most important thing in this process. Nature is looking for a niche, and computer nature will look for a hole in your benchmark to fool it and survive. Wonderful, honestly ...



With all that said, something like this:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The idea is that the farther we are from the desired number 40, the worse. If we scored 40, we don’t go further in the chromosome, we won. We will sort, of course, in increasing order - the less penalty points, the better.



The first generation is created randomly:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Since the genetic algorithm, in fact, approaches the goal, but does not always achieve it, it is important to limit the number of generations.

 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, leave the best:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We breed and multiply, restore the size of the population. That is, we randomly select parents, combine the same signs (if you're lucky - see the exchange flag), mutate (mutation flag), wait for a miracle ...

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

And finally: if you muddle with the parameters - too many mutations, too small population size, etc. - will stagnate or even give all the worst results.



This task, by the way, is often solved already at random and the next generations are not needed :) If you want to complicate the life of the computer, remove this return from the benchmark:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

This will complicate the task and make the computer suffer a bit ...



Good luck



m_OO_m