高级人工智能课件5群体智能

1、计算智能（4）生物群体智能2022/9/262Cockroach2022/9/263Cat2022/9/264Bacterial Foraging2022/9/265Frog2022/9/266Stick Inset2022/9/267Lizard2022/9/268Crab2022/9/269Butt2022/9/2610AntennaGPSSolar WingsMicro-ProcessorSolar WingsWide-Band Attack AntennaBatteryBee2022/9/26人工智能11粒子群优化 生物群体普遍具有智能行为，这种生物群体所具有的智能我们称为群智能。 可

2、以把群(Swarm)定义为某种具有交互作用的组织或智能体的集合。在这种群体中，个体在结构上很简单，而他们的集体行为可能变得相当复杂。 个体行为和全局群行为之间存在着某种紧密地联系，这些个体的行为构成和支配了群行为，同时，群行为又影响和改变这些个体的自身行为。个体之间的交互在构建群行为中起到重要的作用，它帮助群体改善了对环境的经验知识。 对不同群的研究得到不同的应用，其中最引人注目的是通过对鸟群和蚁群的研究而建立的粒子群算法和蚁群算法。2022/9/26人工智能121 粒子群优化概述 粒子群优化PSO（Particle Swarm Optimization）算法是一种基于群智能的演化计算方法，由

3、Kennedy和Eberhart于1995年提出。该算法源于对鸟类捕食行为的模拟。 设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。 在搜寻过程中，每只鸟的位置变化是以成功地超越其他个体的社会心理意向为基础的。因此一只鸟的搜寻行为受到其他鸟的搜寻行为的影响。2022/9/26人工智能13 PSO从这种模型中得到启示并用于解决优化问题。在PSO中，优化问题的潜在解刻画为搜索空间中的一只鸟，称之为“粒子”。每个粒子都有一个由优化函

4、数决定的适应值和一个决定飞翔方向及距离的速度，粒子们追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。 在每一次迭代中，粒子通过跟踪两个“极值”来更新自己的位置。这两个极值分别是： 粒子本身所找到的最优解，称为个体极值； 整个种群目前找到的最优解，称为全局极值。粒子通过不断学习和更新，最终飞至空间中最优解所在的位置。 2022/9/2614What is the Particle Swarm Optimization (PSO)?Particle:Presenting the Solution SetIt contains: coordinate

5、 of the position velocity fitness value2022/9/2615Definition The ith particle position at the tth iteration can be represented as:2022/9/2616 The best previous position (the position giving the best fitness value) of the ith particle from the first iteration to the tth iteration is represented as:De

6、finition2022/9/2617Definition The best position amongst all particles from the first iteration to the tth iteration can be defined as:2022/9/2618Definition The rate of position change (velocity) for the ith particle is recorded as:2022/9/2619Definition The particles are manipulated according to the

7、following equation:(a)(b) Where and are two positive constants, and are two random functions in the range 0,1.W is the inertia weight.2022/9/2620Definition2022/9/26人工智能212 粒子群算法过程 由于在上述的迭代过程中，Pg是整个粒子群的最优位置，因此上述PSO算法称为全局版PSO。还可以把第i个粒子的近邻搜索到的最优位置作为Pg，此时PSO称为局部版PSO。这里我们只对全局PSO算法过程进行描述。 具体算法如下： 2022/9/2

8、6人工智能22(1) 随机初始化粒子群，即t=0时随机为每个粒子指定一个位置Xi(0)及速度Vi(0);(2) 计算每个粒子的适应度值f(Xi(t);(3) 比较每个粒子的当前适应度值f(Xi(t)和个体最优值f(Pi)，如果f(Xi(t)f(Pi)，那么Pi=Xi(t)；(4) 比较每个粒子的当前适应度值f(Xi(t)和全局最优值f(Pg)，如果f(Xi(t)f(Pg)，那么Pg=Xi(t)；(5) 按下列公式更改每个粒子的速度矢量和位置：(6) 如果满足终止条件，则输出Pg；否则，t =t+1，转(2)。2022/9/26人工智能23 在PSO算法中并没有太多需要调节的参数，下面列出了这些

9、参数以及经验设置： 粒子数m(种群大小)：一般取20-40，其实对于大部分的问题，10个粒子已经足够取得好的结果，对于比较难的问题或者特定类别的问题，粒子数可以取到100或200。 粒子的长度n(空间维数)：这是由优化问题决定的，就是问题解的长度。 粒子的坐标范围：由优化问题决定，每一维可设定不同的范围。 学习因子：c1和c2通常等于2，不过在一些文献中也有其它的取值，但是一般c1和c2相等，并且范围在0和4之间。 中止条件：最大循环数以及最小偏差要求，这个中止条件由具体问题确定。2022/9/26人工智能24PSO和遗传算法（Genetic Algorithm，GA）相比 ：相同之处是两者都

10、随机初始化种群，都使用适应度函数来评价系统，并根据适应度值来进行一定的随机搜索，且两个系统都不保证一定找到最优解。但是，PSO 没有遗传操作，如交叉和变异，它根据粒子的速度来决定搜索，操作简单，而且粒子具有记忆功能。 另外，PSO 的信息共享机制也有别于GA。 在GA中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动；在PSO中，只有pg或pi提供信息给其他的粒子，这是单向的信息流动。PSO整个搜索更新过程是跟随当前最优解的过程，因而收敛速度相对要快。 GA比较适用于离散问题的求解，而粒子群较适合连续性问题的求解。3 粒子群算法与遗传算法比较 2022/9/26人工智能25蚁

11、群算法 蚁群算法(ant colony algorithm)是一种模拟进化算法。是由意大利学者M. Dorigo等人在对自然界中真实蚁群的集体行为的研究基础上，于1991年首先提出的。 蚁群算法模拟了自然蚂蚁的协作过程，用一定数目的蚂蚁共同求解，用蚂蚁的移动线路表示所求问题的可行解集，通过正反馈、分布式协作和隐并行性找最优解。 蚁群算法已成功应用于求解TSP 问题、任务分配问题、调度问题等组合优化问题，并取得了较好的实验结果。受其影响，蚁群系统模型逐渐引起了其它研究者的注意，并用该算法来解决一些实际问题。2022/9/26人工智能261 蚁群算法原理 蚂蚁属于群居昆虫，个体行为极其简单，而群体

12、行为却相当复杂。协作能力：一群蚂蚁很容易找到从蚁巢到食物源的最短路径,而单个蚂蚁则不能。自适应能力：例如在蚁群的运动路线上突然出现障碍物时,它们能够很快地重新找到最优路径。 仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone) 的物质进行信息传递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用。2022/9/26人工智能27 蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向。 蚂蚁倾向于朝着该物质强度高的方向移动。因

13、此由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象： 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。2022/9/26人工智能28M. Dorigo 用下面的例子来具体说明蚁群系统的原理。 设A 是巢穴，E 是食物源，HC 为障隘物。各点之间距离如图所示。假设每个时间单位有30 只蚂蚁由A 到达B，有30 只蚂蚁由E 到达D 点，蚂蚁过后留下的激素物质量为1， 设该物质停留时间为1。 (1) 初始时，路径上均无信息存在, 蚂蚁等概率选择路径。 (2) 经过一个时间单位后, 在路径BCD 上的信息量是路径BHD 上信息

14、量的二倍。将有更多的蚂蚁选择路径BCD。2022/9/26人工智能292 蚁群系统模型 人工蚂蚁算法基本原理吸收了生物界中蚂蚁群体行为的某些显著特征：能察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹;能释放自己的信息素; 所遗留的信息素数量会随时间而逐步减少。蚁群算法的核心有三条： (1) 选择机制：信息素越多的路径，被选中的概率越大; (2) 信息素更新机制：路径越短，信息素增加越快; (3) 协作机制：个体之间通过这种信息素进行交流。3 蚁群算法的基本流程AS算法求解流程的两大步骤：1、路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依

15、次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。2、信息素更新信息素蒸发每只蚂蚁根据自己构建的路径长度对本轮经过的边上释放信息素路径构建AS中的随机比例规则：设蚂蚁k当前所在城市为i，其选择城市j作为下一个访问对象的概率为：信息素更新信息素更新的2个步骤：信息素的蒸发和每个蚂蚁根据自己构建的路径长度在本轮经过的边上释放信息素。4 蚁群优化算法的改进精华蚂蚁系统基于排列的蚂蚁系统最大最小蚂蚁系统蚁群系统4 蚁群优化算法的改进精华蚂蚁系统4 蚁群优化算法的改进基于排列的 蚂蚁系统5 蚁群优化算法的应用车间作业调度问题 车辆路径问题其他方面的应用6 蚁群优化算法的

16、参数设置蚂蚁数目m信息素权重和启发式信息权重信息素蒸发因子初始信息素量0终止条件7 蚁群优化算法的实现算法的基本结构Procedure Ant_Colony_OptimizationBeginSetParameters; InitializePheromones;While (not termination condition) doConstructSolutions;UpdatePheromones;End whileReturn the best solution;end7 蚁群优化算法的实现数据结构（以n个城市的TSP问题为例）为了表示待解问题所需要的所有数据，需要以下三个nn的矩阵：

17、（1）距离矩阵Dist，Distij存放城市i与城市j之间的距离dij（2）信息素矩阵Pheromone， Pheromoneij存放信息素ij（3）选择信息矩阵Choice_info, Choice_infoij存放ij ij每只蚂蚁记忆它所经过的路线及每个城市该蚂蚁是否被访问过，需要两个数组：Tour数组：存放第k只蚂蚁的路径；元素值为1-n的整数；Visited数组：元素值为true 或false7 蚁群优化算法的实现求解TSP问题的ACO算法Procedure ACO_TSPBeginSetParameters; InitializeData; L+ -While( not termi

18、nation condition ) doFor k 1 to m dobuildTrip(k); Computer the length Lk of Tk;If(Lk L+) thenT+ Tk; L+ Lk;end ifEnd forUpdatePheromones;End whileOutput T+ as the best solution;end7 蚁群优化算法的实现第k只蚂蚁构建一条回路的过程：蚂蚁的记忆首先被清空；随机地选择一个城市作为起始城市；蚂蚁根据每个城市的选择概率按转轮法依次选择n-1个城市；最后，蚂蚁返回起始城市，为了方便算法的实现，在路径表示时把第一个城市重复第记录在

19、路径的第n+1个位置上。7 蚁群优化算法的实现第k只蚂蚁构建路径的算法过程：Procedure BuildTrip(k)BeginFor i 1 to n doAntk.visitedi false;End forstep 1; r random1,2,.,n;antk.tourstep r; antk.visitedr true;While( step n) dostep step +1; NextCity(k, step);End whileantk.tourn+1 antk.tour1;end7 蚁群优化算法的实现城市选择算法：Procedure NextCity(k,i)BeginC antk.touri-1; sum_probabilities 0;For j 1 to n doIf antk.visitedj then Selection_probabilityj 0；ElseSelction_probabilityj Choice_infoc, j ;Sum_probabiities sum_probailtes+selectio_probabilityj;End ifEnd forr rando