优生优育？Galapagos遗传算法学习杂谈

最近学习了一些Kangaroo 2的课程，其中有一课里讲到一个案例，要在曲线上取点来连接折线，并且希望每一段折线的长度相等，Dixon说用Kangaroo会比传统方法快很多，而且效果更好。

说到这里我猜想这个“传统方法”就是用Galapagos了。于是乎尝试了一下不同的解法，顺便整理了之前学习遗传算法的一些案例和心得。虽然这个算法并不常用，但是了解它的过程也算得上有趣。所有Grasshopper文件都可以在公众号后台回复“Galapagos案例”下载。

说起Galapagos我相信资深的gh用户并不会陌生，在Kangaroo内置之前，这一直是gh里一个“似乎比较高级”的运算器。它被以一个太平洋上的美丽小岛命名，这个岛也影响了影响了达尔文物种起源学说。

Galápagos Islands 科隆群岛

在gh的生态里，还有好几个Evolutionary Optimization Algorithms的插件支持遗传算法，而且相比自带的Galapagos只能优化单个目标，它们都支持多目标的优化。这些插件在本篇中暂且先掠过不表，说点基础的（毕竟Mac能装的插件不多

）。

双击Galapagos运算器图标，就可以打开这个界面，这个运算器包含着遗传算法和模拟退火算法，这些参数大多可以右键来选取一些预设值。在这些参数设置的右边，可以看到有一系列的链接，讲解了遗传算法的基本知识。

点开它们，你会发现来到了Grasshopper作者David Rutten的博客，具体也不须我细说，大部分都通俗易懂。好家伙，距离第一篇文章发布已经过去10年之久了，不知道应该说技术进步快还是慢了。除了遗传算法的文章，你也可以看到其他有趣的生活记录和一些启发性的文字。

i eat bugs for breakfast

比起模拟退火算法，遗传算法并不难理解，一句话概括就是用初代随机参数，经过筛选、交配和突变，迭代出接近优化目标的结果。颇有点优生优育的意思，谈到这个话题，作为UCL的学生其实是很敏感的。UCL 曾经是20 世纪初优生学运动的中心，几个大佬的学说在曾经影响颇深，从学术名词到学校大楼再到科学奖项。然而优生学被用作为种族主义服务，导致了之后很多骇人听闻的事件，产生了恶劣的影响。UCL也在今年年初做出了正式的道歉。

学校新闻截图

这些陈年旧事就不多考究了，说回正题，由于数据（数字）并没有人权，所以用遗传算法不会导致伦理问题

。相比它“高级感”的名字，它的实际效果并没有想象中那么厉害。遗传算法的计算并不快，而且只能尽可能地逼近优化目标，并不一定能得出理论上的最优解，这个在很多例子中可以体现。

两条曲线间找最近点（点击查看大图）

图中这是我几年前第一次接触到Galapagos时做的试验，在两条曲线间找最近点并且测量距离。当时觉得很有意思的一点是在gh中有一个自带的运算器可以求解出两条曲线间的最近点，正好可以和遗传算法的结果去作比较。最后结果也可以看出，Galapagos得出的结果要比CrvProx的更大一点。即使是一个简单的场景，只有两个参数，在小数点三位以后，遗传算法得到的并不是最优解。

相信对Galapagos感兴趣的朋友应该看过David的这个文档，里面有Blog中关于遗传算法的大部分内容，但是还有几篇并未包含，感兴趣的不妨随手看看。其中一篇地址：

https://ieatbugsforbreakfast.wordpress.com/2013/09/17/another-galapagos-tutorial/。主要是关于Fitness的定义和两篇教程，其中一篇有这样一个案例：对于指定的点云，找到一个最为拟合的圆。

点云拟合圆（点击查看大图）

这同样是一个有对应自带电池（Circle Fit）能解决的案例，这次有三个参数，感兴趣的朋友们也可以运行案例文件对比一下两个结果。在另一篇的教学里，讲了一个更加商业和实际的场景，关于进货、装载和盈利。虽然Galapagos只能针对单一目标进行优化，但是我们仍可以用一些数学方法来统一各个目标的参数范围并进行加权，最后合并成一个目标进行评估并优化，这个是在处理复杂场景时需要注意的问题。

寻找路径上的最优视野位置（点击查看大图）

另外一个网上的实际案例是关于展厅的一个问题，在一个展厅里有两个房间，房间的墙上有很多展品。假设游览路线已经确定，需要在路线上找到一点，要求在这一点上环顾四周能看到尽可能多的展品（奇怪的需求，感觉是要拍摄全景照片？）虽然听上去要求变多了，但其实这个问题只有一个参数（点在曲线上的位置），还是非常容易解决的。相比之下困难的是那些参数比较多的场景。

这里就可以说回开头的那个问题了：要在曲线上取点来连接折线，并且希望每一段折线的长度相等。听起来挺简单挺抽象，但是感觉也是面向制造去做形体优化时会遇到的问题（比如建筑幕墙？）如果要指定很多点的位置，可以用Gene Pool来取代大量的Slider。

但这么多参数不仅对运算速度产生了影响，而且如果参数恰好产生重复，即使后面的程序能去除重复，也会使得预期的线段数量和实际的不一样。经过实际测试，kangaroo几乎瞬间就能完成解算，而Galapagos不仅速度上非常慢，而且优化的结果仍有一些差距。如果你反复运算的话甚至可以发现有些时候得到的结果并不相同。为了优化这个程序，我规定了每个点产生的区间，这使得它们不至于太过随机，并且把输入参数数量和实际线段的数量的差值纳入评估，和原来线段长度的标准差相加之后一并作为优化对象。

值得一提的是，计算过程中我注意到最终的优化结果是和参数的精度挂钩的，我需要让参数在小数点后有更多位数，来改善我的优化结果。另一个问题是优化结果（每段线段的长度差异）在取标准差之后是一个非常小的数，我担心会由于计算精度的问题而无法收敛以及无法逼近最优结果，所以尝试乘了1000倍再去计算，也确实改善了最终的结果。

不过话说回来我们忙活了这么久，这个方法效果并不好。要想进一步改善，还得不忘初心

。我们需要的是等长的线段，所以在最开头就可以直接用Divide Distance去做，配合Seam来改变闭合曲线的端点位置。两个参数美滋滋，最终也确实能优化出完美的结果。相比之下，前面的方法就是吃力不讨好。

三种方法解决同一个问题

看完了Kangaroo和Galapagos的对比，其实也不妨尝试一下它们的协作。用ZombieSolver的话，将直接输出最终结果，不显示中间过程，这使得Kangaroo的计算的中间过程不会干扰Galapagos的解算。

ZombieSolver

在这个案例中，网架最高点需要达到一个特定高度，但同时需要保证网架每个单元等长，此时将Kangaroo的弹性，锚点以及载重结合起来，配合Galapagos就可以解决这个问题。

最后，本文出现的所有内容都可以在公众号后台回复“Galapagos案例”下载。这篇就唠这么多，讲完优生优育，以后有机会再聊聊物种多样性以及Generative Design~

感兴趣或者有更好的思路？

在公众号后台回复“UDM Club”，加入群聊和我们交流。