I have implemented a variant of the knapsack problem using Jenetics as follows:
@Value
public class Knapsack {
public static void main( final String[] args ) {
final var knapsackEngine = Engine.builder( Knapsack::fitness, Knapsack.codec() )
.constraint( Knapsack.constraint() )
.build();
final var bestPhenotype = knapsackEngine.stream()
.limit( 1000L )
.collect( EvolutionResult.toBestPhenotype() );
final var knapsack = bestPhenotype.getGenotype().getGene().getAllele();
final var profit = bestPhenotype.getFitness();
final var weight = knapsack.getWeight();
System.out.println( "Valid: " + bestPhenotype.isValid() );
System.out.println( String.format( "Solution: profit %d | weight %d", profit, weight ) );
System.out.println( String.format( "Optimum: profit %d | weight %d", Problem.OPTIMAL_PROFIT, Problem.OPTIMAL_WEIGHT ) );
}
List<Item> items;
public int getProfit() {
return items.stream()
.mapToInt( Item::getProfit )
.sum();
}
public int getWeight() {
return items.stream()
.mapToInt( Item::getWeight )
.sum();
}
private static Codec<Knapsack, AnyGene<Knapsack>> codec() {
return Codec.of(
Genotype.of( AnyChromosome.of( Knapsack::create ) ),
genotype -> genotype.getGene().getAllele() );
}
private static Knapsack create() {
final Random rand = RandomRegistry.getRandom();
final List<Item> items = Problem.ITEMS.stream()
.filter( item -> rand.nextBoolean() )
.collect( Collectors.toList() );
return new Knapsack( items );
}
private static int fitness( final Knapsack knapsack ) {
return knapsack.getProfit();
}
private static Constraint<AnyGene<Knapsack>, Integer> constraint() {
return Constraint.of( phenotype -> {
final Knapsack knapsack = phenotype.getGenotype().getGene().getAllele();
final int weight = knapsack.getItems().stream()
.mapToInt( Item::getWeight )
.sum();
return weight <= Problem.MAX_CAPACITY;
} );
}
}
@Value is part of Lombok and generates a bunch of code like a constructor, getters, etc. The Problem class defines some constants for a particular knapsack problem (P07 from https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html):
public class Problem {
public static final int MAX_CAPACITY = 750;
public static final BitChromosome OPTIMAL_SOLUTION = BitChromosome.of( "101010111000011" );
public static final int OPTIMAL_PROFIT = 1458;
public static final int OPTIMAL_WEIGHT = 749;
private static final List<Integer> profits = List.of(
135, 139, 149, 150, 156,
163, 173, 184, 192, 201,
210, 214, 221, 229, 240 );
private static final List<Integer> weights = List.of(
70, 73, 77, 80, 82,
87, 90, 94, 98, 106,
110, 113, 115, 118, 120 );
public static final List<Item> ITEMS = IntStream.range( 0, profits.size() )
.mapToObj( i -> new Item( profits.get( i ), weights.get( i ) ) )
.collect( Collectors.toList() );
}
Although the Jenetics user guide says (see section 2.5):
A given problem should usually encoded in a way, that it is not possible for the evolution
Engineto create invalid individuals (Genotypes).
I wonder why the engine constantly creates solutions with a weight that exceed the knapsack's maximum capacity. So although these solutions are invalid according to the given Constraint, Phenotype#isValid() returns true.
I'm able to fix this issue by changing the fitness function to:
private static int fitness( final Knapsack knapsack ) {
final int profit = knapsack.getProfit();
final int weight = knapsack.getWeight();
return weight <= Problem.MAX_CAPACITY ? profit : 0;
}
Or by making sure the codec can only create valid solutions:
private static Knapsack create() {
final Random rand = RandomRegistry.getRandom();
final List<Item> items = Problem.ITEMS.stream()
.filter( item -> rand.nextBoolean() )
.collect( Collectors.toList() );
final Knapsack knapsack = new Knapsack( items );
return knapsack.getWeight() <= Problem.MAX_CAPACITY ? knapsack : create();
}
But then what is the purpose of Constraint if it has no effect?
I introduced the Constraint interface in the latest version of Jenetics. It is meant as the last line of defense, when it comes to check the validity of an individual. In your example you used the factory method of the Constraint interface, which only takes the validity predicate. The second important method of the Constraint is the repair method. This method tries to fix the given individual. Without defining this method, only a new, random phenotype is created. Since this interface is new, it seems that I haven't explained the intended use of the Constraint interface good enough. It's on my agenda #541. One possible usage example is given in #540, in the second example.
void constrainedVersion() {
final Codec<double[], DoubleGene> codec = Codecs
.ofVector(DoubleRange.of(0, 1), 4);
final Constraint<DoubleGene, Double> constraint = Constraint.of(
pt -> isValid(codec.decode(pt.getGenotype())),
(pt, g) -> {
final double[] r = normalize(codec.decode(pt.getGenotype()));
return newPT(r, g);
}
);
}
private static Phenotype<DoubleGene, Double> newPT(final double[] r, final long gen) {
final Genotype<DoubleGene> gt = Genotype.of(
DoubleChromosome.of(
DoubleStream.of(r).boxed()
.map(v -> DoubleGene.of(v, DoubleRange.of(0, 1)))
.collect(ISeq.toISeq())
)
);
return Phenotype.of(gt, gen);
}
private static boolean isValid(final double[] x) {
return x[0] + x[1] + x[2] == 1 && x[3] > 0.8;
}
private static double[] normalize(final double[] x) {
double[] r = x;
final double sum = r[0] + r[1] + r[2];
if (sum != 1) {
r[0] /= sum;
r[1] /= sum;
r[2] /= sum;
}
if (r[3] > 0.8) {
r[3] = 0.8;
}
return r;
}
And the Phenotype::isValid method returns true, because it's a local validity check, which only checks if all chromosomes and genes of the individual are valid or in the valid range.
I hope I could answer your question, and a better description with one (or more) examples is on the way. On the other hand: if you have ideas for good usage examples of the Constraint interface, let me know.