集群智能算法,6.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 集群智能优化的特点与不足,集群智能（ Swarm Intelligence, SI ） 人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等） 特点 个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。,优点 灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。 典型算法 蚁群算法（蚂蚁觅食） 粒子群算法（鸟群捕食）,集群智能算法,如何应用 用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题： 预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。 当数据量很大时，难以人为判别分类。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,如何应用 分类的规则： IF THEN 每个term是一个三元组（属性、关系符、属性取值） 希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,例：非典型肺炎 考虑如下因素：,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,例：非典型肺炎 结构图： 一个蚂蚁从始点行走至终点，得到一条路径0, 2, 1, 0，其对应的规则为 IF （职业其他人员）AND（胸部阴影无）THEN （非典型肺炎） 对此路径，应给予非常差的评价。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,蚁群算法的实现 假设a表示属性的总个数，第i个属性的取值域中可取bi个数值。一只蚂蚁的行走k步的路径可以表示为 routek=(y1,y2,ya) yi=0表示不包含属性i。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,评价函数 解的评价函数定义为： Q的数值越接近1，说明对该 类的判断越准确。 TPtrue positives TNtrue negatives FPfalse positives FNfalse negatives,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,True：判断结果，正确 False：判断结果，失误 Positives：真实属性，属于 Negatives：真实属性，不属于,转移概率 ij表示每个条件项的启发式参数值（信息熵），ij(t)表示第 i 个属性的第 j 个取值在 t 时刻的信息素。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,信息素增加 R是当前规则中所有包含的条件项； 信息素挥发 减少没被选中的三元组的信息量。,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,结果分析 诊断准确度比较,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,结果分析 诊断规则数比较,6.1 蚁群优化算法的应用,6.1.1 医学诊断的数据挖掘,由James Kenney（社会心理学博士）和Russ Eberhart（电子工程学博士， http:/www.engr.iupui.edu/eberhart/ ）于1995年提出粒子群算法（Particle Swarm Optimization, PSO）,6.2 粒子群算法的基本原理,6.2.1 粒子群算法的提出,源于对鸟群捕食行为的研究，是基于迭代的方法 简单易于实现，需要调整的参数相对较少 在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。,6.2 粒子群算法的基本原理,6.2.1 粒子群算法的提出,鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。 PSO算法 每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。,6.2 粒子群算法的基本原理,6.2.2 粒子群算法的原理描述,PSO算法 初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来 更新自己的位置。,6.2 粒子群算法的基本原理,6.2.2 粒子群算法的原理描述,粒子速度和位置的更新 假设在D维搜索空间中，有m个粒子； 其中第i个粒子的位置为矢量 其飞翔速度也是一个矢量，记为 第i个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为 第i个粒子的位置和速度更新为：,6.3 基本粒子群优化算法,6.3.1 基本粒子群算法描述,粒子速度和位置的更新 其中，w称为惯性权重， c1和c2为两个正常数，称 为加速因子。 将 vidk 限制在一个最大速 度 vmax 内。,6.3 基本粒子群优化算法,6.3.1 基本粒子群算法描述,粒子速度和位置的更新,6.3 基本粒子群优化算法,6.3.1 基本粒子群算法描述,“惯性部分”，对自身运动状态的信任,“认知部分”，对微粒本身的思考，即来源于自己经验的部分,“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验,迭代过程,6.3 基本粒子群优化算法,6.3.1 基本粒子群算法描述,算法流程,6.3 基本粒子群优化算法,Start,Initialize particles with random position and velocity vectors.,For each particles position (xi) evaluate fitness,If fitness(xi) better than fitness(p) then p= xi,Loop until all particles exhaust,Set best of ps as gBest,Update particles velocity and position,Loop until max iter,Stop: giving gBest, optimal solution.,6.3.1 基本粒子群算法描述,惯性权重w 使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。 表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。 较大的w有利于跳出局部极值，而较小的w有利于算法收敛。,6.3 基本粒子群优化算法,6.3.2 参数分析,加速常数c1和c2 代表将微粒推向pbest和gbest位置的统计加速项的权重。 表示粒子的动作来源于自己经验的部分和其它粒子 经验的部分。 低的值允许粒子在被拉回之前可以在目标区域外徘 徊，而高的值则导致粒子突然冲向或越过目标区 域。,6.3 基本粒子群优化算法,6.3.2 参数分析,加速常数c1和c2 将c1和c2统一为一个控制参数，= c1+c2 如果很小，微粒群运动轨迹将非常缓慢； 如果很大，则微粒位置变化非常快； 实验表明，当=4.1（通常c1=2.0，c2=2.0）时，具有很好的收敛效果。,6.3 基本粒子群优化算法,6.3.2 参数分析,粒子数 一般取2040，对较难或特定类别的问题可以取 100200。 最大速度vmax 决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。 终止条件 最大循环数以及最小错误要求。,6.3 基本粒子群优化算法,6.3.2 参数分析,共性 （1）都属于仿生算法； （2）都属于全局优化方法； （3）都属于随机搜索算法； （4）都隐含并行性； （5）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等； （6）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。,6.3 基本粒子群优化算法,6.3.3 与遗传算法的比较,差异 （1）PSO有记忆，所有粒子都保存较优解的知识，而GA，以前的知识随着种群的改变被改变； （2）PSO中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群都向最优区域移动； （3）GA需要编码和遗传操作，而PSO没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。,6.3 基本粒子群优化算法,6.3.3 与遗传算法的比较,共同特点 基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性； 存在的问题 （1）数学理论基础相对薄弱； （2）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；,6.4 集群智能优化的特点与不足,存在的问题 （3）比较性研究不足，缺乏用于性能评估的标准测试集； （4）不具备绝对的可信性，存在应用风险；,6.4 集群智能优化的特点与不足,进一步的工作 （3）进一步提高收敛速度，从而解决大规模优化问题； （4）进一步研究各种参数设置问题； （5）研究群智能的并行算法； （6）进一步研究各算法的适用范围； （7）研究与其它算法的混合技术。,6.4 集群智能优化的特点与不足,