旅行者日志 首页 创造 随笔 笔记 诗 翻译 关于

使用演化算法拟合图像PUNK#4

Jul 2, 2024

在这里，令我们感兴趣的并不是这个算法所关联的那些技术细节，而是这个算法本身的概念和限制。

接下来，我们将运用严格的分析方法，来给出演化算法的描述。

演化分析

首先需要强调的是，演化算法是一种量化方法。它类似于对一个作为目的的量的搜索，但是更合适的说法是对一个量的探索，因为系统本身并不认识这个所将探索的量。接下来我们将称呼这个量为遗传信息Gene。

这种探索可以由三个关键的原则所描述：

在由这三个原则所构成的演化装置中，超越代际的目的层面被排除了。无论是遗传、变易还是选择原理，它们没有一个暗示存在一个超越代际的超越性原理。因而，应用遗传算法时，我们不能预设一个终极图景、算法需要去拟合的终极图像。一切同拟合相关的责任全数落在系统的设计者（往往是选择机制的设计者）身上。

但是，既然我们不得不总是把对预期目的的拟合纳入到系统设计的考虑范围内，我们感到一种需要：给出演化装置的一种特定的外延，令其同演化装置的内涵对立。这个外延的方面是面向设计者的界面，仅仅对于我们而言而非对演化装置本身而言具有意义。

为了令这一点对于算法的设计而言有意义，我们引入一种新的原则：

有了表达原则的约束，遗传信息将仅仅是涉及到为我们而言的那些性状的遗传信息。——达尔文的进化论，其中最值得考察的地方难道不就是遗传信息同其表达之间所存在的张力吗？对这种张力的忽略、在遗传信息及其表达之间的短路，以至于诞生出了社会达尔文主义这样的退行产物。须知「种群」与「竞争」这些观念，仅仅是为我们的特定阐释方向所认识而言才成立的表象，它们对于自在而言演化装置并不一定具有意义：仅仅因为达尔文所关注的那些性状是遗传信息在种群层面上表达的，所以种群作为一个外延的量的单位才被接纳入理论，从它出发说不清任何事。

在对于表达原则的不同态度上，遗传算法和达尔文进化论分道扬镳了。遗传算法以表达原则为导向、为设计界面，而在达尔文那里，表达仅仅意味着表象。——如果仅以进化方向为导向，那么我们可以说，莎士比亚全集是进化中的一个偶然的东西、一条歧路。但是如果我们忠实于进化论的精神，它恰恰意味着对设计维度的排除，也就是说进化的方向根本不可能作为一种导向，不能作为一个预先给出的目的，进化论恰恰要求走遍几乎所有歧路——「选择的到底是什么？」难道不正是大他者的欲望之谜吗？

对于遗传信息所表达的量，我们可以使用直观的量来可视化，即适应度得分，其表达形式往往是图表（διαγράμμα/diagram）及其评估函数。与其对应的则是同遗传信息相关的、对其进行操作的装置所会涉及到的晦涩的结构化的图式（σχῆμα/schema）。

评估函数的设计

我们依据我们心目中所要拟合的整体性图像来作为评估标准，如果可能，我们可以直接把同这个最终的图像相符当作最终的评估标准，就像我们把莎士比亚全集当作猴子与打字机的评判标准那样。

可以想象，「绝对同一」这样的评估函数固然可以达成我们想要的目标，但是它会造成算法运行效率相当低效的。更何况这样的算法没有任何意义，如果我们能够直接提供最终图像，那么我们还算什么呢？

因而这个作为目的的整体性图像至少是模糊不清的，当我们提供一副确定的整体性的图像时，我们所提供的仅仅是一种参考。实际上我们所根据的始终是性状。

我们如何用性状来结构化地描述我们所要拟合的图像？这意味着需要对作为选择对象的种的整体性图像进行一种拆分。这里我们采取一种最基本的拆分方法，即把它拆解为多个元素的组合。

假设我们将图像考虑为一系列笔触，它们在总数上不定、在顺序上不定、在大小上不定、在形状上不定、在笔触的起始和结束位置上不定……这些不定的元素的组合就可以作为性状的结构定义。

struct Trait {
  strokes: vec<Stroke>,
};

struct Stroke {
  pos_begin: vec2<f32>,
  pos_end: vec2<f32>,
  rotation: f32,
  scale: f32,
  color: vec3<f32>,
  texture_id: u32,
};

对此，我们可以设计许多种不同的评估函数，例如说我们可以直接对最终的图像进行评估，也可以分别对每一个笔触都进行一次评估，然后再整体性地进行一次评估。

因为我们所定义的性状包含了线条的序列，我这里选择是根据这些序列来进行评估的函数：

评估函数f(性状t):
  按照顺序，对于每一条笔触：
    计算其被添加之前和之后的效果，如果更加接近参考图像，就把它加入集合V中;
    按顺序检查集合V中的每一元素x:
      如果x被后续元素覆盖，就将其移除集合V;
  设所有笔触数量为s, 集合V中元素数量为v;
  比值v/s即为评估函数的结果;

也就是说，我们的评估函数取决于有效笔触数量同全部笔触数量的比值。

初看上去，这似乎是一个合理的标准。然而，在全部笔触数量为1时，这个函数达到了最好的结果，这是完全不可接受的。因而，我们可以添加一个预先评估的函数，使得笔触铺满整个图像，只有满足了这个条件的笔触才能进入上述评估函数：

评估函数g(性状t):
  如果笔触没有铺满整个图像:
    评估函数的结果为图像的覆盖率；
  否则:
    评估函数的结果为1+f(t)的值;

注意，这里我们达成了覆盖率评估函数和笔触评估函数之间的连续：即使没有铺满整个图像，评估函数的结果依然不一定为0，而是等于覆盖率；而对于铺满了整个图像的情况，结果等于1+有效笔触率。之所以这一点是关键的，是因为对于遗传算法来说，评估函数只有足够平滑，才能保证迭代间具有连贯性，所有的跳变应该由变异过程实现。

变异和遗传

接下来，仍需要规定的是遗传和变异的方式。

对于遗传，这是整个过程中最具有规律的部分，因而也是最好设计的部分。得益于线条的线性特征，我们简单地利用父代线条的插值来生成子代。对于线条数量不相同的情况，我们简单地取中值。

对于变异，一切差异由此得以生成。需要考虑的是以下一组对立：

  1. 所有我们所需要的笔触要能够由此产生；
  2. 变异的结果和父代要有足够的区分度。

第一点决定了，变异的最小值不能过大，不然会令一些中间的值无法产生。而第二点决定了，变异的最大值不能过小，不然会令迭代的过于漫长、降低算法的运行效率。

考虑到以上两方面，我设计的变异方法是保留遗传后一定比例的笔触不变，改变其中一定数目的笔触的要素，并根据笔触的总数量随机添加或删除一定数量的笔触。

总结：遗传算法的特征

根据以上分析，我们知道了遗传算法的几项特征：

这一小片精神，这一小块血肉，随你处置，愿你善待它