遗传/进化算法 - 画家

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不同,总有一些小概率.为此,我们对子元素进行随机更改(通过随机数改变颜色,或将随机数添加到他的(x,y)坐标 - 或他的节点).

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

Answer 1

我将使每个子项的补丁数量动态化，并进行变异操作以一定（低）概率插入/删除补丁。当然，这可能会导致孩子的基因组出现大量冗余和膨胀。在这些情况下，通常最好使用个体基因组的长度作为适应度函数的参数，以便个体因使用较少的补丁而获得奖励（具有更高的适应度值）。例如，如果个体 A 和 B 的 PictureDif 相同，但 A 的 patch 少于 B，则 A 具有更高的适应度。

另一个问题是您提出的生殖算子（即交叉操作）。为了使进化过程有效地进行，你需要实现合理的探索和利用平衡。实现此目的的一种方法是拥有一组表现出良好适应度相关性的繁殖算子[1]，这意味着子代的适应度必须接近其父代的适应度。

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

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

...对 child 中的元素进行随机更改（通过随机数更改其颜色，或将随机数添加到他的 (x,y) 坐标 - 或他的节点）

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

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