在 Jenetics 中计算背包问题的适应度

Question

我正在尝试了解进化和适应度函数的工作原理。我实现了自己的背包问题，它试图从给定的集合中找到 3 件最有价值的物品。这是我自己的成本函数：

  static int counter=1;
    static double MyCostFunction(boolean[] chromosome, double[] data){
        System.out.println("COST FUNCTION: "+counter++);
        double sum = 0;
        int count = 0;
        for (int i =0; i<chromosome.length; i++){
            if (chromosome[i]){
                sum += data[i];
                count ++;
            }
        }
        return  count<=3 ? sum : 0;
    }

我打印出来只是为了看看 MyCostFunction 执行了多少次。现在我正在处理一小组 8 件物品。这是：

public static void main(String[] args) {
        double[] data = {-15,-7, -1, -1,7,100,200,300};
        Integer[] items = new Integer[data.length];
        int i = 0;
        for (double d : data){
            items[i] = i;
            i++;
        }

        ISeq<Integer> zbiorDlaGA = ISeq.of(items);


        final ISProblem knapsack= new ISProblem(zbiorDlaGA,
                chromosome -> ISProblem.MyCostFunction(  chromosome,  data)
        );

这是我正在使用的引擎：

final Engine<BitGene,Double> engine= Engine.builder(knapsack)
                .executor( Runnable::run)
                .populationSize(5)
                .survivorsSelector(new TournamentSelector<>(3))
                .offspringSelector(new RouletteWheelSelector<>())
                .alterers(
                        new Mutator<>(1.0),
                        new SinglePointCrossover<>(0.0)
                ).build();

这就是我获取统计数据的方式：

 final EvolutionStatistics<Double,?> statistics=EvolutionStatistics.ofNumber();

        final  Phenotype<BitGene,Double> best=engine.stream()
               // .limit(bySteadyFitness(15))
                .limit(5)
                .peek(r-> System.out.println("########CURRENT GEN: "
                        +r.generation()+
                        ": "+ r.totalGenerations()+
                        ": "+r.bestPhenotype()+
                        " ALTERED: "+r.alterCount()+
                        " INVALID: "+r.invalidCount()+
                        " GENOTYPE: "+r.genotypes()))
                .peek(statistics)
                .collect(toBestPhenotype());


        
        System.out.println(statistics);
        System.out.println(best);

我有几个关于你的库的一些行为的问题，我不是很理解：即使我将突变概率设置为 1.0（我认为它应该改变每一点）它也会给我这个结果：

COST FUNCTION: 1
COST FUNCTION: 2
COST FUNCTION: 3
COST FUNCTION: 4
COST FUNCTION: 5
COST FUNCTION: 6
COST FUNCTION: 7
COST FUNCTION: 8
########CURRENT GEN: 1: 1: [01100000] -> 300.0 ALTERED: 24 INVALID: 0 GENOTYPE: [[10110100],[00011011],[01011101],[00111001],[01100000]]
COST FUNCTION: 9
COST FUNCTION: 10
COST FUNCTION: 11
########CURRENT GEN: 2: 2: [00011011] -> 0.0 ALTERED: 24 INVALID: 0 GENOTYPE: [[00011011],[01011101],[10100101],[01111010],[00001011]]
COST FUNCTION: 12
COST FUNCTION: 13
COST FUNCTION: 14
########CURRENT GEN: 3: 3: [10100101] -> 0.0 ALTERED: 24 INVALID: 0 GENOTYPE: [[10100101],[01011101],[01111011],[01010011],[10010101]]
COST FUNCTION: 15
COST FUNCTION: 16
COST FUNCTION: 17
########CURRENT GEN: 4: 4: [10000010] -> 293.0 ALTERED: 24 INVALID: 0 GENOTYPE: [[01011101],[01010011],[01111011],[10000010],[00001001]]
COST FUNCTION: 18
COST FUNCTION: 19
COST FUNCTION: 20
########CURRENT GEN: 5: 5: [10000010] -> 293.0 ALTERED: 24 INVALID: 0 GENOTYPE: [[10000010],[01011101],[01000100],[10111100],[10011001]]
+---------------------------------------------------------------------------+
|  Time statistics                                                          |
+---------------------------------------------------------------------------+
|             Selection: sum=0,003352000000 s; mean=0,000670400000 s        |
|              Altering: sum=0,010647600000 s; mean=0,002129520000 s        |
|   Fitness calculation: sum=0,011403300000 s; mean=0,002280660000 s        |
|     Overall execution: sum=0,033579600000 s; mean=0,006715920000 s        |
+---------------------------------------------------------------------------+
|  Evolution statistics                                                     |
+---------------------------------------------------------------------------+
|           Generations: 5                                                  |
|               Altered: sum=120; mean=24,000000000                         |
|                Killed: sum=0; mean=0,000000000                            |
|              Invalids: sum=0; mean=0,000000000                            |
+---------------------------------------------------------------------------+
|  Population statistics                                                    |
+---------------------------------------------------------------------------+
|                   Age: max=4; mean=0,560000; var=1,090000                 |
|               Fitness:                                                    |
|                      min  = -23,000000000000                              |
|                      max  = 300,000000000000                              |
|                      mean = 41,840000000000                               |
|                      var  = 10763,306666666665                            |
|                      std  = 103,746357365773                              |
+---------------------------------------------------------------------------+
[01100000] -> 300.0

为什么只计算三个人的适应度？它是否以某种方式缓存了已经为同一染色体计算的值？

为什么第一代计算了8次？

改变个体的数量总是3*8，这意味着在进化过程中只有3条染色体发生了改变。为什么？我以为跟TournamentSelector sampleSize有关系，但它并没有改变改变染色体的数量。

突变概率等于100%，交叉概率=100%，染色体上的每一位都应该改变，所以每一代只有两个版本的染色体，但它不是这样工作的.为什么？它是随机 select 位的值还是设置相反的值？

在population/generation中设置为true的位数是否必须是一个常量（或近似常量）？

我将这些奇怪的值用于交叉和变异概率，因为我之前想知道为什么它没有给出等于 populationSize*NumberOfGenerations 的适应度计算次数。于是我开始尝试。

Answer 1

所描述的行为符合预期:)

以下事实导致观察到的结果：

种群在进化过程中分为后代和幸存者.
只有后代是改造者的目标（变异操作）。
默认 offspring 分数设置为 0.6，这使得您的示例的后代数为 3。
缓存未改变个体的适应度值。

结果：

前五个适应性评估的原因是由新鲜的初始种群 5 引起的。
接下来的三个评价是三个后代个体的评价，100%确定发生了变异。
后面三个评价的评价块同理

我认为这解释了输出，不是吗？

控制初始设置位数

如果您想控制 BitChromosome 的初始位数，您可以使用原始 Codec 创建您自己的变体。

public static <T> InvertibleCodec<ISeq<T>, BitGene>
ofSubSet(final ISeq<? extends T> basicSet, final double onesProbability) {
    final InvertibleCodec<ISeq<T>, BitGene> codec = Codecs.ofSubSet(basicSet);
    return InvertibleCodec.of(
        Genotype.of(BitChromosome.of(basicSet.length(), onesProbability)),
        codec.decoder(),
        codec.encoder()
    );
}

在 Jenetics 中计算背包问题的适应度

Calculating fitness in Knapsack problem in Jenetics

java

genetic-algorithm

jenetics