用蚂蚁绘制：使用蚁群优化算法的程序图像

我为什么要画蚂蚁

我想创作一幅艺术品，探讨软件设计的复杂性。当我提出一个庞大的代码库时，我会想到它的独立产生的复杂性及其相互联系的相互联系的部分。可以说，它的一般形式来自许多个人的行为。

我当时正在考虑如何以图形方式呈现此图像，而在我身上引起反响的图像之一就是蚁群的图像。蚂蚁是新兴（新兴）复杂性的一个很好的例子。没有一个蚂蚁是建筑师，但是他们共同构建了宏伟的复杂结构。

杀虫剂方案。资料来源：Wikimedia Commons。

我从寻找有关蚁群模拟的信息开始。显然，有关于此的文献，它是美丽的。但是诀窍在于，蚁丘的出现部分取决于它们所在的沙子和地球的物理特性-因为它们的产生取决于当蚂蚁将其放置时粒子的位置。我想在2D中创建某些东西，所以我尝试不编写沙子物理代码而直接进行模拟，也就是说，我不得不放弃蚁丘的物理模拟。

因此，我再次开始搜索，他们将我带到了完全不同的蚂蚁模拟类：蚁群优化算法（ant Colony algorithm）。

蚁群优化是一种代理算法，用于解决在图形的两个点之间找到最短路径的问题。 “代理”是指算法由单独的过程（在这种情况下为“蚂蚁”）组成，这些过程的紧急行为解决了该问题。

它的工作非常简单。每个蚂蚁在其路径中都留下一丝“信息素”。蚂蚁离开蚁丘后会留下一种信息素，而当他们找到食物时会留下另一种信息素。寻求食物的蚂蚁试图找到一种“食物”信息素，而那些寻求蚁丘的蚂蚁则寻求一种“家庭”信息素。

发现自己走的路较短的蚂蚁可以更快地从家到食物，反之亦然。这意味着它们将创建更饱和的信息素层。蚂蚁移动的时间越长，轨道越丰富，移动路径越短。每个蚂蚁都按照非常简单的规则工作，但是随着时间的流逝，蚂蚁会发现两点之间的最优路径。

模拟

我在Processing 3上编写了我的蚂蚁模拟器。我通过模拟Gregory Brown的这篇令人惊奇的帖子中的代码来开始自己的实现。

蚂蚁开始移动后，我开始扩展和修改代码，以使其在较大的像素网格中更好地工作。我想获得有趣的外观模拟（不一定有效），这决定了我在代码上的工作。我为蚂蚁创建了一个非常基本的构想，以便每个蚂蚁可以看到前方几个像素。我添加了蚂蚁的死亡和重生，以使它们不会在整个空间中随机散布。最后，我使蚂蚁有些笨拙：即使搜索不成功，它们也会不断离开信息素，这与蚂蚁的真实行为相似。

在这里，您可以在浏览器中直接在p5.js上播放模拟端口！

您也可以在Github上查看移植的源代码。

在仿真中最重要的是，我对蚂蚁​​创造的美丽，奇怪和复杂的形状着迷。它们不是沿直线前进，而是形成循环，转弯和分支。更有趣的是，您可以通过更改蚂蚁世界中的各种变量来控制它们创建的图形的外观。例如，您可以更改信息素蒸发速率和蚂蚁的视觉范围（以像素为单位）。

把蚂蚁变成艺术

模拟开始工作之后，下一步就是研究其输出的数据。我的目标是创建某种二维图像，也就是说，我需要捕获并绘制由蚂蚁创建的图形。

最后，我编写了不同类型的输出：几种类型的栅格输出和一个矢量。为了捕获栅格输出，我跟踪了蚂蚁访问过的像元以及它们访问的频率。在使用了此结论的筛选器之后，您可以幽灵地找到蚂蚁去过的那些地方。

栅格输出的示例。沿着流行的蚂蚁步道和蚂蚁随机在蚂蚁山周围漫游的路径要宽得多。

栅格输出很有趣，但是我想更清楚地看到各个路径，因此我探索了导出到svg的可能性。对于矢量输出，我保存了每只蚂蚁的历史记录，当它们到达食物或蚁丘时，我在列表上写下了这个故事。为了进行渲染，我对每个保存的路径进行了采样，并将其渲染为一系列曲线。

向量输出的示例。在这里，您可以看到蚂蚁的各个路径。在有很多蚂蚁的地方，稍微重叠的线形成了更宽的路径。

将点连接

我知道我想绘制在多个点之间移动的蚂蚁，因此将多个模拟链接到一个图像中的代码是最早的代码之一。但是那我应该画什么呢？

最初，我决定创建非常文字的图：从简单的二叉树开始，然后继续进行更复杂的可视化。这似乎是很自然的一步，因为优化蚁群可以解决在图形中查找路径的问题。我还认为这是一种可视化代码复杂性的有趣方式：为什么不采用UML图或依赖图并用蚂蚁渲染它们？

我已经熟悉Graphviz，因此决定使用此工具包和DOT图形描述语言指定模拟的节点和边缘。Graphviz具有输出带有像素坐标注释的DOT文件的模式。我编写了一个非常难看的DOT文件解析器，并将其与带注释的DOT文件一起使用，以模拟蚁丘和食物位置。

用二叉树进行的实验似乎很有希望，并给出了非常自然的有机外观。

一个简单的二叉树。有人告诉我，这就像血管造影。

稍复杂的树，已经很深了。

然后，我开始使用各种代码库作为输入来构建更多图形。我编写了一些简单的Python脚本：一个将git树转换为DOT文件，另一个将C导入依赖项转换为DOT文件。

蚂蚁在git对象树中绘制的对象图。

Linux内核中文件之间的依赖关系。使用Graphviz图的正方形样式创建节点和边。实际上，没有什么比随机图有趣得多了。

尽管所有这些图都很有趣并且肯定很复杂，但令我感到失望的是，实际上它们并没有说明构建它们的代码库的一般形式。我对代码可视化进行的试验越多，我越意识到从代码库本身构造一个有趣的图形是一项单独的，更加困难的任务。但是，我喜欢非常大的图的复杂性，后来我又回到了这一点。

我的下一个实验是使用简单形式的游戏。我根据线，圆，正弦曲线和其他易于用节点和边线描述的形状创建了图形。

段上的点，在段的右侧，这些点彼此靠近。

不同的正弦波频率。我想蚂蚁会产生出很好的示波器。

在我看来，最简单的三角空间似乎最有趣。我生成了许多均匀分布的点（随机地或通过绘制形状），然后使用处理库将这些点转换为Delaunay三角剖分或Voronoi图。然后，将所得的肋骨用于模拟蚂蚁，其中每个肋骨表示一个“蚁丘”或“食物”。

由蚂蚁Voronoi图绘制。

这导致出现了复杂的蚂蚁错综复杂的美丽空间，它描述了使我更感兴趣的复杂性。

最后，我从另一个角度完成了任务。一位朋友查看了模拟情况，并询问蚂蚁与墙壁碰撞时会发生什么-他们可以避免简单的障碍吗？我的代码已经知道如何将墙作为边界案例处理，因此我只是添加了内墙，然后花了很多时间尝试教蚂蚁如何解决迷宫问题。

蚂蚁试图解决一个简单的迷宫的路径。通过注意蚂蚁无法到达的地方，可以看到迷宫的形状。

我的想法是，如果蚂蚁可以解决简单的迷宫，那么您可以将它们组合在一起以创建更大的作品。我花了很多时间来设置模拟变量，以便蚂蚁可以解决它们，但是我仍然无法让他们稳定地解决迷宫。最后，所有这些变成了蚂蚁路径的弯曲，受到迷宫本身形状的限制。

艺术品完成

在这个阶段，我决定退后一步，考虑所有实验的结果。我意识到，最有趣的图像是从半随机点和边缘的大区域中获得的，因此，我决定通过设置模拟以在随机点的Delaunay三角剖分之间绘制线来做出最终决定。

完成模拟运行。它包含许多叠加路径，可从这些路径获得模糊点。

最后一个问题是如何将SVG折弯加工成成品。通过实验，我知道我想以某种方式对路径进行排序，以突出显示形状优美的路径。但是完成的模拟过程要花一到两个小时，这就是为什么在每次实验中都难以更改变量的原因。

我决定编写第二个处理图，将模拟输出加载到SVG中，然后应用所需的视觉效果。此外，我想使后处理脚本具有交互性，以便可以试验不同的线条粗细和颜色以及排序阈值。

我尝试了几种不同的方法来评估应该位于前台和后台的路径。计算了几个不同的因素：线的自交点数，斜率线的交点数以及该线遵循前两个点预测的斜率的可能性。

我将后处理脚本用于这些估计的不同权重和值的实验，直到获得所需的外观为止。

前线和背景线的阈值设置。

在这一点上，更改每个变量时保存图像很有帮助。当我接近所需的图像时，比较多个较小的变化比一次更改多个因素要容易得多。

经过长时间的设置并进行了少量更改，我从仿真中创建了以下图像：

我放大了对我来说最有趣的区域，并对其进行裁剪以在空白空间和填充空间之间建立良好的平衡。

最后一步是如何将图像转换为物理对象的选择。我曾经以40×50厘米的海报进行数字打印，然后尝试（不成功）在彩色纸上打印屏幕。数字印刷的海报看起来很棒，但将来我想将图像复制为图片的一部分。我发现复杂的图纸具有冥想性，我认为通过手动绘制它们可以实现有趣的效果。

在这个项目上花费的时间比我预期的要多得多，结果比一开始看起来要复杂得多。但这是尝试各种计算几何和算法问题的好方法。我为复杂性工作编写了数千行代码，这很具有讽刺意味，但是我很高兴它看起来很酷并且可以说明一切。

Source: https://habr.com/ru/post/undefined/