二进制粒子群算法论文（精选10篇）
二进制粒子群算法论文 第1篇
配电网一般具有环形结构,通常以开环方式运行,配电网中包含大量常闭的分段开关和少量联络开关。网络中的分段开关在正常运行情况下闭合,联络开关用于提供可选择的供电通道,在一般情况下处于开断状态。在正常运行或故障恢复条件下可以根据不同的负荷情况,改变这些开关的状态来调整网络结构。
配电网重构[1]是指线路电压、电流、功率及电网辐射状运行等都满足基本要求的前提下,通过改变网络中开关的状态来改变网络运行结构,从而达到降低配电网有功损耗、改善节点电压、消除线路过载,提高系统经济安全运行的目的。配电网重构成为优化配电网运行情况的重要手段。
配电网重构是一个多目标非线性混合优化问题,其求解算法主要分为三类:传统数学优化算法,如线性规划法、动态规划法等,这类方法在理论上可获得全局最优解,但计算复杂,且随着系统规模的增大,计算量将大大增加;启发式算法,如支路交换法、最优流模式法等,计算速度得到提高,但是很难保证收敛到最优解;人工智能优化算法,如遗传算法(GA)、人工神经网络法(ANN)、粒子群算法(PSO)等。
本文采用以联络开关和分段开关为基变量,基于网络闭合环路的二进制粒子群算法,以降低配电网有功网损为目的进行配电网的重构。
1 配电网络的数学模型
配电网的重构一般以降低配电网络有功损耗、均衡负荷、提高电压稳定性、减小停电损失为目标或综合上述多个指标为目标,还有以考虑开关操作次数最少为目标的。本文以配电网有功损耗最小为目标进行网络重构,其数学模型为:
n为支路总数。
约束条件:
(1)配电网潮流约束:
(2)节点电压、电流容量约束:
(3)负荷及网络拓扑约束:配电网闭环设计,开环运行,呈辐射状;重构后的配电网必须连通、无环、无孤岛。
2 粒子群算法
粒子群优化算法[2,3]是一种群智能优化算法,是通过群体间的相互协作和信息共享来进行全局搜索的。粒子群算法初始化是随机的,然后通过更新迭代寻找最优解。每次迭代中,粒子通过跟踪两个“极值”来更新自己,一个是粒子本身寻找到的最优解pbest,另一个是整个种群搜索到的最优解gbest,每个粒子根据以下公式来更新自己的速度和新的位置。
其中,vk是粒子的飞行速度,xk是当前粒子寻找到的位置;pbest是粒子本身寻找到的最优值,gbest是整个种群找到的最优值;c0、c1、c2是速度更新的系数,是粒子群体的认知系数,c0一般取(0,1)之间的随机数,c1、c2取(0,2)之间的随机数。
粒子群优化算法因其具有简单、有效、收敛速度快等优点,目前已被广泛应用于连续或离散型的线性、非线性组合优化问题。
3 二进制粒子群法的网络重构
基本的PSO算法是在连续性区域中搜索一个数值函数的最优值的有力工具。在许多优化领域,问题的变量是整数,比如运筹学中的背包问题、任务指派问题、武器分配,生产中的调度问题,通信中的路由选择问题等,这些都是以离散变量作为自变量的,在求解的过程中就不能以连续性PSO算法来解决。
Kennedy和Eberhart在基本粒子群法的基础上,在参考文献[4]中提出了一种离散二进制版本的PSO算法,Clere推广了这一算法,研究了离散型的PSO算法,并将其应用于旅行商问题的求解,取得了较好的结果。
配电网中的每一个联络开关对应着一个环,闭合一个联络开关将形成一个环,此时,必须断开环中的一个分段开关才能使配电网恢复辐射状。故本文采用基于环路的二进制编码策略,以配电网的联络开关全部闭合所形成的网孔为环路,在粒子编码中,以环路为组进行约束调节,对同一个节点在多个组中的情况要同时对所在的组进行约束调节,粒子的长度为网络中的开关总数,组数为网络中的环路数,粒子的初始状态表示网络中开关的闭合状态。
考虑同一节点在不同组中的情况,设置种群的形成及粒子更新的规则:(1)只在一个环路中出现的开关最多有一个是断开状态的。(2)在多个环路中出现的开关至少在一个环路中是闭合状态。(3)两个环路中共同存在的公共支路开关在编码时不允许打开两个以上。(4)为保证配网中所有负荷都能得到供电,对于不处于任何环路内的支路上的开关必须闭合。(5)与电源点直接相连接的分段开关必须处于闭合状态。
Kennedy和Eberhart提出的针对0-1整数规划问题的二进制粒子群算法(BPSO),每个变量的取值只有0、1两种情况,配电网中的开关的状态只有两种情况:0(开)或1(闭),粒子的每一维代表开关的闭合情况。粒子的更新公式为:
算法步骤:(1)读取配电网的数据,设置粒子群算法的参数。(2)按所提出的规则初始化粒子每维的状态,随机初始化粒子的速度。(3)按公式(3)计算配电网的潮流,更新每个粒子和全局的最优解。(4)判断是否满足结束条件,若满足,迭代结束,输出结果;否则,转至步骤(5);(5)按公式(5)和(7)更新粒子的速度和位置,迭代次数加1,转至步骤(3)。
4 算例分析
为了检验算法的有效性,采用IEEE 33节点系统作为测试算例。该系统有33个节点,37条支路,其中5条为联络开关控制的联络支路,并取额定电压为12.66 kV。IEEE 33节点系统如图1所示,实验结果如表1所示。
从表中可以看到,配电网重构前的线路损耗为202.66 k W,重构后降低到140.96 k W,减少了30%,说明该算法是可行的,有效地减少了损耗,提高了配电网的经济性[5,6,7]。
5 结语
本文以配电网中分段开关和联络开关为基变量,以环路为限制条件,采用二进制粒子群算法进行了配电网的重构,降低了系统的有功损耗,在一定程度上提高了电压水平,增强了系统的供电可靠性。
参考文献
[1]王守相,王成山.现代配电系统分析[M].北京:高等教育出版社,2007.
[2]李振坤,陈星莺,余昆,等.配电网重构的混合粒子群算法[J].中国电机工程学报,2008,28(31):35-41.
[3]安源,彭先胜,姚李孝,等.基于改进粒子群算法的配电网多目标重构[J].西安理工大学学报,2010,26(2):192-196.
[4]Eberhart R,Kennedy J.A New Optimizer UsingParticle Swarm Theory[C]//Proceedings of the6th International Symposium on Micro Machineand Human Science.Nagoya,1995:39-43.
[5]曾建鑫,朱子坤.基于量子遗传算法的大规模配电网实时重构研究[J].广东电力,2011,24(1):28-31.
[6]邱正美.含分布式电源的配电网络重构研究[D].北京:华北电力大学,2011.
基于量子粒子群算法求解整数规划 第2篇
基于量子粒子群算法求解整数规划
通过引入量子行为来增强粒子的全局收敛能力,提出了量子粒子群优化算法(QPSO),并用于求解整数规划问题.测试函数的`仿真结果表明,通过适当的参数设置,并将每次迭代所生成的实数值截至整数值后进行下一次迭代,可以保证QPSO算法求解的精度,提高收敛速度且能有效避免早熟.
作 者：刘静 须文波 孙俊 LIU Jing XU Wen-bo SUN Jun 作者单位：江南大学,信息工程学院,江苏,无锡,214036 刊 名：计算机应用研究 ISTIC PKU英文刊名：APPLICATION RESEARCH OF COMPUTERS 年，卷(期)： 24(3) 分类号：O22 关键词：粒子群算法 量子粒子群算法 整数规划改进的自适应多目标粒子群算法 第3篇
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
二进制粒子群算法论文 第4篇
行人识别是行人检测过程中最为关键的一步, 行人的识别过程实际上就是一个目标标记的过程, 即运用一些图像识别算法来进一步判断己经分割出来的是否是行人, 如果“是”便将行人以某种方式 (本研究以矩形框的方式) 标记出来。行人识别是行人检测的第二步也是最为关键的一步, 即对上一步分割出来的行人候选区域进行一些简单的图像处理 (二值化、均衡化、离散变换等) , 同时提取一些典型特征, 然后利用这些典型特征进行机器学习并训练得到行人检测所需的分类器, 完成行人识别的目的。传统行人识别的方法是支持向量机, 虽然检测效率很高, 但是前期处理时间长、过程复杂, 不能满足实际的应用[1,2,3,4,5]。将基于二进制粒子群优化的方法应用到行人检测中, 以解决在实际中应用的问题, 为汽车主动安全技术提供了有效的理论基础。
二进制粒子群优化算法是由Kennedy和Eberhart博士在1997年提出[6], 该算法主要用于解决传统粒子群优化算法无法解决的离散优化问题。该算法主要应用于人脸识别、行人识别以及数字识别等。
1 行人样本图像的离散余弦变换
行人图像的各像素数据之间存在极强的相关性和很大的冗余性。冗余信息是指由于数据结构、存储等方面设计的不合理而造成的信息重复, 最常见的冗余信息出现在数据库的设计中。进行图像压缩最主要的目的是提高图像重建之后的质量, 同时, 尽量多地去除这些冗余信息。
1.1 离散余弦变换 (DCT)
图像DCT变换是图像处理中变换效果最好的方式, 因为它有以下的优势: (1) DCT是正交变换, 它可以将88图像的空间表达式转换为频率域, 只需用很少数据点来表示图像; (2) DCT产生的系数易被量化, 块压缩的效果很好; (3) DCT算法的性能稳定, 而且速度快, 这就保证其在硬件和软件中都能够实现; (4) DCT算法具有对称性, 因此可利用逆DCT算法来解压缩图像。
由于离散余弦变换核函数是余弦函数, 而傅里叶变换的核函数是指数, DCT的变换速度比DFT要快得多, 而且对于一些本身含有一阶马尔柯夫过程的随机信号, DCT最接近K-L变换, 目前在图像边缘提取、图像压缩以及图像识别领域得到广泛应用。
设f (x, y) 一幅分辨率为MN的行人图像矩阵, 则对应的二维离散余弦变换和和反余弦变换的公式分别为:
矩阵表示为:
1.2 (DCT) 正逆变换行人样本图像
DCT变换图像变换后如图1 (a) 所示, 候选区域经过DCT变换之后, 有了明显的变化, 高、低频分量显而易见, 其中高的部分分布在右下角, 低的部分分布在左上角。对于一副图片来说, 其关键信息都分布在低频分量中, 因此本研究将高频分量舍掉, 进而实现图像压缩的目的, 而且重建后图像的频谱几乎保持不变, 如图1 (c) 、1 (d) 所示。理论上可以直接对整个图像进行DCT变换, 但是因为图像每个部分在细节上有很大的不同, 对整个图像直接进行DCT变换效果非常不好。为了提高实验效果, 本研究采取先将对角图像分块, 并对每个块进行DCT变换, 然后对每个块进行IDCT变换, 最后将每个处理后的块组合起来形成一幅图像。离散余弦变换的优势在于:能量集中, 频域变化因子u、v较大时DCT系数a (u, v) 较小;而数值较大的a (u, v) 主要分布在u、v较小的左上角区域, 有价值信息都集中在该区域。由于利用DCT系数重建图像时, 将有用信息多的低频分量保留, 而去除无用的高频分量, 利用反余弦变换仍可获得与原始图像相像的重建图像, 新、旧图像理论上存在一定的误差, 但是一些重要信息都存在。
DCT逆变换图像如图2所示。待处理图像如图2 (a) 所示, 光谱图如图2 (b) 所示, 离散余弦逆变换重构的图像如图2 (c) 所示。从图2 (b) 看出, 图像的重要信息都聚集在变换后图像的左上角。该特性对行人检测系统起着非常关键的作用。
2 粒子群优化算法的行人特征向量提取
2.1 二进制粒子群优化算法
标准PSO算法已经应用于许多领域, 但是这些应用都是求解无约束连续型最优化问题, 而对于有约束的离散型的优化问题, 目前应用相对较少。为了使PSO算法能够解决离散型的优化问题, 文献[6]提出了BPSO算法 (二进制粒子群优化算法) 。在BPSO算法中, 将粒子看成字符串, 该字符串是经过二进制编码, 因此粒子的位置xkid只能取0或者1。为使迭代后xkid+1只能取0或1这两个值, 下面引入sig (x) :
这样迭代公式变为:
在标准的PSO算法中, vkid表示粒子的速度, 由于粒子具有向其他粒子学习的能力, 会使当前位置xkid的方向和位置发生一定的变化, 从而使得算法可以在指定范围内进行搜索。然而, 在BPSO算法中, vkid代表一个概率, 也就是说粒子的每一维分量Sig (vkid) 的概率取1, 而以非Sig (vkid) 的概率取0。
2.2 行人特征向量提取
本研究利用BPSO算法对行人进行识别的主要思想是:从经过DCT变换以后的候选区域特征空间中, 提取有典型的特征子集。每个粒子通过适应度函数更新 (进化) , 每个粒子代表一个可能的优化解。适应度函数如下:
式中:Mi, M0分类的数目和样本空间总平均数。
且:
式中:N所有类中图像的数目;Wji, Ni类数和wi样本图像。
二进制粒子群算法进行特征提取的流程与标准PSO[7,8]算法大体一致, 只是先对图像进行DCT处理, 然后按照标准PSO算法流程进行特征提取。
3 行人检测实验
行人检测算法流程如图3所示。
3.1 图像均衡化处理
本研究对图像 (已经分割出来的候选区域) 进行直方图均衡化处理, 通过直方图均衡化对图像进行去噪, 提高对比度, 为识别做准备;部分经过均衡化的图像如图4所示。
直方图均衡化是一种使输出图像直方图近似服从均匀分布, 采用均衡化处理就是让所有的灰度级出现的概率基本相同, 即在每个灰度级上都具有相同的像素点数。在数字图像处理中, 实现直方图均衡化的具体步骤如下:
(1) 设原始图像的灰度级为fj, j=0, 1, 2, k, L-1 (其中, L是灰度级的个数) 。
(2) 计算原始图像灰度级的像素数目nj, j=0, 1, 2, k, L-1。
(3) 计算原始图像灰度级的频度:
式中:n原始图像的总像素数目。
(4) 计算累计分布函数:
(5) 计算输出图像的灰度级gi, i=0, 1, 2, k, m-1 (m为灰度级的个数) 。
且:
式中:INT取整。
(6) 统计映射后各灰度级的像素数目ni, i=0, 1, 2, k, , m-1。
(7) 计算输出图像的直方图:
(8) 用fj和gi的映射关系调整原始图像的灰度级, 从而获得直方图近似均匀分布的输出图像。
3.2 图像DCT特征提取
图像DCT特征提取的5个步骤如下:
(1) 把已经分割出来的候选区域进行二维离散余弦变换;
(2) 根据DCT的理论基础, 对得到的归一化后的图像进行DCT变换, 得到特征向量, 并将其存入向量库中以便后期比较。
(3) 应用BPSO算法对步骤 (2) 中得到的特征向量进行特征提取;
(4) 采用Euclidean距离, 将待识别图像的特征向量与特征库中的每个图像分别进行比较, 得到的最小的距离的特征向量即为识别得到的图像[9];
(5) 输出结果。
3.3 行人检测实验结果
为了验证本研究提出的算法的高效性, 笔者在Intel (R) Xeon (R) CPU E5520 2.27 GHz 2.00 GB的计算机上, 利用Matlab软件进行仿真实验。实验的结果如图5所示, 训练样本为50时识别率最高达到99.91, 识别时间也很快仅用10.5 s。
3.4 与SVM算法对比分析
支持向量机简称SVM, 虽然它在统计学习理论中发展的比较晚, 但是, 目前已经有一套坚实的理论基础为保障, 尤其在解决有限样本学习问题起着关键的作用。郭烈[10]运用SVM算法对行人进行分类识别。为了与本研究算法进行对比分析, 笔者也分别选取数量为50、500、1 000、1 500个正负样本进行试验, 并把训练时间以及识别率等方面进行数据的比较。SVM的试验结果如图6所示。
图6中, 横坐标表示样本的数量, 纵坐标为正负样本, 1代表正样本, 2代表负样本。Accuracy为识别率, MR表示漏检率, FFPW表示误检率。
为了获得最佳的识别效果, 本研究结合粒子群优化算法对识别寻优, 设置初始种群数目为30, 惯性权重取0.5, 学习因子分别取c1=1.456、c2=1.555, 最大迭代次数为100。进化迭代次数与适应度值之间的关系如图7所示, 迭代40次左右, 粒子达到最佳位置, 满足识别率, 达到最佳效果。
BPSO算法与SVM算法的对比结果如表1所示。
由表1可以看出:
(1) 无论数量是50、500、1 000还是1 500, 本研究算法无论在检测率还是检测时间上都优于SVM算法。
(2) 本研究算法在数量为50时检测率最高, 由于笔者研究的是车辆前方的行人, 数量不会很大, 刚好符合研究要求, 具有很好的应用前景。
(检测率/时间, 单位:s)
4 结束语
使用DCT图像压缩, 具有方法操作简单、准确率高、效率高、速度快等优点, 避免大量矩阵计算, 极大提高了图像压缩的效率和精度。本研究首先对以分割出来的行人候选区域进行二维离散余弦变换 (DCT) , 得到大量的典型特征, 然后应用BPSO算法进行特征选择, 最后与SVM算法进行比较, 实验结果如图5、图6所示。实验结果表明: (1) 在行人识别中运用BPSO算法, 有较高的识别率, BPSO算法是一种有效的特征提取方法。 (2) 与SVM算法的比较结果表明该算法无论在检测率还是在检测时间方面都更好。综上所述, 本研究算法可以达到预期的效果, 而且有很好的发展前景, 能够满足实际应用的要求。
摘要：针对汽车前方道路上的行人安全问题, 对道路行人采用二进制粒子群优化算法 (BPSO) 进行了检测, 以确保行人的安全。首先, 对随机采集的道路行人图像样本进行了二维离散余弦变换 (DCT) , 将行人的描述从图像空间转换为用少量数据点来表示频率域空间, 再利用DCT算法的对称性, 解压缩图像, 获得了行人图像的特征向量;其次, 应用BPSO算法对得到的特征向量进行了特征选择, 从行人频域特征空间中, 提取了有价值的特征子集, 得到了最具代表性的行人特征, 完成了行人检测。试验结果表明, 在样本数量较少的情况下, 无论在检测正确率还是检测实时性方面BPSO算法都优于传统的支持向量机 (SVM) 算法。研究结果表明, 二进制粒子群优化算法能够高效快速的检测到行人, 为车辆主动安全技术提供重要基础, 对于减少交通事故具有重要意义。
关键词：行人检测,二进制粒子群优化,离散余弦变换,支持向量机,特征提取
参考文献
[1]DOLLAR P, WOJEK C, SCHIELE B, et al.Pedestrian detection:an evaluation of the state of the art[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34 (4) :743-761.
[2]GUO Lie, GE Ping-shu, ZHANG Ming-heng, et al.Pedestrian detection for intelligent transportation systems combining AdaBoost algorithm and support vector machine[J].Expert Systems with Application, 2012, 39 (4) :4274-4286.
[3]ZENG Bo-bo, WANG Gui-jin, RUAN Zhi-wei, et al.Pair normalized channel feature and statistics-based learning for high-performance pedestrian detection[J].Optical Engineering, 2012, 51 (7) :077206-1-077206-9.
[4]YE Q, LIANG J, JIAO J, et al.Pedestrian detection in video images via error correcting output code classification of manifold subclasses[J].IEEE Transactions on Intelligent Transportation Systems, 2012, 13 (1) :193-202.
[5]ARMANFARD N, KOMEILI M, KABIR E, et al.TED:a texture-edge descriptor for pedestrian detection in video sequences[J].Pattern Recognition, 2012, 45 (3) :983-992.
[6]XU Yi-chun, XIAO Ren-bin.An improved binary particle swarm optimizer[J].Pattern Recognition and Artificial Intelligence, 2007, 20 (6) :788-793.
[7]GE W, COLLINS R T, RUBACK R B, et al.Vision-based analysis of small groups in pedestrian crowds[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34 (5) :1003-1016.
[8]SUHR J K, KANG H M, JUNG H G, et al.Dense stereobased critical area detection for active pedestrian protection system[J].Electronics Letters, 2012, 48 (19) :1199-1201.
[9]程国建, 石彩云, 朱凯.二进制粒子群算法在人脸识别中的应用[J].计算机工程与设计, 2012, 33 (4) :1558-1562.
二进制粒子群算法论文 第5篇
摘要：针对标准支持向量机训练时间过长与参数选择无指导性问题，给出一种通过粒子群优化双支持向量机模型参数的方法。与标准支持向量机不同，该方法的时间复杂度更小，特别适合不均衡的数据样本分类问题，对求解大规模的数据分类问题有很大优势。将该算法与标准的支持向量机分类器在不同的文本数据集上进行仿真实验对比，以验证算法的有效性。结果表明基于粒子群优化的双子支持向量机分类器的分类结果高于标准支持向量机分类结果。
关键词：双子支持向量机(TWSVM);分类算法;粒子群优化算法(PSO)
DOIDOI：10.11907/rjdk.151455
中图分类号：TP312
基金项目：玉林师范学院校级科研项目(YJYB04)
作者简介作者简介：刘建明(1986-)，男，广西博白人，硕士，玉林师范学院数学与信息科学学院助教，研究方向为数据挖掘与机器学习。
0 引言
粒子群优化算法[1](Particle Swarm Optimization，PSO)是由美国研究学者Kennedy等人在1995年提出的，PSO算法每一代的种群中的解具有向“他人”学习和“自我”学习的优点，该算法能在较少的迭代次数中找到全局最优解，这一特性被广泛应用于神经网络方法、函数优化问题、数据挖掘、模式识别，工程计算等研究领域。
双子支持向量机(Twin Support Vector Machines， TWSVM)是Jayadeva[23] 基于传统支持向量机在提出来的。TWSVM是从SVM演化而来的，是一种新型的基于统计学习理论的机器学习算法。TWSVM具有SVM优点，同时适合处理像文本自动分类、基因表达、空间信息遥感数据、语音识别等这样的大规模数据分类问题。
针对TWSVM对惩罚参数和核函数参数缺乏指导性问题，本文结合PSO算法的优点，给出一种基于PSO的
算法优化改进策略，对TWSVM分类器进行优化。PSO是一种基于群体智能的全局寻优算法，该算法能在较少的迭代次数中找到全局最优解，通过利用粒子群优化算法对双子支持向量机进行优化后，分类器较之标准支持向量机有更好的分类效果。
1 PSO算法
PSO算法步骤：①初始化粒子群，利用随机函数法给每一个粒子的初始位置和速度赋值;②根据第①步的赋值及初始位置与速度更新每一个粒子新的位置;③利用选定的适应度函数计算每一个粒子的适应度值;④对每一个粒子，对比其个体和群体的适应度值，并找出粒子经过的最好位置的适应度值，如果发现更好的位置及适应度值，那么就更新其位置;⑤根据公式更新每个粒子的速度与位置，如果找到最优的位置或者是到了最大的迭代次数，算法终止，否则转入第3步继续迭代求解。
2 双子支持向量机(TWSVM)
与SVM不同，TWSVM求解的`是一对分类超平面，SVM求解一个QP问题而TWSVM解决的是两个QP问题，而这两个QP问题的求解规模比SVM小很多。传统SVM构造两个平行的超平面，并且使两个超平面之间的距离最大即最大间隔化，TWSVM虽然也是构造超平面，但超平面之间不需要平行。TWSVM对每一个样本都构造一个超平面，每个样本的超平面要最大限度地靠近该类的样本数据点，而同时尽可能地远离另一类样本数据点。新数据样本将会分配给离两个超平面中最近的一个平面。事实上，该算法还可以沿着非平行面聚集，而且样本聚集方式是根据完全不同的公式聚合而成的。实际上，在TWSVM中的两个QP问题与标准SVM的QP问题除了求解约束问题不同外，求解公式是相同的。TWSVM的二分类算法通过求解下面的一对QPP(Quadratic Program Problem)问题进行二次规划优化[5]。
3 基于PSO的TWSVM分类算法
在TWSVM中，与SVM相同，都需要对参数进行确定，TWSVM对每个类均有一个惩罚参数和核函数参数。不同的惩罚参数和核函数参数影响分类的准确率，而PSO算法拥有全局的优化能力，因此，本文将PSO算法引入TWSVM中，解决TWSVM参数的选择问题，PSOTWSVM算法不仅能提高TWSVM的准确率同时又能降低SVM的训练时间，提高训练效率。图2展示了应用PSO算法对TWSVM参数选择的优化流程。
传统SVM是基于二分类提出的，其复杂度为O(n3)，其中n为样本数目[2]。然而在TWSVM二分类算法中，设每类样本数据为n/2，因此，求解两个优化问题时间复杂度为：O(2*(n/2)3)，所以在二分类问题中的TWSVM时间复杂度为传统SVM的1/4。推广到多分类问题时，可以发现在时间复杂度方面，TWSVM求解优化问题的时间更少。例如样本类别数为k类，那么该样本的时间复杂度为O(k*(n/k)3)。由于TWSVM分类算法对每类都构造一个超平面，因此该算法在处理不平衡数据时，即一类的样本数目比另一类的样本大得多情况时，TWSVM分别实施不同的惩罚因子，TWSVM克服了传统的SVM处理不均衡样本的局限性，这一点非常适用于大规模的不均衡分类问题。 4 算法仿真实验
为验证基于PSO的TWSVM分类算法的有效性，本文利用该算法构建一个文本分类器，运用不同数据集在该分类器上进行实验并与标准支持向量机构建的分类器进行对比仿真实验。
4.1 分类器性能评价
常用的分类器评价方法包括：准确率和召回率。这两个指标广泛应用于文本分类系统的评价标准。准确率(Precision)是指全部分类文本中划分的类别与实际类别相同的文本数量占全部文本的比率。召回率(Recall)是指分类正确的文本数占应有文档数的比率。文本分类输出结果见表1。
4.2 实验结果分析
由表2可知，PSOTWSVM的分类性能比TWSVM要好。因此，基于PSO的TWSVM是一个有效算法。该算法不但比标准的SVM算法训练时间更短，而且比TWSVM有更好的准确率，PSOTWSVM解决了TWSVM的参数选择问题，提高了TWSVM的泛化性。
5 结语
通过基于PSO的TWSVM分类算法与TWSVM算法的分类对比实验可知，应用PSO算法的全局寻优能力提高了TWSVM分类的能力。PSO优化后TWSVM分类器的性能更为优越。基于PSO的TWSVM分类算法比标准的SVM时间复杂度更小，比TWSVM的准确率更高，基于PSO的TWSVM算法在分类问题上较之传统的SVM算法有更大的优越性。
参考文献：
[2]JAYADEVA，R KHEMCHANDAN， S CHANDRA.Twin support vector machines for pattern Classification[J]. IEEE Trans. Pattern and Machine Intelligence，，29(5)：905910.
[4]谷文成，柴宝仁，腾艳平. 基于粒子群优化算法的支持向量机研究[J].北京理工大学学报，2014， 34(7)：705 709.
[6]王振.基于非平行超平面支持向量机的分类问题研究[D].长春：吉林大学，2014.
二进制粒子群算法论文 第6篇
微网是一种由负荷、微电源 (分布式电源) 和储能装置共同组成的有机系统。它可以有效地整合各种分布式电源, 充分发挥分布式电源所带来的经济效益和环境效益;可以更好地满足用户对电能质量和供电可靠性更高的要求;可以实现多种能源的梯级利用[1,2,3,4,5,6,7]。
微网的优化运行[8,9,10,11,12]是微网研究的重点和难点问题, 属于多约束、多目标问题, 一般采用智能优化算法来进行优化。
二进制粒子群算法具有结构简单、收敛速度快、对目标函数要求少等优点, 可以很好地解决机组组合优化的问题;但是也存在“早熟”问题, 易陷入局部最优解[13,14]。混沌优化算法具有随机性、遍历性和内在规律性的特点, 但是算法的精度与寻优函数的复杂程度和寻优空间的大小有关。混沌二进制粒子群算法将二进制粒子群算法和混沌算法相结合, 利用混沌变量的遍历性和对初值敏感的特性, 可以有效地克服二进制粒子群算法的早熟问题[15,16,17]。
微电源可以分为输出功率完全可控和不完全可控2种类型, 根据微电源的类型不同, 采用的控制策略也不一样。光伏发电、风力发电等输出功率不完全可控的微电源一般采用最大功率点跟踪 (MPPT) 控制的方式, 不承担负荷波动和调整频率的任务。燃料电池、蓄电池等储能设备和燃气轮机、小型汽轮机等输出功率完全可控的微电源[18,19,20,21,22], 可以通过采用合理的控制策略相互配合完成频率调整的任务, 是微网研究的重点和难点。
本文针对独立微网系统内可控型微电源的组合优化问题, 首次应用混沌二进制粒子群算法求解优化问题, 仿真结果证明了该方法的有效性和正确性。
1 独立微网系统模型
1.1 微网结构
本文采用简化的独立微网模型, 该微网共有10个节点, 具体结构如图1所示。微电源有微型燃气轮机 (MTG) 、柴油发电机 (DEG) 、燃料电池 (FC) 、光伏电池 (PV) 、风力发电 (WT) 。不同种类的微电源具有不同的特性。
光伏电池与风力发电机组的发电出力受气候环境影响较大, 具有波动性、随机性、间歇性, 属于输出功率不完全可控的微电源。因此, 本文采用homer软件对光伏电池和风力发电机组的发电出力进行预测, 并且将光伏电池与风力发电机组的预测发电出力作为“负”负荷, 与传统负荷相叠加得到广义负荷, 并将可控型微电源作为优化变量。
1.2 目标函数
独立微网系统的微电源组合优化是一个多目标、多约束条件的复杂优化问题。本文同时考虑了微网的经济成本最小和网损最小作为目标函数, 其中经济成本主要考虑了燃料成本、运行维护成本、污染物排放折算成本和启停成本。赋予不同的子目标函数不同的权重, 并进行线性加和, 将多目标问题转化为微网系统综合成本最低的单目标优化问题, 同时采用罚函数的方法对等约束条件进行处理, 采用越限取限值的方法对不等式约束条件进行处理。
1.2.1 微网经济成本
(1) 启停成本。
微电源的启停需要一定的费用, 表达式如下:
其中, FtOC为t时刻微网的启停成本;Uit为第i种微电源在t时刻的状态, 取值为0或1, 1表示开机状态, 0表示停机状态;Csi为第i种微电源的启停成本。
(2) 燃料成本。
a.微型燃气轮机的燃料成本与自身的工作效率有关, 表达式如下:
其中, FtMTG为t时刻微型燃气轮机的燃料成本;C为燃气轮机采用的燃料气体的单价, 本文取2元/m3;TLHV为天然气的低热热值, 本文中取9.7 k Wh/m3;PtMTG为微型燃气轮机在t时刻的发电出力;ηMTG为燃气轮机的效率, 其大小与微型燃气轮机输出功率的大小有关[9]。
b.柴油发电机的燃料成本就是它的耗量特性函数, 表达式如下[13]:
其中, 参数a、b、c的大小一般由生产厂家给定, 本文选取a=6, b=0.012, c=8.510-4。
c.燃料电池的燃料成本与其自身的工作效率有关。表达式如下:
其中, FtFC为燃料电池在t时刻的燃料成本, PtFC为燃料电池在t时刻的发电出力, ηFC为燃料电池的效率[17]。
(3) 运行维护成本。
微电源的运行维护成本可以用微电源输出功率乘以相关的系数来表示, 表达式如下:
其中, FMt为微电源在t时刻总的运行维护成本, ki为第i种微电源的运行维护成本系数, Pit为第i种微电源的输出功率, N为微电源的数目。ki的取值按照文献[11]选取, 其中微型燃气轮机、柴油发电机、燃料电池的运行维护成本系数分别为0.038 49元/k W、0.082 49元/k W、0.027 48元/k W。
(4) 污染物排放折算成本。
微型燃气轮机和柴油发电机在运行的过程中会产生氮氧化物 (NOx) 、二氧化硫 (SO2) 、二氧化碳 (CO2) 等空气污染物。考虑到微网的环境效益, 将这些污染物按照一定的成本进行折算, 作为微网优化运行的目标。具体表达式如下:
其中, FPt为微网的环保折算成本, aij为第i种微电源排放的第j种污染物的排放因子, q为污染物的种类, cj为第j种污染物的折算成本。
不同种类的污染物折算成本以及微型燃气轮机、柴油发电机、燃料电池的排放因子如表1所示[16]。
综合考虑以上因素, 微网的经济成本如下:
其中, Ct为在t时刻微网的经济成本。
1.2.2 网损
由于独立微网系统的电压等级相对较低, 一般为380~1000 V, 因此独立微网系统中的电阻与电抗的比值, 即R/X值一般较大, 在5至几十之间[17], 由此, 独立微网系统的网损可通过潮流计算的方法得到, 表达式如下:
其中, Pk、Qk为第k条支路传输的有功、无功功率, M为支路总数, Rk为支路k电阻, 为支路电压幅值。
在充分考虑独立微网系统的经济成本与系统网损的基础上, 通过赋予不同目标函数合适的权重, 并进行线性加和, 其多目标函数转化为微网系统的综合成本最低:
其中, λ1、λ2分别为多目标的权重系数, λ1、λ2赋权的原则主要是在独立微网系统中, 通过权衡微网系统的经济成本与系统网损之间的重要性, 进行线性加权。比如重点考虑微网系统中的网损对独立微网系统优化运行的影响, 可以取λ2=0.8, 并且满足λ1+λ2=1, 这样将多目标问题转化为单目标问题。
1.3 约束条件
a.功率平衡约束。
其中, Pi为第i种微电源输出的功率, Pload为总负荷。
b.微电源输出功率约束。
其中, Pimin、Pimax分别为第i种微电源输出功率的下限和上限。
c.节点电压约束。
其中, Ui为第i个节点的电压, Uimin、Uimax分别为第i个节点的电压下限和上限。
d.最短开停机时间约束。
其中, Tti, on和Tit, off分别为第i种微电源的开、停机时间, Ti, up和Ti, down分别为第i种微电源的最短开、停机限制。
e.微电源爬坡率约束。
其中, Pti为第i种微电源在t时刻的输出功率;Pit-1为第i种微电源在t-1时刻的输出功率;ΔPimax、ΔPimin分别为第i种微电源单位时间内的发电出力上、下限。
2 混沌二进制粒子群算法原理
2.1 混沌搜索
混沌优化算法具有遍历性、随机性、规律性的特点, 能在一定的范围内按照自身的规律不重复地遍历所有的状态。混沌优化算法能避免陷入局部极小, 比随机搜索更具有优越性, 易于跳出局部最优解。
在混沌优化中, 一般应用Logistic映射来产生混沌变量, Logistic映射的形式如式 (17) 所示:
其中, xk为第k次迭代的混沌变量。
Logistic映射是模拟生物种群随时间演变的数学模型。当μ=4时, 系统进入混沌状态, 混沌变量能遍历在[0, 1]之间的所有状态。注意式 (17) 中存在不动点0.25、0.5、0.75, 应避免混沌变量的初值为这些点。
2.2 二进制粒子群
二进制粒子群算法是在基本粒子群算法的基础上提出的, 适用于离散空间优化问题[18]。在二进制粒子群中, 粒子的速度向量不再是粒子位置的变化率, 而是粒子位置改变的概率。速度向量表示粒子以某一概率确定是1状态还是0状态。根据速度的大小来选择粒子在对应位置上为1或0。在二进制粒子群中, 粒子位置更新公式为:
其中, Uik, d为在d维的搜索空间中第i个粒子在第k次迭代时的位置;r为[0, 1]之间的随机数;Sigmoid函数定义为式 (19) 所示[15]。
2.3 混沌二进制粒子群算法
粒子群算法后期收敛速度慢、收敛精度差、容易陷入局部最优解, 为此很多研究学者将二进制粒子群算法和混沌优化算法相结合, 利用混沌变量的初值敏感性和遍历性特点, 对失去搜索能力的粒子进行混沌搜索。文献[23]提出了粒子群早熟现象的判断机制, 并给出了混沌粒子群算法的计算步骤。文献[24]提出了自适应的混沌粒子群算法, 利用混沌优化算法初始化粒子群体和对优选粒子进行操作。
在粒子群体的一次迭代寻优过程中, 至少有1个粒子处于不动状态, 其他粒子逐渐向该粒子靠近。当存在一个粒子, 其位置距离不动粒子足够近时, 该粒子只能搜索有限的区域, 寻优功能大幅减弱[17]。为了提高此粒子的搜索性能, 本文在粒子群进行优化的前期采用混沌算法进行初始化, 优选初始粒子群体。
采用混沌搜索的方法对即将重叠的粒子进行分离, 通过判断任意粒子与当前最优粒子之间的距离作为粒子是否重叠的标准。当粒子的距离小于设定值时, 认为2个粒子已经重叠, 此时当前最优粒子保持位置不变, 另一个粒子映射到混沌变量空间, 以混沌变量进行式 (17) 所示的混沌运动。将得到的新的混沌变量重新映射到变量搜索空间中得到新的粒子, 用混沌搜索得到的新粒子替换原来的粒子。
2.4 算法步骤
a.初始化。输入粒子群规模、变量个数、惯性权重、最大飞行速度、最大迭代次数、各个微电源的参数、初始启停状态等。利用混沌迭代公式初始化N个矢量, 并尽可能均匀地分布在[0, 1]空间中, 然后映射到变量搜索空间, 得到粒子的初始化位置。
b.计算每一个粒子的适应值δfit=Ft (x) , 取最小值作为群体当前的最优解Fbest, 并记录该粒子位置为全局极值点xgbest, 设定当前每个粒子的位置为个体极值点xpbest。并设定当前迭代次数nit为1。
c.判断当前的迭代次数是否满足最大迭代次数, 若满足则输出计算结果, 否则设定迭代次数nit=nit+1。
d.更新粒子的位置和速度。并根据式 (18) 更新微电源的开停机状态变量。
e.计算任意粒子与当前最优粒子之间的距离, 若x (i) 为任意粒子i当前的位置, x (r) 为当前最优粒子的位置, 当粒子的距离d (i) = (x (i) -x (r) ) 2小于给定值 (本文中取10-3) 时, 则一个粒子不变, 另一个粒子赋予混沌运动, 在给定的步数内进行混沌搜索, 用得到的结果替换原来的粒子。
f.判断粒子的状态是否满足各类不等式约束条件, 若满足则保留粒子位置, 否则取限值。
g.计算当前每个粒子的适应值, 保存全局最优解Fbest, 全局最优位置xgbest和个体最优位置xpbest, 并转到步骤c。
3 仿真分析
本文选取的独立微网系统的电压等级为380 V, 线路选择LJ-16型导线, 线路阻抗为R=1.98Ω/km, X=0.358Ω/km[24]。本文采用混沌二进制粒子群优化算法进行计算, 其中粒子群规模为200, 变量个数为3, 每个变量是24维, 代表一天24个小时时间段, 惯性权重C1=2、C2=2, 最大飞行速度vmax=10, 最大迭代次数为1500。假设本文同等看待微网系统的经济成本与系统网损, 因此赋权为λ1=0.5, λ2=0.5。各个微电源的相关参数如表2所示。
微网的“广义负荷”曲线、日负荷预测曲线和风力发电、光伏发电在某个典型日24 h内的功率预测曲线如图2所示。
本文首次将混沌二进制粒子群算法应用到微网经济优化运行中进行分析, 计算结果得出的微网总费用曲线如图3所示, 微网的总网损曲线如图4所示。
由图2、图3可以看出微网总的费用变化趋势与微网的“广义负荷”变化趋势相同;由图2、图4可以看出微网的总网损变化趋势与微网的“广义负荷”变化趋势相同。
各个微电源输出功率的变化情况如图5所示。由图5中可以看出在03:0008:00和10:0018:00, 微型燃气轮机的输出功率为0, 此时微型燃气轮机处于停机状态;在01:0009:00, 柴油发电机输出功率为0, 此时柴油发电机处于停机状态;燃料电池的输出功率一直大于0, 所以燃料电池一直处于开机状态。
图6是微型燃气轮机、柴油发电机、燃料电池的发电费用与发电出力关系图。由图6可知, 在发电出力小于50 k W的范围内, 燃料电池的发电费用总是比微型燃气轮机、柴油发电机的发电费用要少, 所以燃料电池应一直处于开机状态。当发电出力小于4 k W时, 微型燃气轮机的发电费用小于柴油发电机的发电费用, 与图5中微型燃气轮机处于开机状态, 而柴油发电机处于关机状态时的发电出力相对应, 验证了图5结果的正确性。
根据表1、图4和图5可以看出, 虽然微型燃气轮机和柴油发电机是可控的微电源, 但在当前低碳环保的市场环境下, 由于其排放CO2等污染物, 微型燃气轮机和柴油发电机的发电效率受到了一定的限制。而燃料电池是环境友好型的发电装置, 发电效率较高。
4 结论
本文针对独立微网系统中可控型微电源的组合优化问题进行深入研究, 并将二进制粒子群与混沌优化算法相互结合, 首次应用混沌二进制粒子群算法进行求解, 实现了独立微网系统的经济优化运行, 进一步提高了微网系统的整体经济效益和环境效益, 主要结论如下。
a.针对独立微网系统, 充分考虑了微网中不同种类微电源的发电出力特性, 以微网的经济成本和系统网损成本线性加和构成的微网系统的综合成本最低为目标函数, 保证了系统的经济性。
b.将二进制粒子群与混沌优化算法相结合, 首次将混沌二进制粒子群算法应用到微网优化运行中进行求解, 并通过算例仿真验证。仿真分析表明, 混沌二进制粒子群算法可以有效地解决独立微网系统的优化运行问题。
c.根据不同种类微电源的发电出力与其发电费用的比较可以看出, 虽然微型燃气轮机和柴油发电机是可控的微电源, 但在当前低碳的环境下, 由于其排放CO2等污染物, 微型燃气轮机和柴油发电机的发电效率受到了一定的限制。而燃料电池是环境友好型的发电装置, 发电效率较高。
由于本文仅针对独立微网系统可控型微电源的组合优化问题进行了研究, 并未涉及微网并网优化运行问题, 因此在本文研究的基础上, 可针对微网并网系统以及考虑微网与大电网之间的交互功率等方面继续深入研究。
二进制粒子群算法论文 第7篇
基因选择的目的是从基因表达出的海量数据中筛选出一些与分析的疾病具有最大相关性的部分, 这部分基因又称为诊断基因。然而, 应该在海量的数据中选取哪些部分, 选择多少基因对解决问题效果最好是一个复杂度极高的NP难问题。可以利用穷举的方法来解决这一问题, 但是, 基因表达的数据是海量的, 所以穷举法是不可行的。不过可以通过寻找次优解的方法来解决该问题。
一、基于二进制细菌群算法的基因选择和支持向量机优化方法算法
基于二进制细菌群算法的基因选择和支持向量机优化算法的具体流程步骤说明如下:
步骤1:使原始基因的表达数据样本通过留一交叉验证法分成测试集和训练集两部分。将基因数据库中的数据平均分成n份作为样本, 首次验证时, 选取n-1个样本用来训练, 其余的样本用来测试, 将上述方法执行n次。
步骤2:通过Wilcoxon方法对被归一化后的训练集上的基因表达数据进行预处理。大量的噪声基因将在这一步中被剔除。在实验中保留了区分能力最强的前100个基因。
步骤3:通过细菌群算法和支持向量机对步骤二获得的基因子集进行选择同时优化支持向量机核函数的参数。
二、实验结果及分析
(一) 基因表达数据库
在该实验中, 通过已经公开的3个基因数据库对本论文算法的性能进行评价: (1) 白血病数据库; (2) 乳腺癌数据库; (3) 结肠数据集。
(二) 实验结果
在本实验中, 选择高斯核作为支持向量机的核函数, 所以应该同时对惩罚参数C和高斯核宽度sigma进行优化。
为了更好地对实验结果进行比较, 细菌群算法又分别与C4.5决策树 (C4.5 decision tree) 算法和朴素贝叶斯 (Naive Bayes) 算法相结合对基因进行选择和分类。三种不同的方法分别在三个数据集上选出的基因数目的平均值与分类正确率的平均值如表1所示。由表能够看出, 在白血病数据集上, 本文提出的BCC+SVM算法通过28个基因就能够得到100%的正确率, 但PSO+NB算法的正确率只为96.9%, PSO+C4.5算法为96.1%;该论文的算法在乳腺癌数据集上利用27.6个基因得到了正确率100%的分类结果, 其他两个算法的结果都只为95.2%;在结肠癌数据集上该论文的算法结果为92.2%, 同样比其他算法分类效果好。
三、结论
该论文在二进制细菌群算法中加入遗传选择算法中的选择、交叉、变异算子, 得到了基于二进制细菌群算法的基因选择和支持向量机优化方法, 进而用这种方法搜寻最优基因集合。最后对一些公开数据集进行了仿真实验, 实验表明这种算法选出来的基因可以有效增加分类推广能力。
参考文献
[1]Pierre, Brunak, 张东晖等译.生物信息学 (第2版) [M].北京:中信出版社, 2003.
蚁群粒子群混合算法研究 第8篇
1 蚁群、粒子群算法
1.1 基本蚁群算法
蚁群算法(Ant Colony Algorithms)是一种源于大自然中生物世界的新的仿生类算法，作为与遗传算法同属一类的通用型随机优化方法，它根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索的模型，在一系列困难的组合优化问题求解中取得了卓有成效的结果。与遗传算法类似,蚁群算法不需要任何先验知识,最初随机的选择搜索路径，随着对解空间的了解，搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间
基本的蚁群算法AS可以简单表述如下：在0时刻进行初始化过程，蚂蚁放置在不同的城市，每一条边都有一个初始外激素强度值τij(0).每一只蚂蚁禁忌表的第一个元素置为它的开始城市.然后，每一只蚂蚁从城市i移动到城市j，依据两个变量的概率函数选择移动城市(包括参数α和β)).在n次循环后，所有蚂蚁都完成了一次周游，同时他们的禁忌表将满，这时，计算每一只蚂蚁k的路径长度Lk，ΔτkijΔ依据公式(3)更新.而且，保存由蚂蚁找到的最短路径(即minLk,k=1,,m)，置空所有禁忌表.重复这一过程直到周游计数器达到最大(用户定义)周游数maxNc，或者所有蚂蚁都走同一路线.后一种情况被称为停滞状态.如果算法在Nc次循环后结束，蚂蚁算法的复杂度为o(Ncn2m).信息素更新公式：
其中，ρ是一个参数，1-ρ表示在时刻t和t+n之间外激素的蒸发，
Δτkij是单位长度上在时刻t和t+n之间第k只蚂蚁在边e(i,j)留下的外激素的数量,其中,
如果在时刻t和t+n之间第k只蚂蚁在边e(i,j),其他Q是一个常数，Lk是第k只蚂蚁周游的路程长度.
第k只蚂蚁从城市i到城市的跃迁概率为
其中准，N为一组城市，tabuk表示第k只蚂蚁的禁忌表，α和β都是控制外激素与可见度的相对重要性的参数.跃迁概率是可见度和t时刻外激素强度的权衡。
1.2 粒子群算法
粒子群优化算法(particle swarm optimization PSO)是基于群体智能的一种进化计算，由Eberhart博士和kennedy博士发明。粒子群优化算法也是基于人口的最优化方法，该方法是随机产生一组数据，然后执行最佳收索路径，粒子群优化算法在运算过程通过其中最好的粒子找到最佳的解决方案。粒子群优化算法有较好的后台计算智能，而且运算更加简单，依照它的优势，粒子群优化算法不仅适用于科学研究，而且还适用于工程应用，目前粒子群优化算法在进化计算领域中已经吸引了众多人的注意，近几年来，有很多关于粒子群优化算法的研究成果，粒子群优化算法已经被广泛地应用于最优化、人工神经网络、仿生识别、模糊控制和其它一些领域[2]。
PSO中每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数昕决定的适应值，对于每个粒子，还有一个速度决定它们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪2个“极值”更新自己，一个是粒子本身所找到的最优解，称为个体极值pbest;另一个极值是整个种群目前找到的最优解，该极值是全局极值gbest。另外，也可以不用整个种群而只用其中一部分为粒子的邻居，那么在所有邻居中的极值就是局部极值。在找到这两个最优值时，每个粒子根据如下公式更新白己的速度和新的位置：
其中：vk为第k步粒子的速度向量;xk为第k步粒子的位置;pbestk为第k步粒子本身所找到的最好解的位置：gbestk为第k步整个种群目前找到的最好解的位置：w表示惯性权重：c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长，c1,c2通常在0～2间取值;r1奂(0,1)，r2奂(0,1)为2个相互独立的随机函数;每一个维粒子的速度都被限制于一定范围内，即vk[-vmax,vmax]如果v1>vk时，vk=vmax;如果v1<-vk时，vk=-vmax。
2 混合算法
蚁群粒子群混合算法，在众多的领域中应用价值得到越来越多的体现，其在解决旅行商问题、聚类问题、函数连续优化问题以及实际应用领域如电力系统等的运算效率及与其他算法的仿真实验证实其优越性。
2.1 蚁群粒子群混合算法求解旅行商问题
蚁群算法利用了信息素进行传递信息，而粒子群优化算法利用了本身的信息，个体极值信息和全局极值信息三个信息，来指导粒子下一步迭代位置。混合的特性是让蚂蚁也具有粒子的特性，首先蚂蚁按照蚁群算法，先完成一次遍历，再让蚂蚁根据局部最优解和全局最优解进行调整，思路如下：对于旅行商问题，其当前的位置是基本路径，让当前解与个体极值和全局极值做做交叉操作，产生的解为新的位置，再做变异操作。交叉变异参考：蚁群算法应用及其他算法混合[3]。检验算法有效性,与模拟退火算法、遗传算法分别解决30个城市的Oliver30，结果表明混合算法的效果最好，算法可以显著提高计算效率，具有较大的是使用价值。
2.2 蚁群粒子群混合算法求解聚类问题
周丽娟的改进的粒子群算法和蚁群算法混合[4]在文本聚类问题中取得了很好的效果。该方法主要思想是:
第一步,利用粒子群算法有效的全局搜索特性,对文本进行粗聚类,可以得到聚类原型,这里对精度不做要求,只要得到聚类原型处于最优解的附近邻域即可;
第二步,在第一步得到的聚类原型上的基础上,利用蚁群算法精确求解得到最优聚类
在改善基本粒子群算法的收敛性能方面,引用了Y.Shi和R.C.Eberhart首次在速度进化方程中引入惯性权重[1],即
其中,0<ω<1称为惯性权重,因此,基本粒子群算法是惯性权重ω=1的特殊情况。惯性权重ω使得粒子保持运动惯性,具有扩展空间的趋势,有能力探索新的区域,用来平衡全局搜索能力和局部搜索能力。
2.3 广义蚁群粒子群算法求解电力系统经济负荷分配问题
侯云鹤等人将PSO引入GACO的局部搜索中[5]，采用GACO进行全局搜索，确定最优解存在的邻域，通过PSO实现局部搜索，由于PSO算法充分利用以往的信息，又不依赖于梯度，可实现非凸空间上的高效搜索，在实际计算中比蒙特卡罗法J具有更高的精度和更快的速度。GACO与PSO的结合算法在保证算法全局收敛的前提下，提高了优化的效率和精度。
对于一般的约束优化问题，采用外点法构造辅助函数，将较难计入可行域的l0个等式约束和U0个不等式约束以罚函数形式计入目标函数中，即
式中X=(x1,x2,,xn)T为待优化矢量;l、u分别为原等式约束和不等式约束的个数。为加速迭代，使罚系数σi与当前迭代次数K有关，开始时较小，这样有助于大范围搜索，再逐步增大，使最终结果成为原问题的解。记式(8)的可行域为S。
式中α为正系数，用于调节σi的变化速度;σi,max为σi(K)的上限值;T为迭代次数上限值。
经试验广义蚁群与粒子群结合算法与粒子群算法及改进进化规划算法相比，收敛精度更高，解的离散度更小。将粒子群算法应用于广义蚁群算法的邻域搜索中，在确保广义蚁群算法的全局收敛性的同时，也提高了算法的优化效率，该方法还可求解常规算法难以解决的非凸、非线性约束优化问题。在提供最优解的同时，还可提供一组次优解以供选择，且容易实现并行运算。
2.4 混合算法解决函数连续优化问题
薛嘉等首先对解空间进行区域划分[6]，进而利用ACO在优化初期具备的快速收敛性能，在整个解空间内搜索最优解的敏感区域。然后利用蚁群的搜索结果初始化PSO粒子，利用PSO快速和全局收敛性进行所在小区域内的搜索。种群更新时根据蚁群的拓扑结构和小区域间的阶跃规则，蚁群不断向最优解敏感区域聚集，使得敏感区域内粒子数增加，则局部的PSO搜索策略可以更细密的搜索最优。实例结果表明，CA-PSO既能保证解的分布性与多样性，又避免了在多峰值函数寻优过程中陷入局部最优解而停止运算，最终将收敛到全局最优解。
2.5 主从递阶结构的蚁群粒子群求解算法
张维存,康凯提出一种主、从递阶结构的蚁群粒子群求解算法[7]。算法中,主级为蚁群算法,完成任务模式选择;从级为粒子群算法,完成主级约束下的任务调度。然后,以工期最小和资源均衡分配为目标设计蚂蚁转移概率、模式优选概率和任务优选概率。最后,针对PSPLIB中的测试集对算法主要参数进行优化,并通过与其他算法比较验证了算法的有效性。仿真和比较表明,该算法具有良好的求解性能和应用前景。
3 结束语
蚁群算法在求解复杂优化问题特别是离散优化问题方面已经显示出了优势，具有较强的鲁棒性和搜索较好解的能力，易与其他算法结合。粒子群优化算法PSO具有并行处理、鲁棒性好和计算效率高等特点,已成功应用于各种复杂的优化问题。而二者结合的蚁群粒子群混合算法在解决旅行商问题的仿真实验表明，混合算法的优化质量和效率都优与模拟退火算法、传统蚁群算法和遗传算法进行比较，接近理论最佳值，混合算法效果较好;在解决连续优化问题、电力系统经济负荷分配、非凸、非线性约束优化问题等方面，都有很好的效果，当然混合算法的研究还处于初级阶段，蚁群算法、粒子群算法在各自的改进算法在优越性方面又有所提升，而针对改进算法的混合算法还有很大的探索空间，其理论依据、收敛性等方面还有待进一步的研究。
参考文献
[1]李炳宇,萧蕴诗.一种基于粒子群算法求解约束优化问题的混合算法[J].控制与决策,2004(7):804-812.
[2]Shi Y,Eberhart R C.A modified particle swarmoptimizer[C].//Proceedings of the IEEE Congress on Evolutionary computation.Piscat-away:IEEE Press,1998:3032-3081.
[3]高尚,韩斌,吴小俊,等.求解旅行商问题的混合粒子群优化算法[J].控制与决策,2004,19(11).
[4]周丽娟.改进粒子群算法和蚁群算法混合应用于文本聚类[J].长春工业大学学报2009,30(3):341-345.
[5]林昭华,侯云鹤,熊信艮,等.广义蚁群算法用于电力系统无功优化[J].华北电力人学学报,2003,30(2):6-9.
[6]薛嘉,蔡金燕,马飒飒,等.基于群智能的连续优化算法研究[J].计算机工程与设计,2009,30(8):1969.
粒子群优化算法综述 第9篇
通过对生物群体的观察和研究发现, 生物群体内个体间的合作与竞争等复杂性行为产生的群体智能,往往能为某些特定的问题提供高效的解决方法。
Kennedy等受鸟群觅食行为的启发,于1995年提出粒子群优化算法(Particle Swarm Optimization,PSO)[1]。与进化算法相比,PSO保留了基于种群的全局搜索策略,但其所采用的速度位移搜索模型操作简单,避免了复杂的进化操作。
PSO首先初始化为一群随机粒子(随机解),然后通过迭代搜索最优解。在每一次迭代中,粒子通过个体极值与全局极值更新自身的速度和位置:
vi=wvi+c1rand()(pi-xi)+c2rand()(g-xi) 。 (1)
xi=xi+vi 。 (2)
其中:vi是第i个粒子的速度;xi是第i个粒子的位置;w是惯性权重;pi是第i个粒子经历的最好位置;g是群体所有微粒经历的最好位置;rand()是均匀分布在(0,1)之间的随机数;c1和c2是学因子,通常c1=c2=2。
粒子就在解空间内不断跟踪个体极值与全局极值进行搜索,直到达到规定的最大迭代次数或达到最小的误差标准为止。图1为粒子群优化算法流程图。
2 PSO算法的改进
PSO算法在多维空间函数寻优、动态目标寻优等方面有着收敛速度快、解质量高、鲁棒性好等优点,特别适合于工程应用。而且比较简单,计算量小,实用性好,编程实现较更容易。PSO算法在搜索的初期收敛速度很快,但在后期却易于陷入局部最优。针对这个缺陷,众多学者提出了改进的办法。
2.1 自适应PSO
较大的惯性权值w有利于搜索时跳出局部极值点,而较小的w有利于算法收敛和提高搜索精度。在最初版本中w为常数,后来,文献[2]提出了w的自适应调整策略,刚开始时w较大,随着迭代的进行,w线性减小。文献[3]认为刚开始w=1.4,然后逐步减小到w=0.35比较合适。这种方法的进一步发展是模糊自适应PSO,它用自适应模糊惯性权值控制器来动态优化w。
2.2 带选择机制的PSO
基本的PSO没有选择机制,微粒个体不会被别的微粒个体所取代,迭代时,每个微粒不断地改变自己的位置直到搜索结束。
文献[4]提出一种带选择机制的PSO。这种算法依据某些预定的规则,将每个个体的适应值基于其当前位置,与其他个体进行比较,然后根据定义的规则将所有个体排序,得分最高的出现在群体的前面。一旦群体排序完毕,群体中当前得分低的一半被群体中当前得分高的另一半取代。带选择机制的PSO在解决单峰函数的优化问题时效果明显,但并不一定对所有的优化问题都很有效。这种算法由于有了选择机制,加快了对当前较好区域的开发过程,使得收敛速度较快,但也增加了陷入局部极值解的可能性。
2.3 带空间邻域的PSO
Angeline的研究表明,尽管PSO能比其他进化算法更快地得到较为理想的解,但当迭代次数增加时,并不一定能进行更精确的搜索。为此,可引入一个变化的邻域算子(neighborhood operator)。在迭代的初始阶段,一个微粒的邻域就是它本身;随着迭代的进行,根据候选个体与邻域中心的距离,逐步引入距离近的个体,邻域逐渐变大,包含越来越多的微粒,最后包含所有的微粒。这样,原来的全局历史最好位置搜索就变成了微粒邻域的局部历史最好位置搜索。文献[5]用更为详细的资料和许多测试函数的仿真结果表明这一方法能有效地获得全局最优解。
结合空间邻域和环状拓扑结构,文献[6]进一步提出了具有社会模式(social stereotyping)的聚类分析PSO。该法将微粒群体中的一些微粒作为中心,再将离它最近的N个微粒和中心微粒作为一簇,然后计算每个簇的中心位置,并用这些中心位置替代个体历史最优位置和全局历史最优位置。但文献[6]所示的研究结果并没表明这一方法具有更好的性能,结果难以令人满意,还有许多问题有待于进一步研究。
2.4 带变异算子的PSO
针对PSO算法存在易陷入局部最优点的缺点,文献[7]引入变异算子,与遗传算法类似,在子群的历史最优粒子位置连续无变化或变化极小时,若粒子群出现较严重聚集情况,则保留历史最优粒子位置,将粒子中少部分重新随机初始化,以此来增强全局搜索能力,克服收敛到局部最优点的缺点,同时又不降低收敛速度和搜索精度。
2.5 免疫PSO算法
免疫PSO算法是受生物系统免疫机制的启发,把免疫系统的免疫信息处理机制引入到PSO算法中[8]。此算法结合了PSO算法所具有的全局寻优能力和免疫系统的免疫信息处理机制,改善了PSO算法摆脱局部极值点的能力,提高了算法优化过程中的收敛速度和精度。
3 PSO算法的应用
当前,PSO算法已得到了广泛应用,最直接的应用或许就是多元函数的优化问题,包括带约束的优化问题。如果所讨论的函数受到严重的噪声干扰而呈现非常不规则的形状,同时所求的不一定是精确的最优值,而PSO算法能得到很好的应用。比如在半导体器件综合方面,需要在给定的搜索空间内根据所希望的器件特性来得到符合要求的设计参数,而所能利用的器件模拟器通常得到的特性空间是高度非线形的。有人用PSO替换GA进行了计算,发现PSO能比GA更快地找到较高质量的设计参数。
另外,还有一种更广泛的应用:简单而有效地演化人工神经网络,不仅用于演化网络的权重,而且包括优化神经网络的结构。作为一个演化神经网络的例子,PSO算法已经用于分析人的颤抖,包括帕金森(Parkinson)病和原发性颇抖,是一个非常具有挑战性的领域。PSO已成功地应用于演化一个用来快速和准确地辨别普通个体和有颤抖个体的神经网络。而网络的输入则为从一个活动变化记录系统中获得的归一化的移动振幅。另一个应用例子是使用PSO对一个电气设备的功率反馈和电压进行控制。这里采用一种二进制与实数混合的PSO算法来决定对连续和离散的控制变量的控制策略,以得到稳定的电压。
4 PSO算法研究展望
(1)应用领域的拓展:
虽然已被成功地用于函数优化及神经网络的训练等领域,但在更多领域的应用还处于研究阶段,可见报道不多。开拓新的应用领域,在应用的广度和深度上进行拓展都是很有价值的工作。
(2) 算法参数的确定:
PSO中的一些参数如c1、c2、w、微粒个数以及迭代次数等往往依赖于具体问题,依据应用经验,经多次测试来确定,并不具有通用性。因此,如何方便有效地选择算法参数,也是迫切需要研究的问题。
(3)算法的改进研究:
由于实际问题的多样性和复杂性,尽管已出现了许多改进的算法,但远不能满足需要。研究新的改进以便能更好地用于实际问题的求解也是很有意义的工作。就目前来看,将与其他技术相结合,根据不同的优化问题提出相应的改进算法是PSO当前的研究热点。
(4)算法的基础理论研究:
与相应的相对鲜明的社会特性基础相比,其数学基础显得相对薄弱,缺乏深刻且具有普遍意义的理论分析,不能对PSO的工作机理做出合理的数学解释。虽然PSO的有效性、收敛性等性能在一些实例和函数的仿真研究中得到验证,但没能在理论上进行严谨推敲和严格证明。因此,对PSO的基础理论研究非常重要。
摘要：首先介绍了PSO的原理及具体实现步骤;然后针对PSO算法在搜索的初期收敛速度很快,但在后期却易于陷入局部最优的缺点,提出了各种改进办法;最后介绍了PSO算法的应用领域以及研究展望。
关键词：粒子群算法,综述,优化
参考文献
[1]Kennedy J,Eberhart R C.Particle swarm optimization[G]//Proc of IEEE Int Conf on Neural Networks.NewYork:IEEE,1995:1942-1948.
[2]Shi Y,Eberhart R C.A modified particle swarm[G]//Proceeding of IEEE International Conference onEvolutionary Computaion.New York:IEEE,1998:69-73.
[3]Eberhart R C,Shi Y.Particle swarm optimizationdevelopments,applications and resources[G]//Proceedings of the 2001 Congress on EvolutionaryComputation.Piscataway:IEEE,2001:81-86.
[4]Aneline P J.Using selection to improve particle swarmoptimization[G]//Proceeding of the InternationalConference on Evolutionary Computation.New York:IEEE,1998:84-89.
[5]Suganthan P N.Particle swarm optimizer withneighborhood operator[G]//Proceeding of the 1999Congress on Evolutionary Computation.New York:IEEE,1998:1958-1962.
[6]Kenndy J.Stereotyping improving particle swarmperformance with clusteranlysis[G]//Proceeding of the2000 Conference on Evolutionary Computation.Piscataway:IEEE,2000:1507-1512.
[7]Bergh F van den.An analysis of particle swarmoptimizers[D].South Africa:University of Pretoria,2002:1341-1344.
粒子群算法研究概述 第10篇
随着通信技术、计算机技术与人工生命技术的发展和成熟, 使得具有收敛快, 计算应用强, 应用领域广等优点的人工智能算法在各个领域开始扮演重要的角色。人工智能算法通过模拟各种自然界里的生物行为, 通过利用仿生学的各种知识, 进行计算模拟, 来得到各种计算所需的最优解。正是由大量的计算组成的工业生产体系, 使得人工智能算法其价值在于可以实时计算, 处理网络分布区域内的各种环境和监测对象的信息, 并对这些信息进行处理, 获得所要的最佳处理数据, 并将信息传递给用户。在人工智能算法领域里, 粒子群算法因其独特魅力受到广泛关注。
由于粒子群算法具有搜索速度快、效率高, 算法简单等优点, 使其容易被工业生产应用或者应用于人工智能领域, 提高了粒子群算法提供服务的质量。阿尔伯特.爱因斯坦曾说过“当数学原理用于现实时, 是不确定的, 当他们确定时, 又不适用于现实”。近年来, 国内外对于人工智能算法及其应用技术的研究日趋热烈, 也取得了丰富的研究成果。本文从粒子群算法和其发展方向介绍了人工智能算法的研究进展。
1 粒子群算法分析概述
粒子群算法的产生是科学家采用了仿生学的相关概念, 它通过模仿自然界里动物的行为来寻找最优解.
1.1 粒子群算法的产生模型
粒子群算法是由鸟群的捕食行为来得到启发而发展起来的智能算法。整个算法通过模拟这样一个自然场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远, 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。
1.2 粒子群算法的原理
粒子群算法从这种模型中得到启示并用于解决优化问题。粒子群算法中, 每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值 (fitness value) , 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
粒子群算法初始化为一群随机粒子 (随机解) 。然后通过迭代找到最优解。在每一次迭代中, 粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解, 这个解叫做个体极值p Best。另一个极值是整个种群目前找到的最优解, 这个极值是全局极值g Best。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居, 那么在所有邻居中的极值就是局部极值。
粒子群算法通过不断更新适应度值, 对每个d维 (任务的数量) 的粒子进行每一维度的赋值, 对粒子群赋值 (包括position vector and velocity vector) , 粒子在d维 (任务的数量) 空间中所经历过的最好位置, 通过计算更新粒子速度和位置信息, 更新个体粒子的最优解, 进行粒子更新操作, 全局搜索想要的结果, 最后通过比较获取种群中的最优解。
在整个粒子群算法里, 通过化抽象为具体, 将实际生活里的运动转化为代码里的更新, 计算完成时间, 局部最优解, 当然也使用了ETC[i][j], 在算法实现过程中还应计算时间矩阵ETC[][], 为ETC[i][j]=work Load[i]/computing Power[j], 此时通过抽象, i, j被赋予了不同的意义, 更切合粒子群优化算法的意义。并且不断利用提前定义好的数学公式进行粒子更新操作, 更新粒子速度和位置信息。同时在计算里也可以找到最好的迭代次数, 通过比较大小, 最好的迭代次数就是当前最优解的迭代次数, 然后利用该值进行相应操作, 比如更新惯性系数, 最后把每次迭代的最优解进行排序, 得到相应的处理结果。在计算机里, 通过给参数赋予不同意义, 可以抽象出鸟的数目 (粒子群大小) , 离食物的距离, 速度, 鸟的位置 (鸟的任务) 等与实际生活相对应的算法, 体现了计算机世界的奇妙以及与实际生活的联系。
1.3 粒子群算法的计算流程
粒子群优化算法是通过个体之间的协作来寻找最优解, 它利用了生物群体中信息共享会产生进化优势的思想。
通过上文描述, 可以知道粒子群算法的计算流程图为:
2 粒子群算法的发展方向
粒子群算法应该与机器学习和数据挖掘紧密地联系在一起。
机器学习涉及了计算机如何模拟和实现人类的学习行为, 利用已经获取的新的知识和技能, 组织知识结构, 来不断改善自身的性能和工作能力。并且机器学习的目的就是预测性能更好的算法, 它可以自我学习, 提高自身的预测性能, 这一点与粒子群算法不谋而合。粒子群算法通过和机器学习的结合可以使自己的优点得到发挥, 通过粒子群算法的搜索能力可以使机器的自学习能力增强, 通过智能的搜索方法, 可以准确定位所需资源并且可以优化配置资源。机器学习使用了各种算法, 优化了计算模型, 粒子群算法应用于机器学习中, 可以快速地获取当前需要的知识。
在数据挖掘中, 需要综合使用结果, 要综合使用到数据库, 人机交互, 统计分析等技术, 而通过和粒子群算法的结合, 可以用来快速分析数据。而且数据挖掘本身需要用到很多算法, 并且把它们结合起来在广大的数据网里面得到自己所需的信息, 而粒子群算法可以加速这个过程, 通过有效率的计算来保障结果的正确性和搜索的快速性。数据挖掘会从数据本身挖掘信息, 这种发现潜在信息的方式往往会通过算法来实现, 粒子群算法可以给数据挖掘带来一种不同的发现隐藏信息的方式。
3. 结束语
本文主要分析了粒子群算法原理及其流程, 并且提出粒子群算法的发展方向, 粒子群算法应该与机器学习和数据挖掘紧密地联系在一起的思想, 以及粒子群算法在这两个尖端领域里可以起到的作用。由于只是从理论上对这个发展方向进行客观分析, 缺少实践去验证。而粒子群算法在以后的工作研究中会更有利于推动国家高性能的计算发展。随着经济、生产生活和科技研发等方面对高性能的计算越来越多的依赖, 人工智能算法的夏天正慢慢走来。
参考文献
[1]Pinel, F., Pecero, J., Bouvry, P., and Khan, S.U.:“Memory-aware Green Scheduling on Multi-core Processors, ”in 39th IEEE International Conference on Parallel Processing (ICPP) , pp.485╞488, USA, 2010.
[2]Xhafa, F., Abraham, A.:“Computational modelsand heuristic methods for grid scheduling problems”, Future Generation Computer Systems, vol.26, pp.608╞621, 2010.
[3]Zomaya, A.Y.:“Energy-Aware Scheduling and Resource Allocation for Large-Scale Distributed Systems”, in 11th IEEE International Conference on High Performance Computing and Communications (HPCC) , Seoul, Korea, 2009.
[4]Ali, S., Siegel, H.J., Maheswaran, M., and Hensgen, D.:“Task execution time modeling for heterogeneous computing systems”, Proceedings of Heterogeneous Computing Workshop, pp.185╞199, 2000.
