1

我已经使用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/的 P07背包_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 节）：

一个给定的问题通常应该以某种方式编码，即进化不可能Engine创造出无效的个体（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但是，如果它没有效果，那么它的目的是什么？

4

1 回答 1

1

我Constraint在最新版本的 Jenetics 中介绍了该接口。当涉及到检查个人的有效性时，它是最后一道防线。在您的示例中，您使用了Constraint接口的工厂方法，它只接受有效性谓词。第二个重要的方法Constraint是repair方法。此方法尝试修复给定的个人。如果不定义此方法，则只会创建一个新的随机表型。由于这个接口是新的，所以我似乎没有很好地解释Constraint接口的预期用途。它在我的议程#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界面的良好使用示例有想法，请告诉我。

于 2019-07-13T05:50:52.960 回答