犹太人约束似乎没有任何作用 [英] Jenetics constraint seems to have no effect

问题描述

我已经使用背包问题的变体: //jenetics.io/"rel =" nofollow noreferrer> Jenetics 如下:

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是 Lombok 的一部分，并生成一堆代码，例如构造函数，getters等. Problem类为特定背包问题定义了一些常量(来自 https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html ):

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

}

尽管Jenetics 用户指南表示(请参见第2.5节):

Although the Jenetics user guide says (see section 2.5):

给定问题通常应以某种方式编码，即进化Engine不可能创建无效个体(Genotypes).

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.

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

但是Constraint无效的目的是什么?

But then what is the purpose of Constraint if it has no effect?

推荐答案

我在最新版本的Jenetics中引入了Constraint界面.这是检查个人有效性的最后一道防线.在您的示例中，您使用了Constraint接口的factory方法，该方法仅使用有效性谓词. Constraint的第二个重要方法是repair方法.此方法尝试修复给定的个人.如果不定义此方法，则仅创建一个新的随机表型.由于此接口是新接口，因此似乎我还没有充分解释Constraint接口的预期用途.它在我的议程上#541 .在第二个示例中的#540 中给出了一个可能的用法示例.

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

Phenotype::isValid方法返回true，因为这是 local 有效性检查，该检查仅检查个体的所有染色体和基因是否有效或在有效范围内.

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.

我希望我能回答您的问题，并且正在提供一个(或多个)示例的更好描述.另一方面:如果您对Constraint界面的用法示例有好的想法，请告诉我.

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.

这篇关于犹太人约束似乎没有任何作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！