优化算法从鸟群、鱼群中借鉴了什么算法科普文

　　本文作者将与你分享：算法是如何借鉴大自然中的鸟群、鱼群等，来找寻最优解的，以及算法是不是可能自己设计算法。enjoy
　　生活工作中，很多时候都是在寻求最优解。
　　比如选择进入哪个行业去工作，怎样填写高考志愿，怎样找到自己深爱的伴侣，怎样在合适时机和地点购房，怎样在变幻莫测的股市中淘金，怎样在平衡客户需求和开发能力之间找到一个成本效益最佳的项目方案，等等。
　　这些待解决的问题，按理说，都有最优解。
　　而本文作者岳亚丁博士将告诉你，算法是如何借鉴大自然中的鸟群、鱼群等，来找寻最优解的，以及算法是不是可能自己设计算法。
　　文章要点：
　　哪些问题需要优化算法？
　　设计优化算法时，大自然给了我们什么启发
　　举个例子看优化算法到底啥样
　　摆脱对大自然的依赖，自创更好的优化算法
　　算法工程师与他的好友在公园观鱼。一群色彩斑斓的锦鲤在水面翻腾，追逐着游人们抛下的鱼食。
　　最优决策需要优化算法
　　：想什么呢？你不想喂它们吗？
　　：我在想，这些鱼游动的轨迹，与鱼群算法有多么的相似。
　　：这里也有算法？
　　：你看，它们时而捕食，时而群聚，时而追随，时而漫游，最终目的是尽快找到更多的食物，同时又避免可能的风险。鱼群算法，正是由此而来啊。
　　：你说的鱼群算法，是指仿生学吗？
　　：不是。仿生学主要是借鉴生物界的形态、结构、功能，设计出新的机械、装置、设备，比如人类受鱼类形状的启发，设计出水下航行的潜艇；或者通过研究鸟类肢体构造和飞行技能，来改进飞机的性能。
　　鱼群算法，则是受鱼群行为的启发，设计出的一种算法，可以用来找到问题的最优解。
　　：问题的最优解，是什么意思？
　　：我们生活和工作中，很多时候都是在寻求最优解。
　　比如说，选择进入哪个行业去工作，怎样填写高考志愿，怎样找到自己深爱的伴侣，怎样在合适时机和地点购房，怎样在变幻莫测的股市中淘金，怎样在平衡客户需求和开发能力之间找到一个成本效益最佳的项目方案，等等。这些待解决的问题，按理说，都有最优解。
　　：听起来，像是在做最优决策。
　　：是同一个意思。人是智慧生物，是解决问题的高手，有分析、综合、归纳、推理等能力，有寻找最优解的能力。
　　但是当面临的问题规模太大，复杂程度太高，特别是大社会、大工业中的问题，要找到最优解，哪怕记忆力再好、再聪明的人脑也吃不消了，靠直觉、拍脑袋做决策，已经不靠谱，还是需要用计算机来帮忙做这个事情，这时就需要优化算法了。
　　：计算机算数还是挺快的，听说都每秒多少亿次了，用它做优化，还没怎么听说。所以你让它模仿鱼群？
　　：计算机比较笨，只能按照我们人类的指令来做事情，但它最大的特点是算得快，我们可以利用这个特点来做更复杂的事情，包括优化。
　　勤能补拙嘛。我先通过一个简单例子，解释一下计算机是怎么做优化的，然后再说鱼群的事。
　　：好吧，你说说看。
　　一种简单的优化算法
　　：假设有一个人，在漆黑不见五指的夜里，独自登山，目标是山顶，你觉得他应该怎么做？
　　：山上不会有断崖、溪流、野兽吧？
　　：暂时假定没有这些危险东西。
　　：那就只能四处伸脚试试，感受一下，哪个方向是向上的，就往那个方向走呗。
　　：是的。这也正是计算机的最简单的优化算法之一。山顶就是待求的最优解。
　　从某个坐标点（东经多少度、北纬多少度）出发，算法开始之后，给计算机一个旁边紧挨着的新坐标点（相当于人往某个方向挪动一步），它算一下，是不是好些（人感觉是不是升高了一点），如果是，计算机就认定这个坐标点更好（人就往这个方向走一步），然后在这个点的基础上继续尝试；否则，就退回来，给它旁边另一个坐标点算一下（人往另一个方向挪动一步），再试。
　　就这样逐步尝试，走了很多步之后（所幸计算机“走”得挺快），如果发现四处挪动都是下降的方向，就算是到达山顶了。
　　：是够笨的，但是听起来，似乎还是有效的。
　　：对呀。
　　：不过，我觉得这里有一个问题。按照这样的方案，会不会走到了一个小山包的顶端，甚至一个小土堆上，就以为到山顶了，而实际上真正的山顶还远着呢？
　　：你说得对。小山包的顶端，只是一个局部的最优解，真正的山顶，才是一个全局的最优解。我们当然希望找到后者。上面说的算法还不是一个非常好的算法，它有可能找不到全局最优解。
　　：还有一个问题：如果能够通过鞋底感觉到地面的不平，有点倾斜，那就不需要前后左右地伸腿尝试，而只要按照鞋底感觉到的往上倾斜的方向走，这样岂不是更快？
　　：正是！如果待求问题与目标之间可以表示为一个数学公式，我们一般就可以求出哪个方向是往上倾斜的，然后让计算机沿着那个方向进行搜索，就更快捷了。
　　学术界把这种算法叫做“瞎子爬山法”。但是很多情况下，待求问题很复杂，没法写出一个数学式子，所以还是得四处伸脚尝试。
　　：这也是没有办法的办法了。
　　：但这样也好，可以处理更多类型的问题。
　　例如，学生成绩受很多因素影响，包括学生的年龄、性别、学习时长、健康程度、家庭背景等等，但到底是怎样影响的，我们可能写不出一个很精确的数学公式来（总不能瞎编一个“数学期考成绩年龄x平均每天学习小时数”吧）。
　　也没必要去写，可以通过“伸腿”去试，照样可以求得最优解，从而得知怎样才能获得更高分数。
　　：最后一个问题：如果真的有断崖、溪流这些东西，怎么办？
　　：现实世界中，它们当然对爬山人构成阻碍和威胁。计算机做的话，都是在虚拟世界中尝试，即使突然发现“踩空一脚”，也没什么大不了的，照样可以退回来，不影响后续的逐步搜索。
　　：这个瞎子爬山法，除了用来爬到山顶，还能用于更复杂的问题吗？比如说炒股，你前面也提到了的。
　　：瞎子爬山法难以胜任，其它优化算法恐怕也够呛，因为股市数据的随机性太强。当然，也可以试一试，只要能够把问题用数值表示出来。
　　炒股的情况虽然很复杂，但简略地讲，我们的目标，还是希望一段时间内的投资收益最大化；要寻找的，则是应该买哪几只股票，买多少股，持有多长时间，等等，这些待求的东西，都是可以表示成一组数值的，就跟上面爬山的情况那样，那里是用经纬度坐标值来表示的。
　　：你是说，把待求的东西表示为一组数（如经纬度、股票仓位），目标是另一个数（如海拔、收益），然后让优化算法来找出能使目标最大的一组数，对吗？
　　：是的，这就是优化算法的本质。
　　鸟群算法的优势
　　：比瞎子爬山法好的优化算法，有哪些？
　　：还有鱼群、鸟群、蜂群、蚁群、萤火虫、细菌、猴群、布谷鸟、蝙蝠、病毒、免疫系统、生物进化
　　人们从它们的行为得到启发，设计了优化算法，很多情况下，它们比瞎子爬山法好。
　　：嚯！开动物园了。
　　：也有非生物的，例如，和声、水滴、螺旋、星系、重力、量子
　　：够多的了。能举一个例子吗？我来感受一下比瞎子爬山法好在哪里。
　　：就说说鸟群算法吧，它比起鱼群算法更简单一点，也相对容易解释一点。
　　：好。
　　：鸟群算法里面，假设食物就像蚊虫，不均匀散落在空中，在某些点更密集。一群鸟在空中盘旋飞翔，想找到那个食物最集中的点，也就是全局最优点。
　　：有一只头鸟带领它们飞吗？
　　：不需要，假定每只鸟的能力都一样。每只鸟的下一步飞翔方向受到三股力量的影响：
　　第一，是当前的飞翔方向，即它自身有一定惯性，会有一股力量想拉着它沿着当前的方向飞。
　　第二，是它自己迄今为止经过的食物最密集的某个点，它对此还有记忆，觉得那个点有戏，于是也会受到那个点的牵引，尽管那个点不一定是全局最优点。
　　第三，假设鸟群之间是有通信联系的，随时保持沟通，对于整个鸟群迄今为止经过的食物最密集的某个点，每只鸟都是知道的，于是这只鸟也有点受那个点的牵引，尽管那个点也不一定是全局最优点。
　　：这样的假设，好像还是有道理的，但不知道是否符合实际情况。
　　：对实际情况，我们可能无法准确知道。但是设计一种算法，只要借鉴生物的一部分行为，只要效果好，也就可以了，不一定非要完全符合实际情况。
　　：然后呢，鸟群怎么飞？
　　：每只鸟受三股力量的牵引，在空中飞翔，会逐渐向最优点靠拢。
　　飞了一段时间后，估计差不多了，就盘点一下，所有鸟截止到最后时刻经过的食物最密集的某个点，就被认为是全局最优点。
　　：什么叫做“认为是全局最优点”？它不是真正的全局最优点吗？
　　：不能确保。这样找到的，仍然可能是局部最优点。要想找到全局最优点，还是需要别的更复杂算法，或者与其它算法结合进行。
　　例如，在爬山情况下，改为允许犯错，即使在局部最优点，伸腿尝试时发生下降，也听之任之，说不定就能慢慢走出局部最优点，重新找到通往真正山顶的路径。
　　：既然都不能确保找到全局最优点，那鸟群算法比瞎子爬山法好在哪里呢？
　　：很多情况下，鸟群算法可以更快地找到最优点。这一点，数学上可以证明，大量的实验和实际的工程应用，也可以证实。
　　可能是因为有一群鸟在行事，它们之间互相协作，集团智慧高于个体智慧嘛。
　　信天翁的搜索策略
　　：这样比较，好像不太公平哦。我也可以安排很多个瞎子同时爬山的。
　　：但是瞎子之间没有通信协作吧。如果允许瞎子之间有协作，那就又有点像是鸟群算法了。
　　：倒也是。不过，你能否找一个单打独斗的情况，一个瞎子，和一个别的什么，看他们做优化时，谁更厉害？
　　：是有一些依靠一个个体进行搜索的其它优化算法，只是很少看到哪份资料中比较过它们谁更厉害，我自己也没有实验过。
　　：你说说看吧。我总觉得瞎子爬山法还有点过于机械，希望还有更聪明的做法。
　　：如果旷野中的食物稀少，随机分布在一块很大的区域里，动物在搜寻它们时，并不一定是完全漫无目的地随机搜索，那样的效率是比较低的。
　　科学家们发现，海洋中的掠食者，如皱鳃鲨、黄鳍金枪鱼、蓝色马林、旗鱼，还有信天翁，它们的搜索方式，有一些很独特的特征，即：可能沿某个方向走出很远，才改变方向另搜。
　　这种搜索方式称为“列维飞行”，是根据法国数学家Lvy的名字命名的。在相同时间内，列维飞行找到的食物数量，很可能高于随机搜索。可能是千百万年的进化，使得他们学会了这种搜索方式。
　　（左图：随机搜索形成的轨迹右图：Levy飞行搜索形成的轨迹）
　　：哦，这倒有点意思。你们可以让计算机也学着这么搜索，快点找到最优解吗？
　　：已经有人做了。
　　当算法自己设计算法
　　：感觉只要是要求“最大”、“最小”、“最优”的问题，就可以用优化算法来做了，对吗？
　　：基本上可以这么说。其实，优化算法还可以帮我们更多的忙，它不仅授人以鱼，也能授人以渔。
　　：这是怎么说？
　　：就好像一个小学生在做数学题，因为掌握的方法不熟练，或者运用的方法不对，做得很慢，旁边坐着的老师，就会指点他改进方法。
　　：嗯，改进学习方法，这很重要，老师、家长、学生们都在说这个事。
　　：有一类优化算法，就是可以在一个算法正在工作的时候，随时指点这个工作的算法进行改进的。
　　：神奇。这回优化的是算法的好坏了。
　　：此外，我们还面临的一种情况是，已经有很多优化算法，告诉我们如何尽快到达山顶，或者解决别的问题。但优化算法太多了，为什么不用一个优化算法来帮我们选一个呢？
　　：是啊。我刚才还在琢磨，你说了一大堆优化算法，但是我真正动起手来，也不知道应该用哪一个。
　　我总不能每一个都去试一下，那样也太耗费时间了。如果有一个算法来帮我选出一种好的，就省事了。
　　：最后，脑洞不妨再开大一点：如果有一种优化算法，它作为母体，能够自行设计出一个优化算法，使得其在效率上优于所有人工设计出来的优化算法，岂不更妙？
　　：这有可能么？
　　：只要待设计的优化算法本身，能够用数值表示，就好办了。而且已经有一些这方面的研究，也有一些初步成果，似乎还不错。当然，这个过程还有很多困难，理论上也尚待突破。
　　：那以后都不用借鉴大自然、动物的行为，不需要那么费力地人工地构造那么多的优化算法了，甚至计算机科学家们都可以失业了，是不是？
　　：还没有那么激进。至少，用于设计优化算法的那些优化算法，我们称之为“元算法”的，还是需要人工设计的。元算法，是关于算法的算法。
　　：就不能再加多一层，再另外用一个算法来设计元算法，出现一种关于算法的算法的算法，甚至关于算法的算法的算法的算法？
　　：你还真问倒我了。学术界好像还没有人搞这么多层的，我也不清楚这样做，带来的好处有多大。再看看吧。
　　：我想起来了，打败世界围棋冠军的AlphaGo，据说是向人类学习，借鉴了几千万局人工对弈的棋谱。
　　后来的AlphaGoZero，摆脱对人类的模仿，左右手互搏，自学围棋，最后以100：0的战绩打败它的“前辈”。这个是不是关于算法的算法？
　　：有一点类似。
　　：想一想都很恐怖，感觉以后的算法会越来越厉害，它们可以自主设计出算法，比我们人类设计出来的算法更牛，说不定哪天会全面超过人类的智力。
　　：AI能否超越人类，是一个有争议的话题。今天我们没时间细聊了，留待下次吧。
　　：好的。
　　：还是得感谢大自然的馈赠，启发了人类设计出这么多的优化算法，可以用于解决很多的实际问题。就看我们能否很好地利用了。
　　：就像中医药人处在大自然的环境中，得了病怎么办，答案还是在大自然中。
　　文中图片来源于网络