Jenetics 约束似乎没有效果

Question

我实现了 knapsack problem using Jenetics 的变体，如下所示：

@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 是 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() );

}

虽然 Jenetics user guide 说（见第 2.5 节）：

A given problem should usually encoded in a way, that it is not possible for the evolution Engine to create invalid individuals (Genotypes).

我想知道为什么引擎会不断创建重量超过背包最大容量的解决方案。因此，尽管这些解决方案根据给定的 Constraint、Phenotype#isValid() returns true.

是无效的

我可以通过将适应度函数更改为来解决此问题：

private static int fitness( final Knapsack knapsack ) {
    final int profit = knapsack.getProfit();
    final int weight = knapsack.getWeight();
    return weight <= Problem.MAX_CAPACITY ? profit : 0;
}

或者通过确保编解码器只能创建有效的解决方案：

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();
}

但是如果没有效果的话Constraint还有什么用呢？

Answer 1

我在最新版本的 Jenetics 中引入了 Constraint 界面。在检查个人有效性时，它是最后一道防线。在您的示例中，您使用了 Constraint 接口的工厂方法，它只采用有效性谓词。 Constraint 的第二个重要方法是 repair 方法。此方法尝试修复给定的个体。如果不定义此方法，只会创建一个新的随机表型。由于这个接口是新的，我似乎没有很好地解释 Constraint 接口的预期用途。在第二个示例中，它在我的议程上 #541. One possible usage example is given in #540。

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;
}

和Phenotype::isValid方法returnstrue，因为它是一个local有效性检查，它只检查是否所有的染色体和基因个人有效或在有效范围内。

我希望我能回答你的问题，并且正在提供一个（或多个）示例的更好描述。另一方面：如果您对 Constraint 界面的良好用法示例有任何想法，请告诉我。

Jenetics 约束似乎没有效果

Jenetics constraint seems to have no effect

java

optimization

genetic-algorithm

jenetics