粒子群优化算法研究（精选11篇）
粒子群优化算法研究 篇1
(一) 引言
粒子群算法 (Particle Swarm Optimization;PSO) , ) 是一种新型的群体智能算法, 由Eberhart博士和kennedy博士于1995年提出, 其基本思想起源于对鸟群捕食行为的研究。与其他优化算法相比, PSO收敛速度快、易实现并且仅有少量参数需要调整, 因而一经提出就成为智能优化与进化计算领域的一个新的研究热点, 目前己经被广泛应用于目标函数优化、动态环境优化、神经网络训练、数据挖掘、模糊控制系统等许多领域。
(二) 基本粒子群算法
标准 (PSO) 粒子群算法主要根据下面两个式子进行演化计算的:
即每个粒子的新位置由原有位置加上速度组成, 而速度由其原速度、粒子最优位置以及所有粒子最优位置共同决定。其中:ω为惯性权值, iv (t) 粒子i于t时刻的飞行速度, ix (t) 为粒子i当前的位置, ip (t) 为粒子i所经过的位置中的最好位置, p g (t) 为所有粒子经历过的位置中的最好位置, 1c和2c为加速系数, ω、1c和c2为一固定常数, 1r和r2是两个在[0, 1]范围内变化的随机数。式 (1) 的第1部分由粒子先前速度的惯性引起, 为“惯性”部分;第2部分为“认知”部分, 表示粒子本身的思考, 即粒子本身的信息对自己下一步行为的影响;第3部分为“社会”部分, 表示粒子间的信息共享和相互合作, 即群体对粒子下一步行为的影响。
(三) 粒子群优化算法的改进
到目前为止, 对PSO算法的改进非常多, 但是总共可以归结为以下几种目的:增强算法自适应性的改进, 增强收敛性的改进、增加种群多样性的改进、加强局部搜索的改进、与全局优化算法相结合、与确定性的局部优化算法融合等。以上所述的是对于算法改进的目的讨论的, 实际改进中应用的办法有基于参数的改进, 即对PSO算法的迭代公式的形式上作改进:还有从粒子的行为模式进行改进, 即粒子之间的信息交流方式, 如拓扑结构的改进、全局模式与局部模式相结合的改进等;还有基于算法融合的粒子群算法的改进, 算法融合可以引入其他算法的优点来弥补PSO算法的缺点, 设计出更适合问题求解的优化算法。下面主要介绍儿种具有代表性的改进PSO算法。
1. 加入惯性权重的粒子群模型
shi等对式 (1) 做了如下的改动:
其中w是非负数, 称为惯性权重 (inertiaweight) 。
惯性权重w是用来控制粒子以前速度对当前速度的影响的, 即粒子对自己以前速度的信任程度, 它将影响粒子的全局和局部搜索能力。较大的w值有利于全局搜索, 较小的w有利于局部搜索。选择一个合适的w可以平衡全局和局部搜索能力, 即平衡算法的收敛速度和收敛精度, 这样可以以最少的迭代次数找到最优解。
2. 压缩因子PSO算法
PSO算法来源于模拟社会系统, 算法本身缺乏坚实的数学基础。直到最近几年才开始尝试建立算法的数学基础。Clerc于1999年对算法的数学研究证明, 提出了压缩因子的概念[20]。该方法描述了一种选选择ω和cl、c2的方法, 以保证算法收敛。算式如下:
其中为压缩因子, 的作用类似于Vmax的作用, 用来控制与约束粒子的飞行速度, 同时增强算法的局部搜索能力。Shi和Eberhart将惯性权重PSO模型和带收敛因子PSO模型进行了比较, 通过对Sphere, Rosenbroek, Rastrigrin, Griewank和sehaffer F6等五个测试函数的实验后指出, 当将Vmax端限定为Xmax时, 收敛因子PSO模型的计算结果好于惯性权重PSO模型的计算结果。因而压缩因子方法控制群体行为最终收敛, 且可以有效搜索不同的区域, 该算法能得到高质量的解, 较好的克服PSO算法的早熟收敛。
3. 带选择机制的PSO
基本PSO没有选择机制, 粒子个体不会被别的粒子个体所取代, 迭代时, 每个粒子不断地改变自己的位置直到搜索结束。带选择机制的PSO算法依据某些预定的规则, 将每个个体的适应值, 基于其当前位置, 与其它个体进行比较, 然后根据定义的规则将所有个体排序, 得分最高的出现在群体的前面。一旦群体排序完毕, 群体中当前得分低的一半被群体中当前得分高的另一半取代。带选择机制的PSO在解决单峰函数的优化问题时效果明显, 但并不一定对所有的优化问题都很有效。这种算法由于有了选择机制, 加快了对当前较好区域的开发过程使得收敛速度较快, 但也增加了陷入局部极值解的可能性。
借鉴遗传算法的思想, 提出了杂交PSO的概念, 将基本PSO和选择机制相结合, 进一步提出具有繁殖和子群的杂交PSO。杂交PSO的选择机制与遗传算法十分相似。该法按预定的准则, 给粒子群中的每个粒子赋予一个繁殖概率, 在每次迭代中, 依据繁殖概率的高低选取一定数量的粒子放入一池中。池中的粒子随机地两两杂交, 产生与父代粒子数目相同的子代粒子, 并用子代粒子代替父代粒子, 以保持种群的粒子数目不变。子代粒子的位置由父代粒子位置的算术加权和计算。实验结果显示, 杂交PSO的收敛速度比较快, 搜索精度相对比较高, 对一些非线性优化问题可以得到满意的结果, 尤其是对多峰值函数优化问题具有更好的性能。
4. 带空间邻域的PSO
尽管PSO能比其它进化算法更快地得到较为理想的解, 但当迭代次数增加时, 并不一定能进行更精确的搜索。为此, 可引入一个变化的邻域算子, 在迭代的初始阶段, 一个粒子的邻域就是它本身;随着迭代的进行, 根据候选个体与邻域中心的距离, 逐步引入距离近的个体, 邻域逐渐变大, 包含越来越多的粒子, 最后包含所有的粒子。这样, 原来的全局历史最好位置搜索就变成了粒子邻域的局部历史最好位置搜索。
结合空间邻域和环状拓扑结构, 提出了具有社会模式的聚类分析PSO。该法将粒子群体中的一些粒子作为中心, 再将离它最近的N个粒子和中心粒子作为一簇, 然后计算每个簇的中心位置, 并用这些中心位置替代个体历史最优位置和全局历史最优位置。
5. 其它方面的改进
文献[4]提出适应性粒子群寻优算法 (APSO) , 社会性的群体寻优是秩序与混沌之间的平衡, 适应性微粒群寻优算法 (APSO) 是在标准PSO上添加反映适应性的随机项, 并引入小概率因子, 使微粒飞行到粒子群的中心, 平衡秩序和随机两个行为, 从而使得寻优的决策尽可能模拟社会性群体寻优的复杂行为。典型复杂函数优化的仿真结果表明, APSO算法具有较好的稳定性, 但精确度不高。
(四) 粒子群优化算法的应用
粒子群优化 (PSO) 算法具有很强的通用性, 且无需问题的特殊信息, 因此, 其应用领域非常广泛。目前主要的应用领域包括: (1) 训练人工神经网络。PSO可完成人工神经网络中的各种任务, 包括连接权值的训练、结构设计、学习规则调整、输入特征选取、连接权值的初始化和规则提取等。 (2) 跟踪动态系统。 (3) 解决多目标优化问题。 (4) 求解约束满足问题。 (5) 与控制工程问题的结合, 如PID调节问题的研究、ARMAX模型的辨识和预报研究等。 (6) 应用到动力系统, 包括供电系统的工作条件、反应动力和电压的控制、电容器的布置等。 (7) 数据挖掘。总的说来, 其他进化算法能够求解的问题或者能够转化为优化的问题, PSO算法均能够求解。
Kassabalidis等利用PSO实现对卫星无限网络路由的自适应调整, 提高网络容量的有效利用率。Robinsonj, SintonS和Rahmat Samii将PSO用于PCHA (剖面波状喇叭天线) 的优化设计, 并与GA的优化效果进行了比较, 在此基础上又研究了二者混合应用的可行性。其中所完成的一系列实验证实PSO作为一种新型的优化算法具备解决复杂工程优化问题的能力。Engelbrechtap利用PSO实现了对人工神经网络权值和网络模型结构的优化, 并将研究结果应用于“自然语言组词”的分析方法设计。Hux采用经PSO优化的神经网络实现了对人类肢体颤抖现象的分析, 并完成了对正常颤抖和帕金森氏症的诊断功能。在疾病和乳腺肿瘤是良性和恶性的判断、心脏病的诊断, PSO训练的神经网络也取得了较高的诊断成功率。EIHawary, ME Sallam, KalaS同样采用PSO对神经网络进行了优化, 并利用其设计了电力变压器的智能保护机制。YoshidaH, KawataK, FukuyamaY, Nakanishi利用PSO实现了对各种连续和离散控制变量的优化, 从而达到了控制核电机组电流稳定输出电压的目的。
除了以上领域外, PSO在自动目标检测、生物信号识别、决策调度、系统辨识以及游戏训练、分类、信号处理、机器人应用等方面也取得了一定的成果。目前在模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、语音识别、烧伤诊断、探测移动目标、时频分析和图象分割等方面己经有成功应用的先例。
(五) 结束语
PSO算法通过个体之间的协作来搜寻最优解, 它利用了生物群体中信息共享的思想, 其概念简单, 易于实现, 同时又有深刻的智能背景, 即适合科学研究, 又特别适合工程应用。因此, 越来越受到人们的重视, 而且应用也越来越广泛。但是, PSO的发展历史尚短, 在理论基础与应用推广上都还存在一些问题有待解决。
摘要：文章介绍了传统的粒子群算法的基本原理、数学模型、算法流程、算法参数等, 并且介绍了传统算法存在的一些问题及近年来进行改进和研究工作, 以及粒子群算法的应用。
关键词：粒子群,收敛速度,应用
参考文献
[1]Kennedy J, Eberhart R.Particle Swarm Optimization[A].IEEE Int Conf on Neural Networks[C].Perth, 1995:1942-1948.
[2]Angeline P J.Evolutionary Optimization Versus Particle Swarm Optimization:Philosophy and Performance Differences[J].Evolutionary Programming, 1998, 256-260.
[3]任斌, 丰镇平.改进遗传算法与粒子群优化算法及其对比分析[J].南京师范大学学报, 2002, 2 (2) :14-2.
[4]罗辞勇, 陈民铀.适用性粒子群寻优算法[J].控制与决策, 2008, 23 (10) :1135-1138.
[5]高鹰, 谢胜利, 免疫粒子群优化算法[J].计算机工程与应用, 2004 (6) :4-7.
粒子群优化算法研究 篇2
基于粒子群算法的并联机构结构参数优化设计
介绍了粒子群优化算法的原理和实现方法,分析了该算法的主要参数对搜索性能的`影响,并把粒子群算法用于六自由度的并联机构的参数优化设计中,取得了较好的效果,试验证明,粒子群算法是一种有效的优化方法,适用于大型复杂结构的优化设计.
作 者：孙凡国 黄伟 KONG Fan-guo HUANG Wei 作者单位：五邑大学,机电工程系,广东,江门,529020刊 名：机械设计与研究 ISTIC PKU英文刊名：MACHINE DESIGN AND RESEARCH年，卷(期)：22(3)分类号：V221.6关键词：粒子群优化算法 进化计算 优化设计
粒子群优化算法研究 篇3
关键词：计算机神经网络；粒子群优化算法；应用
中图分类号：TP183
粒子群优化算法是一种相对简单、有效的随机全局优化技术，通过对粒子群优化算法进行相应的改进，以此确保其收敛性，然后再将粒子群优化算法应用到神经网络的学习训练中，能够更有效的找出最优化解。粒子群优化算法和遗传算法相比，粒子群优化算法并没有遗传算法复杂的交叉、变异以及编码，而是对粒子所在解空间的具体位置进行搜索，不需要对众多的参数进行调整，其收敛速度相对较快。
1 粒子群优化算法的基本原理以及优化改进
1.1 粒子群吧优化算法的基本原理
PSO中，每一个优化问题的解都是搜集空间中的一个“粒子”的状态，粒子群优化算法是对群体的全局进行考虑，通过迭代搜寻选取最优值，通过将系统转化成一组随机的例子，由于例子在解空间追随最优的例子进行凑所，所以粒子群优化算法是一种具有全局寻优能力的优化工具。例子群优化算法的基本原理表现为：假设在一个D维的目标搜集中间中，由N个不同的粒子组成了一个特定的群体，其中第i个粒子表示成其在这个D维空间中的向量（xi），也就是该粒子在D为空间中的位置，每一个粒子的位置都存在一个特定的解，通过将xi带入到相应的目标函数中，通过适当的函数计算就能得到其适应度值，然后根据该xi适应度值的大小，以此衡量xi的优劣程度。其中，第i个粒子飞行的速度表示D维中的另一个向量，表示为vi，将在D维空间中搜索到的第i个粒子的最有位置记录为pi，则整个粒子群搜索到的最有位置pi的粒子群优化算法表现为：公式一：vi=ci+c1r1（pi-xi）+c2r2（pg-xi）；公式二：vik+1=vik+c1×rand（）×（pbest-xik）+c2×rand（）×（gbest-xik）；公式三：xi=xi+vi，其中i=1，2，…N；r1和r2为学习因子，rand（）表示介于[0，1]之间的随机常数，c1和c2表示为非负常数。其中迭代的终止条件是根据选择的最大迭代次数决定的，表示的为第i个李在迄今为止搜索到的最优化位置应该满足的适应度的最小值。
从社会学角度方面来说，粒子群优化算法公式中的表示的是粒子的记忆项以及自身认知项，能够表示上次速度的方向以及大小对粒子造成的影响，还能够将当前的指向粒子当作自身的最优化矢量，以此表示粒子的动作来源于自身的经验，能够反映粒子之间的协同作用以及知识共享，粒子能够根据粒子群中相邻粒子的最好经验，然后再结合自身的经验，以此来决定自身的下一步运动，从而形成PSO的标准形式。
1.2 粒子群优化算法的改进
粒子群粒子群优化算法需要用户确定的参数相对较少，并且其操作相对简单，因此该种方法使用起来非常方便，但是，由于粒子群优化算法容易陷入局部极值点，导致搜索的收敛性相对较低，并且粒子群优化算法的收敛性分析已经收到众多学者的重视，因此，为了增强粒子群优化算法的收敛性，可以将抗体多样性保持机制引入到粒子群优化算法中，其步骤表现为：首先，确定参数值，记忆粒子个数M，即常数因子c1和c2粒子群的个数N，粒子的浓度概率选择阀值Pi，其随机产生的N个粒子xi的飞行速度表示为vi，以此计算粒子的适应度函数值；根据公式计算粒子的选择概率，将粒子群体中前M个最大适应度的粒子当作记忆细胞进行储存，将概率大于Pi的粒子根据相应的方法进行计算，从而把M个记忆细胞替换成适应度最差的M个粒子，以此形成全新的粒子群，最终判断其能付满足相应的选择条件，如果满足输出适应度值最好的要求，则选定该粒子。由此可见，通过上述的方法对粒子群优算法进行改进，能够保证粒子群优化算法的精确性，并且通过实践证明，经过改进后的粒子群优化算法，其计算机的仿真结果显示，该种粒子群优化算法的收敛速度明显优于没有改进的粒子群优化算法的收敛速度。
2 粒子群优化算法在计算机审计网络中的应用
计算机神经网络能够模拟大脑的思维能力，然后通过对各种数据进行分析，从而建立其相应的数学模型，计算机神经网络中除了包含许多处理器以外，还包含了许多与人脑神经相似的节点，这些节点按照一定的规律进行连接。如果将计算机神经网络中的每一个过程都细分为若干个微程序，并且将所有的微程序都交付于处理器进行处理，那么处理器处理所有的微程序的过程，就是一条微程序的处理流水线，这样计算机处理信息的速度也将会显著的提高。粒子群优化算法在计算机神经网络中的应用，包括的内容有组合优化、参数优化、神经网络训练、学习算法、网络拓扑结构和传递函数、链接权重等，通过把个体转化成微粒，其中包括计算机神经网络中的所有能够用到的参数，然后经过一些列的复杂、重复的程序，最终达到最终的训练目标。相对于传统的神经训练法来说，由于BP算法需要可微的函数以及梯度信息等大量的数据，只有通过大量的计算才能得到相应的训练结果，其运行难度较大、程序相对复杂，而采用离子群优化算法，其处理信息的速度显著的提升，能够有效的克服其运行效率低的问题。粒子群优化算法在计算机神经系统网络中的应用，主要表现在两个方面：其一，粒子区优化算法在参数优化中的应用，能够通过解决计算机神经网络中的各种离散型问题，从而进行参数优化；其二，粒子群优化算法在组合优化中的应用，其中典型的应用表现为其在工程经济问题中的应用，其能够通过将各种资源进行科学的组合，通过设置一定的约束条件对这些组合进行排序，通过不断的尝试最终能够找到最有效的解决方案，然后合理的利用所有的组合实现经济效益的最大化。此外，粒子群优化算法不仅能够应用在计算机神经网络中，还能够应用在更多的领域中，例如软件编辑、游戏开发、电力系统等领域中。
3 结束语
文章对计算机神经网络中粒子群优化算法的应用进行了研究，对粒子群优化算法进行了相应的改进，有效的提高了粒子群优化算法的收敛速度。将粒子群优化算法应用在计算机神经网络中，其操作相对简单，比较容易实现，并且其还能够更快的收敛于最优解，有效的克服了传统遗传算法缺点。因此，在计算机神经网络学习训练中，广泛的推广和应用粒子群优化算法具有很大的现实意义。
参考文献：
[1]丁玲，范平，闻彬.粒子群优化算法在计算机神经网络中的应用[J].理论与算法，2013（17）：39-41.
[2]曹大有.一种免疫粒子群优化算法及在小波神经网络学习中的应用[J].计算机应用于软件，2009（06）：189-192.
[3]刘爱军，杨育，李斐.混沌模拟退火粒子群优化算法研究及应用[J].浙江大学学报（工学版），2013（10）：1722-1729.
[4]虞斌能，焦斌，顾幸生.改进协同粒子群优化算法及其在Flow Shop调度中的应用[J].华东理工大学学报（自然科学版），2009（03）：468-474.
[5]刘宝宁，章卫国，李广文.一种改进的多目标粒子群优化算法[J].北京航空航天大学学报，2013（04）：458-473.
作者简介：张小军（1980.01-），男，河南人，讲师，研究方向：云计算，数据挖掘，通信技术。
粒子群优化算法研究 篇4
演化算法是经典的不确定性算法, 通过将大自然中各类事物的演化规律与求解问题的过程相结合, 能够保证在多项式时间内得到实际问题的高精度近似解。其中遗传算法、模拟退火算法、蚁群算法等演化算法都在生产实践中得到了广泛的应用。而粒子群算法因其结构简单易于实现, 成为当今研究的热点。但是, 粒子群算法参数优化方案仍然处在热烈讨论之中。针对这个问题, 本文选择了Linwpso以及Asylncpso两种优化算法[1]进行实验对比, 提出了粒子群算法参数优化的研究方向。
2 粒子群算法
粒子群算法, 也称粒子群优化算法 (Particle Swarm Optimization) , 缩写为PSO, 属于进化算法的一种, 1995年由Eberhart博士和kennedy博士提出, 源于对鸟群捕食的行为研究[1,2]。群体中的个体通过对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程, 从而获得最优解。
PSO模拟鸟群的捕食行为, 每个粒子就是解空间的一个解, PSO初始化为一群随机粒子 (随机解) , 然后通过迭代找到最优解。在每一次迭代中, 每个粒子根据自己的飞行经验和同伴的飞行经验所产生的两个“极值”来调整自己的飞行。一个是粒子本身所找到的最优解叫做个体极值p Best, 另一个是整个种群目前找到的最优解叫全局极值g Best。实际操作中通过由优化问题所决定的适宜性 (fitness value) , 来评价粒子的“好坏”程度。
在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置, 标准粒子群算法表达式如下所示:
其中, v是粒子的速度, w是惯性权重, present是当前粒子的位置。pbest是个体极值。gbest是全局极值。c1, c2是学习因子, 通常c1=c2=2。rand是 (0, 1) 间的随机数。
3 优化方案
W惯性权重控制了粒子的全局搜索能力与局部搜索能力之间的平衡。w值较大, 全局寻优能力强, 局部寻优能力弱;w值较小反之。初始时, w取为常数, 后来实验发现, 动态能够获得比固定值更好的寻优结果。动态可以在PSO搜索过程中线性变化, 也可根据PSO性能的某个测度函数动态改变。
c1、c2协同控制算法向最优解演化, 决定了收敛精度。
3.1 惯性权重优化方案
惯性权重优化方案的优化函数如下所示:
其中wmax表示惯性权重系数最大值, wmin表示惯性权重系数的最小值, t表示当前迭代次数, M表示迭代总次数。由此方案可见, 迭代过程开始时, 惯性权重系数取最大值wmax, 且惯性权重系数随着迭代次数线性递减。
3.2学习因子优化方案
学习因子优化方案函数如下所示:
4实验分析
本实验以求解单目标函数作为实验对象求出该函数的低误差近似最优解为算法终止目标。设定优化算法最大迭代300次。实验将粒子群标准算法、惯性权重优化的粒子群算法以及学习因子优化的粒子群算法进行对比, 分别利用三种粒子群算法求解实验对象最优解300次, 比对各个算法获得最优解的迭代次数, 以此评价3种算法的执行效率;对比3种算法的求解过程, 以此评价算法的可靠性和有效性。
实验中所采用的测试函数如公式 (1) 所示:
该函数在x=0.9350-0.9450达到最大值y=1.3706。
首先, 在群体中个体数量为3、5和8的情况下执行300次实验得到的迭代次数平均计算结果曲线, 由结果可见学习因子优化方法在每个实验场景中都有最高的变化率, 而权重优化方法的变化率则相对稳定, 而标准PSO算法变化率介于两者之间。但是当群体个体数量为3时, 学习因子的变化率过快则更倾向于算法早熟, 收敛于局部最优解;而惯性权重优化方法则用比标准算法更少的迭代次数就得到了相对准确的最优解。而当种群数量增加到8的时候, 学习因子优化方法展示出了它极大的优越性, 算法利用更少的迭代次数求得了实验对象函数的最优解。
接下来我们对群体中含有8个个体的情况进行进一步分析。观察300次实验过程, 发现学习因子优化方案仅通过平均14次迭代就能获得最优解, 且最高经过49次迭代。而标准粒子群算法需要17次迭代, 且最高近70次迭代。惯性权重优化算法需要24次迭代, 最大83次迭代。
综上所述实验可见, 当个体数量较少时, 惯性权重优化方案能够有效的改善算法效率且保障算法的有效性, 而当个体数量较高时, 学习因子优化方案能够改善算法效率。
5总结与展望
通过实验我们发现权重优化方案会让我们得到稳定的优化效果, 但是如果需要更高的求解效率时, 学习系数优化方案是一个不错的切入点。但是要用更为有效的方法控制系数的变化率。智能算法能够有效的求解NP问题获得不错的近似解, 同时也很容易和机器学习算法相结合, 各取所长。
参考文献
[1]龚纯, 精通MATLAB最优化计算[M].北京:清华大学出版社, 279-291.
[2]R Eberhart, J Kennedy.A new optimizer using particle swarm theory.In:Proc of the 6th Int’l Symposium on Micro Machine and Human Science.Piscataway, NJ:IEEE Service Certer, 1995.39-43.
一种改进的变异粒子群算法研究 篇5
粒子群优化算法PSO(Particle Swarm Optimization)是一类性能优越的寻优算法.但由于早熟问题,影响了算法性能的发挥.针对这一问题,引入粒子距离的概念,提出一种新的PSO改进方法(称为NA-PSO).通过求解组网雷达的系统偏差,表明了NA-PSO算法的`可行性,与对比方法相比较,能有效配准,且具有更好的收敛精度和更快的进化速度.
作 者：王波 李瑞涛 王灿林 朱丹 WANG Bo LI Rui-tao WANG Can-lin ZHU Dan 作者单位：王波,李瑞涛,王灿林,WANG Bo,LI Rui-tao,WANG Can-lin(海军航空工程学院,山东,烟台,624001)
朱丹,ZHU Dan(91550部队,辽宁,大连,116023)
改进的自适应多目标粒子群算法 篇6
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
智能算法中粒子群优化研究和实现 篇7
有优化作用的粒子群算法是主要应用在计算智能领域中。相比早期的智能算法如经典的蚁群算法和鱼群算法等, 它又是又一类群体智能的优化算法。该算法最早由Kennedy和Eberhart在1995年提出的。该算法的灵感来源于对鸟类捕食行为的研究。我们观察在鸟类捕食时, 对所有鸟来说, 找到食物最有效、简单的的数据信息就是由当前距离食物最近的周围区域的鸟群提供。粒子群算法就从这种生物种群行为特征受到启发并借鉴应用于求解优化问题的。在算法中可知优化问题每次的潜在存在的解集合都是由搜索空间中假定的“粒子”的状态决定, 每个粒子的适应度值由目标函数决定的, 它们飞翔的方向和距离由粒子的速度决定了。粒子由自身及同群同伙伴的飞行经验协调性地且动态地调整进行, 即粒子自己单个个体具备的最优解和整个种群所具备的最优解。如此反复在解空间中不断搜索, 如遇满足要求停止。本测试用例就是用PSO算法来求标准测试函数的极值, 表明该算法在系统极值寻优中的有效作用。
2 原理
放在N维的一个目标搜索空间中, 任意选取m个粒子组成一个群落, 把第i个粒子表示N维的向量, 从这样的表示中可得出第i个粒子在N维搜索中的空间位置即是。作为潜在的解存在的每个粒子, 只要带入一个目标函数就对应计算出相应的适应值, 权衡的优劣也就是在比较适应值的大小。速度方面第i个粒子的同样用一个N维的向量表示, 速度取决于粒子在搜索空间单位迭代次数的位移, 我们通常理解为“步长”。记录在第i个粒子群搜索到截止当前的自身的最优位置为。整个粒子群搜索到截止当前的最优位置为。粒子根据如下公式来替换更新其速度和位置:
其中, i=1, 2, ...m, n=1, 2, ...N;c1, c2是学习因子, 通常为非负常数, r1, 和r2是[0, 1]服从随机分布的随机数, 是常数, 由用户自我设定.选择中止的时机一般选为粒子群到目前为止所能找到的最优化位置 (此时它满足适应特定阂值) 或者事先指定好的最大迭代次数
由于是粒子群体的最优值, 上述PSO算法有“全局PSO算法”的提法。可以视为第i个粒子的周围附近粒子所能得到的最优位置, 上述方法也有“局部PSO算法”的提法。比较而言, 全局PSO算法收敛快, 数值在局部最优附近容易聚集。相反局部PSO收敛速度会慢一点, 但不易走入局部最优。
3 算法实现
3.1 算法流程
(1) 群算法参数初始化, 群体规模, 每个粒子的位置xi和速度, Vi
(2) 对应计算每个粒子的适应度值Fit[i];
(3) 对应于每个粒子, 比较它的适应度值和个体极值, 如存在Fit[i]>pbes (i) , 则用Fit[i]替换掉pbes (i) ;
(4) 对应于每个粒子, 比较它的适应度值Fit[i]和全局极值gbes (i) , 如存在Fit[i]>pbes (i) 则用Fit[i]代替gbes (i) ;
(5) 根据公式 (1) , (2) 更新替换粒子的速度xi和位置Vi;
(6) 如遇结束条件满足退出 (误差足够好或到达最大循环次数) , 否则重复步骤 (2) 。
3.3 实现结果
在本实验中, 采用matlab实现该算法, 如下是算法的显示结果:
4 应用
PSO算法简易实现, 没有太多参数需要调整, 且不需要可微可导信息和与之相关的此类的信息。PSO可作为连续优化和混合整数非线性问题和排列组合优化问题的优化方法[2]。PSO早期应用于诸如神经等网络初步训练上, 稍后PSO进一步可以用来确定在神经网络中的实质结构。如今广泛应用于在神经网络训练为后的函数优化、模糊性系统控制与其他智能算法的应用领域。
4.1 函数优化
粒子群算法原理与收敛性的研究都是为了更好研究和解决函数的优化问题, 通常象这一类问题都是相当复杂的, 问题特征表现为规模之大、维数之高、数学性质上可体现为非线性、非凸和不可微等微积性质, 大量极小局部存在函数分布里。相对早期的传统的优化确定性算法解决这类问题速度较快, 反应灵敏度高, 初值的选择上体现出相应的的要求, 局部特性上可见易陷入局部最小。提到另外具有优化全局性的算法, 如智能遗传算法、退火模拟算法、进化规划等, 它们各自的不同的机理和结构单一, 难以实现在高维复杂函数等方向上的高效优化。但PSO算法综合这些优缺点, 实现高效优化对复杂高维函数的作用。
4.2 神经网络的训练
PSO算法现在主要是在训练神经网络的3个大的方面 (网络几何拓扑结构及函数传递、连接时权重的设置、智能学习采用算法) 。每个粒子可完整勾勒表达出神经网络的相关的所有参数, 反复更新来实现对这些参数的优化, 由此达到训练的功效。相比同类型的学习算法如误差反向传播算法, 使用粒子群算法在神经网络的方面的优点在于不借助于可微可导等微分性质, 进而使用一些不可微的在函数之间传递信息。大概率情况下所能得到的结果比误差反向传播算法要好, 速度也更快些。
4.3 参数优化
粒子群算法选用在连续的各类问题和离散的各类问题的参数优化。目前有信号处理机器人路径规划、模糊控制器的设计和模式识别等问题
4.4 组合优化
由“01”串的编码方式实现的粒子群算法在许多组合优化问题中有序结构的表达问题以及约束条件处理问题等上尚需有更合理的解决方案和措施。所以问题的不同, 提相应问题的特定粒子表达方式不同, 也可以通过重新定义算子来解决。已解决了多种TSP、VRP以及车间调度等问题的优化方案。
5 结束语
粒子群算法是新型的群体智能的进化算法, 其研究也开始兴起, 远没有像遗传算法和模拟退火算法稳健发展, 有一定的系统的分析方法和一定的数学基础, 许多问题要进一步地分析, 给出方法。
可喜的是目前我国大量学者在对PSO算法的适用性和方法性的研究上有了新的研究动态[4], 能让粒子群算法能在更多优化研究工作上带来更多的新的启发和思路。
摘要：粒子群优化 (PSO) 算法是一种新颖的演化算法, 它属于一类随机全局优化技术, 通过粒子间的相互作用在复杂搜索空间中发现最优区域。该文介绍了PSO算法的基本原理、应用领域, 并用matlab实现了该过程。
关键词：粒子群算法优化应用,智能算法,编程语言matlab
参考文献
[1]Kennedy J, Eberhart R C.Particle Swarm Optlmization.Proc[R].IEEE Int, Lconf.on Neural Networks.IEBE Service Center, Pisca-taway, NJ, 1995 (4) :1942-1948.
[2]Eberhart R, Kennedy J.A New Optimizer Using Particle Swarm Theory[C].In:Proc of the Sixth International Symposium on Micro Machineand Human Science, Nagoya, Japan, 1995:39-43.
[3]Richards M, Ventura D.Choosing a starting configuration for particle swarm optimization[A].in:Proc.IEEE Int.Joint.Conf.Neural Net work[C], 2004 (3) :2309–2312.
[4]何妮, 吴燕仙.粒子群优化算法的研究[J]科技信息, 2008 (6) :179-220.
[5]王万良, 唐宇.微粒群算法的研究现状与展望[J].浙江工业大学学报, 2007, 35 (2) :136-141.
[6]谢晓锋, 张文俊, 杨之廉.微粒群算法综述[J].控制与决策, 2003, 18 (2) :129-134.
粒子群优化算法研究 篇8
粒子群优化算法[1]是1995年由Kennedy和Eberhart最先提出来的, 主要思想是受生物进化中的鱼或鸟类觅食行为启发而产生。它们寻找食物过程中, 除了寻找独立性和随机性的目标外, 彼此之间也相互交换信息, 帮助它们可以从不同的方向走向最终目标。由于PSO算法的高效、简单和快速的收敛速度, 粒子群优化算法已成功地应用于许多不同的领域[2,3]。然而, PSO算法在优化过程中粒子的性能和多样性容易丢失从而造成算法的过早收敛。目前, 针对算法的缺陷许多学者提出改进方法。主要是针对基本PSO算法中Pbest和Gbest的选择过程。首先在搜索空间中引入基于模糊积分的概念使单个粒子在搜索过程中获取群行为信息行为从而调整自身的搜索策略, 减小搜索的时间。此外, 还运用模糊积分来动态调整惯性权重加速算法收敛, 这增加了找到全局最优解的机会。
2 标准PSO和SUGENO的模糊积分
2.1 标准PSO
标准粒子群优化算法[1]系统中, 一个粒子表示一个问题的候选解。每个粒子被视为D维空间中的一个点。粒子由xi= (xil, xi2…, xi D) i=1, 2, …N表示, 粒子的速度是根据粒子在每一次迭代移动距离获得。每个粒子在每一次迭代过程中调整其运动轨迹努力达到pbest和gbest。粒子在每次迭代过程中的搜索方向vid调整和移动距离xid调整为:
算法中粒子优化过程中根据公式 (1) 和 (2) 进行更新。当粒子发现一个比以前较好的位置时, 它就存储。优化过程终止于得到一个满意的解决方案或达到预设的迭代次数。
2.2 Sugeno模糊积分
Sugeno模糊积分[4]是关于模糊测度最具代表性的真实函数积分。它是给定模糊测度中聚集视角下的理论研究。在Sugeno模糊积分中, 模糊测度已被证明为一种高效的特征集非加集函数的信息聚合方法。
μ是定义在X集合上的模糊测度, Sugeno模糊积分是从[0, 1]n到[0, 1]的集合函数。Sugeno模糊积分在函数x:X→[0, 1]上关于μ的定义为:
模糊积分的几种性质中, 主要是运用模糊积分中的非加性, 它描述了属性间的相互作用, 描述了组合属性或多或少于所有独立属性的总和。理解为属性的重要性被视为一个整体。
3 Sugeno模糊积分粒子群算法
经过对标准PSO和Sugeno模糊积分理论的研究分析, 在迭代过程中运用模糊积分理论将粒子之间的相互作用加入粒子运行速度和运行方向的改变中, 同时考虑动态调整粒子的惯性权重提高粒子的优化速度。
3.1 粒子的多样性
由于标准PSO算法中只考虑了粒子个体最优和全局最优, 个体之间的相互影响作用没有引起注意, 所以在优化过程中引入Sugeno模糊积分参数来度量个体之间作用作为权重添加到优化过程中使得有更多的因素调整搜索方向和移动位置。该作用权重形成优化过程中粒子的多样性。
算法中, 粒子位置的模糊度用Sugeno模糊积分来表示。μ表示迭代过程中单个粒子与多个粒子的作用的最大概率。为更好地利用粒子与粒子之间的相互作用, 粒子位置更新公式调整为:
3.2 动态惯性权重的调整方法
目前粒子群算法中运用的惯性权重ω根据之前粒子的变化确定粒子目前的速度来平衡局部与全局搜索。如果ω大, 粒子很难达到局部和全局最优并且会偏离最优解。当ω变小, 情况又会相反。因此目前的惯性权重大多选择随迭代次数线性递减变化, 即在迭代过程中调整速度权重和自动抑制最大速度来切换从全局搜索到局部搜索, 从而加速算法收敛。现有算法的缺点就是没有考虑到迭代过程中各权重之间的影响。
经过研究分析, 采用Sugeno模糊积分计算惯性权重变化趋势及惯性权重之间的相关性, 将该变化运用到迭代过程中调整惯性权重。设计的ω在优化过程除参考了原有的线性变化结果还增加了各迭代中惯性权重的相关关系, 以此在寻优过程中减少迭代次数, 提高搜索能力。文中的惯性权重主要根据迭代过程中最大惯性权重和所有相关惯性权重结合来计算, 采用了模糊因子集来动态调整惯性权重, 模糊因子集的计算公式表示为:
根据模糊因子在迭代过程中惯性权重调整公式为:
其中, t代表迭代次数;当前权重积分值为Sμ (t) 。优化过程中, 搜索空间随ω (t) 的变化调整寻优空间的大小从而搜索目标。
4 实验仿真与分析
还运行了标准PSO算法与算法进行比较, 结果如表1所示:
通过表1可以看出算法用较少迭代次数得到最优解。且该算法的收敛速度比标准PSO快。算法收敛图由图1和图2表示。
在算法设计过程中, 所提方法的主要特点为提高算法的收敛速度和寻找最优解。通过图1和2图, 可以比较出所提方法在寻优计算中, 既考虑迭代过程中的收敛速度, 又平衡局部最优与全局最优并最终获得最优解。
5 结语
采用Sugeno模糊积分来改进粒子群优化算法, 文中运用模糊因子在优化过程中动态调整惯性权重ω和添加粒子间相互作用来改进粒子寻优过程。粒子搜索的能力通过算法中粒子的多样性和寻优过程中的惯性权重更好地表现出来。不同粒子的搜索路径的不同使算法的搜索空间变得不同, 扩大了寻优范围的同时大大增加了全局寻优能力。通过实验证明提出的算法既保证了寻优过程中的收敛速度, 同时, 提高了算法的寻优能力。总体来说所提Sugeno模糊积分改进粒子群算法具有很强的寻优能力。
摘要：粒子群优化算法是模拟鸟类觅食的行为思想的随机搜索算法, 主要是通过迭代寻找最优解。将模糊积分技术引入优化算法调整粒子的多样性的同时动态改变惯性权重, 以此来提高粒子的搜索能力。仿真实验结果表明, 该方法大大提高了搜索过程中粒子的多样性, 并缩短了粒子的搜索时间, 保持快速的收敛性的同时获得了算法最优解。
关键词：模糊测度,Sugeno模糊积分,PSO算法
参考文献
[1]Kennedy, R.C.Eberhart, Particle swarm optimization, Proc.IEEE International Conference on Neural Networks IV, Australia, 1942-1948, 1995.
[2]M.Clerc, J.Kennedy, The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation 6 58-73, 2002.
[3]R.C.Eberhart, Y.Shi, Particle swarm optimization:Developments, applications and resources, Proceedings of the IEEE Congress on Evolutionary Computation, Korea, 81-86, 2001.
粒子群优化算法研究 篇9
1粒子群优化算法的原理
粒子群优化算法是一种进化计算技术,是由Kennedy与Eberhart于1995年提出的源于对鸟群捕食行为的研究,是一种基于迭代的优化工具,是一种群智能算法。由于它的原理简单,所需参数少,计算快速以及算法的容易实现,目前已广泛应用于目标函数优化、神经网络训练、数据挖掘、模糊系统控制以及其他的应用领域。
粒子群优化算法的基本思想是,每个优化问题的潜在解都是搜索空间的一只鸟,这里称为“粒子”,所有的粒子都有一个被优化的函数决定的适应值,每个粒子还有一个速度向量决定他们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索[1]。粒子群优化算法初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在D维搜索空间中,第i个粒子的位置为Xi=(xi1,xi2,…,xiD),i=1,2,…,m,其速度为Vi=(vi1,vi2,…,viD),在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。一个是粒子本身所找到的最优解叫做个体极值pbest,另一个是整个种群目前找到的最优解,这个极值是全局极值gbest。在找到这两个最优值时,每个粒子根据如下公式来更新自己的速度和新的位置:
式中:i=1,2,…,m,m是该群体中粒子的总数;d=1,2,…,D;为第k次迭代粒子飞行速度矢量的第d维分量;为第k次迭代粒子i位置矢量的第d维分量;pid为粒子i个体最好位置pbest的d维分量;pgd为粒子群体最好位置gbest的第d维分量;c1,c2表示群体认知系数,也被称作学习因子,通常c1=c2=2;rand()是随机函数,一般产生介于(0,1)之间的随机数。粒子群优化算法以它特有的记忆使其可以动态跟踪当前的收缩情况来调整其搜索策略。与进化算法比较,粒子群算法是一种更高效的并行搜索算法。
2粒子群优化算法的改进
由式(1)可以看出来公式右边由三部分组成,第一部分是粒子的更新前的速度,而后两部分反映了粒子速度的更新,Shi与Elbert的研究发现,式(1)的第一部分由于具有随机性且其本身缺乏记忆能力,有扩大搜索空间、搜索新的区域的趋势。因此具有全局优化的能力。在考虑实际优化问题时,往往希望先采用全局搜索,使搜索空间快速收敛于某一区域,然后采用局部精细搜索以获得高精度的解。
因此,在式(1)的前乘以惯性权重ω,ω较大则算法具有较强的全局搜索能力,ω较小则算法倾向大于局部搜索。一般的做法是将ω初始为0.9,并使其随迭代次数的增加线性递减至0.4,已达到上述期望的优化目的。通常惯性权重函数ω由下式来确定:
式(3)中:ωmax、ωmin分别是ω的最大值和最小值;iter、itermax分别是当前迭代次数和最大迭代次数。
3粒子群优化算法的实现
BP算法是最常用的神经网络训练方法,它是基于梯度的学习方法,但由于其算法内在的原因会出现训练收敛较慢,易陷入局部最优值等问题,采用PSO代替BP训练神经网络,用PSO调节和优化具有全局性的网络参数,用BP神经网络学习方法优化具有局部性的参数。用PSO作为一种粗优化或离线学习过程,用BP神经网络学习作为一种细优化或在线学习过程,就这样将这两种方法进行综合使用。
(1)初始化BP网络结构,设定网络的输入层、隐含层、输出层的神经元个数。
(2)初始化粒子群及每个粒子的位置、速度,以及个体极值和全局最优值。
(3)计算每个粒子的适应度。
(4)比较适应度,确定每个粒子的个体极值点和全局最优极值点。
(5)利用PSO算法的式(1)、式(2)、式(3)对每个粒子的位置和速度进行更新。
(6)计算算法的误差。
(7)检查是否符合结束条件,如果算法误差满足预设精度或迭代次数满足最大迭代次数,则停止迭代,输出神经网络的最终权值和阈值,否则返回第3步,算法继续迭代。
4异步电机的故障诊断
4.1神经网络训练
选用异步电机转子故障为研究对象,使用涡流传感器采集转子水平和垂直方向上的振动信号,通过放大、滤波和A/D转换,由DSP对振动信号进行频谱分析[2]。分别提取振动信号频谱中的8个频段上的不同频谱峰值作为特征量,当作神经网络的输入,而与其转子振动频谱分量对应的不平衡、不对中、油膜涡动、转子径向碰摩、喘振、轴承座松动6种故障信息作为神经网络的输出。建立起输入层为8节点,隐含层为11节点,输出层为6节点的三层BP神经网络。从故障诊断的实践中形成训练样本,并给出样本的目标输出,如表1所示,转子震动故障原因与征兆表。
在表1中每一故障分别选3组频谱,构成18组学习样本。该算法为有教师学习算法,在样本目标输出中“1.00”表示对应故障发生,“0.00”表示对应故障不发生。
4.2训练结果比较与分析
故障诊断调用Matlab程序分别进行BP神经网络和基于PSO优化的BP神经网络的训练,选取表1中的3、6、9、12、15、18组样本故障数据作为检验数据,如表2所示,得到基于BP算法的网络输出结果,如表3所示,得到基于PSO算法的网络的输出结果。
本系统中,PSO的固定粒子数取20,ω初始值可取稍大些为1.2,后迭代次数由1.2线性递减为0.4,迭代步数取20 000次[3,4]。从表2、表3的对比可以看出,基于PSO算法神经网络的训练结果相对于基于BP算法的神经网络有较高的准确度。
基于BP算法的神经网络训练曲线(见图1)。
基于PSO算法的神经网络训练曲线(见图2)。
图2及图2中横坐标代表网络训练次数,纵坐标代表网络性能即系统误差。从图中训练曲线可以看出:PSO算法迭代次数为597次时,系统误差就达到了0.001,而BP算法迭代次数为10 000次时,还未达到系统精度,陷入局部极小值0.166 8。图2与图1相比,训练曲线变得曲折,说明PSO算法易于跳出多个局部极小值向全局最优值搜索。因此,采用基于粒子群优化算法训练的BP神经网络对异步电机进行故障诊断要优于基于传统BP算法的诊断方法。
5结论
应用神经网络对电机进行故障诊断是目前一个十分活跃的研究领域,而加入了粒子群优化算法的电机故障诊断又为其提供了新的思路和方法。本文应用基于粒子群优化算法和BP神经网络对异步电机转子的常见故障进行了诊断。仿真结果表明,基于PSO算法的BP神经网络对异步电机故障征兆能给出较理想的输出结果,其迭代次数少,收敛快,诊断精度高,性能优于BP算法,具有较好的工程应用价值和非常广阔的应用前景。
参考文献
[1]潘昊,候清兰.基于粒子群优化算法的BP网络学习研究.计算机工程与应用,2006;(16):41-42
[2]李占峰,韩芳芳,郑德忠.基于BP神经网络的电机转子故障研究.河北科技大学学报,2001;22(3):24-25
[3] Bocaniala C D,da Costa J S.Tuning the parameters of a classifier for Fault Diagnosis-particle swarm optimization vs genetic algorithms. ICINCO,2004;(1):157-162
粒子群优化算法研究 篇10
网络技术突飞猛进的发展也增加了网络入侵的风险性。设计安全措施来防范未经授权访问系统的资源和数据, 是当前网络安全领域的一个十分重要而迫切的问题。目前, 要想完全避免安全事件的发生并不太现实。网络安全人员所能做到的只能是尽力发现和察觉入侵及入侵企图, 以便采取有效的措施来堵塞漏洞和修复系统。这样的研究称为入侵检测, 为此目的所研制的系统就称为入侵检测系统IDS (Intrusion Detection System) [1]。
近年来, 国内外学者已提出大量的入侵检测方法, 如统计方法[2] 、贝叶斯推理方法[3] 、神经网络[4]、粗糙集[5]和聚类方法等。在聚类方法中, Fuzzy C-Means (FCM) [6]方法应用最为普遍。然而, FCM方法在使用的过程中存在自身难以克服的问题:对初始值敏感, 对噪声数据敏感, 容易陷入局部最优等。这样就使得聚类的结果不能满足要求。本文采用混合粒子群优化算法PSO进行入侵检测研究。
1FCM原理
FCM算法是最重要也是最流行的模糊聚类算法之一。1973年Dunn首先提出了FCM算法的一个特例, 同年Bezdek将Dunn的算法进行了推广, 之后又出现了许多相关的算法。
给定数据集X={x1, x2, …, xn}⊂Rs是S维模式空间的一个特征向量集, 根据某种相似性度量, 该集合被聚合成c个聚类X1, X2, …, Xc;2≤c<n, 每个聚类的中心为qj, 2≤j<n组成Q={q1, q2, …, qc}。这c个聚类组成特征向量X的一个模糊划分, μik表示特征向量xi属于子集Xk的隶属度, 从而可得n×c维隶属度矩阵Ut= (μi, k) , μi, k∈[0, 1];i=1, 2, …, n;k=1, 2, …, c;且
其中:‖xi-qk‖2= (xi-qk, xi-qk) , 指xi与聚类中心qk之间的欧几里德距离;1<m<+∞。m是一个模糊加权指数, 又称平滑因子, 用来控制隶属矩阵的模糊程度, m越大越模糊。如果m=1则FCM算法退化为HCM聚类算法。要实现模糊聚类就必须选定一个m, 但最佳m的选取目前尚缺乏理论依据, m的选择大都来自实验或经验, 一般取1.1≤m≤5, 用Lagrange乘数法结合
以上的原理指导人们去寻找在一定意义下的最优解, FCM算法的计算过程就是反复修改聚类中心和分类过程, 最终得到最优的聚类结果。FCM算法的一般步骤如下:
(1) 由随机数产生器产生分类中心矩阵Q (0) , 记迭代次数t=0, 终止误差ε>0;
(2) 按照 (2) 式根据Q (t) 计算每个样本点隶属各个聚类的隶属度矩阵:U (t) = (μi, k) , μi, k∈[0, 1];i=1, 2, …, n;k=1, 2, …, c;
(3) 按照 (3) 式计算下一次计算时的聚类中心Q (t+1) ;
(4) 如果‖U (t+1) -U (t) ‖<ε则算法结束, 否则t=t+1再次循环, 继续步骤 (2) 。
FCM算法是K-Means算法的改进, 但是同时也具有K-Means算法不可克服的一些缺点, 如FCM算法是基于目标函数的模糊聚类算法, 目标函数存在许多局部极小点, 而算法的每一步迭代都是沿目标函数减小的方向进行。所以, 如果初始化落在了一个局部极小点附近, 就可能使算法收敛到局部极小, 从而影响运算结果的最优性。
2混合PSO在入侵检测技术中的应用
2.1基本PSO算法
Eberhart和Kennedy在文献[7]中引入了一种新的基于种群的优化算法, 即粒子群优化 (PSO) 算法。其最初的出发点是为了模拟鸟群、鱼群、蜂群等生物群体的社会性行为。通过对这些群体一些不可预测行为的图像化模拟和大量试验, 他们不断排除一些无关因素, 最终得到了非常简单的PSO迭代公式。
常见的惯性权值PSO算法公式如下:
vid=w*vid+c1*rand () * (pid-xid) +c2*Rand () * (pgd-xid) (4)
xid=xid+vid (5)
其中:c1、c2为两个正常数, rand ( ) 和Rand ( ) 是在[0, 1 ]范围内的随机数。在PSO中, 每个粒子都认为是D维空间内的一个点。第i个粒子可以表示为Xi= (xi1, xi2, ..., xiD) ;第i个粒子以前最好的位置 (对应的目标函数或者适应度值最小) 被保存下来并表示为Pi= (pi1, pi2, …, piD) , 在PI向量中最好的粒子成员下标用g表示 (全局最优) 。第i个粒子位置变化的快慢用VI= (vi1, vi2, …, viD) 表示。w是非负数, 称为惯性权重。w控制粒子的先前速度对当前速度的影响程度, 若w较大, 粒子有能力扩展搜索空间, 全局搜索能力强。若w较小, 粒子主要在当前解的附近搜索, 局部搜索能力较强。由此可见, 改变其取值可以调整算法全局和局部搜索能力。w由式子:w=wmax- (wmax-wmin) /itermax×iter确定, 其中itermax时迭代的最大值, iter是当前迭代次数。
PSO算法步骤如下:
(1) 预先设定粒子种群维数、粒子规模 (成员数) 、迭代次数等参数, 并将种群和速度随机初始化;
(2) 计算目标函数值;
(3) 比较以前最优位置对应的目标函数值与当前目标函数值。如果当前值更好, 则用当前xid取代pid;否则, pid保持不变;
(4) 经过一次迭代以后, 重新计算下标g, 以确定新的全局最优点pgd;
(5) 利用公式 (4) 更新速度并限制其最大范围, 利用公式 (5) 更新粒子位置并限制其范围;
(6) 重复步骤 (2) ～ (5) 直到满足终止条件或达到最大迭代次数。
2.2混合PSO在入侵检测技术中的应用
针对FCM算法存在的缺点, 本文采用一种基于PSO结合模糊聚类算法的混合PSO算法。设聚类样本集为:X= (x1, x2, …, xn) , 其中的xi为任意维向量。混合PSO算法的思路是:以PSO 中的一个微粒代表一个簇中心的集合Q= (q1, q2, …, qk) , 其中qi是与xi维度相同的向量, 代表一个簇中心, 通过公式 (3) 计算适应度矩阵U (t) = (μi, k) , 令PSO中的适应度函数为:
混合PSO算法实现过程可以描述为:
(1) 给定聚类数目c, 群体规模n, 学习因子c1、c2, 惯性权重wmax、wmin, 迭代的最大次数tmax;
(2) 初始聚类中心Q (0) , 并对其进行编码, 形成n个第1代粒子。每个粒子的pid为其当前位置, pgd为当前种群中所有粒子中的最好位置;
(3) 对每个聚类中心按式 (2) 计算隶属度μik, 其中i=1, 2, …, n;k=1, 2, …, c;
(4) 按式 (1) 计算每个粒子的适应度值, 比较以前最优位置对应的目标函数值与当前目标函数值。如果当前值更好 (如更小) , 则用当前xid取代pid;否则, pid保持不变;
(5) 利用公式 (4) 更新速度并限制其最大范围, 利用公式 (5) 更新粒子位置并限制其范围, 产生下一代的粒子群;
(6) 重复步骤2～5, 直到满足终止条件或者达到最大迭代次数。
由于PSO 虽然能找到接近全局的近似解, 但不能绝对保证收敛到全局最优解。因此, 将混合PSO求得的解作为FCM的初始值, 然后用FCM算法进一步求全局最优解, 这样得到的结果最理想。
3实例仿真
试验采用了KDD Cup 1999 Data的数据集。该数据集曾与KDD99 同时举办的第三届国际知识发现和数据挖掘工具竞赛上使用, 它包含了在军事网络环境中仿真的各种入侵数据。
该数据集提供了从某模拟的美国空军局域网上采集来的9个星期的网络连接数据, 其训练数据集包含5百万个连接数据, 测试数据集包含了2百万个连接数据。一个连接就是在规定的协议下、在规定的时间内完成的起始并终止的TCP 分组序列, 这些序列在固定的源IP 地址与目的IP 地址之间进行数据传输。每个连接都带一个类标识, 或者是正常, 或者是某个具体的攻击类型。表1给出了部分连接记录的显示。
KDD99数据集中的每一条记录都是一条网络连接纪录, 共包含42个属性。由于数据集中的记录的属性之间存在着很大差异性, 直接进行聚类处理会产生不真实的结果。以包含3 个属性的数据为例, A = (6, 376, 5) , B = ( 5, 200, 3) , 在计算欧几里德距离时, 由于属性2远远大于属性1和属性3, 因此将掩盖属性1和属性3对结果的影响。为此, 对原始集数据按以下方式进行归一化处理。首先计算记录Ij的均值
在实验中, 对数据集进行了筛选:主要检测拒绝服务攻击 (DOS) 和来自远程机器的非法访问 (R2L) , 将不属于实验要求的数据去除。为了进一步减少数据量, 从每个类型的数据中取出至多2100条记录, 最后得到待分析的连接记录的总数为4189。为了更方便地应用聚类方法来对TCP连接进行分类, 主要选择连续型属性进行考察, 共选择了13种属性其中包括4个离散的属性和9个连续的属性。其中的4个离散型属性主要是为用于对原始数据集进行子集划分以改善算法性能而考虑的。FCM 算法中的允许最小误差为10-7, m=2, 粒子群的群体大小为40, 最大迭代步数为800, 学习因子c1=c2=1.5, 惯性权重wmax=0.8、wmin=0.6。表2给出了三种算法运行50次后平均结果的对比。
从表2中可以看出, 经过聚类后的实验数据很好地被标示出哪些簇是入侵的数据, 哪些是正常数据。可以明显地看出聚类2和4中正常的数据占的比例很高, 说明这两个簇为正常。远程机器的非法访问 (R2L) 和拒绝服务攻击 (DOS) 分别在聚类1和3中占绝大多数, 所以聚类1是远程机器的非法访问的入侵, 聚类3是拒绝服务攻击。实验中同样采用了原始的FCM算法和混合聚类算法对同样的数据进行了聚类分析。
在入侵检测中通常用2个参数来评价入侵检测算法的性能:误报率FPR (False Positive Rate) =正常连接误报为异常连接的数目/正常连接总数目;检测率DR (Detection Rate) =已检测出来的异常连接的数目/异常连接总数目。表3表示了实验中采用的3种入侵检测的算法, 从结果中可以清楚地看出, 混合PSO算法相对于其他两种聚类算法具有较高的检测率和相对较低的误报率, 其目标函数的最小值也非常接近最优值, 全局寻优能力强。可见把混合PSO算法应用在入侵检测系统中, 具有较强的实际意义。
4结论
PSO算法是一种群体智能优化算法, 具有很强的全局搜索优化能力, 把PSO和FCM算法相结合的新算法混合PSO应用于入侵检测系统, 很好地解决了原来FCM算法容易陷于局部最优的局限性, 其效果优于混合聚类算法和FCM算法。
参考文献
[1]蒋建春, 马恒太, 任党恩, 等.网络安全入侵检测:研究综述[J].软件学报, 2000, 11 (11) :1460-1466.
[2]Aanderson J P.Computer Security Threat Monitoring and Surveillance[R].James P.Anderson Company, Fort Washington, Pennsylvania, 1980.
[3]Lunt TF, Tamaru A, Gilham F.A Real Time Intrusion Detection ExpertSystem (IDES) [R].Computer Science Laboratory, SRI Internation-al, Menlo Park, California, 1992.
[4]马绚, 张瑞山.智能入侵检测Agent中基于神经网络的结构学习算法[J].计算机应用与软件, 2006, 23 (1) :38-41.
[5]王艳芳, 张连华, 白英彩.基于粗糙集数据挖掘和分类集成学习的网络入侵检测模型[J].计算机应用与软件, 2006, 23 (4) :47-50.
[6]Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algo-rithms[M].New York:Plenum Press, 1981.
粒子群优化算法研究 篇11
粒子群优化算法 (Particle Swarm Optimization, PSO) [3]源于对鸟群捕食行为的研究, 由Kennedy和Eberhart共同提出的一类模拟群体智能的优化算法。与其它进化算法类似, PSO采用“群体”与“进化”的概念, 主要依据个体的适应值大小进行操作。它具有概念简单、容易实现、依赖经验参数较少等特点。目前已成功地用于求解多种组合优化问题。
本文在对蚁群算法和粒子群算法研究的基础上, 提出一种新算法来解决TSP问题。它使用ACS的框架对最优路径进行搜寻;采用粒子群算法对蚁群算法中的控制参数β, ρ, q0进行优化。新算法克服了蚁群算法中参数的影响, 减少了大量盲目的实验, 实现了对搜索空间高效、快速的全面寻优。仿真实验结果显示无论是求解精度还是迭代次数, 新算法比传统蚁群算法具有更高的性能。
1 蚂蚁群系统 (ACS)
与蚂蚁算法 (AS) 相比, ACS引入了新的路径选择策略和信息素的局部更新。新的路径选择策略采用贪婪选取和随机选取相结合的方法, 增加了对最优路径的识别强度;信息素局部更新削弱了当前已选路径上信息素对后续蚂蚁影响力, 这样增加了其他路径在下一次循环中被选择的机会, 从而扩大了算法的搜索空间, 使蚂蚁对没有被访问的边有更强的探索能力, 有效地避免了算法陷入局部最优。
下面以求解平面上N个城市的TSP问题为例, 具体说明ACS原理。设m是蚁群系统中蚂蚁的数量, U代表蚂蚁k从i点出发的可行点集合 (在一次寻路过程中, 已经遍历过的城市将从该集合中删除) 。di1代表城市i, l之间的距离。蚂蚁k在城市i向城市j移动的转移规则为:
V代表蚂蚁k在城市i随机探索下一城市j的概率, 其值根据式 (2) 进行选择;q是一个在[0, 1]均匀分布的随机变量, 它决定了选择下一城市的概率;q0是一个给定的在[0, 1]的常数, q0越小, 蚂蚁随机选择下一城市的概率越大。
其中:τij为边 (i, j) 上的信息素浓度;ηij=1/dij代表边 (i, j) 上的自启发量, α、β是两个参数, 分别代表信息素浓度的权重和自启发量的权重。
从式 (2) 、式 (3) 可以发现, 蚂蚁在选择转移路径的时候, 既选择路径短并且信息素浓度高的路径;又以一定的概率探索新的路径。这样既保证了算法的收敛特性, 又可以使算法不陷入局部最优解。
当蚂蚁选定一个城市之后, 就对已走过的城市使用式 (4) 进行信息素局部更新,
其中, ρ为局部信息素蒸发率, τ0为信息素初始值。
当所有蚂蚁遍历完所有城市以后, 仅对最优路径上的信息素按式 (5) 进行更新。
其中, a为全局信息素蒸发率, lk为当前最优路径的长度, ij∈global-best-tour表示蚂蚁k所走的路径 (i, j) 属于最佳路径。
这就完成一次迭代, 当所有的迭代全部执行完毕时, 算法结束, 输出最优值。
2 粒子群算法原理
PSO模拟鸟群的捕食行为, 假设一群鸟在只有一块食物的区域内随机搜索食物, 所有的鸟都不知道食物的位置, 但它们知道当前位置与食物的距离。最简单有效的方法是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示, 并将其用于解决优化问题。PSO中每个优化问题的解都是搜索空间中的一只鸟, 称之为“粒子”。所有的粒子都有一个由被优化的函数所决定的适应值, 对于每个粒子, 还有一个速度决定它们飞翔的方向和距离, 然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子 (随机解) , 然后通过迭代找到最优解。在每一次迭代中, 粒子通过跟踪两个“极值”更新自己, 一个是粒子本身所找到的最优解, 称为个体极值pbest;另一个极值是整个种群目前找到的最优解, 该极值是全局极值gbest。在找到这两个最优值时, 每个粒子根据如下公式更新自己的速度和新的位置:
其中:vk为第k步粒子的速度向量;xk为第k步粒子的位置;pbestk为第k步粒子本身所找到的最好解的位置;gbestk为第k步整个种群目前找到的最好解的位置;w表示惯性权重;c1调节微粒飞向自身最好位置方向的步长, c2调节微粒向全局最好位置飞行的步长, c1、c2通常在0-2间取值;r1:R (0, 1) , r2:R (0, 1) 为两个相互独立的随机函数;每一维粒子的速度都被限制于一定范围内, 即vk∈[-vmax, v max]。如果vk>v m a x时, v k=vmax;如果v k<-vmax时, v k=-vmax。
3 融合粒子群优化的蚁群算法
蚁群算法和粒子群算法都属于群智能的算法。蚁群算法擅长解决离散优化问题, 而PSO擅长连续问题的优化。在求解TSP问题中, 蚁群算法是离散优化问题, 但算法的控制参数是连续变化的。新算法的基本思想是汲取两种算法的长处, 优势互补。算法采用PSO来优化蚁群算法中的三个控制参数 (β, ρ, q0) , 运用ACS算法进行路径查找, 从而实现对搜索空间高效、快速的全面寻优。
PSO初始化:
随机选择n (n为TSP城市的数量) 个粒子 (particle) , 每个粒子包含三个参数β, ρ, q0, 组成一个3×n的随机数组。其中β在[1, 5]随机取值, ρ和q0在[0, 1]随机取值。
AC S初始化:
对任意的边 (i, j) , 信息素初值τij (t) =const, Vτij=0;
将n只包含各自参数的蚂蚁随机地放置在n个结点上, 根据各自的变量值, 求适应度函数值, 即4只蚂蚁分别进行下面的A CS寻径:
对每一只包含各自参数 (β, ρ, q0) 的蚂蚁运行ACS:按式 (2) 、 (3) 进行状态转移寻找路径;对经过的边, 按式 (4) 进行局部信息素更新;记录每个蚂蚁的结果。
end for
对当前最好解的路径按式 (5) 进行全局信息素更新。
end for
将寻径后的每个蚂蚁的最短路径长度作为相应粒子的适应度函数值;使用PSO算法, 按式 (1) , (2) 更新每个粒子的速度和位置, 即更新每个粒子的3个参数。
end for
最后输出全局最优TSP路径值和全局最优参数β, ρ, q0。
4 仿真实验
我们选取TSP_lib[4]中数据对新算法进行测试, 并且与ACS算法的执行结果进行比较。每组测试均运行10次, 并记录最优值与获得最优值时的迭代次数。如表1所示。实验环境:CPU赛扬1.0GHz、内存256MB, 开发工具BCB6.0。算法的参数取值如下:蚂蚁数量m=n (n为城市的数量) ;最大迭代次数NC_MAX=500;PSO迭代次数MaxIt_PSO=10 0, c1=1.8, c2=1.8 (见表1、2) 。
由表1可知, ACS在第2, 3, 4测试数据中得到了最优解, 而新算法对所有的测试数据均取得了最优解, 并且取得最优解的迭代次数要比ACS算法要少得多。主要原因在于ACS算法参数事前设定是多次实验相比较得到的一个结果。这对于一个未知的优化问题是不可能的, 因为它的参数是未知的, 需要大量的运算, 才能比较出一个相对较好的参数, 且易陷入局部最优。新算法很好的解决了这一问题, 它随机产生初始控制参数, 在优化解的同时, 采用PSO对3个控制参数不断地进行连续优化选择, 上表2列出了这些控制参数的最优值。
5 结语
本文通过基本蚁群算法和粒子群优化算法的结合, 避免了在蚁群算法中采用人工方式寻求参数的方法, 从而使基本蚁群算法在参数选取时具有一定的优化与自适应依据;并在计算过程中能够达到最优路径的同时, 使花费的时间最少。通过仿真实验可知, 与传统蚁群算法相比, 新算法体现了较高的性能, 取得了不错的效果。
参考文献
[1]M.Dorigo, Carogd.Ant algorithms for discrete opti-mization[J].Artificial Life, 1999, 5 (3) :137～172.
[2]DORIGO M, GAMBARDELLA L M.Ant colony system:a cooperative learn-ing approach to the traveling salesman problem[J].IEEETransactions on Evo-lutionary Computation, 1997, 1 (1) :53～66.
[3]Kennedy J, Eberhart R C.Particle swarm optimization[C].International Conference on Neural Networks.1995:1942～1948.
【粒子群优化算法研究】推荐阅读：
自适应粒子群优化算法06-12
改进多粒子群优化算法06-23
基于改进粒子群算法的盘式制动器优化设计07-21
混沌粒子群优化09-06
随机粒子群优化09-29
自适应粒子群优化05-10
概率并行粒子群优化05-22
多目标粒子群优化06-10
粒子群优化的模糊特征08-04
双层多目标粒子群优化08-08