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

Thomas Darimont

Erfahrenes Mitglied
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.

Java:
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:
Code:
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:
Code:
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