[Quiz#15] Thomas Darimont (Java Genetischer Algorithmus)

[Thomas Darimont]

Hallo,

hier mal eine prototypische Lösung des Rucksack Problems mit einem generischen Genetischen Algorithmus.
Eine Erklärung zu genetischen Algorithmen findet man beispielsweise hier:
http://de.wikipedia.org/wiki/Genetischer_Algorithmus

Die Beispiel-Implementierung kann die kleineren / einfacheren Knappsackeingaben ohne Probleme lösen, scheitert jedoch
an der großen 100k.txt-Eingabe von onlyfoo. Durch tuning bzw. einführen neuer Algorithmus Parameter sowie
weiterer Problemnäherer genetischer Operatoren würde man dieses Problem sicherlich auch noch hinbekommen.

package de.tutorials.contest.quiz15;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class GeneticEasterEggs {

  public static void main(String[] args) throws Exception {
    System.out.println("GeneticEasterEggs");
    new GeneticEasterEggs().solve();
  }


  void solve() throws Exception {
    SweetProblem problem = readInput("easterEggs.dat");

    GeneticSolver<BitSet> geneticSolver = new GeneticSolver<BitSet>();

    SolutionFitness<BitSet> best = geneticSolver.solve(problem);

    System.out.println(best);

    int mass = 0;
    int kcal = 0;
    int takenSweets = 0;
    for (int i = 0; i < problem.sweets.size(); i++) {
      if (best.solution.get(i)) {
        Sweet sweet = problem.sweets.get(i);
        mass += sweet.weight;
        kcal += sweet.kcal;
        System.out.print((takenSweets++ > 0 ? "," : "") + sweet.name);
      }
    }
    
    System.out.println();
    System.out.println("Masse: " + mass);
    System.out.println("Nährwert: " + kcal);
  }


  SweetProblem readInput(String fileLocation) throws FileNotFoundException {
    SweetProblem problem = new SweetProblem();
    Scanner scanner = new Scanner(new File(fileLocation));
    problem.sweets = new ArrayList<Sweet>();
    problem.maxWeightInGramm = Integer.parseInt(scanner.nextLine().trim());

    while (scanner.hasNext()) {
      String line = scanner.nextLine();
      if ("".equals(line)) {
        break;
      }
      String name = line;
      String[] weightAndKcal = scanner.nextLine().split(" ");
      int weight = Integer.parseInt(weightAndKcal[0]);
      int kcal = Integer.parseInt(weightAndKcal[1]);

      problem.sweets.add(new Sweet(name, weight, kcal));
    }
    return problem;
  }

  static class Sweet {
    String name;
    int weight;
    int kcal;


    public Sweet(String name, int weight, int kcal) {
      this.name = name;
      this.weight = weight;
      this.kcal = kcal;
    }
  }
  
  

  static class SweetProblem implements Problem<BitSet>{
    List<Sweet> sweets;
    int maxWeightInGramm;
    Random randomizer = new Random();


    @Override
    public double fitness(BitSet bitSet) {
      double fitness = 0.0;
      int weight = 0;

      for (int i = 0, size = sweets.size(); i < size; i++) {
        if (bitSet.get(i)) {
          Sweet sweet = sweets.get(i);
          fitness += sweet.kcal;
          weight += sweet.weight;
        }
      }

      if (weight > maxWeightInGramm) {
        fitness = 0; // penalty for weight constraint violation
      }

      return fitness;
    }


    @Override
    public BitSet breed() {
      int size = sweets.size();
      BitSet bitSet = new BitSet();
      bitSet.set(randomizer.nextInt(size));
      return bitSet;
    }


    @Override
    public BitSet combine(BitSet first, BitSet second) {
      int size = sweets.size();
      int crossOverIndex = randomizer.nextInt(size);

      BitSet combination = new BitSet();

      for (int i = 0; i < crossOverIndex; i++) {
        if (first.get(i)) {
          combination.set(i);
        }
      }

      for (int i = crossOverIndex; i < size; i++) {
        if (second.get(i)) {
          combination.set(i);
        }
      }

      return combination;
    }


    @Override
    public BitSet mutate(BitSet individual) {
      int size = sweets.size();
      BitSet mutation = new BitSet();
      mutation.or(individual);
      mutation.flip(randomizer.nextInt(size));
      return mutation;
    }

  }

  static class Population<TSolution> {
    List<TSolution> solutions = new ArrayList<TSolution>();


    public Population() {
    }


    public Population(SolutionFitness<TSolution>[] topElite) {
      for (SolutionFitness<TSolution> soluationFitness : topElite) {
        solutions.add(soluationFitness.solution);
      }
    }


    public int size() {
      return solutions.size();
    }


    TSolution get(int index) {
      return solutions.get(index);
    }


    void add(TSolution solution) {
      solutions.add(solution);
    }
  }

  static interface Problem<TSolution> extends FitnessFunction<TSolution>, Breeder<TSolution>, Combiner<TSolution>, Mutator<TSolution>{
  }
  
  static interface FitnessFunction<TSolution> {
    double fitness(TSolution solution);
  }

  static interface Breeder<TSolution> {
    TSolution breed();
  }

  static interface Combiner<TSolution> {
    TSolution combine(TSolution first, TSolution second);
  }

  static interface Mutator<TSolution> {
    TSolution mutate(TSolution solution);
  }

  static class SolutionFitness<TSolution> implements Comparable<SolutionFitness<TSolution>> {
    TSolution solution;
    double fitness;


    public SolutionFitness(TSolution solution, double fitness) {
      this.solution = solution;
      this.fitness = fitness;
    }


    @Override
    public int compareTo(SolutionFitness<TSolution> that) {
      return -Double.compare(this.fitness, that.fitness);
    }
  }

  static class GeneticSolver<TSolution> {
    Breeder<TSolution> breeder;
    Combiner<TSolution> combiner;
    Mutator<TSolution> mutator;
    FitnessFunction<TSolution> fitnessFunction;
    Random randomizer = new Random();

    int populationSize = 500;
    int maxIterations = 100;
    int maxIterationsWithNoImprovement = maxIterations;
    double elite = 0.3;
    double mutationProbability = 0.4;


    public SolutionFitness<TSolution> solve(Problem<TSolution> problem) {

      init(problem);

      System.out.println("Starting genetic search...");

      SolutionFitness<TSolution> currentBest = null;

      Population<TSolution> currentPopulation = generatePopulation();
      int eliteCount = (int) (populationSize * elite);

      int iterationsWithNoImprovement = 0;

      for (int i = 0; i < maxIterations; i++) {
        SolutionFitness<TSolution>[] solutionFitnesses = evaluate(currentPopulation);
        SolutionFitness<TSolution>[] rankedSolutions = computeRankingBestSolutionsFirst(solutionFitnesses);
        SolutionFitness<TSolution>[] topElite = takeTopEliteSolutions(eliteCount, rankedSolutions);
        
        currentPopulation = new Population<TSolution>(topElite);

        while (currentPopulation.size() < populationSize) {
          TSolution candidate = applyGeneticOperators(topElite);
          currentPopulation.add(candidate);
        }

        SolutionFitness<TSolution> nextBest = topElite[0];

        if (currentBest != null) {
          if (currentBest.fitness == nextBest.fitness) {
            iterationsWithNoImprovement++;
          } else {
            iterationsWithNoImprovement = 0;
          }

          if (iterationsWithNoImprovement > maxIterationsWithNoImprovement) {
            System.out.println("No improvement for " + maxIterationsWithNoImprovement + " iterations");
            break;
          }
        }

        currentBest = nextBest;
        // System.out.println("Current best: " + currentBest.fitness
        // + " " + best.individual
        // );
      }

      return currentBest;
    }


    private SolutionFitness<TSolution>[] takeTopEliteSolutions(int eliteCount,
      SolutionFitness<TSolution>[] rankedSolutions) {
      return Arrays.copyOf(rankedSolutions, eliteCount);
    }


    void init(Problem<TSolution> problem) {
      this.breeder = problem;
      this.combiner = problem;
      this.mutator = problem;
      this.fitnessFunction = problem;
    }


    TSolution applyGeneticOperators(SolutionFitness<TSolution>[] topElite) {
      TSolution candidate;
      if (randomizer.nextDouble() < mutationProbability) {
        TSolution mutationCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
        TSolution mutation = mutator.mutate(mutationCandidate);
        candidate = mutation;
      } else {
        TSolution firstCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
        TSolution secondCandidate = topElite[randomizer.nextInt(topElite.length)].solution;
        TSolution combination = combiner.combine(firstCandidate, secondCandidate);
        candidate = combination;
      }
      return candidate;
    }


    SolutionFitness<TSolution>[] computeRankingBestSolutionsFirst(SolutionFitness<TSolution>[] individualFitnesses) {
      Arrays.sort(individualFitnesses);
      return individualFitnesses;
    }


    SolutionFitness<TSolution>[] evaluate(Population<TSolution> population) {
      SolutionFitness<TSolution>[] solutionFitnesses = new SolutionFitness[populationSize];
      for (int i = 0; i < solutionFitnesses.length; i++) {
        TSolution solution = population.get(i);
        double fitness = fitnessFunction.fitness(solution);
        solutionFitnesses[i] = new SolutionFitness<TSolution>(solution, fitness);
      }
      return solutionFitnesses;
    }


    Population<TSolution> generatePopulation() {
      Population<TSolution> population = new Population<TSolution>();
      for (int i = 0; i < populationSize; i++) {
        TSolution individual = breeder.breed();
        population.add(individual);
      }
      return population;
    }
  }

}

Eingabe:

500
Nougat-Eier
84 427
Fondant-Eier
150 540
Ostereier
189 291
Spannungs-Eier
63 330
Waffeleier
120 600
Melker Runzelhase
70 371
Lynt Platinhase
250 1360

Ausgabe:

GeneticEasterEggs
Starting genetic search...
de.tutorials.contest.quiz15.GeneticEasterEggs$SolutionFitness@6ef0eed6
Nougat-Eier,Spannungs-Eier,Melker Runzelhase,Lynt Platinhase
Masse: 467
Nährwert: 2488

Gruß Tom

 

[Matthias Reitinger]

Hey Tom,

sehr coole Lösung! Muss ich mir nachher mal in Ruhe genauer anschauen…

Grüße,
Matthias