粒子群算法最全的课件.ppt

1、 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w群智能（群智能（Swarm Intelligence,SI Swarm Intelligence,SI）人们把群居昆虫的集体行

2、为称作人们把群居昆虫的集体行为称作“群智能群智能”（“群体智能群体智能”、“群集智能群集智能”、“集群智能集群智能”等）等）w特点特点 个体的行为很简单，但当它们一起协同工作时，个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。却能够突现出非常复杂（智能）的行为特征。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w描述描述 群智能作为一种新兴的演化计算技术已成为研究群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。

3、法有着极为特殊的关系。w特性特性 指无智能的主体通过合作表现出智能行为的特性，指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。找复杂的分布式问题求解方案提供了基础。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优点优点 灵活性：群体可以适应随时变化的环境；灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监自我组

4、织：活动既不受中央控制，也不受局部监管。管。w典型算法典型算法 蚁群算法（蚂蚁觅食）蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）粒子群算法（鸟群捕食）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w蚁群的自组织行为蚁群的自组织行为 “双桥实验双桥实验”通过遗留在来往路径通过遗留在来往路径 上的信息素上的信息素 （PheromonePheromone）的挥）的挥 发性化学物质来进行发性化学物质来进行 通信和协调。通信和协调。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w蚁群的自组织行为蚁群的自组织行为

5、 “双桥实验双桥实验”华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w提出蚁群系统提出蚁群系统 19921992年，意大利学者年，意大利学者M.DorigoM.Dorigo在其博士论文中提在其博士论文中提出出 蚂蚁系统（蚂蚁系统（Ant SystemAnt System）。）。近年来，近年来，M.DorigoM.Dorigo等人进一步将蚂蚁算法发展等人进一步将蚂蚁算法发展为一种通用的优化技术为一种通用的优化技术蚁群优化（蚁群优化（ant colony ant colony optimization,ACOoptimization,ACO）。）。蚂

6、蚁从蚂蚁从A A点出发，随机选择路线点出发，随机选择路线ABDABD或或ACDACD。经过经过9 9个时间单位时：走个时间单位时：走ABDABD的蚂蚁到达终点，走的蚂蚁到达终点，走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到C C点。点。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 蚁巢蚁巢食物食物 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 经过经过1818个时间单位时：走个时间单位时：走ABDABD的蚂蚁到达的蚂蚁到达终点后得到食物又返回了起点终点后得到食物又返回了起点A A，而走，而走ACDAC

7、D的蚂蚁刚的蚂蚁刚好走到好走到D D点。点。蚁巢蚁巢食物食物 最后的极限是所有的蚂蚁只选择最后的极限是所有的蚂蚁只选择ABDABD路线。路线。（正反馈过程）（正反馈过程）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 蚁巢蚁巢食物食物 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决解决TSPTSP问题问题 在算法的初始时刻，将在算法的初始时刻，将m m只蚂蚁随机放到只蚂蚁随机放到n n座城座城市市;将每只蚂蚁将每只蚂蚁 k k的禁忌表的禁忌表tabutabuk k(s s)的第一个元素的第一个元

8、素tabutabuk k(1)(1)设置为它当前所在城市设置为它当前所在城市;设各路径上的信息素设各路径上的信息素ijij(0)=(0)=C C（C C为一较小的常为一较小的常数）数）;ijijkkkkiJsisisijijkijdtabuniJiJjiJjtttttpk/1 ,2,1)()(,0)(,)()()()()()(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决解决TSPTSP问题问题 每只蚂蚁根据路径上的信息素和启发式信息每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：（两城市间距离）独立地选择下一座

9、城市：在时刻在时刻t t，蚂蚁，蚂蚁k k从城市从城市i i转移到城市转移到城市j j的概率为的概率为 、分别表示信分别表示信 息素和启发式因子息素和启发式因子 的相对重要程度。的相对重要程度。下一步允许的城市的集合下一步允许的城市的集合 否则在本次周游中经过边若蚂蚁 ,0 ,)()1()(1ijkLQtntkkijmkkijijijijij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决解决TSPTSP问题问题 当所有蚂蚁完成一次周游后，各路径上的信息当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：素将进行更新：其中，其中，（0 0

10、1 q q0 0时，时，S S以以下概率来选择：以以下概率来选择：otherwiseSqqiftjiuiualloweduk ,)(maxarg0)(,0)(,)()(),()(iJjiJjttjipkkiJsisisijijkk华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w局部信息素更新局部信息素更新 使已选的边对后来的蚂蚁具有较小的影响力，使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市当蚂蚁从城市i i转移到城市转移到城市j j后，边后，边ijij上的

11、信息上的信息素更新为：素更新为：其中，其中，0 0为常数，为常数，(0,1)(0,1)为可调参数。为可调参数。0)1(ijij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w全局信息素更新全局信息素更新 只针对全局最优解进行更新：只针对全局最优解进行更新：否则包含在最优路径中如果边 ,0 ,/1)1,0(,)()1()1(ijLttgbgbijgbijijij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w最大最小蚂蚁系统（最大最小蚂蚁系统（max-min ant system,MMASmax-mi

12、n ant system,MMAS）的改进之处的改进之处 （1 1）每次迭代后，只有最优解（最优蚂蚁）所）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新；属路径上的信息被更新；（2 2）为了避免过早收敛，将各条路径可能的信）为了避免过早收敛，将各条路径可能的信息素限制于息素限制于 minmin ,maxmax；（3 3）初始时刻，各路径上信息素设置为）初始时刻，各路径上信息素设置为maxmax ，在算法初始时刻，在算法初始时刻，取较小值时算法有更好的发现取较小值时算法有更好的发现较好解的能力。较好解的能力。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 20072007

13、2007年年年 w信息素的全局更新信息素的全局更新 使所有蚂蚁完成一次迭代后，进行信息素更新：使所有蚂蚁完成一次迭代后，进行信息素更新：否则包含在最优路径中如果边 ,0 ,/1)1,0(),()()1()1(ijLtttbestbestijbestijijij华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w基于排序的蚂蚁系统（基于排序的蚂蚁系统（rank-based version of rank-based version of ant system,ASant system,ASrankrank）每次迭代完成后，蚂蚁所经路径按从小到大的每次迭

14、代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，路径越短权值顺序排列，并对它们赋予不同权值，路径越短权值越大。全局最优解权值为越大。全局最优解权值为w w，第，第r r个最优解的权值为个最优解的权值为max0,max0,w w-r r。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w基于排序的蚂蚁系统（基于排序的蚂蚁系统（rank-based version of rank-based version of ant system,ASant system,ASrankrank）信息素更新：信息素更新：gbgbijrrijgbij

15、rijwrijijLttLttwtrwtt/1)(),(/1)()1,0(),()()()()1()1(11华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w优化结果比较优化结果比较 对对称对对称TSPTSP各迭代各迭代1000010000次，对非对称次，对非对称TSPTSP各迭代各迭代2000020000次：次：TSP实例实例MMASACSASeliteASEil51.tsp427.6428.1428.3437.3kroA100.tsp21320.321420.021522.8322471.4D198.tsp15972.516054.016205

16、.016705.6Lin31842220.242570.043422.845535.2Ry48p.atsp14553.214565.414685.215296.4Ft70.atsp39040.239099.039261.839596.3Kro124p.atsp36773.536857.037510.238733.1Ftv170.atsp2828.82826.52952.43154.5华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w典型应用列表典型应用列表 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年

17、 w如何应用如何应用 用蚁群算法解决数据分类（数据挖掘任务中的用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：一种）的问题：预先定义一组类，然后把数据系中的每一个数预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。当数据量很大时，难以人为判别分类。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w如何应用如何应用 分类的规则：分类的规则：IF IF THEN THEN 每个每个termterm是一个三元组（属性、关系符、属性是一个三元组（属

18、性、关系符、属性取值）取值）希望在一个规则中使用最少的判别语句，采用希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。蚁群优化算法达到最优的选择。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w例：非典型肺炎例：非典型肺炎 考虑如下因素：考虑如下因素：属性属性发热发热职业职业胸部阴影胸部阴影流行病学史流行病学史值值（0,1,2,3）（0,1,2）（0,1,2）（0,1,2）说明说明0：不考虑该属性：不考虑该属性1：37.5以下以下2：37.5 38.5 3：38.5 以上以上0：不考虑该：不考虑该属性属性1：医务人员：医务人员2

19、：其他人员：其他人员0：不考虑该：不考虑该属性属性1：无：无2：有：有0：不考虑该：不考虑该属性属性1：无：无2：有：有可编辑华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w例：非典型肺炎例：非典型肺炎 结构图：结构图：一个蚂蚁从始点行走至终点，得到一条路径一个蚂蚁从始点行走至终点，得到一条路径0,0,2,1,02,1,0，其对应的规则为，其对应的规则为 IF IF（职业其他人员）（职业其他人员）ANDAND（胸部阴影无）（胸部阴影无）THEN THEN（非典型肺炎）（非典型肺炎）对此路径，应给予非常差的评价。对此路径，应给予非常差的评价。华东理

20、工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w蚁群算法的实现蚁群算法的实现 假设假设a a表示属性的总个数，第表示属性的总个数，第i i个属性的取值域中个属性的取值域中可取可取b bi i个数值。一只蚂蚁的行走个数值。一只蚂蚁的行走k k步的路径可以表步的路径可以表示为示为 routeroute k k=(=(y y1 1,y y2 2,y ya a)y yi i=0=0表示不包含属性表示不包含属性i i。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w评价函数评价函数 解的评价函数定义为：解的评价函数

21、定义为：Q Q的数的数值越接近值越接近1 1，说明对该，说明对该 类的类的判断越准确。判断越准确。TPtrue positivesTPtrue positives TNtrue negatives TNtrue negatives FPfalse positives FPfalse positives FNfalse negatives FNfalse negativesTNFPTNFNTPTPQTrueTrue：判断结果，正确：判断结果，正确FalseFalse：判断结果，失误：判断结果，失误PositivesPositives：真实属性，属于：真实属性，属于NegativesNegativ

22、es：真实属性，不属于：真实属性，不属于华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w转移概率转移概率 ijij表示每个条件项的启发式参数值（信息熵），表示每个条件项的启发式参数值（信息熵），ijij(t t)表示第表示第 i i 个属性的第个属性的第 j j 个取值在个取值在 t t 时刻的时刻的信息素。信息素。ibqiqiqijijijbjaittpi,1,0;,2,1 ,)()(0华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w信息素增加信息素增加 R R是当前规则中所有包含的条件项；是当前

23、规则中所有包含的条件项；w信息素挥发信息素挥发 减少没被选中的三元组的信息量。减少没被选中的三元组的信息量。10 ,),(,)()()1(QRjiQtttijijijiaibjijijijbjaittti,1,0;,2,1 ,)()()1(11华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w结果分析结果分析 诊断准确度比诊断准确度比较较 数据库数据库蚁群优化算法蚁群优化算法CN2Ljubljana breast cancerWisconsin breast cancerTic-tac-toeDermatologyHepatitisClevelan

24、d heart disease75.282.2496.04 0.9373.04 2.5394.29 1.2090.00 3.1159.67 2.5067.69 3.5994.88 0.8897.38 0.5290.38 1.6690.00 2.5057.48 1.78华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w结果分析结果分析 诊断规则数比诊断规则数比较较 数据库数据库蚁群优化算法蚁群优化算法CN2Ljubljana breast cancerWisconsin breast cancerTic-tac-toeDermatologyHepat

25、itisCleveland heart disease7.100.316.20 0.258.50 0.627.30 0.153.400.169.50 0.9255.40 2.0718.60 0.4539.70 2.5218.50 0.477.200.2542.40 0.71华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w由由James KenneyJames Kenney（社会心理学博士）和（社会心理学博士）和Russ Russ EberhartEberhart（电子工程学博士，（电子工程学博士，http:/www.engr.iupui.edu/

26、eberhart/http:/www.engr.iupui.edu/eberhart/）于）于19951995年提出粒子群算法（年提出粒子群算法（Particle Swarm Particle Swarm OptimizationOptimization,PSO,PSO）华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w源于对鸟群捕食行为的研究，是基于迭代的方法源于对鸟群捕食行为的研究，是基于迭代的方法w简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少w在函数优化、神经网络训练、工业系统优化和模糊在函数优化、神经网络训练、工

27、业系统优化和模糊系统控制等领域得到了广泛的应用。系统控制等领域得到了广泛的应用。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w鸟群：鸟群：假设一个区域，所有的鸟都不知道食物的位置，假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。但是它们知道当前位置离食物还有多远。wPSOPSO算法算法 每个解看作一只鸟，称为每个解看作一只鸟，称为“粒子粒子(particle)”(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最

28、度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。优粒子在解空间中搜索。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 wPSOPSO算法算法 初始化为一群随机粒子，通过迭代找到最优。初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪每次迭代中，粒子通过跟踪“个体极值个体极值（pbestpbest）”和和“全局极值全局极值(gbest)”(gbest)”来来 更新自己的位置。更新自己的位置。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w粒子速度和位置的更新粒子速度和位置

29、的更新 假设在假设在D D维搜索空间中，有维搜索空间中，有m m个粒子；个粒子；其中第其中第i i个粒子的位置为矢量个粒子的位置为矢量 其飞翔速度也是一个矢量，记为其飞翔速度也是一个矢量，记为 第第i i个粒子搜索到的最优位置为个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为整个粒子群搜索到的最优位置为 第第i i个粒子的位置和速度更新为：个粒子的位置和速度更新为：Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211),(21iDiiipppp),(21gbestDgbestgbestgb

30、estpppp),(21iDiiixxxx),(21iDiiivvvv华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w粒子速度和位置的更新粒子速度和位置的更新 其中，其中，w w称为惯性权重，称为惯性权重，c c1 1和和c c2 2为两个正常数，称为两个正常数，称 为加速因子。为加速因子。将将 v vididk k 限制在一个最大速限制在一个最大速 度度 v vmax max 内。内。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211xkvkp

31、pgbestxk+1vk+1kkk+1k+1华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w粒子速度和位置的更新粒子速度和位置的更新 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211“惯性部分惯性部分”，对自身运动状对自身运动状态的信任态的信任“认知部分认知部分”，对微，对微粒本身的思考，即来粒本身的思考，即来源于自己经验的部分源于自己经验的部分“社会部分社会部分”，微粒间的，微粒间的信息共享，来源于群体中信息共享，来源于群体中的其它优秀微粒的

32、经验的其它优秀微粒的经验华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w迭代过程迭代过程 华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w算法流程算法流程 StartStartInitialize particles with random positionInitialize particles with random position and velocity vectors.and velocity vectors.For each particles position(For each pa

33、rticles position(x xi i)evaluate fitnessevaluate fitnessIf fitness(If fitness(x xi i)better than)better than fitness(fitness(p p)then)then p p=x xi iLoop until all Loop until all particles particles exhaustexhaustSet best of Set best of p ps as s as gBestgBestUpdate particles velocity andUpdate part

34、icles velocity and position positionLoop until max Loop until max iteriterStop:giving Stop:giving gBestgBest,optimal solution.,optimal solution.华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w惯性权重惯性权重w w 使粒子保持运动惯性，使其有扩展搜索空间的使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。趋势，有能力探索新的区域。表示微粒对当前自身运动状态的信任，依据自表示微粒对当前自身运

35、动状态的信任，依据自身的速度进行惯性运动。身的速度进行惯性运动。较大的较大的w w有利于跳出局部极值，而较小的有利于跳出局部极值，而较小的w w有利有利于算法收敛。于算法收敛。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w加速常数加速常数c c1 1和和c c2 2 代表将微粒推向代表将微粒推向pbestpbest和和gbestgbest位置的统计加速位置的统计加速项的权重。项的权重。表示粒子的

36、动作来源于自己经验的部分和其它表示粒子的动作来源于自己经验的部分和其它粒子粒子 经验的部分。经验的部分。低的值允许粒子在被拉回之前可以在目标区域低的值允许粒子在被拉回之前可以在目标区域外徘外徘 徊，而高的值则导致粒子突然冲向或越过目标徊，而高的值则导致粒子突然冲向或越过目标区区 域。域。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w加速常数加速常数c c1 1和和c c2 2 将将c c1 1和

37、和c c2 2统一为一个控制参数，统一为一个控制参数，=c c1 1+c c2 2 如果如果很小，微粒群运动轨迹将非常缓慢；很小，微粒群运动轨迹将非常缓慢；如果如果很大，则微粒位置变化非常快；很大，则微粒位置变化非常快；实验表明，当实验表明，当=4.14.1（通常（通常c c1 1=2.0=2.0，c c2 2=2.0=2.0）时，）时，具有很好的收敛效果。具有很好的收敛效果。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w粒子数粒子数 一般取一般取20204040，对较难或特定类别的问题可以，对较难或特定类别的问题可以取取 1001002002

38、00。w最大速度最大速度v vmaxmax 决定粒子在一个循环中最大的移动距离，通常决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。设定为粒子的范围宽度。w终止条件终止条件 最大循环数以及最小错误要求。最大循环数以及最小错误要求。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w共性共性 （1 1）都属于仿生算法；）都属于仿生算法；（2 2）都属于全局优化方法；）都属于全局优化方法；（3 3）都属于随机搜索算法；）都属于随机搜索算法；（4 4）都隐含并行性；）都隐含并行性；（5 5）根据个体的适配信息进行搜索，因此不受）根据个体的适配

39、信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；函数约束条件的限制，如连续性、可导性等；（6 6）对高维复杂问题，往往会遇到早熟收敛和）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。收敛性能差的缺点，都无法保证收敛到最优点。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w差异差异 （1 1）PSOPSO有记忆，所有粒子都保存较优解的知有记忆，所有粒子都保存较优解的知识，而识，而GAGA，以前的知识随着种群的改变被改变；，以前的知识随着种群的改变被改变；（2 2）PSOPSO中的粒子是一种单向共享信息机

40、制。中的粒子是一种单向共享信息机制。而而GAGA中的染色体之间相互共享信息，使得整个种群中的染色体之间相互共享信息，使得整个种群都向最优区域移动；都向最优区域移动；（3 3）GAGA需要编码和遗传操作，而需要编码和遗传操作，而PSOPSO没有交叉没有交叉和变异操作，粒子只是通过内部速度进行更新，因和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。此原理更简单、参数更少、实现更容易。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w用途用途 基本基本PSOPSO是用来解决连续问题优化的，离散二进是用来解决连续问题优化的，

41、离散二进制制PSOPSO用来解决组合优化问题。用来解决组合优化问题。w运动方程不同运动方程不同 粒子的位置只有粒子的位置只有(0,1)(0,1)两种状态。速度值越大，两种状态。速度值越大，则粒子位置取则粒子位置取1 1的可能性越大，反之越小。的可能性越大，反之越小。维分量。的第是随机矢量dvvSxelsexthenvS ifxprandcxprandcwvvkikidkidkidkidkidkidkidkidgbestkididkidkid11111111211 1,0 ,)exp(11)(0 ;1 )()()()()(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720

42、072007年年年 w思路思路 在考虑实际优化问题时在考虑实际优化问题时，往往希望先采用全局往往希望先采用全局搜索搜索，使，使搜索空间快速收敛于某一区域搜索空间快速收敛于某一区域，然后采用然后采用局部精细搜索以获得高精度的解。局部精细搜索以获得高精度的解。研究发现，较大的研究发现，较大的 w w 值有利于跳出局部极小点，值有利于跳出局部极小点，而而 较小的较小的 w w 值有利于算法收敛，因此提出了自适值有利于算法收敛，因此提出了自适应调应调 整的策略，即随着迭代的进行，线性地减小整的策略，即随着迭代的进行，线性地减小 w w 的的 值。值。华东理工大学自动化系华东理工大学自动化系华东理工大学

43、自动化系 200720072007年年年 w变化的惯性权重变化的惯性权重 w wmaxmax、w wminmin分别是分别是w w的最大值和最小值；的最大值和最小值；iteriter、iteritermaxmax分别是当前迭代次数和最大迭代次数。分别是当前迭代次数和最大迭代次数。iteriterwwwwmaxminmaxmax华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w提出提出 19991999年年ClercClerc对算法的研究证明，采用收敛因子对算法的研究证明，采用收敛因子能能 够确保算法的收敛够确保算法的收敛。w收敛因子模型收敛因子模型

44、 通常将通常将设为设为4.14.1，经计算，经计算k k为为0.7290.729。4,422)()(212211cckxprandcxprandcvkvkidgbestkididkidkid其中华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w主要研究方向主要研究方向 主要集中于对算法结构和性能的改善方面，包主要集中于对算法结构和性能的改善方面，包括：参数设置、粒子多样性、种群结构和算法的融括：参数设置、粒子多样性、种群结构和算法的融合。合。w发展方向发展方向 目前大部分成果都是通过大量试验获得的，缺目前大部分成果都是通过大量试验获得的，缺少对算法

45、机理的研究，对少对算法机理的研究，对PSOPSO中的参数分析没有实中的参数分析没有实质性的认识，还处于试验分析阶段。质性的认识，还处于试验分析阶段。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w交换子和交换序交换子和交换序 设设n n个节点的个节点的TSPTSP问题的解序列为问题的解序列为s s=(=(a ai i)，i i=1=1n n。定义交换子。定义交换子SO(SO(i i1 1,i i2 2)为交换解为交换解S S中的点中的点a ai i1 1和和a ai2i2，则，则S=S+SO(S=S+SO(i i1 1,i i2 2)为解为解S

46、S经算子经算子SO(SO(i i1 1,i i2 2)操操作后的新解。作后的新解。一个或多个交换子的有序队列就是交一个或多个交换子的有序队列就是交换序，记作换序，记作SSSS，SS=(SOSS=(SO1 1,SO,SO2 2,SO,SON N)。其中，。其中，SOSO1 1,SO,SON N等是交换子，之间的顺序是有意义的等是交换子，之间的顺序是有意义的,意味着所有的交换子依次作用于某解上。意味着所有的交换子依次作用于某解上。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w符号的定义符号的定义 若干个交换序可以合并成一个新的交若干个交换序可以合并

47、成一个新的交换序，定义换序，定义 为两个交换序的合并算子。为两个交换序的合并算子。设两个交换序设两个交换序SSSS1 1和和SSSS2 2按先后顺序作用按先后顺序作用于解于解S S上，得到新解上，得到新解SS。假设另外有一个交换序。假设另外有一个交换序SSSS作用于同一解作用于同一解S S上，能够得到形同的解上，能够得到形同的解SS，可定义，可定义21SSSSSS华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w符号的定义符号的定义 和和 属于同一属于同一等价集，在交换序等价集中，拥有最少交换子的交等价集，在交换序等价集中，拥有最少交换子的交换序称

48、为该等价集的基本交换序。换序称为该等价集的基本交换序。21SSSS SS华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w解决解决TSPTSP问题的速度算式定义问题的速度算式定义 、为为0,10,1上的随机数。上的随机数。v vidid表示交换序，表示交换序，x xidid表示路径序列（解）。表示路径序列（解）。ididididgdididididvxxxpxpvv)()(华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w算法流程算法流程 1.1.初始化粒子群，给每个粒子一个初始解初始化粒子群，给每个粒

49、子一个初始解(x xidid)和随机的交换序和随机的交换序(v vidid););2.2.如果满足结束条件，转步骤如果满足结束条件，转步骤5;5;3.3.根据粒子当前位置根据粒子当前位置x xidid计算下一新解计算下一新解x xidid;4.4.如果整个群体找到一个更好的解，更新如果整个群体找到一个更好的解，更新P Pgdgd，转步骤转步骤2;2;5.5.显示结果。显示结果。华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年年 w算法流程算法流程 3.3.根据粒子当前位置根据粒子当前位置x xidid计算下一新解计算下一新解x xidid:1 1）计算

50、）计算A=A=p pidid-x xidid，A A是一个基本交换序，表是一个基本交换序，表示示A A作用于作用于x xidid得到得到p pidid；2 2）计算）计算B=B=p pgdgd-x xidid，B B也是一个基本交换序；也是一个基本交换序；3 3）更新速）更新速度度 ，并将其转换为一个基本交换序；，并将其转换为一个基本交换序；4 4）更新解）更新解 ；5 5）如果找到一个更好得解，更新）如果找到一个更好得解，更新p pidid。idididvxx)()(idgdididididxpxpvv华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 200720072007年年