人工智能第12章群智能.pptx

《人工智能第12章群智能.pptx》由会员分享，可在线阅读，更多相关《人工智能第12章群智能.pptx（73页珍藏版）》请在优知文库上搜索。

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

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

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

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

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

6、为由简单个体交互而来。蚁群算法，又称为蚂蚁算法，1992年多里戈（M. Dorigo）受自然界中真实蚁群的群体觅食行为启发提出，是最早的群智能优化算法，起初被用来求解旅行商（Total Suspended Particulate，TSP）问题。12.2.1 蚁群算法概述蚁群算法概述蚂蚁是一种社会性生物，在寻找食物时，会在经过的路径上释放一种信息素，一定范围内的蚂蚁能够感觉到这种信息素，并移动到信息素浓度高的方向，因此蚁群通过蚂蚁个体的交互能够表现出复杂的行为特征。蚁群的群体性行为能够看作是一种正反馈现象，因此蚁群行为又可以被理解成增强型学习系统（Reinforcement Learning S

7、ystem）。12.2.2 蚁群算法的数学模型蚁群算法的数学模型蚁群优化算法的第一个应用是著名的旅行商问题。蚁群优化算法的第一个应用是著名的旅行商问题。旅行商问题旅行商问题阐明 蚁群系统模型蚁群系统模型旅行商问题（旅行商问题（Traveling Salesman Problem，TSP）：在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。蚂蚁搜索食物的过程蚂蚁搜索食物的过程 ：通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径。符号表示符号表示 m 是蚁群中蚂蚁的数量； 表示结点i（城市）和结点j（城市）之间的距离； 表示t时刻在ij连线上残留的

8、信息素，初始时刻，各条路径上 的信息素相等，蚂蚁k在运动过程中，根据各条路径上的信息 素决定转移方向。 称为启发信息函数，等于距离的倒数；( ,1,1)ijdi jnij( )ijt 表示在t时刻蚂蚁 k 选择从结点 （城市）i 转移到结点（城 市） j的概率，也称为随机比例规则。kijP信息素 共同决定( )ijt局部启发信息ij ( )( ) ( )( )0 kijijkkijijijj allowedittjallowedittp其他 表示蚂蚁k下一步允许选择的城市 记录蚂蚁k当前所走过的城市 是信息素启发式因子，表示轨迹的相对重要性 表示期望启发式因子，表示能见度的相对重要程度( )k

9、kallowed ictabu), 2 , 1(tmkabuk 值越大该蚂蚁越倾向于选择其它蚂蚁经过的路径，该状态转移概率越接近于贪婪规则。当 = 0时不再考虑信息素水平，算法就成为有多重起点的随机贪婪算法。当 = 0时算法就成为纯粹的正反馈的启发式算法。1-表示信息素残留因子，常数 为信息素挥发因子， 表示路径上信息素的损耗程度； 的大小关系到算法的全局搜索能力和收敛速度。蚂蚁完成一次循环，各路径上信息素浓度挥发规则为： 蚁群的信息素浓度更新规则为： 0,1 ijt 11ijijijttt 1mkijijktt根据信息素更新策略不同，多里戈提出了3种基本蚁群算法模型。 1、蚁周系统（Ant-

10、cycle System）单只蚂蚁所访问路径上的信息素浓度更新规则为： Q 为常数Lk 为优化问题的目标函数值，表示第k只蚂蚁在本次循环中所走路径的长度。(01)kkijQLtkttij 第 只蚂蚁过其他在 和之间走 2、蚁量系统（Ant-quantity System） 3、 蚁密系统（Ant-density System） (1)0kkijktQtdijt 第 只蚂蚁在其他和之间走过( )01kijktttijQ第 只蚂蚁在 和之其他间走过蚁圈系统利用的是全局信息 ，即蚂蚁完成一个循环后，更新所有路径上的信息。蚁量系统利用的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。蚁密系统利用

11、的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。三种模型比较三种模型比较/kQ L效果最好，通常作为蚁群优化算法的基本模型。效果最好，通常作为蚁群优化算法的基本模型。/kQ dQ设置参数,初始化信息素浓度While（不满足条件时）dofor蚁群中的每只蚂蚁for每个解构造步骤(直到构造出完整的可行解)1）蚂蚁按照信息素及启发因子构造下一步问题的解；2）进行信息素局部更新。(可选)end forend for1）以已获得的解为起点进行局部搜索；(可选)2）根据已获得的解的质量进行全局信息素更新。end Whileend 蚁群算法蚁群算法流程流程12.2.3 蚁群算法的改进蚁群算法的改进为

12、提高蚁群算法性能，诸多研究学者对蚁群算法进行了改进，其中主要包括蚂蚁-Q系统（Ant-Q System）、蚁群系统（Ant Colony System, ACS）、最大-最小蚂蚁系统（Max-Min Ant System，MMAS）、自适应蚁群算法。 蚂蚁-Q系统1995年，意大利学者卢卡（M. Luca）、甘巴德拉（L. M. Gambardella）、多里戈在ACO算法的基础上，进行了创新，提出了蚂蚁-Q系统。在解构造过程中提出了伪随机比例状态迁移规则；信息素局部更新规则引入强化学习中的Q学习机制；在信息素的全局更新中采用了精英策略。其概率分布计算、AQ值更新规则分别为： , ,0 kkk

13、j allowediHE i jAQ i jjallowediHE i uAQ i uP i j其他 ( ),1,max,kj allwoediAQ i jAQ i jAQ i jAQ i u,0 kwkijLAQ i j 蚂蚁 从 走向其他其中：1996年，甘巴德拉和多里戈又在Ant-Q算法的基础上提出了蚁群系统，蚁群系统是Ant-Q算法的一种特例。其主要创新如下： 蚁群系统 相比ACO算法，蚁群系统中的蚂蚁在下一步移动之前，增加一次随机实验，将选择情况分成“利用已知信息”和“探索”两类。 提出了精英策略（Elitist Strategy）。 设置精英蚂蚁数目的最优范围：若低于该范围，增加精

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

15、自适应蚁群算法自适应蚁群算法能够根据搜索结果进行信息素浓度更新，如果算法陷入局部最优，自适应调整陷入局部最优的蚂蚁所经过路径中的信息素和信息素强度Q，使得算法能够较快的跳出局部最优，避免算法“早熟”，同时自适应蚁群算法限定所有路径上的信息素范围，有利于提高算法全局搜索能力。蚁群算法最早被用来解决旅行商问题，随后陆续被用于解决图着色问题、二次分配问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题、数据聚类问题、武器攻击目标分配和优化问题、区域性无线电频率自动分配问题等。12.2.3 蚁群算法的蚁群算法的应用示例应用示例,GV E1,2, Vn ,ijEei j i jV

16、 ij,ijdi jV ij0ijdijd,ijjiddi jV旅行商问题描述如下：假设为一个加权图，为顶点集，为边集。为顶点i到顶点j的距离，其中且，同时。 minijijijFd x1 .0 ijijijest xe边 在最优路径上边 不在最优路径上i j1 ijxiV（）i j1 ijxjV（）, i j sssG（ 是 的子图 ）s经典TSP的数学模型为： 是图s的顶点数。实际问题可以描述为：一行人要去27个城市旅行，其中城市坐标如表所示，该人从一城市出发，使用蚁群算法计算，应如何选择行进路线，以使总的行程最短。城市 1 2 3 4 5 6 7 8 9行值304639177 712 488326238196312列值312315244399535556229104790城市 10 11 12 13 14 15 16 17 18行值386107562788381332715918161列值570970756491676695678179370城市 19 20 21 22 23 24 25 26 27行值780676329263429507394439935列值2125788389