algorithm - 遗传/进化算法 - Painter

Question

我的任务:

创建一个程序来仅使用基元(如三角形或其他东西)复制图片(作为输入给出)。该程序应使用进化算法来创建输出图片。

---

我的问题:

我需要发明一种算法来创建种群并检查它们(它们与输入图片的匹配程度 - 百分比)。我有个主意;你可以在下面找到它。

那么我想从您那里得到什么: 建议(如果您觉得我的想法还不错)或灵感(也许您有更好的想法？)

---

我的想法:

假设我将只使用三角形来构建输出图片。

我的第一个种群是 P 图片(使用 T 随机生成的三角形生成 - 称为元素)。

我通过我的适应度函数检查人口中的每张图片，并选择其中 E 作为精英，其余的人口只是删除:

    To compare 2 pictures we check every pixel in picture A and compare his R,G,B with
    the same pixel (the same coordinates) in picture B.
    I use this: 
           SingleDif = sqrt[ (Ar - Br)^2 + (Ag - Bg)^2 + (Ab - Bb)^2]
    then i sum all differences (from all pixels) - lets call it SumDif
    and use:
           PictureDif = (DifMax - SumDif)/DifMax
    where
           DifMax = pictureHeight * pictureWidth * 255*3

最好的被用来以这种方式创造下一个种群:

    picture MakeChild(picture Mother, picture Father)
    {
             picture child;
             for( int i = 0; i < T; ++i )
             {
                      j //this is a random number from 0 to 1 - created now
                      if( j < 0.5 ) child.element(i) = Mother.element(i);
                      else child.element(i) = Father.element(i)
                      if( j < some small % ) mutate( child.element(i) );
             }
             return child;
    }

所以这很简单。只有突变需要注释:因此，子元素 X 与父元素 X 不同的可能性总是很小。为此，我们对 child 的元素进行随机更改(通过随机数更改他的颜色，或将随机数添加到他的 (x,y) 坐标 - 或他的节点)。

所以这是我的想法......我没有测试它，没有编码。请检查我的想法 - 你怎么看？

Answer 1

我会让每个 child 的补丁数量动态化，并让变异操作以某种(低)概率插入/删除补丁。当然，这可能会导致 child 的基因组出现大量冗余和膨胀。在这些情况下，使用个体基因组的长度作为适应度函数的参数通常是个好主意，这样个体会因使用更少的补丁而获得奖励(具有更高的适应度值)。因此，例如，如果个体 A 和 B 的 PictureDif 相同，但 A 的斑 block 比 B 少，则 A 具有更高的适应度。

另一个问题是您提出的再生算子(即交叉操作)。为了使进化过程有效地进行，您需要实现合理的探索和开发平衡。一种方法是拥有一组表现出良好适应度相关性 [1] 的生殖算子，这意味着 child 的适应度必须接近它的 parent 。

在单亲繁殖的情况下，你只需要找到正确的突变参数。然而，当谈到多亲繁殖(交叉)时，常用的技术之一是从相同的 2 个 parent 生产 2 个 child (而不是 1 个)。对于第一个 child ，每个基因来自母亲的概率为 0.2，来自父亲的概率为 0.8，对于第二个 child 则相反。当然交叉之后，你可以做变异。

哦还有一件事，对于变异算子，当你说

... make random changes in element in child (change his colour by random number, or add random number to his (x,y) coordinate - or his node)

使用高斯分布来改变颜色、坐标等是个好主意。

[1] 进化计算:Kenneth A. De Jong 的统一方法，第 69 页