java - 基因约束似乎没有效果

Question

我已经实现了 knapsack problem 的变体使用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 的一部分并生成一堆代码，如构造函数、getter 等。 Problem 类为特定的背包问题定义了一些常量(来自 https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html 的 P07):

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() 返回 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 接口(interface)。当涉及到检查个人的有效性时，它是最后一道防线。在您的示例中，您使用了 Constraint 接口(interface)的工厂方法，该方法仅采用有效性谓词。 Constraint 的第二个重要方法是 repair 方法。此方法尝试修复给定的个人。如果不定义此方法，则只会创建一个新的随机表型。由于这个接口(interface)是新的，所以我似乎没有足够好地解释 Constraint 接口(interface)的预期用途。它在我的议程上#541 。 #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 方法返回 true，因为它是一个本地有效性检查，仅检查是否所有染色体和基因个人有效或在有效范围内。

我希望我能回答您的问题，并且即将通过一个(或多个)示例提供更好的描述。另一方面:如果您有关于 Constraint 接口(interface)的良好使用示例的想法，请告诉我。