进化中的机器人Pt.1
“加入光荣的进化！”
引子
无数的科幻作品里都曾描绘这样一个场景：无穷无尽的外星种族冲向一道防线，而无论防御者如何强大，防线如何坚固，那些潮水般的冲锋的生物从不退缩。而每一种试图消灭它们的方法最终都会被它们的进化所解决。在最后的最后，它们总能踏平它们面前的一切。当然，不是人人都需要在充斥着亚空间邪祟的地方向着神圣泰拉祈祷，也不是人人都需要害怕自己的家旁边会不会有萨尔那加圣器。不过有一点值得注意，那就是我们的科技水平与技术实力已经能让我们做到类似的事情。与血肉造物相比，我们所创造的，能快速适应各类环境的机器人或许能成为开启崭新未来的钥匙。而最为宏大的梦想则是有一天他们能成为我们的“使徒”，代替我们遨游星海，作为我们文明的象征直到宇宙终结的那一天。
当然，千万年之后的事情与我们的关系并不大，而了解当前的算法实现则是非常有趣的。在这篇博客(以及之后的一系列博客)里，我会介绍一系列进化算法或者以更时髦的话来说“population based method”。 而在这篇博客里，我将介绍这一系列算法的起点，Multi-dimensional Archive of Phenotypic Elites即MAP-elites。到目前为止还没有一个通行的中文翻译，直译的话是多维优势特性档案算法，虽然有些拗口但是还算达意。这篇由我的导师的导师Jean-Baptiste Mouret和DL标杆式人物Jeff Clune共同创作的paper本意是为了使大量使用MAP-elites或受其启发的算法能有一个依据。同时也是一篇很好的入门作品，它回答了一个其实对整个人类来说都很重要的哲学问题：“Do we survive to learn, or we learn to survive?”.
注意 本文并不仅仅是MAP-elites的简单翻译介绍，还掺杂了一些个人理解。
缘起
当今的工业界和学界无时不刻不在使用优化算法，但是通行的优化算法，无论如何先进与高效，一般都只会给出一个最优解，或者一个对于最优解的可被数学表达的解释。长久以来，这样一个算法的构成都是足够的，或者说都是够用的，因为在ai的早期阶段或者说实验室环境里，环境是相对固定和单一的，这就使得一个简单的或者说单调的解法可以比较容易得得到较好的结果。但是本质上，所有通过这种方法得到的解都是过拟合的（此处暴论，就是一说）。不过其实这是可以通过简单逻辑推导的，假设当前系统的dimensionality为K，那么一定有真实场景为K+1，否则当前系统一定包含了所有可能出现的情况也就是成为了神谕机。假如用K种情况学习K+1种场景，那么它一定与用K+1种情况学习K种情况更对K种场景拟合。不过这个理论场景在绝大多数普通AI的应用中都不会遇到，因为只要是人工标定的边界那么对场景上来说就算超越其边界也没有什么大不了的，毕竟哪怕这只是个local optima但是只要够optimal那就足够好了。但是对真正cutting edge的场景来说，这一点点的过拟合就会导致整个场景的不可用。所以人们其实也有另一种思路，那就是完全放弃所谓的optima。这种方法单纯得在所定义的低维空间中搜寻最优解，而最终可以获得一系列的解。不过这样的算法并不能真正得解决问题，在低维空间中的查找效率低到令人发指，就算几百万次运算也不一定能够找到那些最优解法。而哪怕通过筛选算法也没有办法从根本上解决这个问题，因为低维的搜索对高维的信息是很难进行完整表述的。
而MAP-elites则通过对用户所提供的N维目标特征空间进行搜索来得到一个多元的，高效率，高性能的搜索。同时它还可以将整个特征空间的相互逻辑关系展示出来，有时候能通过这个方法得到对于特征空间整体的一些有趣信息。同时由于MAP-elites的结果会得到一系列多元化的高性能解，它还可以作为一系列相关算法的基石。在多年后的今天我们也可以确认这一点，MAP-elites至少在某些方法大大推动了人类科技的进步。
详谈
在展开详谈之前，我们首先明确两个概念，所有由fitting为目标的都可以视为optimization，即优化算法；而所有以探索为目标的则可以视为illumination，即启迪算法（霸气的起名，爱了）。而MAP-elites则是一个启迪优化算法，首先它通过大量的exploration来获得启迪，然后它在对每个特征点做fitting。在当时这类算法其实没有一个明确的名字，但是今天，他们被叫做massive parallelism，即巨量平行算法。不过更多关于这类算法的整体细节之后再谈，今天我们仅仅来了解一下MAP-elites本身的想法。
根据paper的原话MAP-elites其实非常得易于理解和实现，其实也确实如此。举个例子，假设一个二维空间内，以汽车的加速踏板和刹车踏板各位一个轴，希望得到最快的车速。假设选择每十分之一刻度为一个选项，那么MAP-elites则会产生100个不同的场景，最终会通过或是模拟，或是规定的数学公式最终算出每个场景的车速。很显而易见得，如果在一般正常情况下那么不碰刹车和油门到底的情况会成为最终的最优解。不过有趣的地方不止于此，假如我们添加一个不合常理的摩擦力系数，那么结果很有可能变成一个根据摩擦系数不同而出现的完全不同的多个解。假如我们再添加额外的例如道路面的标准差（用来表示凹凸不平的道路面）等等，那么我们能得到更多更加广泛的数据。这是我们在一般情况下完全无法想象的丰富可能。
从效率的角度来看，假如以低维启迪算法作为例子。以一个六足机器人为例，它可能有大概36个维度，而假如操控够细致，则每个维度大概会有120个~180个刻度。用传统的方法则会有1.5481398e+81个低维特征去计算，这大概需要…额…无穷无尽的时间。完全没有任何生产上面的价值去。但是对MAP-elites来说，我们可以非常方便得抽象出一个高维的数据出来。例如我导师的nature封面作品ITE就使用了机器人足尖与地面接触时间这一个特征。这个6维的archive大大减少了运算消耗。借助高效的GPU框架，我们甚至能够在几十分钟内就高效搜索到大量的优秀解，其中某些解法即使在今天（2022年中）也无法通过其他类型的算法来轻易获得。
当然这个算法也并非是十全十美的，它的阿克琉斯之踵就是所谓的“特征”。这是一个非常玄乎的概念，其实到现在为止我们依然不能真正得了解到如何选取正确的特征。大多数情况下，我们都会猜测什么样的特征比较具有代表性，然后进行实验来确定猜测这样的是否正确。总得来看未来可能会由meta learning一类的方法来选取可靠的特征值，或者对当前系统的数学原理进行更深入得探究来确定出一个通行的，可以被广泛使用的特征选择方法。
对比
在paper里，作者们主要对比了Novelty Search + Local Competition 和 MOLE两种类似的算法。不过其实可以这么看，在当时，根本没有其他算法有能力达到相近的结果，于是只能从原理上接近的算法来进行一个比较。哪怕时至今日，也只有巨量平行算法或者一些记忆计算算法能够做到类似的事情。而这两种被对比的算法所对应的实现细节就不在这里过多阐述了，前一种NS+LC代表的是传统的进化算法，通过惩罚过近的子体来实现搜索。而后者和MAP-elites一样是NS+LC的后序发展，不过同样的只是改变了惩罚函数以更倾向于搜索（指下一个子体必须对所有其他存在的个体都尽量远）。
在paper里，MAP-elites对NS+LC的优势主要有:
- 高效
- 计算更高效，这里指的是MAP-elites不需要对整个archive做nearest neighbour的操作，因为整个的算法设计是仅基于一个slot的。
- 存储更高效，这里说的是MAP-elites仅保存一个整体的archive而不会记忆每一个过往的solution。这是因为算法本身存在与feature space种就完全可以省略掉。
- 更稳定
- 这里指的是整体模型上的稳定，NS+LC由于需要参考其他子体，所以本身的计算会出现cycling即来回切换专注区域的问题，这回导致整个运算的时间结果无法被准确预判。
在paper里，MAP-elites对MOLE的优势主要有:
- 多元
- 这里的多元指的是MAP-elites不会被少数几个非常高性能的算法所主宰，相对的则会保留所有场景下最好的结果。这就可以让MAP-elites不会错过任何一个可能重要的新方法，因为它本身有可能并不是最高性能的那几个子体。但是它有可能会作为下一个超高性能子体的基石。
- 更稳定
- 具体理由和对NS+LC的一致
应用
从理论上来说，这个算法的应用是非常之多的，但是其实每一个应用都或多或少的调整了这个算法。毕竟MAP-elites的本意其实是一个理论算法的框架，本身的实现还是要依照不同的实际情况来处理的。
不过最直接的应用场景就是机器人方面，在复杂多变的真实世界里，只有掌握足够的知识才能生存下去，而在未来的未来，生存下去的elites又会持续学习（不过那是另一个故事了）。在之后介绍的ITE，我会着重聊一聊应用。
总结
这篇博客简单介绍了MAP-elites，由于我想要传教而当前没有任何关于这个算法的详细中文资料所以就个人转义了一些。我同时希望这篇博客能对这世界上某个角落的某些人提供帮助。
“Hail the Omnissiah! He is the God in the Machine, the Source of All Knowledge.”
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.