什么是进化计算中的适应性共享和利基计数？

Question

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

Answer 1

随着人口多样性的减少,进化算法(EA)倾向于收敛到单一解决方案[1].这种行为称为遗传漂变.任何基于群体成员之间的距离维持群体多样性的技术称为Niching技术.

健身共享是一种Niching,其中每个人的健康状况是根据其与其他人的接近度来缩放的.这意味着人口密集地区的良好解决方案的适应性值低于人口稀少地区的相对较好的解决方案.实际上,该算法的选择技术不太重视这些高质量,高密度的解决方案.距离可以根据决策空间(基因型),溶液空间(表型)或两者中的值计算(如Goldberg和Richardsen [2]).基因型中的距离通常使用汉明距离来定义,而表型中的距离通常使用欧几里德距离来定义.

以下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]具有多模态函数优化共享的遗传算法
• [2]多目标优化的遗传算法:配方讨论和推广