遗传学中背包问题的适应度计算

我试图理解进化和适应度函数是如何工作的。我实现了自己的背包问题，即尝试从给定集合中找到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条染色体被改变。为什么?我认为这与锦标赛选择器sampleSize有关，但它不会改变改变染色体的数量。

突变概率为100%，交叉概率。=100%它应该改变染色体上的每一个比特，所以每一代只有两个版本的染色体，但事实并非如此。为什么?它是随机选择位的值还是相反的设置?

在population/generation中设置为true的位数必须是一个常数(或近似常数)吗?

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

描述的行为符合预期:)

下列事实导致了观察到的结果:

在进化过程中，种群分为后代和幸存者。
只有后代是改变者(突变操作)的目标。
默认的后代分数被设置为0.6，这使得在您的示例中后代计数为3。
保存未改变个体的适应度值。

前5次适应度评价的原因是由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()
);
}

相关内容

最新更新

热门标签：