《计算智能补充》PPT课件

集群智能算法,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集群智能优化的特点与不足,集群智能（SwarmIntelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）特点个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。,描述集群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。,集群智能算法,优点灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）,集群智能算法,如何应用用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。,6.1蚁群优化算法的应用,6.1.1医学诊断的数据挖掘,如何应用分类的规则：IFTHEN每个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，说明对该类的判断越准确。TPtruepositivesTNtruenegativesFPfalsepositivesFNfalsenegatives,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医学诊断的数据挖掘,由JamesKenney（社会心理学博士）和RussEberhart（电子工程学博士，/eberhart/）于1995年提出粒子群算法（ParticleSwarmOptimization,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,Initializeparticleswithrandompositionandvelocityvectors.,Foreachparticlesposition(xi)evaluatefitness,Iffitness(xi)betterthanfitness(p)thenp=xi,Loopuntilallparticlesexhaust,SetbestofpsasgBest,Updateparticlesvelocityandposition,Loopuntilmaxiter,Stop:givinggBest,optimalsolution.,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集群智能优化