计算智能补充

集群智能算法

16.1蚁群优化算法的应用

6.1.1典型应用

6.1.2医学诊断的数据挖掘6.2粒子群算法的基本原理

6.2.1粒子群算法的提出

6.2.2粒子群算法的原理描述6.3基本粒子群优化算法

6.3.1基本粒子群算法描述

6.3.2参数分析

6.3.3与遗传算法的比较6.4集群智能优化的特点与不足2集群智能（SwarmIntelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）

特点

个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。3描述集群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。集群智能算法4优点灵活性：群体可以适应随时变化的环境；

稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）集群智能算法5如何应用

用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。

6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘6如何应用分类的规则：

IF<term1ANDterm2AND…>THEN<class>

每个term是一个三元组（属性、关系符、属性取值）希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘7例：非典型肺炎考虑如下因素：

6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘属性发热职业胸部阴影流行病学史值（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：其他人员0：不考虑该属性1：无2：有0：不考虑该属性1：无2：有8例：非典型肺炎结构图：

一个蚂蚁从始点行走至终点，得到一条路径{0,2,1,0}，其对应的规则为

IF（职业＝其他人员）AND（胸部阴影＝无）THEN（非典型肺炎）对此路径，应给予非常差的评价。6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘9蚁群算法的实现

假设a表示属性的总个数，第i个属性的取值域中可取bi个数值。一只蚂蚁的行走k步的路径可以表示为

route[k]=(y1,y2,…,ya)

yi=0表示不包含属性i。6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘10评价函数

解的评价函数定义为：

Q的数值越接近1，说明对该类的判断越准确。

TP—truepositivesTN—truenegativesFP—falsepositivesFN—falsenegatives6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘True：判断结果，正确False：判断结果，失误Positives：真实属性，属于Negatives：真实属性，不属于11转移概率

ηij表示每个条件项的启发式参数值（信息熵），τij(t)表示第i个属性的第j个取值在t时刻的信息素。6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘12信息素增加

R是当前规则中所有包含的条件项；信息素挥发

减少没被选中的三元组的信息量。6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘13结果分析

诊断准确度比较

6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘数据库蚁群优化算法CN2LjubljanabreastcancerWisconsinbreastcancerTic-tac-toeDermatologyHepatitisClevelandheartdisease75.28±2.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.7814结果分析

诊断规则数比较

6.1蚁群优化算法的应用6.1.1医学诊断的数据挖掘数据库蚁群优化算法CN2LjubljanabreastcancerWisconsinbreastcancerTic-tac-toeDermatologyHepatitisClevelandheartdisease7.10±0.316.20±0.258.50±0.627.30±0.153.40±0.169.50±0.9255.40±2.0718.60±0.4539.70±2.5218.50±0.477.20±0.2542.40±0.7115由JamesKenney（社会心理学博士）和RussEberhart（电子工程学博士，

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

6.2粒子群算法的基本原理6.2.1粒子群算法的提出16源于对鸟群捕食行为的研究，是基于迭代的方法简单易于实现，需要调整的参数相对较少在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。6.2粒子群算法的基本原理6.2.1粒子群算法的提出17鸟群：假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。PSO算法

每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。6.2粒子群算法的基本原理6.2.2粒子群算法的原理描述18PSO算法

初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来更新自己的位置。6.2粒子群算法的基本原理6.2.2粒子群算法的原理描述19粒子速度和位置的更新

假设在D维搜索空间中，有m个粒子；其中第i个粒子的位置为矢量其飞翔速度也是一个矢量，记为第i个粒子搜索到的最优位置为整个粒子群搜索到的最优位置为第i个粒子的位置和速度更新为：6.3基本粒子群优化算法6.3.1基本粒子群算法描述20粒子速度和位置的更新

其中，w称为惯性权重，

c1和c2为两个正常数，称为加速因子。将vidk限制在一个最大速度vmax内。6.3基本粒子群优化算法6.3.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+121粒子速度和位置的更新

6.3基本粒子群优化算法6.3.1基本粒子群算法描述“惯性部分”，对自身运动状态的信任“认知部分”，对微粒本身的思考，即来源于自己经验的部分“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验22迭代过程

6.3基本粒子群优化算法6.3.1基本粒子群算法描述23算法流程

6.3基本粒子群优化算法StartInitializeparticleswithrandompositionandvelocityvectors.Foreachparticle’sposition(xi)evaluatefitnessIffitness(xi)betterthanfitness(p)thenp=xiLoopuntilallparticlesexhaustSetbestofpsasgBestUpdateparticlesvelocityandpositionLoopuntilmaxiterStop:givinggBest,optimalsolution.6.3.1基本粒子群算法描述24惯性权重w

使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。较大的w有利于跳出局部极值，而较小的w有利于算法收敛。6.3基本粒子群优化算法6.3.2参数分析25加速常数c1和c2

代表将微粒推向pbest和gbest位置的统计加速项的权重。表示粒子的动作来源于自己经验的部分和其它粒子经验的部分。低的值允许粒子在被拉回之前可以在目标区域外徘徊，而高的值则导致粒子突然冲向或越过目标区域。

6.3基本粒子群优化算法6.3.2参数分析26加速常数c1和c2

将c1和c2统一为一个控制参数，φ=c1+c2

如果φ很小，微粒群运动轨迹将非常缓慢；如果φ很大，则微粒位置变化非常快；实验表明，当φ=4.1（通常c1=2.0，c2=2.0）时，具有很好的收敛效果。6.3基本粒子群优化算法6.3.2参数分析27粒子数

一般取20～40，对较难或特定类别的问题可以取

100～200。最大速度vmax

决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。终止条件

最大循环数以及最小错误要求。6.3基本粒子群优化算法6.3.2参数分析28共性

（1）都属于仿生算法；（2）都属于全局优化方法；（3）都属于随机搜索算法；（4）都隐含并行性；（5）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；（6）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。6.3基本粒子群优化算法6.3.3与遗传算法的比较29差异

（1）