genetic-algorithm - 如何让我的 GA 收敛？

Question

我正在尝试编写一个 GA 来解决以下难题...

二进制编码(我认为)非常有效。每件作品可以是:

• 原始向上或翻转的方式 - 1 位
• 旋转 0(即无)、90、180 或 270 度 - 2 位
• 在位置 (x, y)，其中 x 和 y 从 0 到 7 - 每个坐标 3 位

这意味着每 block 的方向和位置都可以用 9 位进行编码，使得整个拼图总共有 117 位。

通过将每个 block 放入框架中，忽略框架外的任何部分，然后将空方 block 的数量相加来计算适合度。当这个值为零时，我们就有了解决方案。

我有一些在其他代码中使用过的标准 GA 方法(我将在下面粘贴)，但我似乎无法让它收敛。适应度下降到大约 11(给予或接受)，但似乎从未降低过。我尝试过修改参数，但无法得到更好的结果。

冒着发布太多代码的风险，我将展示我所拥有的内容(在看起来相关的地方)。如果有人能给我一些如何改进的想法，那就太好了。这些都是用 C# 编写的，但对于使用其他语言的人来说应该足够清楚了。

生成 1000 个染色体的初始种群(代码未显示，因为它只是生成长度为 117 的随机二进制字符串)后，我进入主循环，在每一代中，我调用 Breed 方法，传入当前种群并一些参数...

private static List<Chromosome> Breed(List<Chromosome> population, int crossoverGene, 
                  double mutationProbability, double mutationRate) {
  List<Chromosome> nextGeneration = new List<Chromosome>();
  // Cross breed half of the population number
  for (int nChromosome = 0; nChromosome < population.Count / 2; nChromosome++) {
    Chromosome daddy = Roulette(population);
    Chromosome mummy = Roulette(population);
    string babyGenes = daddy.Genes.Substring(0, crossoverGene)
                     + mummy.Genes.Substring(crossoverGene);
    Chromosome baby = new Chromosome(babyGenes);
    baby.Fitness = Fitness(baby);
    nextGeneration.Add(baby);
  }
  // Mutate some chromosomes
  int numberToMutate = (int)(P() * 100 * mutationProbability);
  List<Chromosome> mutatedChromosomes = new List<Chromosome>();
  for (int i = 0; i < numberToMutate; i++) {
    Chromosome c = Roulette(population);
    string mutatedGenes = MutateGenes(c.Genes, mutationRate);
    Chromosome mutatedChromosome = new Chromosome(mutatedGenes);
    mutatedChromosome.Fitness = Fitness(mutatedChromosome);
    mutatedChromosomes.Add(mutatedChromosome);
  }
  // Get the next generation from the fittest chromosomes
  nextGeneration = nextGeneration
    .Union(population)
    .Union(mutatedChromosomes)
    .OrderBy(p => p.Fitness)
    .Take(population.Count)
    .ToList();
  return nextGeneration;
}

MutateGenes 只是根据传入的突变率随机翻转位。主循环将继续，直到我们达到最大代数，或者适应度降至零。我目前已经运行了 1000 代。

这是轮盘赌方法...

private static Chromosome Roulette(List<Chromosome> population) {
  double totalFitness = population.Sum(c => 1 / c.Fitness);
  double targetProbability = totalFitness * P();
  double cumProbability = 0.0;
  List<Chromosome> orderedPopulation = population.OrderBy(c => c.Fitness).ToList();
  for (int i = 0; i < orderedPopulation.Count; i++) {
    Chromosome c = orderedPopulation[i];
    cumProbability += 1 / c.Fitness;
    if (cumProbability > targetProbability) {
      return c;
    }
  }
  return orderedPopulation.Last();
}

不知道您是否需要查看其他代码。我对发布太多内容有点担心，以免让人们望而却步!

任何人都可以就如何改进此问题提出任何建议吗？

Answer 1

托多尔·巴拉巴诺夫的回答非常有趣。可能使用相对坐标和适当的打包函数是关键。

无论如何，我想尽可能地扩展你的想法。对于 Stackoverflow 来说，完整的讨论可能太长了......

TL;DR

1. 二进制编码不会给您带来任何优势。
2. 所选字母表并不是能够自然表达问题的最小字母表。

3. 考虑每 block 的完整坐标范围 ([0;7] x [0;7]) 是过多的(并且对健身评估有些误导)。

   第 (2) 点和第 (3) 点允许​​将搜索空间从 2^117 减少到 2^95 元素。

4. 信息更丰富的健身功能会有很大帮助。
   • 您可以使用多值健身得分，对存在漏洞的配置进行惩罚。
   • 不应计算由重叠 block 覆盖的方 block :非法配置的适应度不能大于合法配置的适应度。
5. ALPS可以减少早熟收敛的问题(引用实现 here )。

---

我已经在 GitHub wiki 中详细阐述了这些观点(这是一项正在进行的工作)。