artificial-intelligence - 进化计算中的适应度共享和生态位计数是什么？

Question

在进化计算的背景下，什么是“健身共享”和“利基计数”？

Answer 1

随着种群多样性的减少，进化算法 (EA) 往往会收敛到一个单一的解决方案 [1] .这种行为被称为遗传漂变。任何基于种群成员之间的距离来保持种群多样性的技术都称为 Niching 技术。

健身共享是一种 Niching，其中每个人的健身都根据其与他人的接近程度进行缩放。这意味着人口稠密地区的良好解决方案比人口稀少地区的同等良好解决方案的适应度值更低。实际上，算法的选择技术不太重视这些高质量、高密度的解决方案。可以根据决策空间(基因型)、解空间(表型)或两者(如 Goldberg 和 Richardsen [2])中的值计算距离。基因型的距离通常使用 Hamming distance 定义而表型中的距离通常使用 Euclidean distance 定义.

下面的Java方法给出了一个简单的健身分享方法:

/** 
* Computes the shared fitness value for a solution
* @param index the index of the solution for which a shared fitness value will be computed
* @param minDist any solution closer than minDist will share fitness with the current solution
* @param shareParam a parameter that defines how much influence sharing has. Higher = more sharing.
* @param population the array of solutions. Each solution has a genotype and associated fitness value.
*/
public double computeSharedFitnessValue(int index, double minDist, double shareParam, Solution[] population){

  double denominator = 1;

  for(int j = 0; j < population.length; j++){

     final double dist = hamming_dist(population[index],population[j]);

     if (dist < minDist){
        denominator += (1-(dist/shareParam))
     }
  }

  return population[index].getFitnessValue()/denominator;
}

励志示例:下图完美地说明了为什么适应度共享在多目标问题中如此重要。在图 A(左)中，在整个执行过程中都保持了多样性。因此，这些解决方案跨越了真正的帕累托前沿(此处显示为线框)的很大一部分。在图 B(右)中，人口仅收敛到帕累托前沿的一小部分区域。在许多情况下，即使图 B 中的解决方案质量更高，决策者也会更喜欢图 A 中提供的选项多样性，而不是图 B 质量的(名义上)改进。



其他资源:

[1] Genetic algorithms with sharing for multimodal function optimization

[2] Genetic Algorithms for Multi-Objective Optimization: Formulation Discussion and Generalization