Knapsack problem

From JCLEC wiki
Jump to: navigation, search

The knapsack problem is a combinatorial optimization problem: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Knapsack.svg

Example

Download and run the knapsack problem

java -jar jclec4-tutorial.jar Knapsack.cfg

Output

Generation 100 Report

Best individual: net.sf.jclec.binarray.BinArrayIndividual[genotype={1,1,0,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},fitness=net.sf.jclec.fitness.SimpleValueFitness@75fc25e5[value=620.0]]
Worst individual: net.sf.jclec.binarray.BinArrayIndividual[genotype={1,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},fitness=net.sf.jclec.fitness.SimpleValueFitness@627787a5[value=-724.0]]
Median individual: net.sf.jclec.binarray.BinArrayIndividual[genotype={1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},fitness=net.sf.jclec.fitness.SimpleValueFitness@3bce4a8a[value=608.0]]

Average fitness = 204.42
Fitness variance = 315595.9436

The ouput shows the best, worst and median individual from the population at generation 100. Each gene from the genotype maps to the corresponding item. 0 indicates that the item hasn't been inserted and 1 has.

For further information see the Knapsack Wiki