Riders on a swarm 蚁群背上的骑士——用群体的方法解决人工智能问题

本帖最后由 lilywizardry 于 2010-8-15 13:53 编辑 Artificial intelligence人工智能 Riders on a swarm 蚁群背上的骑士——用群体的方法解决人工智能问题 Mimicking the behaviour of ants, bees and birds started as a poor man's version of artificial intelligence. It may, though, be the key to the real thing 在人工智能领域，模拟蚂蚁、蜜蜂和鸟类的行为刚兴起时被当做是笨人做的事情。但是它可能是真正能解决问题的关键。 Aug 12th 2010 | ROME ONE of the bugaboos that authors of science fiction sometimes use to scare their human readers is the idea that ants may develop intelligence and take over the Earth. The purposeful collective activity of ants and other social insects does, indeed, look intelligent on the surface. An illusion, presumably. But it might be a good enough illusion for computer scientists to exploit. The search for artificial intelligence modelled on human brains has been a dismal failure. AI based on ant behaviour, though, is having some success. 科幻小说家们常用来吓唬读者的奇谈怪论之一就是，蚂蚁会变得有智慧并且代替人类接管地球。蚂蚁和其他社会性昆虫有目的的集体活动表面上看起来确实是有智慧的。可能这只是一个假象。但是这个假象已经足够让计算机科学家利用了。以人类大脑为模型的人工智能一直没什么进展。而以蚂蚁行为为基础的人工智能正在取得一些成功。 Ants first captured the attention of software engineers in the early 1990s. A single ant cannot do much on its own, but the colony as a whole solves complex problems such as building a sophisticated nest, maintaining it and filling it with food. That rang a bell with people like Marco Dorigo, who is now a researcher at the Free University of Brussels and was one of the founders of a field that has become known as swarm intelligence. 二十世纪九十年代早期，蚂蚁首次引起了软件工程师的注意。仅仅一只蚂蚁干不了什么，但是一群蚂蚁作为一个整体就可以解决一些复杂的问题，比如说建造并维护一个精致复杂的巢穴并在里面储存食物。这引发了一些人的灵感，比如说Marco Dorigo。Marco Dorigo现在是布鲁塞尔自由大学一名研究员，也是众所周知的蚁群智能领域的鼻祖之一。 In particular, Dr Dorigo was interested to learn that ants are good at choosing the shortest possible route between a food source and their nest. This is reminiscent of a classic computational conundrum, the travelling-salesman problem. Given a list of cities and their distances apart, the salesman must find the shortest route needed to visit each city once. As the number of cities grows, the problem gets more complicated. A computer trying to solve it will take longer and longer, and suck in more and more processing power. The reason the travelling-salesman problem is so interesting is that many other complex problems, including designing silicon chips and assembling DNA sequences, ultimately come down to a modified version of it. Dorigo博士尤其饶有兴趣的了解到，蚂蚁擅长于在食物所在地和巢穴之间选择最短的可能路线。这是人们想起一个经典的计算机难题——旅行商问题（旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本）。给出一组城市和它们之间的距离，推销员必须找出最短的路线一次就能够访问每个城市。随着城市数量的增长，这个问题变得更复杂了。计算机需要越来越长的时间和越来越强大的处理能力解决这个问题。旅行商问题之所以这么有趣是因为，许多其他的复杂问题，包括芯片的设计和DNA序列的装配顺序最终都要归结于这个问题的解决。 Ants solve their own version using chemical signals called pheromones. When an ant finds food, she takes it back to the nest, leaving behind a pheromone trail that will attract others. The more ants that follow the trail, the stronger it becomes. The pheromones evaporate quickly, however, so once all the food has been collected, the trail soon goes cold. Moreover, this rapid evaporation means long trails are less attractive than short ones, all else being equal. Pheromones thus amplify the limited intelligence of the individual ants into something more powerful. 蚂蚁用一种叫做信息素的化学物质来解决它们自己的"旅行商问题"。当一只蚂蚁找到了食物，它把食物带回巢穴，并且在路上留下信息素以吸引其他的蚂蚁。如此，遵循这条路径的蚂蚁越多，信息素信号就变得越强。然而信息素挥发地很快，所以一旦食物搬运完毕，这条信息素路径就不复存在了。更有意义的是，这种快速挥发意味着长路线没有短路线更具有吸引力。这样信息素就把单个蚂蚁有限的智慧放大了，使得其更有力量。 Hivemind 集成 In 1992 Dr Dorigo and his group began developing Ant Colony Optimisation (ACO), an algorithm that looks for solutions to a problem by simulating a group of ants wandering over an area and laying down pheromones. ACO proved good at solving travelling-salesman-type problems. Since then it has grown into a whole family of algorithms, which have been applied to many practical questions. 1992年Dorigo博士和他的团队开始开发蚁群最优法（ACO）。这是一种靠对在一定区域内活动并且留下信息素的蚁群的模拟来寻找解决问题的办法的算法。ACO被证明在解决旅行商问题上有很好的表现。从那时开始这个算法就发展成为了一整套的算法，用来解决许多实际的问题。 Its most successful application is in logistics. Migros, a Swiss supermarket chain, and Barilla, Italy's leading pasta-maker, both manage their daily deliveries from central warehouses to local retailers using AntRoute. This is a piece of software developed by AntOptima, a spin-off from the Dalle Molle Institute for Artificial Intelligence in Lugano (IDSIA), one of Europe's leading centres for swarm intelligence. Every morning the software's "ants" calculate the best routes and delivery sequences, depending on the quantity of cargo, its destinations, delivery windows and available lorries. According to Luca Gambardella, the director of both IDSIA and AntOptima, it takes 15 minutes to produce a delivery plan for 1,200 trucks, even though the plan changes almost every day. 它在物流上的应用最为成功。瑞士的一家连锁超市Migros和意大利的顶级面条机生产商Barilla都用AntRoute软件来管理他们从中心仓库到地方零售店的日常运输。这款软件是用卢加诺Dalle Molle 人工智能研究所（IDSIA，是瑞士南部应用大学下属的一个研究所）的副产品——AntOptima开发的。这个研究所是欧洲研究蚁群智能的顶尖研究所。每天早上这款软件都会根据货物的数量、目的地、投递点和可用的货车数量来计算出最佳的路线和投递顺序。据IDSIA 和AntOptima的主管人称，软件会花15分钟来为1200辆货车找出一个运送路线，即使这个路线几乎每天都会变。 Ant-like algorithms have also been applied to the problem of routing information through communication networks. Dr Dorigo and Gianni Di Caro, another researcher at IDSIA, have developed AntNet, a routing protocol in which packets of information hop from node to node, leaving a trace that signals the "quality" of their trip as they do so. Other packets sniff the trails thus created and choose accordingly. In computer simulations and tests on small-scale networks, AntNet has been shown to outperform existing routing protocols. It is better able to adapt to changed conditions (for example, increased traffic) and has a more robust resistance to node failures. According to Dr Di Caro, many large companies in the routing business have shown interest in AntNet, but using it would require the replacement of existing hardware, at huge cost. Ant routing looks promising, however, for ad hoc mobile networks like those used by the armed forces and civil-protection agencies. 蚁群模拟算法也被用于解决通过通信网络的路线信息问题。Dorigo博士和IDSIA的另外一个研究员Gianni Di Caro开发了一个路线解决方案AntNet。在这个方案里，信息包从一个节点跳到另一个节点，留下那些可以表明它们运动路径的特征信号，其他的信息包"嗅到"这些信号就可以采取相应的路径了。在小规模网络的计算机模拟和测试中，AntNet比现有的路线解决方案表现的都要好。它能更好的适应变化的条件（比如说流量的增大），并且对节点失效有更强的抵抗力。据Di Caro博士称，许多需要安排路线的大公司都对AntNet感兴趣，但是使用这款软件需要替换现有的硬件，这是一笔巨大的花费。然而对那些像正规军和民防机构所使用的特设移动网络来说，蚁群路线算法看起来还是很有应用前景的。 Routing, of both bytes and lorries, is what mathematicians call a discrete problem, with a fixed, albeit large, number of solutions. For continuous problems, with a potentially infinite number of solutions—such as finding the best shape for an aeroplane wing—another type of swarm intelligence works better. Particle swarm optimisation (PSO), which was invented by James Kennedy and Russell Eberhart in the mid 1990s, is inspired more by birds than by insects. When you place a bird feeder on your balcony, it may take some time for the first bird to find it, but from that moment many others will soon flock around. PSO algorithms try to recreate this effect. Artificial birds fly around randomly, but keep an eye on the others and always follow the one that is closest to "food". There are now about 650 tested applications of PSO, ranging from image and video analysis to antenna design, from diagnostic systems in medicine to fault detection in industrial machines. 无论是网络信息传递过程中的路线还是物流路线，在数学上都称之为离散问题——尽管复杂但是解决问题的方案数量是有限的。与之相对的连续问题则有理论上无穷无尽的解决方案——像是为机翼找出最好的形状——总能找到其他效果更好的蚁群智能算法。James Kennedy和Russell Eberhart在二十世纪九十年代中期受鸟类和昆虫的启发发明了粒子群算法（PSO，见文章结尾注释1）。当你在你家的阳台上放上鸟食，一段时间以后才会有第一只鸟发现它，但是随后很快就会有很多鸟蜂拥而至。PSO力图去模拟这个过程。计算机收索过程中的"人造鸟"随机运动，但是总是盯紧并且跟随那只靠"食物"最近的"鸟"。现在有大约650种经过测试的PSO应用软件，从图像和视频的分析到天线的设计，从医疗诊断系统到工业生产中机器的故障诊断。 Digital ants and birds, then, are good at thinking up solutions to problems, but Dr Dorigo is now working on something that can act as well as think: robots. A swarm of small, cheap robots can achieve through co-operation the same results as individual big, expensive robots—and with more flexibility and robustness; if one robot goes down, the swarm keeps going. Later this summer, he will be ready to demonstrate his "Swarmanoid" project. This is based on three sorts of small, simple robot, each with a different function, that co-operate in exploring an environment. Eye-bots take a look around and locate interesting objects. Foot-bots then give hand-bots a ride to places identified by the eye-bots. The hand-bots pick up the objects of interest. And they all run home. 数字世界的"蚂蚁"和"鸟"能很好的找出解决问题的办法，但是Dorigo博士现在致力于研究机器人——它能思考也能行动。一群小的廉价的机器人通过协同合作不但可以取得和一个大型的昂贵的机器人同样的效果，而且还更具有灵活性和耐用性。如果一个机器人坏了，其他的机器人仍可以照常工作。今年夏天晚些时候他将展示他的"Swarmanoid"项目——三种精小简单而各自具有不同功能的机器人通过合作一通探索外在环境。具有视觉功能的机器人会环顾四周并且对感兴趣的目标定位，具有移动功能的机器人把具有操作功能的机器人移动到目的地，然后后者捡起目标物体，最后它们一起返回。 All this is done without any pre-existing plan or central co-ordination. It relies on interactions between individual robots. According to Dr Dorigo, bot-swarms like this could be used for surveillance and rescue—for example, locating survivors and retrieving valuable goods during a fire. 这个过程中的所有行为都没有预先计划或者由控制中心协调控制。它依赖于单个机器人之间的相互作用。Dorigo博士说，这种协同合作的机器人群可以用于监视和救援——比如说定位幸存者或在火灾中抢救一些有价值的物品。 Intellidance 智能舞蹈 Swarmanoid robots may not much resemble the creatures that originally inspired the field, but insects continue to give programmers ideas. Dr Dorigo's group has, for instance, developed a system to allow robots to detect when a swarm member is malfunctioning. This was inspired by the way some fireflies synchronise their light emissions so that entire trees flash on and off. The robots do the same, and if one light goes out of synch because of a malfunction the other bots can react quickly, either isolating the maverick so that it cannot cause trouble, or calling back to base to have it withdrawn. 机器人群或许并不能像人们兴奋期待的那样很好的模仿人类，但是可爱的昆虫们可以继续为程序员提供灵感。比如说Dorigo博士的团队开发了一个系统可以让机器人群检测到发生故障的成员。一些萤火虫群可以同步它们发光的步调，使整体能够整齐划一的时灭时亮。程序员从此得到启发，是机器人群可以做相同的事情——如果其中一个机器人因为故障不与整体协调了，那么其他机器人就能做出快速反应，要么把这个故障机器人隔离使其不能引起其他麻烦，要么将它从系统中撤掉。 All of which is encouraging. But anyone who is really interested in the question of artificial intelligence cannot help but go back to the human mind and wonder what is going on there—and there are those who think that, far from being an illusion of intelligence, what Dr Dorigo and his fellows have stumbled across may be a good analogue of the process that underlies the real thing. 所有这些听起来都令人振奋鼓舞。但是任何对人工智能真正感兴趣的人都知道这些无能为力，还是要返回到人脑去寻找真理——从这里才能制造出真正的人工智能，而不仅仅是Dorigo博士和他的团队偶然发现的靠模拟昆虫得出的人工智能；从这里才能最好地模拟真正的智能过程。 For example, according to Vito Trianni of the Institute of Cognitive Sciences and Technologies, in Rome, the way bees select nesting sites is strikingly like what happens in the brain. Scout bees explore an area in search of suitable sites. When they discover a good location, they return to the nest and perform a waggle dance (similar to the one used to indicate patches of nectar-rich flowers) to recruit other scouts. The higher the perceived quality of the site, the longer the dance and the stronger the recruitment, until enough scouts have been recruited and the rest of the swarm follows. Substitute nerve cells for bees and electric activity for waggle dances, and you have a good description of what happens when a stimulus produces a response in the brain. 比如说，据意大利罗马国家科研委员会认知科学技术研究所的Vito Trianni称，蜜蜂选择筑巢地点的方式与大脑中发生的事情十分相似。侦查蜂寻找合适筑巢的地点。当它们发现了一个好的地点，就飞回蜂巢跳摇摆舞（一种类似于用来指示富含花蜜的花丛地点的舞蹈）来告知其他的侦查蜂。这个地点越好，侦查蜂跳舞的时间久越长，得知这个信息的蜜蜂就越多，直到足够的侦查蜂知道了这个信息并且其他蜜蜂也跟随它们而去的时候才停止跳舞。如果把神经细胞比作蜜蜂，把神经细胞的点位运动比作用来传递信息的摇摆舞，你就可以很好的描述当大脑受刺激后产生反应的过程了。 Proponents of so-called swarm cognition, like Dr Trianni, think the brain might work like a swarm of nerve cells, with no top-down co-ordination. Even complex cognitive functions, such as abstract reasoning and consciousness, they suggest, might simply emerge from local interactions of nerve cells doing their waggle dances. Those who speak of intellectual buzz, then, might be using a metaphor which is more apt than they realise. 这种群体认知理论的支持者们像Trianni博士一样，认为神经细胞作为地位平等的群体一同工作，不存在至上而下的调节。他们还认为，即使像抽象的推理和意识这些复杂的认知功能，可能也只是局部神经细胞靠跳"摇摆舞"相互作用所产生的结果。那些谈论人类智力活动的人或许可以找到一个比他们意识到的更确切的比方来形容这个过程了。 注释： 1.PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为"粒子"。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索 PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。