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.
Eingabe:
Ausgabe:
Gruß Tom
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