由鸟群和蚂蚁想到的——基于主体的仿真与群集智能的研究

[复制链接]

字体大小: 正常放大

aqua2001

930 主题	18 听众	4983 积分

升级 99.43%

TA的每日心情

	擦汗 2016-1-30 03:42

签到天数: 1 天

[LV.1]初来乍到

群组: 数学建模

群组: 趣味数学

群组: C 语言讨论组

群组: Matlab讨论组

群组: 2011年第一期数学建模

电梯直达

1^#

发表于 2006-10-20 17:52 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

由鸟群和蚂蚁想到的
--基于主体的仿真与群集智能的研究
郑毅吴斌
---- 生物学家探寻的问题

---- 数以百万计的蚂蚁如何组成一个群落？在蚁群中，单只蚂蚁的能力和智力如此简单，不论工蚁还是蚁后都不可能有足够的能力来指挥完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为。那么，它们是如何相互协调、分工、合作来完成这些任务呢？像蚁巢这样复杂结构的信息又是如何存储在这群蚂蚁当中呢？这些一直是困扰生物学家的问题。

---- 经济学家思考的问题

---- 当今处于全球化进程的社会中，各个厂商都是为了自己的最大利益生产、销售产品。没有任何单个厂商有足够的能力把握全局，但各大城市的物品却很少出现匮乏，总能达到供需平衡。厂商是在什么力量的支配下完成这些配给任务的？经济学家一直在思考这个问题。

---- 生态学家感兴趣的问题

---- 我们经常能够看到成群的鸟、鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食者。它们的群落规模动辄以十、百、千甚至万计，并且经常不存在一个统一的指挥者。它们是如何完成聚集、移动这些功能呢？生态学家对这个问题一直十分感兴趣。

基于主体的仿真

---- 传统解释方法

---- 您是否从上面的这些问题看出了什么？

---- 其实，这些看似毫不相关的问题都具有相同的特征，即相对简单的个体在没有一个集中控制的情况下，通过相互作用产生复杂的群体行为。它们都属于复杂系统研究的范围，各个领域的专家已经对这些问题有了长期、深入的研究，提出了一些解释并建立了一些模型。

---- 例如对于动物群体的聚集行为有2种数学的描述。第一种方法是在考虑到相同物种的相互吸引与排斥的同时，基于每个个体的随机移动利用欧拉连续方程(偏微分方程)进行描述，从而描述整个群体的密度。另外一种方法是基于个体的轨迹，利用拉格朗日方程对于个体的移动、速度等进行描述。

---- 基于主体的仿真及Boid模型

---- 然而随着计算能力的普及，我们可以不是利用方程，而是利用通过对个体行为准则的模拟、仿真进行建模，这种建模方式被称作基于主体的仿真(Agent Based Simulation)。这种建模方式强调群体中的每个个体的特性，更强调个体之间的相互交互作用。后者是许多传统建模方式所缺少的。并且这种建模常常能够对模型进行可视化的观察。

---- 例如，1986年Craig Reynolds提出了Boid (Bird-oid)模型用以模拟鸟类聚集飞行的行为。在这个模型中，每个个体的行为只和它周围邻近个体的行为有关，每个个体只需遵循以下3条规则:

避免碰撞(Collision Avoidance): 避免和邻近的个体相碰撞。
速度一致(Velocity Matching): 和邻近的个体的平均速度保持一致。
向中心聚集(Flock Centering): 向邻近个体的平均位置移动。
---- 鸟群中的每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但是随着时间的推移，这些初始处于随机状态的鸟通过自组织(self-organization)逐步聚集成一个个小的群落，并且以相同速度朝着相同方向飞行，然后几个小的群落又聚集成大的群落，大的群落可能又分散为一个个小的群落。这些行为和现实中的鸟类飞行的特性是一致的。

---- 我们可以看出鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的局部感知上面，而且并不存在一个集中的控制者。也就是说整个群体组织起来但却没有一个组织者，群体之间相互协调却没有一个协调者(organized without an organizer , coordinated without a coordinator)，这和前面我们对这些系统的整体感觉是一致的。

---- 基于主体的仿真在其他领域的应用

---- 基于主体的仿真在生物学、文化与人类学、政治学、经济学以及地理学等方面都有广泛的应用。例如可以用它来研究城市的形成、政党的产生、对股市进行模拟等等。

---- 基于主体的仿真与经济学相结合产生了基于主体的计算经济学(Agent-Based Computational Economics，ACE)，ACE将经济学看作交互的自主主体的演化系统，以计算的方法对这个系统进行研究。ACE研究者主要关心2个问题: 其一是在分布式的市场经济中没有自上而下的计划与控制的情况下，全局的秩序是如何产生的; 其二就是将模拟作为一个社会经济学的实验室，用来研究与检验某种社会经济结构对于个体行为与社会总体财富的影响。

---- 虽然基于主体的仿真的研究方法存在着缺陷，但是笔者认为，首先它为自然与社会复杂系统的研究提供了一种新的手段，它通过实验的方法而不是传统意义上的数学建模的方法来描述研究这些复杂系统，通过它建立起的模型更加直观，可视化程度更好，能够作为传统建模方式的补充。其次，不论建立的模型正确与否，它们的思想以及所建立的模型都已经对计算机工作者解决问题时候的思考方法产生了重要的影响。

群集智能的研究

---- 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群体(Swarm)指的是"一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解"。而所谓群集智能指的是"无智能的主体通过合作表现出智能行为的特性"。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。

---- 蚂蚁的故事

---- 蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下"信息素"(Pheromone)作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果2只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。

---- 蚁群优化算法

---- 受到蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群优化算法(Ant Colony Optimization，ACO)来解决计算机算法学中经典的"货郎担问题"--如果有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。

---- 在解决货郎担问题时，蚁群优化算法设计虚拟的"蚂蚁"将摸索不同路线，并留下会随时间逐渐消失的虚拟"信息素"。虚拟的"信息素"也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据"信息素较浓的路线更近"的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。

---- 蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路; 其次由于这种算法特有的解决方法，它已经被成功用于解决其他组合优化问题，例如图的着色(Graph Coloring)以及最短超串(Shortest Common Supersequence)等问题。

---- 将蚁群算法应用于电信路由有比较成功的例子，HP公司和英国电信公司在90年代中后期都开展了这方面的研究，他们应用了蚁群路由算法(Ant Colony Routing，ACR)。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项(Routing-Table Entries)。如果一只蚂蚁因为它经过了网络中堵塞的路段而导致了比较大的延迟，那么就对相应的表项做较小的增强，如果某条路段比较顺利，那么就对该表项做较大的增强。同时应用挥发机制，就可以做到系统信息的更新，从而使得那些过期的路由信息不再保留。这样，在当前最优路径出现阻塞时，ACR算法能很快找到另一条可替代的最优路径，从而提高网络的均衡性、网络负载量以及网络的利用率。

---- 聚类算法

---- 您是否观察过，蚂蚁能够将蚂蚁巢穴中的尸体聚集成几堆。如果一个地方已经有一些尸体的聚集，那么它将吸引蚂蚁将其余的尸体放在这里，越聚越多，最终形成几个较大的尸体的聚集堆。Deneubourg等人对上述现象提出了解释，并提出了基本模型(Basic Model，BM)，这种模型主要是基于对于单只蚂蚁拾起、放下物体的行为方式进行建模。一只随机移动的无负载蚂蚁在遇到一个物体时，周围与这个物体相同的物体越少，则拾起这个物体的概率越大; 一只随机移动的有负载蚂蚁如果周围的与所背负物体相同的物体越多，则放下这个物体的概率越大。这样可以保证不破坏大堆的物体，并且能够收集小堆的物体。实验表明，这种方法可以将相同种类的物体聚集在一起。

---- Lumer和Faieta将Deneubourg等人的BM推广应用到数据分析。主要思想是将待聚类数据初始随机散放在一个二维平面内，然后在这个平面上产生一些虚拟的"蚂蚁"。这些蚂蚁的行为和上面BM中所描述的蚂蚁行为相似。不同之处在于，它们不是观察当前所背负的物体与周围的物体是否相同，而是判断是否相似，这样最终能够将相似的数据聚为一类。

---- 多机器人协同工作

---- 在某些种类的蚂蚁中，工蚁能够合作搬运大的食物。通常情况下，一只蚂蚁找到食物之后，试图去移动它，若一段时间不能成功移动，那么它将通过接触或者化学信号来招募同伴。当一群蚂蚁试图移动大的食物，单只蚂蚁需要移动自身的位置或者改变移动的方向，直到物体能够被移动到巢穴的方向。研究表明，一群蚂蚁协作所能移动的物体重量要大于这个群体中单只蚂蚁单独所能移动的物体的重量之和。

---- Kube等人实现了多机器人系统，使得多机器人系统之间能够相互协作移动单个机器人所无法移动的箱子。如果箱子的移动没有最终目的地，那么每个机器人的能力设计就比较简单，只有3个感应器(Sensor)和2个动作器(Actuator)。3个感应器分别为目标感应器(Goal Sensor)用来探测箱子的位置; 机器人感应器(Robot Sensor)用来探测最近的机器人的有关信息; 障碍感应器(Obstacle Sensor)用来探测临近物体的信息; 2个动作器为左右2个轮子用来移动机器人。如果系统的目的是将箱子移动到一个最终目标位置，那么还需要加入一个用来探测目标位置的感应器。但是，整个系统中每个机器人都是比较简单的，通过一些简单的控制机制能够成功地解决僵滞(Stagnation)现象的发生，最终能够将箱子成功移动到以灯光为指示的目标位置。

---- 中科院计算所智能信息处理开放实验室对于利用蚁群算法解决货郎担问题已经开展了一定的研究，并且将蚁群的聚类算法已经应用到了文本、电信数据等聚类的领域。

---- 群集智能的研究还处于萌芽阶段，还存在很多问题。首先，它们都是概率算法，从数学上对于它们的正确性与可靠性的证明还是比较困难的，所做的工作也比较少。其次，这些算法都是专用的算法，一个算法只能解决某一类问题，各种算法之间的相似性很差。并且系统的高层次的行为是需要通过低层次的昆虫之间的简单行为交互涌现(Emerge)产生的。单个个体控制的简单并不意味着整个系统设计的简单，我们必须能够将高层次的复杂行为(也就是系统所要执行的功能，例如货郎担问题、数据聚类、搬运箱子)映射到低层次的简单个体的简单行为(例如信息素的遗留、物体的拾起与放下)上面，而这二者之间是存在较大差别的。并且我们在系统设计时也要保证多个个体简单行为的交互能够涌现出我们所希望看到的高层次的复杂行为。这可以说是群体智能中一个极为困难的问题。

基于主体的仿真存在的缺陷

---- 虽说基于主体的仿真已经取得了一定的成果，但是有一些研究者对于这种方法仍然存在一定质疑，主要有3点:

---- 首先，并不是总能从涌现的群体行为中推导出个体的行为;

---- 其次，真实生物个体如此复杂，以至于几乎不可能在一个仿真系统中完成复制;

---- 第三，简单的规则产生类似生命的群体行为并不能保证真实的生态系统的确遵循这些简单的规则。

群集智能的特点和优点

群体中相互合作的个体是分布的(Distributed)，这样更能够适应当前网络环境下的工作状态;
没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解;
可以不通过个体之间直接通信而是通过非直接通信(Stimergy)进行合作，这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里是十分小;
系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。
---- 因为具有这些优点，虽说群集智能的研究还处于初级阶段，并且存在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。

---- 基于主体的计算经济学可以看作是演化经济学、认知科学与计算机科学的结合(http://www.econ.iastate.edu/tesfatsi/ace.htm)

---- 信息素痕迹使得蚂蚁能够更加有效的寻找食物。2只蚂蚁同时离开巢穴(上图)，每只蚂蚁选择不同的路径并在该路径上留下信息素。