我怎样才能让我的 GA 收敛？

Question

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

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

原来向上或翻转的方式 - 1 位
旋转 0（即 none）、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

您有一个非常有趣的问题需要解决。我非常喜欢它。首先，这是一个组合问题，很难用经典的遗传算法解决。我有一些评论，但它们是我的主观意见：1）二进制编码不会给你带来任何优势（只有编码和解码的开销），你可以使用 C# 对象； 2）忽略框架外的棋子是不明智的； 3）你会一直陷入局部最优，这是遗传算法的本质； 4) 1K 的人口规模太多，使用更小的东西； 5）不要使用绝对x-y坐标，使用相对坐标和适当的打包函数。

Answer 2

如果您使用像 Apache GA Framework 这样的遗传算法框架，您可以将染色体实现为形状列表，并且您可以使用排列交叉和变异。
您将有空格，您将尝试将其最小化（将它们减少为 0）。你会有空白不是问题，只需计算它们并将它们作为惩罚成分包含在适应度函数中。
一般来说，遗传算法在组合问题上不是那么强。我做了很多实验，比如用 GA 解决魔方或用 GA 解决 Puzzle 15。另一个实验是 2D Optimal Cutting Problem with GA。如果您有兴趣，我可以为您提供研究论文和源代码 (GitHub)。 GA 可以很好地为您提供次优解决方案，但它们不能为您提供最佳解决方案，当它是一个组合问题时更难。
人口规模是一个悬而未决的问题。你应该对不同的人群进行收敛调查。更多的人口并不意味着更好更快的解决方案。对于大多数用 GA 解决的问题，即使是 100 也太多了。

如果使用绝对坐标，则需要处理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

Todor Balabanov 的回答很有趣。可能使用相对坐标和适当的打包函数是重点。

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

TL;DR

二进制编码没有任何优势。
所选字母表不是允许自然表达问题的最小字母表。
考虑到每一块的完整坐标范围 ([0;7] x [0;7]) 是过多的（并且对适应性评估有些误导）。

点 (2) 和 (3) 允许将搜索 space 从 2^117 减少到 2^95 个元素。
信息更丰富的健身功能是一个很大的帮助。
- 您可以使用多值适应度分数，惩罚存在漏洞的配置。
- 不应计算由重叠块覆盖的正方形：非法配置的适应度不能大于合法配置。
ALPS can reduce the problem of premature convergence (reference implementation here).

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

我怎样才能让我的 GA 收敛？

How can I get my GA to converge?

genetic-algorithm

combinatorics

TL;DR