遗传算法优化标签展示位置

背景

这篇文章本来想取名叫“遗传算法在数据可视化中的应用”,但是感觉太浮夸了,与我的人设不符,遂作罢。

来自nanoid的灵感

我第一次发现遗传算法可以应用到前端,是来自这条推,讲的是一个热心网友使用遗传算法优化 nanoid 这个库在 gzip 后的大小。

nanoid

推里提到的这篇文章详细介绍了他的优化过程,大概就是通过遗传算法不断演化,找到了一种字符串的排布方式,使得 nanoid 在 gzip 后比原来小了 2B。

虽然这件事看上去并没什么卵用,但是却成功激起了我对遗传算法的兴趣。

什么是遗传算法

遗传算法是基于进化生物学中的一些现象发展起来的,包括遗传、突变、自然选择、杂交等,通过模拟这个过程,将符合预期的一些特征通过“基因”保留下来,从而得到更加接近预期的结果。

遗传算法的流程大致为:

选择初始生命种群
评价种群中的个体适应度
选择下一个种群
交叉/突变

所以,应用遗传算法的场景需要满足一些前提条件:

  • 每个种群可以编码成一定的数据格式,否则将很难对结果进行评估;
  • 有一个确切的适应度函数来评价每个种群的好坏,方便后续的过滤和选择;
  • 通过一定的交叉/突变方法,可以保留一些符合预期的特性,否则就变成了大海捞针,无法通过进化获得更好的结果。

应用

刚好我就有一个这样的场景,需要在一些方框旁边合适的位置展示一些标签。

标签展示

方框的位置是会变的,所以我无法提前确定文字标签的位置,需要通过实时的计算来找到一个比较合适的展示方式。

问题分析

方框的位置和标签的内容是提前给定的,我们要做的是为每个文字标签找到一个合适的位置,让他们满足以下期望:

  • 尽量避免与别的标签或方框有重叠;
  • 尽量靠近关联的方框;
  • 在满足以上条件的前提下,优先展示在方框的左上角。

再看看上面提到的使用遗传算法的前提条件,看看是否满足:

  • 每个种群的数据编码:我们只需要将所有标签的坐标当成种群的属性即可;
  • 适应度评价函数:我们要把上面提到的期望转换成代码实现,用来评价当前种群的优劣,理论上可行,具体实现后面再说;
  • 优秀特性的保留:由于标签的位置是相互影响的,所以当我们选择保留一部分标签的坐标时,他们之间的相对位置就固定了,在后面的种群中,这一部分结果就可以得到保留,从而向预期靠近。

适应度的评价

现在我们的重点就是如何来实现评价适应度的方法了。

  1. 避免标签与别的标签或方框有重叠。

    我们只需要计算每个标签与其他标签或方框的交叉面积,交叉面积越小,就越符合预期,所以可以将交叉面积的值作为评价的一部分。

  2. 尽量靠近关联的方框。

    计算标签与关联的方框之间的距离,距离越小,越符合预期。

  3. 尽量展示在关联方框的左上角。

    这个简单,判断一下当前标签位置离左上角的距离即可。

评价

所以我最终使用的评价方法为:

k1 * 重叠面积 + k2 * 标签和方框的间距 + k3 * 标签和方框左上角的距离

其中 k1、k2、k3 是权重系数,可以根据需要调整。最后分数越小的种群,越符合预期。

初始种群的选择

接下来,我们要选择一个合适的初始种群,即最初的状态下,标签放在什么位置。

最初为了省事,我直接将标签放在每个方框的正中央,然后让他们自己变异,移动到合适的位置去。后来发现,从正中间开始变异,会导致前期的很多次变异都无法得到有明显优势的种群,白白浪费了很多次迭代。

而在前端与用户交互的场景下,JavaScript 的计算时间是很有限的,所以要想办法节省掉这些时间。

于是我改成了直接将标签放在每个方框的左上角。

初始种群

变异

变异包括交叉和突变两种方式。局部突变可以产生新的特性,有几率得到更优解;交叉则可以更快地结合两个不同种群的优点,当然也有可能是缺点,但那样会被我们的选择方法淘汰,所以最终留下来的应该是优点。

这里我简单地定义了一下变异的方法:突变就是让标签随机地做一个小范围移动;交叉就是把标签分成两组,交换两个种群的其中半段。

优化

上面提到,为了快速得到有效的变异,我把标签的初始位置放到了每个方框的左上角。

这又导致了一个新的问题,如果方框过于拥挤,我们必须要把标签放到方框右侧或是下方,这种方式的弊端就体现出来了,我们需要很多次变异才有可能让标签移到右下方去。

我首先想到的方法是增加初始种群,对每个标签创建4个初始状态,分别定位到方框的四个角上。但是这样会导致种群的数量变成 4n4^n ,效率大大降低。

利用变异,我找到了一个更简单的方法,增加一种新的突变方式——翻转。变异时有一定几率将标签翻转到方框的另一侧,横向或者纵向翻转,既可以满足位置移动,又避免了大量的无效移动。

翻转

在这样的条件下,只需100个种群构成初始状态,经历100个迭代就可以找到一个不错的解了,完全不影响用户体验。

最终效果见 https://intellilab.github.io/force/

对比

暴力搜索

暴力搜索在这个场景下无异于大海捞针,解的空间过于复杂,而且缺乏一个标准来评判最优的解,这会导致搜索的效率低下,而且无法快速收敛,不知道何时可以停下来。

而使用遗传算法,则可以快速地找到一个良好的解,性价比很高。

d3-force

这个问题我曾经尝试过使用和 d3-force 类似的方法,最后以失败告终,因为它更适合处理多个点之间的互相影响。而对于有形状的方框,就复杂得多了,我们甚至需要一个物理引擎才能良好地模拟力的作用。

然而这么复杂的场景,遇到遗传算法就迎刃而解了。

总结

遗传算法的思想比较简单,通过随机的方法,加上适当的评价函数,可以快速地找到较优解。

但是也有一些不足,比如种群数目过大或者种群内部的数据过于复杂,会造成性能问题;评价函数的设计比较麻烦,稍有不慎就会导致筛选出来的结果不符合预期。

总的来看,遗传算法有倾向性的求解方式,很适合一些数据可视化的场景。


© 2020