群体智能苍松教学

1、群体智能群体智能作为一个新兴领域，自从20世纪80年代出现以来，引起了多个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领域。有单个复杂个体完成的任务可有大量简单的个体组成的群体合作完成，而后者往往更具有健壮性、灵活性和经济上的优势。群体智能利用群体优势，在没有集中控制，不提供全局模式的前提下，为寻找复杂问题解决方案提供新的思路。对群体智能的定义进行扩展，普遍意义上有以下几种理解。一是由一组简单智能体（agent）涌现出来的集体智能（collective intelligence），以蚁群优化算法（ant colony optimization）和蚂蚁聚类算

2、法等为代表；二是把群体中的成员看做粒子，而不是智能体，以粒子群优化算法（particle swarm optimization）为代表。群体智能是对生物群体的一种软仿生，即有别于传统的对生物个体结构的仿生。可以将个体看成是非常简单和单一的，也可以让他们拥有学习的能力，来解决具体的问题。第 i 条 研究现状1. 群体算法研究 对群体智能的研究起源于对以蚂蚁、蜜蜂等为代表的社会性昆虫的群体行为的研究，大都是从某一种有大量个体表现出来的群体行为出发，从它们的群体行为中提取模型，为这些行为建立一些规则，从而提出算法应用于解决实际问题。目前国内外研究的比较多而且比较成熟的算法有蚂蚁优化算法、蚂蚁聚类算法

3、、粒子群优化算法，以及对蚂蚁分工的研究。如下表：群体行为算法应用蚁群觅食蚂蚁优化算法首先用来解决tsp问题，之后推广到各种组合优化问题；实际应用与网络路由的优化等。蚂蚁公墓形成、幼虫分类ls算法、kls算法数据分析、图的划分蚂蚁分工任务分配算法任务分配群鸟觅食粒子优化算法函数优化问题、神经网络训练1.1 蚂蚁优化算法蚂蚁算法（ant algorithm）是一种新的仿生类算法，它吸收了生物世界中蚂蚁的行为特性。昆虫学家发现，蚂蚁与蚂蚁之间有一种非常重要的通信媒介，即它们在移运过程中所释放的一种特有的分泌物信息素（phenomenon），蚂蚁可以借此察觉彼此之间的状况并影响自己的行为。若一批蚂蚁出

4、发去寻找食物，当某些路径上走过的蚂蚁较少时，其信息素数量也就相应较少，且随着时间而逐渐挥发，信息素强度会越来越弱，后来蚂蚁选择这些路径的可能性就会越来越小，而当某些路径上走过的蚂蚁较多时，信息素数量就会越来越多，以致于强度越来越大，因此能吸引更多的蚂蚁选择该路径。通过这种内在的搜索机制，便逐渐形成了一条最佳路线。 蚂蚁算法目前已经被扩展应用到许多问题领域中，并表现出相当好的性能，如经典的旅行商问题（tsp），二次分配问题（qap）以及约束平面选址问题、多目标tsp、交通分配等问题中都取得了较好的成效。1.2 蚂蚁聚类算法某些种类的蚂蚁在打扫巢穴时，聚类尸体形成一个“公墓”，或者将它们的幼虫分成

5、几堆。现在还无法充分解释这种行为，但是有一个建大的模型，可以解释蚂蚁聚类或者分类中的某些特征。在该模型中，空间中随机运动的个体（如蚂蚁）根据局部信息拿起或者放下某种物体（蚂蚁尸体或者幼虫）。这个模型可以应用在数据分析上：具有不同属性的对象可被视为要分类的物体。由此受到启发得到蚂蚁分类算法，并且应用于数据挖掘的分类和聚类上。1.3 粒子群优化算法粒子群优化算法（pso）是由james kennedy 博士和r.c.eberhart博士于1995年提出的。该算法源于对鸟群、鱼群觅食行为的模拟。在pso中，首先初始化一群随机粒子（随机解），然后通过迭代寻找最优解。在每一次的迭代中，粒子通过跟踪两个极

6、值来更新自己的速度和位置。第一个就是粒子本身所找到的最优解，这个解叫做个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值，另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。pso算法简单易实现，不需要调整很多参数，主要应用于神经网络的训练、函数的优化问题等。2. 群体机器人群体智能最早笨哦用在细胞机器人系统的描述中，其中多个简单的机器人通过与近邻的交互产生一种自组织的模式。对蚂蚁、蜜蜂的分工、搬运、筑巢等行为的研究中，发现了社会性昆虫的自组织和自组装能力。以此为理论基础，展开了群体机器人自组织、自组装以及协作的研究。1.1 自组织、自组

7、装社会性昆虫的巢穴结构往往复杂而精巧。蚂蚁筑巢过程中，与环境的交互分 2 种：连续的和离散的。离散的交互是指刺激因素类别不同，因而产生不同的反应；连续的交互是指由于刺激因素的量的不同而产生不同的反应。基于离散的交互和自组织提出一个模型，在这个模型中，个体在三维空间运动，依据它的周围空间的砖块的排布决定是否在当前位置放下背负的砖块，利用该模型实验的结果显示可以产生非常类似黄蜂巢穴的结构。自组装的机器人系统可以借鉴这个筑巢模型。 swarm-bots是由布鲁塞尔自由大学 iridia 实验室 macro dorigo 领导的一个项目，该项目是为了研究一种设计和实现自组织和自组装的人工物的新方法。该

8、项目的具体目标是建立一个由多个比较简单的，类似昆虫的机器人的群体swarm-bots。这些机器人使用相对便宜的构件，具有自组织和自组装能力来适应环境。1.2 多机器人协作多机器人系统是一个松散结构的分布式系统 , 其优点在于既可独立工作 ,又可在需要时进行协作. 在任务未知的环境中 ,确定有哪些任务需要多个机 器人协作完成是一个重要而艰巨的问题. 受到蚁群算法的启发,我们想到,可以将“外激励”的方法引入多机器人系统中,由机器人在工作过程中赋予不同 的任务以不同的激素 ,通过对难度较大的工作设置、较大的激素浓度以吸引其它机器人来进行协作。第 ii 条 蚂蚁算法1. 原理蚁群算法的基础是蚂蚁、蜜蜂

9、等昆虫通过一种“外激励”的间接联系方式来协调群体之间的运动，蚂蚁在运动与工作中，如搬运实物的途中，会在自己所经过的路径上留下一种激素。而这种激素会影响到同一蚁群中其他蚂蚁的运动。这种激素的气息越强，吸引其他蚂蚁到这一路径上的可能就越大。下面通过n个城市的tsp问题来介绍蚁群算法的模型。 在用一群智能蚁解决n个城市tsp问题时，与一般情况下不同的是他们运动的同时还在自己走过的路径上留下一定的激素，所留激素的数量与它们通过这一路径的时间成正比。而在选择下一条路径时，则根据各条路径上的激素的浓度进行选择。t时刻，处于城市i的智能蚁k选择下一步到达城市j的概率为：pyk(t) = ijtij(t)ij

10、tij(t) if j jk(i)0 if j jk(i) 式中，jki表示处于城市i的智能蚁k下一步所有可选路径的集合，ijt为t时刻链接节点i和j的路径上的激素量；ij为由城市i转移到城市j的启发信息，该启发信息根据具体问题给出。如可令ij=1/dij, dij表示城市i，j之间的距离，是用来调整ijt和ij对决策影响程度的参数。此外，蚁群算法中常常引入蒸发因子，以消除开始状态的影响。因为，开始的状态是随机给的。开始时的激素轨迹也带有很大的随机性，并不具有指导性的意义。ijt+1=1-ijt+i-1mijt其中，i-1mijt=i-1mijkt是m个蚂蚁在时间段t到（t+n）内的访问过程中

11、，在i到j的路径上留下的激素总量。下面给出蚁群算法的基本步骤：step 1：初始化ij和ij，令nc=0（nc为迭代次数或者搜索次数）t=0，设置最大迭代次数，把m只蚂蚁随机的置于n座城市中；step 2：把第k(k=1,2,3,4， ，m)只蚂蚁的初始化城市i放到当前解集中，蚂蚁m将按照概率公式pyk(t)选择下一个城市j访问，将j放入当前解集中，反复循环；step 3：m只蚂蚁访问完n座城市，计算每只蚂蚁走过的总路径l，更新最新路径；step 4：根据信息素信息公式，更新信息素的数量；step 5：对每一条路径（i，j），置ij=0，nc=nc+1；step 6：如果nc < 预订设

12、定的迭代次数;则转向步骤2;否则输出结果。程序流程图：nnc预先设定的迭代次数y结束输出最短路径按照文字更新信息计算每只蚂蚁周游一次的路径长度l，保存最优解每只蚂蚁根据概率pyk(t)选择下一个将要访问访问的城市设置参数开始第 iii 条 粒子群优化算法粒子群优化算法是在1995年由eberhart博士和kennedy博士一起提出的，它源于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。我们可以利用一个有关pso的经典描述来对pso算法进行一个直观的描述。设想这么一个场景：一群鸟进行觅食，而

13、远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略，也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。pso就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。在pso中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”，而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitness value），可以将其理解为距离“玉米地”的距离。在每次的迭代中，种群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个种群的粒子就会逐步趋于最优解。整个粒子群优化算法的算法框架如下：step 1 种群初始化：可以进行随机初始化或者根据被优化的问题设计特定的初始化方法，然后计算个体的适应值，从而选择出个体的局部最优位置向量pbestipbesti和种群的全局最优位置向量gbestgbest。step 2 迭代设置：设置迭代次数gmaxgmax，并令当前迭代次数g=1