如何让我的GA收敛？

Question

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

二进制编码（我认为）非常有效。每件作品可以是：

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

这意味着每个部分的方向和位置可以编码为9位，整个拼图总共为117位。

通过将每个片段放置在帧中，忽略位于帧外的任何部分，然后将空方块的数量相加来计算适合度。当它达到零时，我们有一个解决方案。

我有一些我在其他代码中使用的标准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

Todor Balabanov的回答非常有趣。可能使用相对坐标和适当的包装功能是关键。

无论如何，我想尽可能地扩展你的想法。对Stackoverflow进行全面讨论可能太长了......

TL;DR

1. 二进制编码不会给你任何好处。
2. 选择的字母表不是允许自然表达问题的最小字母表。
3. 考虑到每个部分的全部坐标（[0;7] x [0;7]）过多（并且对于健身评估有些误导）。 点（2）和（3）允许将搜索空间从2^117减少到2^95元素。
4. 更丰富的健身功能是一个很大的帮助。 您可以使用多值健身分数，惩罚呈现漏洞的配置。 不应计算重叠部分覆盖的正方形：非法配置不能具有超过合法的适应性。
5. ALPS可以减少早熟收敛的问题（参考实施here）。

---

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

Answer 2

1. 如果您使用像Apache GA Framework这样的遗传算法框架，您可以将染色体实现为形状列表，您可以使用置换交叉和变异。
2. 您将有空格，您将尝试最小化（将它们减少到0）。你不会有空白，只计算它们并将它们作为惩罚成分包含在适应度函数中。
3. 通常，GA在组合问题上不是那么强。我做了很多实验，比如用GA解决Rubik's Cube或用GA解决Puzzle 15。另一个实验是GA的2D最优切割问题。如果您有兴趣，我可以为您提供研究论文和源代码（GitHub）。 GA很好地为您提供次优解决方案，但它们不能很好地为您提供最佳解决方案，当它是组合问题时更难。
4. 人口规模是一个悬而未决的问题。你应该对不同的人群进行收敛性调查。更大的人口并不意味着更好更快的解决方案。对于GA解决的大部分问题，即使100也是太多了。
5. 如果使用绝对坐标，则需要处理x和y，这太复杂了。想象一下，你支持形状列表。包装程序可以按形状塑造，并将每个形状尽可能靠近已处理的形状。它将加速您的融合。

   /**
    * Pack function which uses bounding rectangle of the polygons in the sheet
    * with specified dimensions.
    * 
    * @param width
    *            Sheet width.
    * @param height
    *            Sheet height.
    */
   public void pack1(int width, int height) {
       int level[] = new int[width];
       for (int i = 0; i < level.length; i++) {
           level[i] = 0;
       }
   
       /*
        * Insure pieces width according sheet width.
        */
       for (Piece piece: population.get(worstIndex)) {
           if (piece.getWidth() > width) {
               piece.flip();
           }
       }
   
       /*
        * Pack pieces.
        */
       int x = 0;
       int y = 0;
       for (Piece piece: population.get(worstIndex)) {
           if (x + (int) piece.getWidth() >= width) {
               x = 0;
           }
   
           /*
            * Find y offset for current piece.
            */
           y = 0;
           for (int dx = x; dx < (x + piece.getWidth()); dx++) {
               if (dx < width && y < level[dx]) {
                   y = level[dx];
               }
           }
   
           // TODO Check the delta after subtraction.
           /*
            * Set current piece coordinates.
            */
           piece.moveX(x - piece.getMinX());
           piece.moveY(y - piece.getMinY());
   
           /*
            * Move lines for next placement.
            */
           for (int dx = x; dx < (x + piece.getWidth()); dx++) {
               if (dx < width) {
                   level[dx] = (int)(y + piece.getHeight());
               }
           }
   
           // TODO Some strange behavior with the rotation.
           x += (int) piece.getWidth() + 1;
       }
   }
   
   /**
    * Pack function which uses exact boundaries of the polygons in the sheet
    * with specified dimensions.
    * 
    * @param width
    *            Sheet width.
    * @param height
    *            Sheet height.
    */
   public void pack2(int width, int height) {
       /*
        * Pieces already placed on the sheet.
        */
       List < Piece > front = new ArrayList < Piece > ();
   
       /*
        * Virtual Y boundary.
        */
       double level = 0;
   
       /*
        * Place all pieces on the sheet
        */
       for (Piece current: population.get(worstIndex)) {
           double bestLeft = 0;
           double bestTop = level;
           current.moveX(-current.getMinX());
           current.moveY(-current.getMinY() + level);
   
           /*
            * Move across sheet width.
            */
           while (current.getMaxX() < width) {
               /*
                * Touch sheet bounds of touch other piece.
                */
               while (current.getMinY() > 0 && Util.overlap(current, front) == false) {
                   current.moveY(-1);
               }
               // TODO Plus one may be is wrong if the piece should be part of
               // the area.
               current.moveY(+2);
   
               /*
                * Keep the best found position.
                */
               if (current.getMinY() < bestTop) {
                   bestTop = current.getMinY();
                   bestLeft = current.getMinX();
               }
   
               /*
                * Try next position on right.
                */
               current.moveX(+1);
           }
   
           /*
            * Put the piece in the best available coordinates.
            */
           current.moveX(-current.getMinX() + bestLeft);
           current.moveY(-current.getMinY() + bestTop);
   
           /*
            * Shift sheet level if the current piece is out of previous bounds.
            */
           if (current.getMaxY() > level) {
               level = current.getMaxY() + 1;
           }
   
           /*
            * Add current piece in the ordered set and the front set.
            */
           front.add(current);
       }
   }
   
   /**
    * Pack function which uses exact boundaries of the polygons in the sheet
    * with specified dimensions.
    * 
    * @param width
    *            Sheet width.
    * @param height
    *            Sheet height.
    */
   public void pack3(int width, int height) {
       Polygon stack = new Polygon(
           GEOMETRY_FACTORY
           .createLinearRing(new Coordinate[] {
               new Coordinate(0, -2, 0), new Coordinate(width - 1, -2, 0),
                   new Coordinate(width - 1, 0, 0), new Coordinate(0, 0, 0), new Coordinate(0, -2, 0)
           }),
           null, GEOMETRY_FACTORY);
   
       /*
        * Virtual Y boundary.
        */
       double level = stack.getEnvelopeInternal().getMaxX();
   
       /*
        * Place all pieces on the sheet
        */
       for (Piece current: population.get(worstIndex)) {
           double bestLeft = 0;
           double bestTop = level;
           current.moveX(-current.getMinX());
           current.moveY(-current.getMinY() + level);
   
           /*
            * Move across sheet width.
            */
           while (current.getMaxX() < width) {
               /*
                * Touch sheet bounds of touch other piece.
                */
               while (current.getMinY() > 0 && Util.overlap(current, stack) == false) {
                   current.moveY(-1);
               }
               // TODO Plus one may be is wrong if the piece should be part of
               // the area.
               current.moveY(+2);
   
               /*
                * Keep the best found position.
                */
               if (current.getMinY() < bestTop) {
                   bestTop = current.getMinY();
                   bestLeft = current.getMinX();
               }
   
               /*
                * Try next position on right.
                */
               current.moveX(+1);
           }
   
           /*
            * Put the piece in the best available coordinates.
            */
           current.moveX(-current.getMinX() + bestLeft);
           current.moveY(-current.getMinY() + bestTop);
   
           /*
            * Shift sheet level if the current piece is out of previous bounds.
            */
           if (current.getMaxY() > level) {
               level = current.getMaxY() + 1;
           }
   
           /*
            * Add current piece in the ordered set and the front set.
            */
           stack = (Polygon) SnapOverlayOp.union(stack, current.getPolygon()).getBoundary().convexHull();
           stack.normalize();
       }
   }

Answer 3

你有一个非常有趣的问题需要解决。我非常喜欢它。首先，它是一个组合问题，使用经典遗传算法很难解决。我有一些评论，但它们是我的主观意见：1）二进制编码没有给你任何优势（只有编码和解码的开销），你可以使用C＃对象; 2）忽略框架外的碎片是不明智的; 3）你将一直处于局部最优状态，这就是遗传算法的本质; 4）人口规模1K过多，使用较小的东西; 5）不要使用绝对x-y坐标，使用相对坐标和正确的包装功能。