计算背包问题中的适应性

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个染色体。为什么？我认为这与锦标赛驱虫器样品有关，但不会改变变化的染色体数量。

由于突变的概率等于100％和交叉概率。= 100％的染色体中的每一点都应该改变，因此每一代中只有2个版本的染色体，但它不可能这样。为什么？它是随机选择位的值还是设置相反的值？

设置为true的位数是否必须是人口/发电的恒定数量（或大约是常数）？

我将这些奇怪的值用于交叉和突变概率，因为我早些时候想知道它没有给出与人口相等的*数字相等的健身计算的数量。所以我开始实验。

Answer 1

所描述的行为与预期一样：）

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

1. 在进化过程中，种群被分为后代 和幸存者。
2. 只有后代才是变更器的目标（突变操作）。
3. 默认后代分数设置为0.6，示例的后代计数为3。
4. 不变个体的健身值被缓存。

结果：

1. 前五个健身评估的原因是由新鲜的初始人口为5。
2. 接下来的三个评估是由于三个后代个体引起的，这已经以100％的确定性进行了突变。
3. 随后的三个评估评估块具有相同的原因。

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

控制最初设置位的数量

如果要控制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()
    );
}