《计算智能补充》PPT课件.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 集群智能优化的特点与不足,集群智能（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 集群智能优化的特点与不足,