人工智能第12章群智能课件

1、人工智能第十二章 群智能第1页，共73页。12.1 群智能概述12.2 蚁群算法12.3 粒子群优化算法12.4 其他群智能优化算法第2页，共73页。群智能（Swarm Intelligence，SI）优化算法通过模拟自然界中的昆虫、鸟群、鱼群等“社会性”生物群体的行为特征，利用群体性生物能够不断学习自身经验与其他个体经验的特性，在寻优过程中不断获取和积累寻优空间的知识，自适应地进行搜索寻优，从而得到最优解或准有解。群智能优化算法作为一种新兴的演化计算技术，具有较强的自学习性、自适应性、自组织性等智能特征，算法结构简单、收敛速度快、全局收敛性好，在旅行商问题、图着色问题、车间调度问题、数据聚类

2、问题等领域得到广泛的应用，与进化算法和人工神经网络并称为人工智能领域的三驾马车。12.1 群智能概述第3页，共73页。自然界中的群体生物，具有惊人的完成复杂行为的能力，群智能优化算法则是国内外研究学者受到群体生物的社会行为启发而提出。其中提出时间最早、应用最为广泛的群智能优化算法主要是模拟蚂蚁觅食行为的蚁群算法（Ant Colony Optimization，ACO）和模拟鸟类觅食行为的粒子群优化算法（Particle Swarm Optimization，PSO）。 12.1.1 群智能优化算法定义鸟群通过协作进行捕食房间偏僻角落里的蛋糕总会先被蚂蚁发现鱼聚集成群可以有效的逃避捕食者第4页，

3、共73页。群智能优化算法主要源于对自然界中群体生物觅食等行为的模拟，每个具有经验和智慧的个体通过相互作用机制形成强大的群体智慧来解决复杂问题。其主要算法流程如下。将寻优过程模拟成生物个体的觅食等行为过程，用搜索空间中的点模拟自然界中的生物个体；将求解问题的目标函数量化为生物个体对环境的适应能力；将生物个体觅食等行为过程类比为传统寻优方法用较优的可行解取代较差可行解的迭代过程，从而演化成为一种具有“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。群智能主要算法流程第5页，共73页。12.1.2 群智能优化算法原理自然界中的昆虫、鸟群、鱼群等一些生物具有群体性的行为特征，计

4、算机图形学家雷诺兹（C. Reynolds）认为以群落形式生存的生物在觅食时一般遵循以下三个规则。1）分隔规则：尽可能避免与周边生物个体距离太近，造成拥挤；2）对准规则：尽可能与周边生物个体的平均移动方向保持一致，向目标方向移动；3）内聚规则：尽可能向周边生物个体的中心移动。第6页，共73页。上述规则中，分隔规则体现出生物的个体信息特征，即个体根据自身当前状态进行决策；对准规则和内聚规则体现生物的群体信息特征，即个体根据群体状态进行决策。除个体信息与群体信息特征，生物行为还具有适应性、盲目性、自治性、突现性、并行性等特征。群智能优化算法就是利用雷诺兹模型模拟整个生物群体的行为，算法在迭代过程中

5、不断利用个体最优值与群体最优值进行寻优搜索，完成个体信息与群体信息的交互。在群智能优化算法中，个体最优值的随机性使得算法搜索方向具有多样性，能够避免算法收敛过早陷入局部最优；群体最优值能够把握全局寻优方向，提高算法的全局寻优能力，及时收敛。第7页，共73页。12.1.3 群智能优化算法特点群智能优化算法主要用来求解一些复杂的、难以用传统算法解决的问题。与传统优化算法不同，群智能优化算法是一种概率搜索算法，具有以下几个特点。具有较强的鲁棒性，群体中相互作用的个体是分布式的，没有直接的控制中心，不会因少数个体出现故障而影响对问题的求解。结构简单，易于实现，每个个体只能感知局部信息，个体遵循的规则简

6、单。易于扩充，开销较少。具有自组织性，群体表现出的智能复杂行为由简单个体交互而来。第8页，共73页。12.2 蚁群算法蚁群算法，又称为蚂蚁算法，1992年多里戈（M. Dorigo）受自然界中真实蚁群的群体觅食行为启发提出，是最早的群智能优化算法，起初被用来求解旅行商（Total Suspended Particulate，TSP）问题。第9页，共73页。12.2.1 蚁群算法概述蚂蚁是一种社会性生物，在寻找食物时，会在经过的路径上释放一种信息素，一定范围内的蚂蚁能够感觉到这种信息素，并移动到信息素浓度高的方向，因此蚁群通过蚂蚁个体的交互能够表现出复杂的行为特征。蚁群的群体性行为能够看作是一种

7、正反馈现象，因此蚁群行为又可以被理解成增强型学习系统（Reinforcement Learning System）。第10页，共73页。12.2.2 蚁群算法的数学模型蚁群优化算法的第一个应用是著名的旅行商问题。旅行商问题阐明 蚁群系统模型旅行商问题（Traveling Salesman Problem，TSP）：在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。蚂蚁搜索食物的过程 ：通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径。第11页，共73页。符号表示 m 是蚁群中蚂蚁的数量； 表示结点i（城市）和结点j（城市）之间的距离； 表示t时

8、刻在ij连线上残留的信息素，初始时刻，各条路径上 的信息素相等，蚂蚁k在运动过程中，根据各条路径上的信息 素决定转移方向。 称为启发信息函数，等于距离的倒数； 表示在t时刻蚂蚁 k 选择从结点 （城市）i 转移到结点（城 市） j的概率，也称为随机比例规则。第12页，共73页。信息素 共同决定局部启发信息 表示蚂蚁k下一步允许选择的城市 记录蚂蚁k当前所走过的城市 是信息素启发式因子，表示轨迹的相对重要性 表示期望启发式因子，表示能见度的相对重要程度第13页，共73页。 值越大该蚂蚁越倾向于选择其它蚂蚁经过的路径，该状态转移概率越接近于贪婪规则。当 = 0时不再考虑信息素水平，算法就成为有多重

9、起点的随机贪婪算法。当 = 0时算法就成为纯粹的正反馈的启发式算法。第14页，共73页。1-表示信息素残留因子，常数 为信息素挥发因子， 表示路径上信息素的损耗程度； 的大小关系到算法的全局搜索能力和收敛速度。蚂蚁完成一次循环，各路径上信息素浓度挥发规则为： 蚁群的信息素浓度更新规则为： 根据信息素更新策略不同，多里戈提出了3种基本蚁群算法模型。第15页，共73页。1、蚁周系统（Ant-cycle System）单只蚂蚁所访问路径上的信息素浓度更新规则为： Q 为常数Lk 为优化问题的目标函数值，表示第k只蚂蚁在本次循环中所走路径的长度。第16页，共73页。2、蚁量系统（Ant-quantit

10、y System） 3、 蚁密系统（Ant-density System） 第17页，共73页。蚁圈系统利用的是全局信息 ，即蚂蚁完成一个循环后，更新所有路径上的信息。蚁量系统利用的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。蚁密系统利用的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。三种模型比较效果最好，通常作为蚁群优化算法的基本模型。第18页，共73页。设置参数,初始化信息素浓度While（不满足条件时）dofor蚁群中的每只蚂蚁for每个解构造步骤(直到构造出完整的可行解)1）蚂蚁按照信息素及启发因子构造下一步问题的解；2）进行信息素局部更新。(可选)end foren

11、d for1）以已获得的解为起点进行局部搜索；(可选)2）根据已获得的解的质量进行全局信息素更新。end Whileend 蚁群算法流程第19页，共73页。12.2.3 蚁群算法的改进为提高蚁群算法性能，诸多研究学者对蚁群算法进行了改进，其中主要包括蚂蚁-Q系统（Ant-Q System）、蚁群系统（Ant Colony System, ACS）、最大-最小蚂蚁系统（Max-Min Ant System，MMAS）、自适应蚁群算法。第20页，共73页。蚂蚁-Q系统1995年，意大利学者卢卡（M. Luca）、甘巴德拉（L. M. Gambardella）、多里戈在ACO算法的基础上，进行了创新

12、，提出了蚂蚁-Q系统。在解构造过程中提出了伪随机比例状态迁移规则；信息素局部更新规则引入强化学习中的Q学习机制；在信息素的全局更新中采用了精英策略。第21页，共73页。其概率分布计算、AQ值更新规则分别为：其中：第22页，共73页。1996年，甘巴德拉和多里戈又在Ant-Q算法的基础上提出了蚁群系统，蚁群系统是Ant-Q算法的一种特例。其主要创新如下：蚁群系统相比ACO算法，蚁群系统中的蚂蚁在下一步移动之前，增加一次随机实验，将选择情况分成“利用已知信息”和“探索”两类。提出了精英策略（Elitist Strategy）。设置精英蚂蚁数目的最优范围：若低于该范围，增加精英蚂蚁数目，以便能够较快

13、的发现最优路径；若高于该范围，精英蚂蚁会在搜索初期迫使寻优过程停留在次优解附近，降低算法性能。第23页，共73页。其中状态转移规则为： 其中，Sk表示蚂蚁k所选中的下一个结点；q是一个随机变量，为设定阈值。第24页，共73页。1997年，德国学者施蒂茨勒（T. Stutzle）提出了最大-最小蚂蚁系统。其主要创新如下：最大-最小蚂蚁系统为了避免算法收敛过早，陷入局部最优，将各条路径的信息素浓度限制到min,max区间范围内。采用了平滑机制，路径上信息素浓度的增加与max和当前浓度(i, j)之差成正比，即其中，0 1。第25页，共73页。自适应蚁群算法自适应蚁群算法能够根据搜索结果进行信息素浓

14、度更新，如果算法陷入局部最优，自适应调整陷入局部最优的蚂蚁所经过路径中的信息素和信息素强度Q，使得算法能够较快的跳出局部最优，避免算法“早熟”，同时自适应蚁群算法限定所有路径上的信息素范围，有利于提高算法全局搜索能力。第26页，共73页。蚁群算法最早被用来解决旅行商问题，随后陆续被用于解决图着色问题、二次分配问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题、数据聚类问题、武器攻击目标分配和优化问题、区域性无线电频率自动分配问题等。12.2.3 蚁群算法的应用示例旅行商问题描述如下：假设为一个加权图，为顶点集，为边集。为顶点i到顶点j的距离，其中且，同时。 第27页，

15、共73页。经典TSP的数学模型为： 是图s的顶点数。第28页，共73页。实际问题可以描述为：一行人要去27个城市旅行，其中城市坐标如表所示，该人从一城市出发，使用蚁群算法计算，应如何选择行进路线，以使总的行程最短。城市123456789行值304639177 712 488326238196312列值312315244399535556229104790城市101112131415161718行值386107562788381332715918161列值570970756491676695678179370城市192021222324252627行值7806763292634295073944

16、39935列值212578838931908367643201240第29页，共73页。应用基本蚁群算法进行建模，可计算得出行程最短路径为：城市19城市4城市2城市24城市26城市8城市7城市3城市18城市1城市5城市10城市6城市25城市14城市15城市9城市21城市22城市11城市23城市12城市16城市20城市13城市27城市17。第30页，共73页。12.3 粒子群优化算法粒子群优化算法（Particle Swarm Optimization，PSO）源于对鸟群社会系统的研究，由美国普渡大学的埃伯哈特（J. Eberhart）和肯尼迪（R. Kennedy）于1995年提出。其核心思想

17、是利用个体的信息共享促使群体在问题解空间从无序进行有序演化，最终得到问题的最优解。第31页，共73页。可用如下经典描述直观理解粒子群优化算法：设想这么一个场景：一群鸟在寻找食物，在远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最优策略就是搜寻目前距离玉米地最近的鸟群的所在区域。粒子群优化算法就是从鸟群食物的觅食行为中得到启示，从而构建形成的一种优化方法。12.3.1 粒子群优化算法基本思想第32页，共73页。粒子群优化算法将每个问题的解类比为搜索空间中的一只鸟，称之为“粒子”，问题的最优解对应为鸟群要寻找的“玉米地”。每个粒子设

18、定一个初始位置和速度向量，根据目标函数计算当前所在位置的适应度值（Fitness Value），可以将其理解为距离“玉米地”的距离。粒子在迭代过程中，根据自身的“经验”和群体中的最优粒子的“经验”进行学习，从而确定下一次迭代时飞行的方向和速度。通过逐步迭代，整个群体逐步趋于最优解。第33页，共73页。在n 维连续搜索空间中，对粒子群中的第i (i=1, 2, , m)个粒子进行定义： ：表示搜索空间中粒子的当前位置。 ：表示该粒子至今所获得的具有最优适应度 的位置。 ：表示该粒子的搜索方向。12.3.2 粒子群优化算法基本框架 ：表示每个粒子经历过的最优位置（Pbest）。 ：群体经历过的最优

19、位置（Gbest）。第34页，共73页。c1 ，c2 是速度因子，均为非负值；r1 和 r2 为0, 1 范围内的随机数。早期的粒子群优化算法速度和位置向量更新公式如下：；第35页，共73页。由于 的更新过于随机，使得粒子群优化算法具有较强的全局寻优能力，但是局部寻优能力较差。为保证算法具有全局寻优能力的同时，提高其局部寻优能力。1998年Shi Yuhui和埃伯哈特在算法中引入惯性权重（Inertia Weight）系数w，修正了速度向量更新公式：第36页，共73页。参数w取值范围为0,1，与物理中的惯性相似，w反映了粒子历史运动状态对当前运动的影响。如果w取值较小，历史运动状态对当前运动影

20、响较小，粒子的速度能够很快的改变；相反，如果w取值较大，虽然提高了搜索空间范围，但是粒子运动方向不易改变，难于向较优位置收敛。因此w设置较大时，能够提高算法全局寻优能力，w设置较小时，又能够加快算法局部寻优。实际工程应用中w可采取自适应取值方式。第37页，共73页。粒子群优化算法流程procedure PSO for 每个粒子i 初始化每个粒子i，随机设置每个粒子的初始位置和速度 计算每个粒子i的目标函数，Gbest = end for Gbest = minPbesti while not stop for i=1 to m 更新粒子i的速度和位置 if fit() fit(Pbesti)

21、Pbesti = if fit(Pbesti) fit(Gbest) Gbest = Pbesti; end for end while print Gbestend procedure第38页，共73页。12.3.3 粒子群优化算法参数分析与改进粒子群优化算法中主要参数如下：种群规模m种群规模通常设置为20-40，可根据不同问题进行自定义。惯性权重w惯性权重能够保持粒子运动惯性，扩展搜索空间，搜索新的区域。最大速度Vmax最大速度Vmax决定当前位置与最优位置之间的区域的精度。若Vmax过大，粒子可能跨过最优位置；若Vmax过小，粒子无法在局部最优值之外进行足够的探索，易陷入局部最优。限制最

22、大速度可以有效防止计算溢出、决定问题空间搜索的粒度。迭代次数Gmax迭代次数Gmax根据工程应用具体问题决定。第39页，共73页。学习因子c1、c2学习因子c1、c2分别控制个体认知分量和群体社会分量相对贡献的学习率。当c1=0、c2=0时，只有第1部分，粒子保持当前速度飞行，直到达边界，只能搜索有限的区域，无法找到最优解。w=0时，没有第1部分，速度没有记忆性，只取决于粒子当前位置和其历史最优位置。当c1=0时，没有第2部分，粒子没有认知能力，只有“社会模型”。在粒子的相互作用下，有能力达到新的搜索空间。但是复杂问题容易陷入局部最优。当c2=0时，没有第3部分，粒子间没有社会共享信息，只有“

23、认知模型”。个体间没有交互，群体中所有个体独立搜索，因此无法得到最优解。第40页，共73页。粒子群优化算法的改进粒子群优化算法具有收敛速度快的优点，但是在算法运行初期，算法存在精度较低、易发散等缺点。因此国内外诸多研究人员致力于提高粒子群优化算法的性能，现阶段主要侧重理论研究改进、拓扑结构改进、混合改进算法、参数优化等方面。第41页，共73页。粒子群优化算法自提出至今，被广泛的应用于神经网络训练、机器人、经济、通信、医学等多种领域。本节示例为粒子群优化算法在车辆路径问题（Vehicle Routing Problem，VRP）中的应用。12.3.4 粒子群优化算法的应用示例第42页，共73页。

24、假定配送中心最多可以用 辆车对 个客户进行运输配送， 表示仓库。每个车辆载重为 ，每个客户的需求为 ，客户i到客户 j 的运输成本为 cij（可以是距离，时间，费用等）。定义如下变量：第43页，共73页。1、建立车辆路径问题的数学模型如下：每辆车的能力约束：保证每个客户都被服务：保证客户是仅被一辆车访问：保证客户是仅被一辆车访问：消除子回路：表示变量的取值范围：表示变量的取值范围：第44页，共73页。2、编码与初始种群 对这类组合优化问题，编码方式、初始解的设置对问题的求解都有很大的影响。 本问题采用常用的自然数编码方式。 对于K辆车和L个客户的问题，用从1到L的自然数随机排列来产生一组解 。

25、然后分别用节约法或者最近插入法构造初始解。第45页，共73页。粒子群优化算法的各个参数设置如下：种群规模p=50 ，迭代次数Gmax=1000，w的初始值为1，随着迭代的进行，线性减小到0，c1=c2=1.4 ， 。优化结果及其比较实例PSOGAbestdev(%)bestdev(%)A-n32-k58295.738184.34A-n33-k57056.656741.97A-n34-k58326.948215.52A-n39-k68726.088665.35A-n44-k610168.499915.76A-n46-k79776.899574.7A-n54-k712053.2612033.08A

26、-n60-k914769.0114104.13A-n69-k912751012437.24A-n80-k10199212.9818716.12第46页，共73页。12.4 其他群智能优化算法随着蚁群算法、粒子群优化算法的广泛应用，各类群智能优化算法蜂拥而至。其中较为典型的几种包括人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）、细菌觅食算法（Bacterial Foraging Optimization，BFO）、蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）、果蝇优化算法（Fruit Fly Optimizatio

27、n Algorithm，FOA）等。群智能优化1992年 1995年2002年2003年2005年2007年2011年2014年蚁群算法果蝇优化算法狼群算法鸽群优化算法人工鱼群算法第47页，共73页。人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA），由李晓磊博士于2001年提出，是一种源于鱼群自治行为的群智能优化算法，通过构造人工鱼来模仿鱼群的觅食、聚群、追尾和随机行为，从而实现寻优，具有较快的收敛速度，可以用于解决有实时性要求的问题。12.4.1 人工鱼群算法人工鱼的结构图第48页，共73页。假设人工鱼当前状态为X，Visual代表其视野范围，Xv表示

28、某时刻其视点所在位置。若该位置的状态优于当前状态，向当前位置方向前进一步到达状态Xnext；若状态Xv比当前状态差，继续巡视视野内的其他位置。巡视的次数越多，对视野范围内的信息了解越全面，从而能够全方位立体感知周围的环境，有助于对目标问题做出相应的判断和决策。人工鱼群算法基本概念人工鱼视觉的概念第49页，共73页。其中，状态 ，状态 ，则该过程可以表示为：式中，rand函数用来产生0,1之间的随机数；Step为移动步长。第50页，共73页。人工鱼群算法采用面向对象的技术重构人工鱼的模型，将人工鱼封装成变量和函数两部分。其中变量部分包括人工鱼的总数N，人工鱼个体的状态为待寻优的变量），人工鱼移动

29、的最大步长Step，人工鱼的视野Visual，尝试次数Try_number，拥挤度因子，人工鱼个体i,j之间的距离 。函数部分包括人工鱼当前所处位置的食物浓度 人工鱼的各种行为函数（觅食行为Prey()、聚群行为Swarm()、追尾行为Follow()、随机行为Move()以及行为评价函数Evaluate()）。通过封装，人工鱼的状态能够被其他同伴感知。（Y为目标函数值）第51页，共73页。觅食行为聚群行为追尾行为随机行为人工鱼的四种基本行为算法描述由于鱼类不具备复杂逻辑推理能力和综合判断能力，它们只能通过简单行为达到目的。因此通过模拟鱼类的四种行为觅食行为、聚群行为、追尾行为和随机行为来使鱼

30、类活动在周围的环境。第52页，共73页。觅食行为是人工鱼趋向食物源的一种基本行为，一般通过视觉或味觉感知水中的食物数量或浓度，进行趋向选择。行为描述：设人工鱼i的当前状态为Xi，在其感知范围内随机选择一个状态Xj，则其中，rand是一个0,1之间的随机数，在求解问题极大值时，若YiYj，则向Xj方向前进一步：否则，再次随机选择状态Xj，判断是否满足前进条件，若反复尝试Try_number次后仍不满足前进条件，则随机移动一步：觅食行为第53页，共73页。这是鱼群生存和躲避危害的一种生活习性。在鱼群算法中，一般规定两条，一是尽量向邻近伙伴的中心移动，二是避免过分拥挤。行为描述：设人工鱼当前状态为X

31、i，当前搜索范围内dijVisual，伙伴数目为 ，中心位置为Xo。若 ，表明伙伴中心食物较多且不存在过分拥挤，则向伙伴中心位置方向前进一步，即否则，执行觅食行为。聚集行为第54页，共73页。鱼群在游动过程中，当其中一条鱼或几条鱼发现食物时，其邻近的伙伴会尾随其快速到达食物点。行为描述：设人工鱼i当前状态为Xi，当前搜索范围内dij0表示细菌的游动步长单位； 表示细菌翻转运动后随机改变的角度。 第62页，共73页。细菌觅食算法具体步骤算法参数初始化，包括细菌个数S、趋化操作次数Nc、最大游动步数Ns、繁殖操作次数Nre、驱散操作次数Ned以及细菌个体驱散概率P、随机生成单个细菌的位置。种群位置

32、初始化，计算每个细菌初始适应度值，j=0，k=0，l=0。驱散操作循环l=l+1。繁殖操作循环k=k+1。趋化操作循环i=i+1，每个细菌个体进行趋化操作。若jNc，则回到。繁殖操作，适应度值排在前S/2的个体进行繁殖，替换适应度值较小的另一半细菌。若kNre，则转到。驱散操作。当细菌i满足驱散概率，随机生成新的细菌替换细菌i。若lNed，则转到；否则，算法结束，输出问题最优结果。第63页，共73页。12.4.3 混合蛙跳算法混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA），由尤瑟夫（M. M. Eusuff）和兰西（K. E. Lansey）于2003

33、年提出，是一种全新的后启发式群体智能算法，结合了模因演算MA（Memetic Algorithm）和粒子群优化算法2种算法的优点，具有高效的计算效率和良好的全局寻优能力。第64页，共73页。混合蛙跳算法基本概念混合蛙跳算法可以描述为：在一片空间区域内生活着一群青蛙，为了寻找食物较多的地方，蛙群首先按照一定的规则确定每只青蛙的初始位置。随后，每只青蛙利用个体信息在初始位置附近搜索食物更多的区域，跳跃完成个体位置更新。主要搜索规则为，蛙群利用青蛙的自组织性行为，组成多个子种群，子种群中的青蛙个数基本相同，由子种群中的局部精英个体带领其他个体进行组团搜索。子种群完成一次搜索后，蛙群中的所有个体进行重新混合分组，继续执行组团。组团搜索与蛙群混合迭代进行，直至到达食物最丰富的位置。第65页，共73页。混合蛙跳算法基本流程混合蛙跳算法首先从可行域中随机产生一组初始解，每个解对应一只青蛙，形成初始种群；根据目标函数，计算每个青蛙的适应度值，进行由大到小排列；以一定的规则将蛙群划分为一定数量的子种群，每个子种群进行局部搜索，子种群内最差的青蛙根据更新策略向局部最优位置靠近；子种群完成一次局部搜索后，