[译] Particle swarm optimization

题目：Particle swarm optimization for automatic creation of complex graphic characters
粒子群优化算法用于自动创建复杂图形字符
马里博尔大学，电气工程与计算机科学学院

摘要

受自然启发的算法是解决计算机科学和数学中最棘手问题的非常有前途的工具。 这些算法通常受到生物系统（如蜂群或鱼类）中展示的引人入胜的行为的启发。 到目前为止，这些算法已在许多实际应用中得到应用。 在本文中，我们提出了一种简单的粒子群优化方法，它可以自动创建复杂的二维图形字符。 该方法包括构造基本字符，使用粒子群优化算法优化基本字符的修改，最后从解决方案中生成图形字符。 我们通过创建简单的雪人展示了我们方法的有效性，但同时也详细概述了如何创建更复杂的角色。

简介

电脑游戏是互动娱乐行业中最赚钱的产品之一。在全球范围内，活跃用户的数量惊人，而这在很大程度上与年龄，性别和种族无关。大型在线多人游戏的出现进一步刺激了80年代以来的用户数量的积极趋势。当然，对提供更真实，令人振奋的用户体验的技术的需求也在不断增加，这在行业的许多不同层面上都不断需要创新和改进。除了硬件改进的重要性外，新软件的开发，新的交互可能性以及在市场上的牢固定位都需要专业知识和技能。在这些不同的发展方面，计算机科学，应用数学和复杂系统的理论研究也起着关键作用。我们的目标是特别针对后一个主题。

在过去的几十年中，计算机游戏中首先采用的方法和技术已在基于代理的计算系统研究中取得了显著成功[21]。 许多研究也将视频游戏本身视为一种艺术形式[8]。 在某些大学和研究机构中，计算机游戏已成为人们可以学习硕士或博士学位的主题。 然而，最值得注意的是，视频游戏对个人计算机的发展影响最大。 由于需求旺盛，个人计算机必须在RAM数量，处理器速度，显示分辨率和图形卡功能方面稳步提高，以跟上越来越复杂的游戏的步伐。

硬件的发展同时，也出现了用于解决最困难的现实问题的软件方法。 由于许多问题都是NP-hard问题[19]（NP-hard，指所有NP问题都能在多项式时间复杂度内归约到的问题，NP是指非确定性多项式non-deterministic polynomial，缩写NP），因此提出了许多启发式算法来近似解决此类问题。 这些启发式方法大多数都是从自然界中汲取灵感的。 算法的两个分支因与自然的紧密联系而特别出名，即进化算法（EA）[9]和群体智能算法（SI）[4]。 前者的灵感来自达尔文的“适者生存”原则[26]，而后者则取材于社会昆虫，成群的鸟和鱼群，以基于个体之间基本且非常简单的相互作用来执行复杂的动作 [38]。 两者的交叉点是进化博弈中集体行为的出现[28]。

通常，已经确定在计算机图形学中使用先进的，受自然启发的算法可能非常有用。该领域的应用包括[33,34]中的EA，其中将遗传算法引入了计算机图形学。后来，还应用了其他进化算法[14,2]，而最新的研究还包括用于多项式B样条曲面重构的遗传算法[18]，针对相同问题的粒子群优化[16]和粒子群优化。 Bézier表面重建[15]。例如，Gálvez和Iglesias [17]将萤火虫算法[10,11]用于多项式Bézier曲面参数化，这是计算机图形学中众所周知的问题。在这些进步的基础上，提出了创新的3D形状建模，其中，最初的3D模型群体得到了发展，可以在下一代中产生新颖的形状[40]。一个新的新兴领域，即基于搜索的程序性内容生成也在迅速发展，其目的是在游戏内容的自动生成中使用元启发法[36]。

由于许多游戏都使用大量不同的角色，因此我们在这里以一种新的方式解决了一个非常基本的问题。 特别是，我们探索了粒子群优化（PSO）对于自动创建复杂图形字符的有用性。 我们展示了如何使用经过修改的粒子群优化算法，使用一组预定义的构件来创建具有不同颜色和形状的2D角色图库。 对于可以工作的方法，该问题定义为约束满足问题（CSP）。 满足所有约束条件的每个候选解决方案都放置在画廊中，游戏设计师可以从中选择最佳角色。 作为示例，我们展示了2D雪人的生成，但是我们也概述了创建3D和更复杂字符的方法。

本文的其余部分的结构如下。 第2节回顾了约束满足问题的基础。 在第3节中，我们介绍了用于自动创建图形字符的粒子群优化算法。 实验和结果在第4节中介绍。我们以总结和未来发展的方向作了总结，并就自然启发式算法与智能设计和认知的相关性进行了更广泛的讨论[29]。

约束满足问题

大多数难解决的（NP-hard）真实世界问题都受到约束[19]。 这意味着，在执行各种变化算子后，并非在EA和SI中获得的所有候选解都有效。 通常，这些操作员会根据约束盲目行动，即这些操作员无法提供有效的解决方案。 约束满足问题（CSP）由其中三个分量<x,D,C>组成[30]。

每个域由其上下限确定； 每个约束包括一对<scope,relation>，其中作用域scope确定参与约束的变量，关系relation定义了一个关系，该关系必须有效才能满足所谓的可行性条件。 每个候选解的可行性条件由约束组成，可以表示为约束关联。 实际上，仅当满足所有约束条件时，可行性条件才成立。

自动创建图形字符

粒子群优化（PSO）是最早的群体智能算法之一，该算法是在1995年由肯尼迪和埃伯哈特（Eberhart）在国际神经网络会议上推出的[23]。 PSO受某些动物的社会觅食行为的启发，例如鸟类的植绒行为和鱼类的学习行为。 在这两种动物中，有些人具有更好的寻找食物的本能。 这些人认为，整个群体被引导到健身景观中更有希望的地区。

PSO是一种基于种群的算法，由粒子组成表示它们在n维搜索空间中的位置。 因此，变量Np限制了粒子总数。 粒子根据最佳粒子的位置朝着搜索空间中更有希望的区域移动，并以一定速度移动穿过搜索空间。 但是，该运动还取决于每个粒子的局部最佳位置，并且可以用数学方式表示。

在完成函数‘ init_partscles’（算法1）的初始化后，主循环开始，其中进行适应度函数的评估（‘evaluate_the_new_solution’函数），并根据方程式计算粒子的新位置。 公式（1）和（2）（‘generate_new_solution’功能）。 前者决定解的质量，而后者则将粒子移动到搜索空间的一个新的可能更好的区域[32,31]。 但是，在这两个函数之间，将执行用于保存局部最佳和全局最佳解决方案的代码。 注意，当满足终止条件（第3行）时，主循环终止。 通常，将代数MAX_GEN用于这些目的。 在过去的几年中，还提出了一些PSO变体粒子群优化还用于许多实际和现实应用中。 它被用于电磁应用[7]，垃圾邮件检测[43]，电力系统[1]等。 另一方面，PSO也是解决旅行商问题的一个很好的选择[39]，这是离散优化的问题。

应用粒子群优化

当约束条件为真时，字符的生成被定义为约束满足问题（CSP），可以找到适当的解决方案。 在此，图形字符被分为多个整体部分，这些部分被保存为一组部分。 每个部分可以用不同的颜色着色，并且可以包括各种笔触，即具有笔触宽度，线条样式和颜色的形状轮廓。 前者对角色的外观有影响，而后者对角色的形状有影响。 通常，自动生成图形字符的过程可以分为三个阶段：
基本角色的构造，
使用PSO算法优化基本字符的修改，
从解决方案中生成图形字符。

例如，本文应用了自动生成的雪人图形。 生成雪人图形的动机是，这些图形相对容易构建，而这一代设计师面临的所有问题都可以识别。 鉴于上述问题，本文其余部分将详细介绍雪人图形。

基本字符的构造
在第一阶段，构建基本角色，然后将其划分为不可分割的部分。 这些可以作为修改主题的部件构成一组部件，并具有相同的特征（例如，以相同的颜色着色）。 但是，此集合的大小取决于图形字符的复杂性。 图形字符越复杂，组成零件数量越多，形状也越复杂。

例如，图1中的一个雪人由20个部分和4个笔划组成，如下所示：下部，中间部分，上部，头部，帽子，左右手。 较大的部分（如下部，中部，上部和帽子）以各种厚度的笔划轮廓。 每只手都用掌心完成。 雪人船体中间部分的内部装有三个纽扣，而头部则由两只眼睛，鼻子和嘴巴组成。 用固定厚度的笔触修剪眼睛和鼻子，同时固定嘴巴。

优化基本字符的修改
可以使用不同的优化算法来执行此阶段。 在这项研究中，应用了PSO算法，其中基本字符的每次修改都表示为向量长度为n=24的Np，实值元素在区间。 元素表示定义部分的颜色，元组雪人四个更大部分的笔触。 在此，元组的偶数元素表示颜色，而奇数宽度。 颜色和宽度的映射是根据表1所示的编码方案实现的。注意，宽度的数量越多，笔触就越粗。

当可行性条件为true时，图形字符的自动生成是CSP问题，可以找到适当的解决方案。 使用适应度函数，将可行性条件表示为

使用描述的解决方案表示，该解决方案由等式（3）中表示的适应度函数评估，如算法1所示的原始PSO算法可以应用于图形字符的自动融合问题。

图形字符的生成
由PSO算法生成的解决方案描述了如何组合雪人部件的颜色和笔触以获得2D图形字符的独特视觉呈现。 但是，此描述与2D雪人的真实图形表示无关。 为了绘制真实的2D雪人图形，开发了使用Ruby编程语言的解释器[13]。 修改可以直接转换为从RMagick库[35,3]调用图形功能。 此外，Ruby允许执行任何处理其脚本中的雪人图形字符的操作。 由于解释器易于实现，因此其详细说明不在本文讨论范围之内。

实验与结果

我们实验工作的目的是证明所提出的用PSO算法自动生成图形2D角色的方法也可以应用于现实世界的视频游戏开发中。 为此，定义了一组图形化的雪人零件。 在此基础上，开发了PSO算法来解决雪人二维图形自动生成的约束满足问题。 当设计师提出的所有约束都得到满足时，就可以找到问题的解决方案。 最后，将适当的解决方案添加到雪人图形字符库中。

在实验中，从作者的Github存储库中提取了Ruby中经典PSO算法的实现[5]（https://github.com/clever-algorithms/CleverAlgorithms/blob/master/book/a_swarm/pso.tex）。 PSO算法的参数设置在实验过程中，如下所示。 速度值限制为，间隔种群大小设置为，最大速度设置为，压缩系数设置为。 作为终止条件，在找不到合适的解决方案的情况下，设置了第100代。 由于PSO算法收敛速度更快，因此应用了较小的总体数量。

正确生成的雪人图形字符的库如图2所示，从中可以观察到，通过PSO算法获得了许多不同的解决方案。 最好的解决方案是什么？ 此PSO算法的运行周期与经典随机算法（如EA和SI）的运行周期略有不同，在经典随机算法中，通常在满足特定终止条件后（即，在最大生成次数之后，最大 功能评估的数量等）。 然后，根据统计量评估最小值，最大值，平均值和标准偏差值，以评估更独立运行中的最佳解决方案。

此问题的特征是可以快速找到解决方案。 另一方面，这些解决方案本身并不是最佳的解决方案。 根据观察者的观点，每个适当的解决方案都可以视为最佳解决方案。 不幸的是，这种观点可能是非常主观的。 因此，所有适当的解决方案都将汇总到图库中，并在以后由普通用户（即视频游戏开发人员）进行评估。 视频游戏开发人员是此评估的唯一参考点，因为他们也知道生成的角色应该起作用的上下文。

讨论

电脑游戏是大众娱乐的核心，不仅推动硬件开发，而且推动软件开发的极限。 实际上，硬件和软件开发之间没有如此紧密的联系。 电子游戏正变得越来越复杂，显然有必要通过自然启发算法来协助这种发展。 显然，没有人造系统能够达到自然界所见的复杂性，因此，下一个最好的事情就是向自然界学习，以帮助进行人工设计。

本文对这一领域的主要贡献是帮助游戏设计师减轻了设计通常在历史，体育和战争游戏中出现的大型角色的艰巨任务。基于粒子群算法，提出了一种新的高效自动生成图形字符的方法，该算法能够生成任意复杂度的字符。提出的结果证实，我们在改善现有算法以及收集用于娱乐行业的复杂性科学知识方面正处于正确的道路。

在相关说明上，从事复杂系统，集体行为和认知工作的个人应该对此感兴趣，问题是，寻找最佳计算机游戏算法的工程师是否可以从群体智能中受益，可以想象一下，相同类型的研究工作可能有助于我们加深对智力和认知起源的理解吗？ [37,25,20]。尽管此时不可能精确地论证，但至少显然存在粒子群优化与其他受自然启发的算法之间的概念联系，以及智能的出现。实际上，这些算法的使用使人们得出一个结论，那就是我们正在利用智慧来创造新的智慧，并且可能正是沿着这些思路来激发新发现。