当前位置：文档之家 › 广义粒子群优化模型高海兵周驰高亮

广义粒子群优化模型高海兵周驰高亮

  • 格式：pdf
  • 大小：449.43 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

求解TSP问题的一种启发式算法

求解TSP问题的一种启发式算法

求解TSP问题的一种启发式算法孙宪丽;王敏;李颖【摘要】TSP问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义.根据TSP问题的特点,借鉴无向完全图上最小生成树的生成过程,设计了一种启发式算法对TSP问题进行求解.该算法的基本思想是以无向完全图上不同最小生成树为基础,采用启发式的方法构造不同闭合回路,最后取最短闭合回路作为最优解.文中采用C语言编程,同时分析了算法的性能和时间复杂度,并进行了大量仿真计算.结果表明设计的算法能够有效求得TSP问题的优化解.【期刊名称】《计算机技术与发展》【年(卷),期】2010(020)010【总页数】5页(P70-73,77)【关键词】旅行商问题;启发式算法;最小生成树【作者】孙宪丽;王敏;李颖【作者单位】沈阳工程学院,信息系,辽宁,沈阳,110136;沈阳工程学院,基础部,辽宁,沈阳,110136;沈阳工程学院,基础部,辽宁,沈阳,110136【正文语种】中文【中图分类】TP301.60 引言TSP(Traveling Salesman Problem)问题[1],又称旅行商问题,是运筹学以及最优化理论等领域中的一个经典问题。

TSP问题已经证明是NP(Nondeterministic Polynomial)完全问题。

到目前为止,所有的NP完全问题都还没有多项式时间算法。

然而,由于TSP问题具有广泛的应用背景,例如可以用来解决资源分配问题、路径选择问题、车辆调度问题、产品切割问题等等。

因此,TSP问题长期以来吸引着众多学者对其求解策略展开研究,设计并开发了多种算法对TSP问题求解。

这些算法通常可以分为两类:一类是精确求解;另一类是近似求解。

其中,精确求解在理论上能够保证求得问题的最优解,但算法的时间复杂度按指数规律增长。

因此,难于用此方法解决大规模问题。

在近似求解中,研究较多的是:(1)采用理论的方法证明算法的上界。

例如,对于满足三角不等式的TSP问题,用christofides算法已经证明该算法的界为。

基于混合协同粒子群优化的广义T-S模糊模型训练方法

基于混合协同粒子群优化的广义T-S模糊模型训练方法

基于混合协同粒子群优化的广义T-S模糊模型训练方法
周欣然;滕召胜;易钊
【期刊名称】《系统工程与电子技术》
【年(卷),期】2009(031)005
【摘要】针对广义Takagi-Sugeno(T-S)模糊模型训练中存在的高维、非线性、混合参数估计问题,提出了一种基于混合协同粒子群优化的广义T-S模糊模型训练方法.该方法用离散二进制微粒位置表示模型的结构参数,用普通微粒位置表示模型规则中模糊集隶属函数的参数;这两种微粒位置联合体构成一个模型完整的模型前件参数集.两种群通过协同进化优化所有前件参数;模型后件参数用卡尔曼滤波算法估计.该方法不要任何先验知识,能产生紧凑的、泛化性能较好的模糊模型.函数逼近的数字仿真说明了该方法的有效性.
【总页数】5页(P1189-1193)
【作者】周欣然;滕召胜;易钊
【作者单位】中南大学信息科学与工程学院,湖南,长沙,410075;湖南大学电气与信息工程学院,湖南,长沙,410082;湖南大学电气与信息工程学院,湖南,长沙,410082;湖南大学电气与信息工程学院,湖南,长沙,410082
【正文语种】中文
【中图分类】TP273
【相关文献】
1.一类基于T-S模糊模型的非线性广义系统的鲁棒H∞控制 [J], 朱宝彦;刘爱斌;赵恩良;畅春玲
2.粒子群优化的广义T-S模糊模型参数学习方法 [J], 周欣然;滕召胜;易钊
3.基于改进蚁狮算法的广义预测控制对T-S模糊模型的控制研究 [J], 张文彬
4.基于T-S模糊模型的CSTR系统广义预测控制 [J], 许娣; 佃松宜; 高钰凯
5.基于T-S模糊模型与粒子群优化的非线性预测控制 [J], 王书斌;单胜男;罗雄麟因版权原因，仅展示原文概要，查看原文内容请购买。

粒子群及人工鱼群算法优化研究

粒子群及人工鱼群算法优化研究

粒子群及人工鱼群算法优化研究洪蕾【摘要】本文分析了粒子群算法和人工鱼群算法的基本原理,提出粒子群及人工鱼群算法优化策略,该算法综合利用了人工鱼群算法良好的全局收敛性及粒子群算法快速的局部收敛性,算法易实现,同时,克服人工鱼群算法收敛速度慢及粒子群算法后期全局收敛差的缺点,发挥了两者的优越性,粒子群及人工鱼群优化算法不仅具有较好的全局收敛性能,而且具有较快的收敛速度.【期刊名称】《软件》【年(卷),期】2014(035)008【总页数】4页(P83-86)【关键词】粒子群算法;人工鱼群算法;收敛性;算法优化【作者】洪蕾【作者单位】金陵科技学院江苏南京 211169【正文语种】中文【中图分类】TP301.60 引言粒子群优化(PSO)算法是由Kennedy和Eberhart于1995年用计算机模拟鸟群觅食这一简单的社会行为时，受到启发，简化之后而提出的[1-2]。

粒子群优化(PSO)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，成为发展最快的智能优化算法之一。

人工鱼群算法是一种基于模拟鱼群行为的随机搜索优化算法,主要利用了鱼的觅食、聚群和追尾行为，从构造单条鱼的底层行为做起，通过鱼群中各个体的局部寻优达到全局最优值在群体中突现来的目的。

本文通过对两种算法的研究比对，提出基于这两种算法相结合的优化算法。

1 算法概述1.1 粒子群优化算法在粒子群优化算法中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。

所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。

然后粒子们就追随当前的最优粒子在解空间中搜索。

优化开始时先初始化为一群随机粒子(随机解)。

然后通过迭代找到最优解。

在每一次迭代中，粒子通过跟踪两个极值来更新自己。

第一个极值就是整个种群目前找到的最优解。

这个极值是全局极值。

另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

粒子群优化算法_周驰

粒子群优化算法_周驰

收稿日期:2002-12-22;修返日期:2003-09-23基金项目:国家863/CIMS 主题资助项目(2002AA413720);国家863/CIMS 主题资助项目(2002AA411710)粒子群优化算法＊周　驰,高海兵,高　亮,章万国(华中科技大学机械科学与工程学院教育部智能制造开放实验室,湖北武汉430074)摘　要:系统地介绍了粒子群优化算法,归纳了其发展过程中的各种改进如惯性权重、收敛因子、跟踪并优化动态目标等模型。

阐述了算法在目标函数优化、神经网络训练、模糊控制系统等基本领域的应用并给出其在工程领域的应用进展,最后,对粒子群优化算法的研究和应用进行了总结和展望,指出其在计算机辅助工艺规划领域的应用前景。

关键词:粒子群优化算法;遗传算法;神经网络;模糊系统中图法分类号:TP301.6 文献标识码:A 文章编号:1001-3695(2003)12-0007-05Particle Swarm Optimization (PSO )AlgorithmZHOU Chi ,GAO Hai -bin g ,GAO Liang ,ZHANG Wan -guo(Labor ator y of Int ell igent M anufacturing ,School of Mec hanical Science &Engi nee ring ,Huazhong Uni ver sity of Sci enc e &Technology ,Wuhan Hubei 430074,C hina )A bstract :A new optimizer -Particle S warm Optimization (PSO )is introduced .Developments in the PSO s uch as inertia weight ,constric -tion factor ,tracking and optimizing dynamic systems etc are reviewed .Then ,its applications in s ome basic areas :function optimization ,neural network trainin g and fuzzy control system are sum marized .Followin g this ,several important engineering application examples are given .Finally ,the research and application of PSO in the future are pointed out an d its potential application in computer aided process plannin g is propos ed .Key words :Particle S warm Optimization Algorithm ;Genetic Algorithm ;Neural Net work ;Fuzz y Control1　引言当前,通过模拟生物群体的行为来解决计算问题已经成为新的研究热点,形成了以群体智能(Swarm Intelli -gence )为核心的理论体系,并已在一些实际应用领域取得突破性进展[1]。

改进DPSO算法在干扰资源分配中的应用

改进DPSO算法在干扰资源分配中的应用

改进 Ｄ Ｓ Ｐ Ｏ算 法 在 干 扰 资 源分 配 中 的应 用
徐 华， 吴玮琦
（ 电子信息控制重点 实验 室 ， 成都 ６０３ ） １０６
摘要 ： 引入 改进 的 离散 粒 子群 （ ＰＯ） Ｄ Ｓ 算法 对干扰 资 源分 配 问题进 行 求 解。针 对 干扰 资源分 配
的数学模型， 出了具体的求解方案。在迭代过程 中线性改变权重 系数和认知参数 ， 给 使粒子快 速收敛 ； 为避免粒子陷入局部最优 ， 引入 了一种粒子位置更新机制。仿真验证 了该改进算法的
Ａ ｓ ａｔＡ ｐｏｅ Ｐ Ｏ ａ ｏｉ ｍ ｉ ｐｏ ｏｅ ｌ ｅｐｏ ｌ ｆ ａ ｍｉ ｓｕｃ ｓｉ — ｂ ｔ ｃ： ｎｉ ｒｖｄＤ Ｓ ｌ ｒｈ ｒｐｓｄｔ ｓ ｖ ｔ ｒｂｅ ｏ ｍ ｎ ｒ ｏｒｅａｓ ｎ ｒ ｍ ｇ ｔ ｓ ｏ ｏ ｅｈ ｍ ｊ ｇｅ ｇ
ｎ １ ａｓ１ ｎ
１ 引言
为利 用 有 限 的 干 扰 资 源 达 到 最 优 的 干 扰 效
大时很难用匈牙利算法进行求解 ＿。常规的遗传 ３ ＿
算法 、 模拟 退火算 法 虽然 能够求 解大 规模 问题 ， 但 算 法结 构 复杂 ， 优化 时 间较 长 ， 用于求 解此 问题 不 能 满 足 实 时 性 的 要 求 ＿ 。 而 粒 子 群 （ ａｉｅ ５ ｊ Ｐｒｃ ｔｌ Ｓ ａ ｐｉｉ ｔｎＰ Ｏ） 法 ［ 是 一 种 并 行 算 ｗｒ Ｏ ｔ ｚ ｉ Ｓ 算 ｍ ｍ ａｏ 卜ｊ 法 ， 有 可 调 参数 少 ， 解 简单 ， 具 求 收敛 速 度快 等 特 点 。文献 ［］ ６引入 离 散 ＰＯ算 法 求 解 了干 扰 任 务 Ｓ
算法 具体 求解 步骤 为 ： （ ） 始化 设 置 ： 据 求 解 问题 的 规模 ， １初 根 随机

求解作业车间调度问题的广义粒子群优化算法

求解作业车间调度问题的广义粒子群优化算法
( P art icle Sw arm Opt im ization,
化[ 3 ] 、 神经网络训练 [ 4] 、 多目标优化 [ 5] 和模糊控制系 统
[ 6]
等优化领域。 传统的 P SO 适合于处理连续优化问题, 在复杂
[ 7]
PSO) 算法是一种基于群体智能理论的优化算法, 它 由 Kennedy 和 Eber hart 于 1995 年提出
General particle swarm optimization algorithm for job- shop scheduling problem
PEN G Chuan- y ong, GA O Liang , SH A O X in - y u, ZH O U Chi
( Sch. of M echanical Sci. & Eng. , H uazhong U niv . o f S & T , Wuhan 430074, China) Abstract: T o ov ercome the limitations o f t raditio nal Part icle Sw ar m O pt imization ( P SO ) on so lutio ns to the co mbina to rial o ptimizat ion problems, a General P SO ( G PSO) mo del w as proposed after analy zing the o pt imizatio n mecha nism of t he tr aditional PSO. Based on this model, a G PSO algo rithm w as presented to solve the Jo b- shop Scheduling P ro blem ( JSP) . In GP SO, cr ossover and mutatio n o per ations in genetic alg or ithm wer e respectively ut ilized by par ticles to exchang e info rmation and search r andomly. Besides, T abu Search w as used fo r pa rticles' lo cal sear ch. T o co nt rol the lo ca l search and ensur e its converg ence to the global optimum so lutio n, time- var ying cr ossover proba bility and time- v ary ing max imum st ep size of T abu Sear ch w ere intr oduced. T he experimental results sho wed that JSP co uld be solved by GPSO effect ively. T he feasibility of the pro po sed GP SO model w as also demonstrated. Key words: par ticle sw arm o ptimizat ion; g enet ic alg or ithm; tabu sear ch; job- shop scheduling

基于粒子群优化算法的模式分类规则获取

基于粒子群优化算法的模式分类规则获取

基于粒子群优化算法的模式分类规则获取
高亮;高海兵;周驰;喻道远
【期刊名称】《华中科技大学学报：自然科学版》
【年(卷),期】2004(32)11
【摘要】提出了基于粒子群优化的规则提取算法 .该算法将规则编码为粒子 ,通过粒子群优化算法的速度位移搜索模型以及粒子保存的记忆信息指导生成模式分类规则集 .算法用于Iris数据集模式分类规则的提取 .与其他规则提取方法比较。

【总页数】3页(P24-26)
【关键词】规则提取;粒子群优化算法;群体智能
【作者】高亮;高海兵;周驰;喻道远
【作者单位】华中科技大学机械科学与工程学院
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于粒子群优化算法的分类规则挖掘研究 [J], 李俊林
2.基于多变异粒子群优化算法的模糊关联规则挖掘 [J], 王飞;缑锦
3.基于量子行为的粒子群优化算法分类规则获取 [J], 刘韬;殷锋;陈建英;何蔚林
4.基于粒子群算法的矢量元胞自动机转换规则获取 [J], 沈泉飞;曹敏;董玉军
5.粒子群优化算法在关联规则挖掘中的研究综述 [J], 钟倩漪;钱谦;伏云发;冯勇因版权原因，仅展示原文概要，查看原文内容请购买。

基于粒子群优化的神经网络训练算法研究

基于粒子群优化的神经网络训练算法研究

基于粒子群优化的神经网络训练算法研究高海兵,高　亮,周　驰,喻道远(华中科技大学工业工程系自动化所,湖北武汉430074) 摘　要:　本文提出了基于连接结构优化的粒子群优化算法(SPS O )用于神经网络训练,该算法在训练神经网络权值的同时优化其连接结构,删除冗余连接,使神经网络获得与模式分类问题匹配的信息处理能力.经SPS O 训练的神经网络应用于Iris ,I onosphere 以及Breast cancer 模式分类问题,能够部分消除冗余分类参数及冗余连接结构对分类性能的影响.与BP 算法及遗传算法比较,该算法在提高分类误差精度的同时可加快训练收敛的速度.仿真结果表明,SPS O 是有效的神经网络训练算法.关键词:　粒子群优化;神经网络;遗传算法;模式分类中图分类号:　TP183 文献标识码:　A 文章编号:　037222112(2004)0921572203Particle Swarm Optimization Ba sed Algorithm for Neural Network LearningG AO Hai 2bing ,G AO Liang ,ZH OU Chi ,Y U Dao 2yuan(Inst o f Automation ,Dept.o f Industrial Engineering ,Huazhong Univ o f Sci &Tech ,Wuhan ,Hubei 430074,China )Abstract :　This paper proposes a structure 2im proving particle s warm optimization (SPS O )alg orithm for training artificial neural netw ork (ANN ).The alg orithm is success fully applied to pattern classification problems including Iris ,ionosphere and breast cancer.By tuning the structure and connection weights of ANN simultaneously ,the proposed alg orithm generates optimized ANN with problem 2matched capacity for processing classification in formation.By doing this ,it als o eliminates s ome ill effects introduced by redundant in 2put features and the corresponding structure of ANN.C om pared with BP and G A based training techniques ,SPS O can im prove the clas 2sification accuracy while speeding up the convergence process.S imulation results show that SPS O is a potentially robust learning alg o 2rithm and could be extended to real w orld applications.K ey words :　particle s warm optimization ;artificial neural netw ork ;genetic alg orithm ;pattern classification1　引言 工业、经济、医疗等领域的许多实际问题如质量控制 破产预测、图像识别、医疗诊断等可以转化为模式分类问题求解.神经网络自学习、自组织、容错以及模拟非线性关系的能力使其特别适合解决上述复杂的模式分类问题.H ornik [1]证明采用S igm oid 响应函数的三层前馈神经网络能够以任意精度模拟复杂的非线性关系,而神经网络上述性能的实现依赖于对神经网络的充分训练.因此,训练算法对于神经网络的模式分类性能有着决定性影响.BP 算法是最普遍的神经网络训练算法.但是,Rmulhart [2]研究证明,基于梯度下降的BP 算法依赖于初始权值的选择,收敛速度缓慢且容易陷入局部最优.BP 的上述缺陷尤其是局部优化特性使其训练的神经网络的输出具有不一致性和不可预测性,导致模式分类的可靠性降低.遗传算法的并行搜索策略及全局优化特性使其成为日益普遍的神经网络训练算法.Sexton [3]通过实验证明,与BP 算法比较,遗传算法训练的神经网络在提高分类正确率的同时可以加快训练的收敛速度.但是,遗传算法复杂的遗传操作如选择、复制、交叉、变异使神经网络的训练时间随问题的规模及复杂程度呈指数级增长[4].而且,由于缺乏有效的局部区域搜索机制,算法在接近最优解时收敛缓慢甚至出现收敛停滞现象[5].粒子群优化算法是基于群体智能理论的优化算法,通过种群中粒子间的合作与竞争产生的群体智能指导优化搜索[6].与进化算法比较,PS O 保留了基于种群的全局搜索策略,但是其采用的速度—位移模型操作简单,避免了复杂的遗传操作,在非线性函数优化[7]、电压稳定性控制[8]、动态目标优化[9]等实际问题取得了成功应用.国内对粒子群优化算法的研究刚刚起步.文献[10]综述性地介绍了粒子群优化算法及其理论发展与实际应用.文献[11]通过对算法基本模型的改进,改善了PS O 摆脱局部极值的能力.以5个基准函数测试,改进的算法优于基本PS O 算法以及惯性权重模型的PS O 算法.文献[12]将粒子群优化算法用于同步发电机参数的辨识,实验结果显示,算法可有效地辨识同步发电机的运行参数,简单实用,具有较强的可行性.本文提出了基于粒子群优化的神经网络训练算法SPS O.一般的训练算法仅训练全连接网络结构下的连接权值.但是神经网络存在的冗余连接会降低神经元的信息处理效率,大量的冗余连接甚至会影响模式分类的正确率.SPS O 在训练神经网络权重的同时训练其连接结构,删除冗余连接,使神经网络获得与给定问题匹配的信息处理能力.实验结果显示,SPS O 是有效的神经网络训练算法,可用于解决实际的模式分类问题.2　基于粒子群优化的神经网络训练算法 粒子群优化算法的速度—位移搜索模型操作简单,计算复杂度低,并通过惯性权重协调全局搜索与局部搜索,既能以收稿日期:2003209201;修回日期:2004203229基金项目:国家自然科学基金(N o.50305008);国家高技术研究发展计划(863计划)课题(N o.2002AA42010023)第9期2004年9月电 子 学 报ACT A E LECTRONICA SINICA V ol.32　N o.9Sep.　2004较大的概率保证最优解,克服BP算法局部最优的缺陷,又可以提高局部区域的收敛速度,避免G A在局部区域搜索过程中的收敛停滞现象.必须指出,狭义的神经网络训练仅训练全连接结构下的连接权值.但是神经网络需要的信息处理能力根据模式分类问题的规模和复杂度确定,信息处理能力不足或过剩都会影响其分类性能.广义的神经网络训练应包括对连接结构的优化,即在训练权值的同时优化其连接结构,删除冗余连接.因为部分冗余连接由冗余的输入参数导致,所以冗余连接的删除在一定程度上还可以消除冗余参数对神经网络分类性能的影响.本文提出了适合优化神经网络连接结构的粒子群优化算法.首先,给出算法的基本定义如下:定义1　连接结构{c ih}{c ho}:{c ih}表示输入层与隐含层间的连接结构.{c ho}表示隐含层与输出层间的连接结构. {c ih}与{c ho}均为二进制变量矩阵.对应的连接存在则该变量为1,否则为0.定义2　连接阈值{θih}{θho}:连接阈值{θih}与{θho}为[0,1]区间的实数,与连接变量结合用于控制神经网络的连接结构.定义3　连接变量{δih}{δho}:连接变量{δih}{δho}与连接阈值结合决定神经网络的连接结构.若连接变量的值大于连接阈值,连接阀门开启,则连接存在.连接变量一般为[0,1]区间的实数.在上述定义的基础上建立仅优化神经网络连接结构的PS O算法模型.其中,PS O算法机理、基本定义及算法实现可参考文献[6].连接变量速度的迭代:v ihωw3v ih+c13rand()3(p i-δih)+c23rand()3(g-δih)(1) v hoωw3v ho+c13rand()3(p i-δho)+c23rand()3(g-δho)(2)连接变量位置的迭代:δihωδih+v ih(3)δhoωδho+v ho(4)连接结构的迭代:if　(θih/θho<δih/δho)then c ih/c hoω1else　c ih/c hoω0(5)仅优化连接结构的PS O算法模型中的连接变量速度-位置迭代公式(1)～(4)为PS O算法的基本搜索模型.但是与传统PS O算法不同,该算法中p i,g分别表示连接变量(而非连接结构本身)的个体与全局极值,由连接变量及阈值确定的连接结构结合基本PS O算法训练的连接权值在给定样本下的训练误差精度决定.该算法通过间接优化可连续变化的连接变量达到训练二进制表达的连接结构的目的,并由连接结构的迭代式(5)体现PS O算法对神经网络结构的更新.SPS O 算法在连接结构优化算法的基础上提出,算法在优化连接结构的同时结合传统PS O算法训练神经网络的连接权值.3　实验说明及结果分析 本文使用Iris,I onosphere以及Breast Cancer模式分类数据集作为SPS O算法的测试实例.同时,采用BP及遗传算法训练全连接结构下的神经网络权值,并使用同时训练权值与连接结构的遗传算法(SG A)与SPS O比较.首先给出算法的参数设置.基于粒子群优化的训练算法(PS O与SPS O)种群规模n=40,初始惯性权重w(0)=019并随迭代次数线性递减至014,c1=c2=2.连接权值为[-1,1]区间变量.Iris问题的连接阈值θih=θho=015.由经验公式确定神经网络隐含层节点数n h=8.所有模式分类问题均以最大迭代次数I termax为算法停止条件.Iris数据集中各种算法训练迭代次数为400(BP算法为1000).I onosphere数据集中θih =θho=014,n h=15,各种算法训练迭代次数为800(BP算法为2000).Breast Cancer数据集n h=12,其余参数设置同Iris.SPS O及SG A算法随迭代次数的训练误差曲线如图1～3所示.SPS O、PS O、SG A、G A及BP算法的测试误差、分类正确率、神经网络连接数以及训练阶段的CPU运行时间见表1.表1　神经网络训练性能比较算法性能指标Iris I onosphere Breast cancerSPS O误差指标 1.117 1.9000.627分类正确率97.959%97.351%98.995%连接数2926561CPU时间(s)16.304198.97392.490PS O误差指标 1.613 2.7340.797分类正确率93.877%94.702%98.492%连接数56525120 CPU时间(s)13.439194.73091.701SG A误差指标 1.772 4.809 1.168分类正确率95.918%93.377%98.995%连接数3227271CPU时间(s)49.711899.264308.424G A误差指标 2.928 4.369 1.499分类正确率93.877%93.377%98.492%连接数56525120 CPU时间(s)48.369817.596286.782BP误差指标 2.198 4.037 1.556分类正确率95.918%93.377%98.492%连接数56525120 CPU时间(s)55.340811.477382.580图1　SPS O与SG A训练误差曲线图(Iris) 由图1～3可知,SPS O在训练阶段收敛速度快且误差精度高.此外,与SG A比较,其最优及平均误差曲线具有收敛一3751第　9　期高海兵:基于粒子群优化的神经网络训练算法研究图2　SPS O与SG A训练误差曲线图(I onosphere )图3　SPS O与SG A训练误差曲线图(Breast cancer)致性,从而提高了训练收敛的可靠性.如表1所示,SP SO对结构的优化提高了神经网络的模式分类性能,表明SP SO删除的网络连接为冗余连接.同时也验证了冗余连接对神经网络性能的影响以及信息处理能力过剩导致的过度训练问题.由实验结果还可以推出,粒子群优化算法与遗传算法相比,在训练时间接近时,分类性能显著提高;若达到同样误差目标,采用粒子群优化算法收敛所需的训练迭代次数明显降低.由此可见,粒子群优化算法不仅使训练的收敛速度大大提高,且其训练的神经网络的性能也显著增强.需要指出,尽管对结构的优化增加了SPS O训练阶段的复杂度.但是经过连接结构优化的神经网络分类模型在实际应用中信息处理效率提高.经过连接结构优化的神经网络尤其适合大规模数据的实时处理.4　总结 模式分类问题可能存在冗余分类参数,从而导致了神经网络中的冗余连接,降低了神经网络的处理速度.大量的冗余连接甚至会影响神经网络的模式分类精度.本文提出的SPS O 训练算法在训练神经网络权值的同时删除其冗余连接,实现连接结构的优化.与训练全连接结构权值的PS O比较,算法在保证分类正确率的同时减少了连接数目.与BP及遗传算法比较,在提高分类误差精度的同时加快了训练收敛速度.实验结果验证了SPS O算法的有效性.进一步的工作可以从以下两个方面展开:首先,根据神经网络的实时训练性能自适应地改变连接阈值的设置.其次,根据完成训练的神经网络评价输入参数的影响,并根据重要参数由PS O算法提取分类规则,这些都是基于PS O的神经网络模式分类的改进方向.参考文献:[1]　H ornik K,S tinchcom be M,W hite H.M ultilayer feed2forward netw orks areuniversal approxim ators[J].Neural Netw orks,1989,2(5):359-366. [2]　Rumelhart D E,Hinton G E,W illiams R J.Learning representations byback propagating errors[J].Nature,1986,323(11):533-536.[3]　Sexton R S,D orsey R E.Reliable classification using neural netw orks:a genetic alg orithm and backpropagation com paris on[J].Decision Sup2port Systems,2000,30(1):11-22.[4]　Y angJ M,K ao C Y.A robust ev olutionary alg orithmfor training neural net2w orks[J].Neural C om puting and A pplication,2001,10(3):214-230. [5]　Franchini e of a genetic alg orithm combined with a local searchmethod for the automatic calibration of conceptual rain fall2runoff m odels[J].Hydrological Science Journal,1996,41(1):21-39.[6]　K ennedy J,Eberhart R C.Particle swarm optim ization[A].Proceedingsof IEEE International C on ference on Neutral Netw orks[C].Australia:IEEE,1995.1942-1948.[7]　Shi Y H,Eberhart RC.Em pirical study of particle swarm optim ization[A].Proceedings of IEEE International C ongress on Ev olutionary C om2putation[C].US A:IEEE,1999.6-9.[8]　Y oshida H,K awata K,Y oshikazu F.A Particle swarm optim ization forreactive power and v oltage control considering v oltage security assess2m ent[J].IEEE T ransaction on P ower S ystem,2000,15(4):1232-1239.[9]　Carlisle A,D ozier G.Adapting particle swarm optim ization to dynam icenvironments[A].Proceedings of International C on ference on ArtificialIntelligence[C].US A:IEEE,2000.11-15.[10]　李爱国,覃征,鲍复民,等.粒子群优化算法[J].计算机工程与应用,2002,(21):1-3.[11]　王岁花,冯乃勤,等.一类新颖的粒子群优化算法[J].计算机工程与应用,2003,(13):109-110.[12]　龙云,王建全.基于粒子群游算法的同步发电机参数辨识[J].大电机技术,2003,(1):8-11.作者简介:高海兵　男,1978年9月出生于江苏省南通市,华中科技大学工业工程系硕士研究生,研究方向为计高　亮　男,1974年8月出生于山东省临清市,现为华中科技大学工业工程系副教授、副主任,研究方向运筹学与优化,在国内外发表学术论文20余篇.算智能、运筹学与优化.4751 电 子 学 报2004年。

PSO-ELM_辅助的GNSS-IR_土壤湿度反演方法

PSO-ELM_辅助的GNSS-IR_土壤湿度反演方法

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００３－３１０６．２０２３．０６．０１６引用格式：李信强，刘立龙，刘卓仑，等．ＰＳＯ ＥＬＭ辅助的ＧＮＳＳ ＩＲ土壤湿度反演方法［Ｊ］．无线电工程，２０２３，５３（６）：１３６８－１３７５．［ＬＩＸｉｎｑｉａｎｇ，ＬＩＵＬｉｌｏｎｇ，ＬＩＵＺｈｕｏｌｕｎ，ｅｔａｌ．ＰＳＯ ＥＬＭＡｓｓｉｓｔｅｄＧＮＳＳ ＩＲＳｏｉｌＭｏｉｓｔｕｒｅＲｅｔｒｉｅｖａｌＭｅｔｈｏｄ［Ｊ］．ＲａｄｉｏＥｎｇｉｎｅｅｒｉｎｇ，２０２３，５３（６）：１３６８－１３７５．］ＰＳＯ ＥＬＭ辅助的ＧＮＳＳ ＩＲ土壤湿度反演方法李信强１，２，刘立龙１，２，刘卓仑１，张　志１（１．桂林理工大学测绘地理信息学院，广西桂林５４１００６；２．广西空间信息与测绘重点实验室，广西桂林５４１００６）摘　要：针对如何有效提高全球导航卫星系统多径干涉遥感（ＧｌｏｂａｌＮａｖｉｇａｔｉｏｎＳａｔｅｌｌｉｔｅＳｙｓｔｅｍＩｎｔｅｒｆｅｒｏｍｅｔｒｉｃＲｅｆｌｅｃｔｉｏｎ，ＧＮＳＳ ＩＲ）技术观测量数据反演土壤湿度精度的问题，提出一种基于极限学习机（ＥｘｔｒｅｍｅＬｅａｒｎｉｎｇＭａｃｈｉｎｅ，ＥＬＭ）模型的土壤湿度反演方法，并利用粒子群优化（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）ＥＬＭ来获取该模型的最优参数。

以ＧＮＳＳ ＩＲ提取反射信号的相位作为输入向量，以ＰＢＯＨ２Ｏ的土壤湿度值作为输出向量，构建ＰＳＯ ＥＬＭ神经网络模型，并进一步与ＥＬＭ模型、ＢＰ神经网络模型和线性回归模型进行对比分析。

实验结果表明，ＰＲＮ１０卫星在ＰＳＯ ＥＬＭ模型中的土壤湿度反演结果与土壤湿度值之间的决定系数为０．８７７１，均方根误差为０．０２５２，平均绝对误差为０．０２０７，相比其他３种模型的土壤湿度反演精度更高、稳定性更强，具有较强的拟合能力，证明了该模型的可靠性和优越性。

关键词：全球导航卫星系统多径干涉遥感；土壤湿度；极限学习机；粒子群优化中图分类号：Ｐ２２８文献标志码：Ａ开放科学（资源服务）标识码（ＯＳＩＤ）：文章编号：１００３－３１０６（２０２３）０６－１３６８－０８ＰＳＯ ＥＬＭＡｓｓｉｓｔｅｄＧＮＳＳ ＩＲＳｏｉｌＭｏｉｓｔｕｒｅＲｅｔｒｉｅｖａｌＭｅｔｈｏｄＬＩＸｉｎｑｉａｎｇ１，２，ＬＩＵＬｉｌｏｎｇ１，２，ＬＩＵＺｈｕｏｌｕｎ１，ＺＨＡＮＧＺｈｉ１（１．ＣｏｌｌｅｇｅｏｆＧｅｏｍａｔｉｃｓａｎｄＧｅｏｉｎｆｏｒｍａｔｉｏｎ，ＧｕｉｌｉｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ５４１００６，Ｃｈｉｎａ；２．ＧｕａｎｇｘｉＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳｐａｔｉａｌＩｎｆｏｒｍａｔｉｏｎａｎｄＧｅｏｍａｔｉｃｓ，Ｇｕｉｌｉｎ５４１００６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅａｃｃｕｒａｃｙｏｆｓｏｉｌｍｏｉｓｔｕｒｅｒｅｔｒｉｅｖａｌｆｒｏｍＧｌｏｂａｌＮａｖｉｇａｔｉｏｎＳａｔｅｌｌｉｔｅＳｙｓｔｅｍＩｎｔｅｒｆｅｒｏｍｅｔｒｉｃＲｅｆｌｅｃｔｉｏｎ（ＧＮＳＳ ＩＲ）ｏｂｓｅｒｖａｔｉｏｎｄａｔａ，ａｓｏｉｌｍｏｉｓｔｕｒｅｉｎｖｅｒｓｉｏｎｍｅｔｈｏｄｂａｓｅｄｏｎＥｘｔｒｅｍｅＬｅａｒｎｉｎｇＭａｃｈｉｎｅ（ＥＬＭ）ｍｏｄｅｌｉｓｐｒｏｐｏｓｅｄ，ａｎｄｔｈｅｏｐｔｉｍａｌｐａｒａｍｅｔｅｒｓｏｆＥＬＭｍｏｄｅｌａｒｅｏｂｔａｉｎｅｄｂｙｕｓｉｎｇＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ｏｐｔｉｍｉｚａｔｉｏｎ．ＴｈｅｐｈａｓｅｏｆｒｅｆｌｅｃｔｅｄｓｉｇｎａｌｅｘｔｒａｃｔｅｄｂｙＧＮＳＳ ＩＲｉｓｔａｋｅｎａｓｔｈｅｉｎｐｕｔｖｅｃｔｏｒ，ａｎｄｔｈｅｓｏｉｌｍｏｉｓｔｕｒｅｖａｌｕｅｏｆＰＢＯＨ２ＯｉｓｔａｋｅｎａｓｔｈｅｏｕｔｐｕｔｖｅｃｔｏｒｔｏｃｏｎｓｔｒｕｃｔｔｈｅＰＳＯ ＥＬＭｎｅｕｒａｌｎｅｔｗｏｒｋｍｏｄｅｌ，ｗｈｉｃｈｉｓｆｕｒｔｈｅｒｃｏｍｐａｒｅｄｗｉｔｈｔｈｅＥＬＭｍｏｄｅｌ，ＢＰｎｅｕｒａｌｎｅｔｗｏｒｋｍｏｄｅｌａｎｄｌｉｎｅａｒｒｅｇｒｅｓｓｉｏｎｍｏｄｅ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ：ＴｈｅｄｅｔｅｒｍｉｎａｔｉｏｎｃｏｅｆｆｉｃｉｅｎｔｂｅｔｗｅｅｎｔｈｅｒｅｔｒｉｅｖａｌｒｅｓｕｌｔｏｆｓｏｉｌｍｏｉｓｔｕｒｅｆｒｏｍＰＲＮ１０ｓａｔｅｌｌｉｔｅｉｎＰＳＯ ＥＬＭｍｏｄｅｌａｎｄｔｈｅｔｒｕｅｖａｌｕｅｏｆｓｏｉｌｍｏｉｓｔｕｒｅｉｓ０．８７７１，ｔｈｅｒｏｏｔｍｅａｎｓｑｕａｒｅｅｒｒｏｒｉｓ０．０２５２，ａｎｄｔｈｅｍｅａｎａｂｓｏｌｕｔｅｅｒｒｏｒｉｓ０．０２０７．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｏｔｈｅｒｔｈｒｅｅｍｏｄｅｌｓ，ｔｈｅｓｏｉｌｍｏｉｓｔｕｒｅｉｎｖｅｒｓｉｏｎａｃｃｕｒａｃｙｉｓｈｉｇｈｅｒ，ｔｈｅｓｔａｂｉｌｉｔｙｉｓｓｔｒｏｎｇｅｒ，ａｎｄｔｈｅｆｉｔｔｉｎｇａｂｉｌｉｔｙｉｓｓｔｒｏｎｇｅｒ，ｗｈｉｃｈｐｒｏｖｅｓｔｈｅｒｅｌｉａｂｉｌｉｔｙａｎｄｓｕｐｅｒｉｏｒｉｔｙｏｆｔｈｉｓｍｏｄｅｌ．Ｋｅｙｗｏｒｄｓ：ＧＮＳＳ ＩＲ；ｓｏｉｌｍｏｉｓｔｕｒｅ；ｅｘｔｒｅｍｅｌｅａｒｎｉｎｇｍａｃｈｉｎｅ；ＰＳＯ收稿日期：２０２２－１２－２０基金项目：国家自然科学基金（４２０６４００２）；广西自然科学基金（２０１８ＧＸＮＳＦＡＡ２９４０４５）ＦｏｕｎｄａｔｉｏｎＩｔｅｍ：ＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（４２０６４００２）；ＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＧｕａｎｇｘｉ（２０１８ＧＸＮＳＦＡＡ２９４０４５）０　引言土壤湿度也称为含水量，在自然灾害、环境监测以及农业领域起着举足轻重的作用。

粒子群优化算法的改进及数值仿真

粒子群优化算法的改进及数值仿真

Ｔｈ ｉ ｒ ｄ ｌ ｙ，ａ ｎ ｅ ｗ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ ｉ ａ ｌ ｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ｗａ ｓ ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｅ ｄ ｔ ｏ ａ ｄ ｊ ｕ ｓ ｔ ｔ ｈ ｅ ｖ ｅ ｌ ｏ ｃ ｉ ｔ ｙ ．Ｆｉ ｎ ａ ｌ ｌ ｙ，
射 的方 法处理 粒 子 的越 界．数值 仿 真 结 果 表 明，改进 算 法 明 显 优 于 普 通 粒 子 群 优 化 算 法 、
差分进 化算 法 、人工 蜂群优 化算 法和 蚁群优 化 算法．
关 键词 ：粒子群 优化 ； Ｂ ｅ ｔ ａ分布 函数 ；逆 不完全 ｒ函数 ；数值 优化 ；算 法设 计
ＬＩ Ｊ ｉ ａ ｎ ｐ ｉ ｎ ｇ，ＧＯＮＧ Ｙａ ｏ ｈ ｕ ａ，Ｚ Ｈ ＡＯ Ｓ ｉ ｙ ｕ ａ ｎ ，ＬＵ Ａｉ ｐ ｉ ｎ ｇ，Ｌ Ｉ Ｐａ ｎ ｃ ｈ ｉ
（ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｃｏ ｍｐ ｕ ｔ ｅ ｒ ａ ｎ ｄ Ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ Ｔｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ，Ｎｏ ｒ ｔ ｈ ｅ ａ ｓ ｔ Ｐｅ ｔ ｒ ｏ ｌ ｅ ｕ ｍ Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ，
ｃ ｏｍｍ ｏ ｎ ＰＳＯ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ ，ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ ｉ ａ ｌ ｅ ｖ ｏ ｌ ｕｔ ｉ ｏｎ ａ ｌ ｇｏ ｒ ｉ ｔ ｈｍ ，ａ ｒ ｔ ｉ ｆ ｉ ｃ ｉ ａ ｌ ｂｅ ｅ ｃ ｏ ｌ ｏ ｎｙ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ａ ｌ ｇ ｏｒ ｉ ｔ ｈｍ ａ ｎ ｄ ａ ｎｔ ｃ ｏｌ ｏ ｎ ｙ ｏ ｐｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏｎ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ ． Ｋｅ ｙ ｗｏｒ ｄ ｓ：ｐａ ｒ ｔ ｉ ｃ ｌ ｅ ｓ ｗａ ｒ ｍ ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ；Ｂｅ ｔ ａ ｄ ｉ ｓ ｔ ｒ ｉ ｂｕｔ ｉ ｏｎ ｆ ｕ ｎｃ ｔ ｉ ｏ ｎ；ｉ ｎｖ ｅ ｒ ｓ ｅ ｉ ｎ ｃ ｏ ｍｐ ｌ ｅ ｔ ｅ Ｉ １ ｆ ｕ ｎｃ ｔ ｉ ｏ ｎ； ｎｕ ｍｅ ｒ ｉ ｃ ａ ｌ ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ；ａ ｌ ｇ ｏｒ ｉ ｔ ｈｍ ｄｅ ｓ ｉ ｇｎ

粒子群优化算法

粒子群优化算法

粒子群优化算法
周驰;高海兵;高亮;章万国
【期刊名称】《计算机应用研究》
【年(卷),期】2003(020)012
【摘要】系统地介绍了粒子群优化算法,归纳了其发展过程中的各种改进如惯性权重、收敛因子、跟踪并优化动态目标等模型.阐述了算法在目标函数优化、神经网络训练、模糊控制系统等基本领域的应用并给出其在工程领域的应用进展,最后,对粒子群优化算法的研究和应用进行了总结和展望,指出其在计算机辅助工艺规划领域的应用前景.
【总页数】5页(P7-11)
【作者】周驰;高海兵;高亮;章万国
【作者单位】华中科技大学,机械科学与工程学院,教育部智能制造开放实验室,湖北,武汉,430074;华中科技大学,机械科学与工程学院,教育部智能制造开放实验室,湖北,武汉,430074;华中科技大学,机械科学与工程学院,教育部智能制造开放实验室,湖北,武汉,430074;华中科技大学,机械科学与工程学院,教育部智能制造开放实验室,湖北,武汉,430074
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于云滴粒子群优化算法的多道次端铣削高效稳定切削参数优化方法 [J], 蔡旭林;杨文安;黄超
2.基于改进粒子群优化算法的多目标自适应巡航控制 [J], 毛锦;阳磊;刘凯;杜进辅;崔亚辉
3.多惯性权重的自适应粒子群优化算法 [J], 杨博雯;钱伟懿
4.多惯性权重的自适应粒子群优化算法 [J], 杨博雯;钱伟懿
5.基于遗传-粒子群优化算法的USV路径规划方法 [J], 宫月红;张少君;王明雨;孟雄飞
因版权原因，仅展示原文概要，查看原文内容请购买。

基于粒子群优化的神经网络训练算法在产品种类预测中的应用

基于粒子群优化的神经网络训练算法在产品种类预测中的应用

基于粒子群优化的神经网络训练算法在产品种类预测中的应用高亮;杨林;周驰;胡映兵
【期刊名称】《计算机集成制造系统》
【年(卷),期】2006(12)3
【摘要】市场环境的变化导致产品更新换代加快,产品种类预测成为新的难题.传统的线性预测方法只能对产品需求的数量或价格等数值进行预测,而无法对产品的发展趋势和未来种类做出正确预测.通过对产品种类预测、数据挖掘和粒子群优化算法的研究,建立种类预测模型,利用基于粒子群优化的神经网络训练算法进行产品种类预测,并以手机为例进行预测,结果证明该方法是有效的.
【总页数】5页(P465-469)
【作者】高亮;杨林;周驰;胡映兵
【作者单位】华中科技大学,机械科学与工程学院工业工程系,湖北,武汉,430074;华中科技大学,机械科学与工程学院工业工程系,湖北,武汉,430074;华中科技大学,机械科学与工程学院工业工程系,湖北,武汉,430074;华中科技大学,机械科学与工程学院工业工程系,湖北,武汉,430074
【正文语种】中文
【中图分类】F274
【相关文献】
1.基于粒子群优化算法的RBF神经网络在闸墩裂缝宽度预测中的应用 [J], 闫滨;王闯
2.基于粒子群优化的神经网络训练算法研究 [J], 高海兵;高亮;周驰;喻道远
3.基于粒子群优化算法的神经网络在油品质量预测中的应用 [J], 李方方;赵英凯;贾玉莹
4.基于粒子群优化的反向传播神经网络算法在建筑物沉降预测中的应用 [J], 钱超群
5.Wiener型系统基于神经网络的在线训练算法广义预测控制 [J], 李超璟;熊伟丽;徐保国
因版权原因，仅展示原文概要，查看原文内容请购买。

基于PSO的置换流水车间调度算法

基于PSO的置换流水车间调度算法

基于PSO 的置换流水车间调度算法周　驰,高　亮,高海兵(华中科技大学工业工程系,湖北武汉430074) 摘　要:　置换流水车间调度问题(PFSP )是典型的具有工程背景的组合优化问题.对该问题的研究具有重要的理论意义与应用价值.本文针对PFSP 问题提出了新的基于粒子群优化(PS O )的调度算法.论文分析了广义粒子群优化(G PS O )模型中信息流动拓扑结构的缺陷,提出新的基于种群的元启发式算法信息共享机制SIS M.基于SIS M 信息共享机制的PS O 调度算法利用PFSP 问题的邻域知识指导个体的局部搜索.与历史文献中该问题的代表性算法比较,该算法可在调度质量与计算费用之间获得较好的平衡.仿真实例验证了该调度算法的有效性.关键词:　粒子群优化;置换流水车间调度;信息共享机制;邻域知识中图分类号:　TP38 文献标识码:　A 文章编号:　037222112(2006)1122008204Particle Swarm Optimization Ba sed Algorithm forPermutation Flow Shop SchedulingZH OU Chi ,G AO Liang ,G AO Hai 2bing(Department o f Industrial Engineering ,Huazhong University o f Science and Technology ,Wuhan ,Hubei 430074,China )Abstract :　Permutation Flow shop scheduling (PFSP )is a complex combinatorial optimization problem with strong engineer 2ing background ,and is of great importance in both theory and application.In this paper ,a new PSO based flow shop scheduling al 2gorithm is proposed to generate optimized PFSP schedule.First ,limitation of information sharing mechanism in GPSO model is ana 2lyzed and new population based information sharing strategy is proposed.PFSP scheduling algorithm based on new information shar 2ing strategy utilizes problem 2concerned knowledge to direct its search in the local search pared with representative PFSP scheduling algorithms ,the proposed algorithm can obtain good balance between quality of schedule and computational cost.Simulation results validate its efficiency.K ey words :　particle swarm optimization ;permutation flow shop scheduling ;information sharing strategy ;neighborhood knowledge1　引言 置换流水车间调度(Permutation Flow Shop Scheduling Prob 2lem :PFSP )是制造系统中重要的规划问题.该问题一般可以描述为:n 个待加工的工件J ={1,2,…,n},需要在m 台机床M ={1,2,…,m}上完成加工.每个工件包含m 道加工工序O j 1,O j 2,…,O jm ,其中O jk 代表工件j 在机床k 上加工时间为p jk 的工序.PFSP 规定:(1)每个工件在机床上的加工顺序相同;(2)每台机床上工件的加工顺序相同;(3)每台机床每次最多只能加工一个工件;(4)每个工件每次只能由一台机床加工.优化调度的目的是在该问题的所有可行调度中确定每个工序的开始时间s ij ,使总完工时间C max 最小即:C 3max =min (C max )=min {max (s ij +p ij ):ΠJ i ∈J ,M j ∈M},满足以上条件的工件加工顺序即为置换流水车间调度的最优解.车间生产环境中优化调度的自动生成是智能制造领域的重要研究内容.PFSP 调度算法通过对制造过程进行作业计划,以实现流水车间环境下生产过程的优化调度.PFSP 广泛应用于实际生产,尤其适用于单件大批量生产背景的制造企业.对流水车间生产的优化调度可有效提高制造资源利用率与企业生产效益.置换流水车间调度的常用方法大致可分为三类[1]:构造启发式方法(如G upta 、Johns on 、Palmer 、C DS 、NEH 等)、运筹学方法(如分枝定界法、割平面法、动态规划法等)、基于人工智能的元启发式算法(如模拟退火、禁忌搜索、遗传算法、蚂蚁算法等).PFSP 问题的构造启发式算法可以在较短时间内获得调度问题的解.但是该类方法在构造调度的过程中依赖根据问题局部信息设计的调度规则,所获得的调度一般为局部最优解.运筹学方法的应用受问题规模与计算费用的限制.对于类似PFSP 的复杂组合优化问题,该类方法难以在有限时间内获得问题的优质解.基于物理或仿生学机理的一类元启发式调度算法能够在可行时间内以较大概率获得该类问题的最优解或近似最优解,成为各种车间调度问题最常用的算法.粒子群优化(Particle S warm Optimization :PS O )是受鸟群捕食启发产生的元启发式算法.PS O 通过种群内粒子之间的合收稿日期:2005203215;修回日期:2006206210基金项目:国家自然科学基金(N o.50305008)第11期2006年11月电 子 学 报ACT A E LECTRONICA SINICA V ol.34　N o.11N ov.　2006作与竞争产生的群体智能指导优化搜索.与遗传算法比较, PS O保留了基于种群的全局搜索策略,其优化机理清晰易懂,搜索模型步骤简单,计算费用较低.该算法已在切削参数优化[2]、PI D控制器的参数设计[3]、补偿电容器配置优化[4]等工程优化问题获得成功应用.本文将基于PS O的算法用于PFSP 优化调度的生成,针对遗传算法与广义粒子群优化模型(G P2 S O)中信息共享机制的缺陷,论文提出新的基于群体智能思想的信息共享机制.该信息共享机制可维持算法在全局搜索与计算费用之间良好的平衡.基于新的信息共享机制的PS O调度算法充分利用PFSP问题本身的邻域知识指导算法的局部搜索,很大程度地避免了PS O的随机策略导致的盲目搜索.2　广义粒子群优化算法211　PSO信息共享机制与广义粒子群优化模型K ennedy和Eberhart受鸟群觅食行为的启发,1995年提出粒子群优化算法(Particle S warm Optimization:PS O)[5].最初的设想是仿真简单的社会活动,研究并解释复杂的社会行为,后来发现该算法可以用于优化问题的求解.但是,传统粒子群优化算法局限于速度-位移更新算子,不能有效拓展到离散及组合优化领域.针对连续变量优化问题的速度-位移更新模型使用实数编码,编码的每一维代表独立的变量,不能反映编码中参数间的顺序或其它约束关系.针对粒子群优化算法在解决组合优化问题上的局限性,我们分析了粒子群算法的优化机理,并在此基础上提出了广义粒子群优化模型(G PS O).模型中粒子的更新操作仅为抽象概念,因此基于该模型的算法实现需要设计具体的更新算子.粒子可以以多种形式从其个体及邻域极值获得更新信息.以遗传操作为例,粒子可通过与个体极值及邻域极值进行交叉获得更新信息,并通过线性下降的变异进行随机扰动并趋于局部搜索.以此模型为基础,我们提出采用遗传操作作为粒子更新策略,并成功解决了TSP问题[6].212　GPSO信息共享机制的缺陷分析基于G PS O模型的算法(包括传统PS O算法),其信息共享机制中均采用相同的信息流动拓扑结构,其潜在缺陷在于算法中的每个粒子过于贪婪地获取更新信息,使得粒子的搜索性能受其个体与邻域极值的影响较大,种群容易局部收敛.相对于进化算法,传统PS O算法在连续优化问题显示出较快的收敛速度与较高的收敛精度.需要指出该优势的获得与PS O算法求解问题的解空间分布有关.对于局部最优解遍布整个解空间的复杂组合优化问题,该信息拓扑结构将会导致相对进化算法更严重的早熟现象.针对基于G PS O模型的上述缺陷,本文提出的基于群体智能的信息共享机制,可作为通用的信息共享机制适用于所有基于种群的元启发式算法. 213　基于群体智能的信息共享机制SISM2.3.1　记忆信息机制记忆机制是PS O、蚁群算法AC O、禁忌搜索T abu Search等元启发式算法取得成功的关键因素.此外,研究发现在其它元启发式算法中引入记忆功能可显著改进算法性能.例如遗传算法保留精英解的策略本质上属于对迭代过程中种群最优解的记忆.S A中引入记忆功能可提高算法的收敛稳定性.因此记忆依然作为本文信息共享机制中信息的核心来源.2.3.2　新的信息共享机制基于SIS M的算法种群中的核心部分为记忆库.记忆库保存一定比例的记忆个体,一般占种群规模的15%～20%.新的信息共享机制表达如下:算法种群保证一定规模的记忆库,种群中个体的每次迭代均从自身记录的记忆个体及记忆库中随机抽样的记忆个体获得更新信息;种群的每次更新均同时完成对记忆库的更新,同时对更新后种群中一定比例的劣质解进行启发式初始化.对记忆库的更新采用以下原则:(1)更新种群中最优的记忆个体优于记忆库的最差个体,(2)为保证记忆库中粒子的分布性,该更新记忆个体的编码及目标函数在记忆库中唯一,对于组合优化问题主要是保证个体间海明距离尽量小.为在保证多样性的同时提高计算效率,本文做了简单处理,即只通过目标函数的差异性判断多样性,仿真实验证实了该方法的有效性.2.3.3　SISM信息共享机制的改进分析SIS M信息共享机制中的个体从记忆库而不是邻域极值获得更新信息.记忆库中的个体为种群中具有分布性的较优记忆信息的集合.个体不仅依赖自身经验获得的记忆信息,而且借鉴种群中其他个体的成功经验.相对于遗传算法的信息共享机制,个体从记忆库中获得更新信息同时保留了较大的信息流动效率.另一方面,记忆库个体为随机抽样选择,且记忆库本身具有分布性.因此相对于G PS O的信息共享机制,基于SIS M算法局部收敛的概率较低.3　基于粒子群优化的流水车间调度算法311　基于PFSP邻域知识的局部搜索针对问题知识设计的局部搜索是邻域搜索元启发式算法的关键组成部分.研究表明对于车间调度问题包括JSP与FSP 等,可行调度的关键块中工序的局部移动是该类问题最有效的更新算子之一.PS O算法是基于群体智能的元启发式算法.信息共享机制中更新算子的设计是算法实现的关键步骤.文献[7]对置换流水车间调度中基于关键路径的邻域结构进行了系统的研究.本文PS O算法中基于PFSP邻域知识的局部搜索采用该邻域结构.基于该邻域结构的局部搜索示意图如图1所示.调度问题的邻域结构需要根据问题的具体特点设计.例如针对JSP问题各机器上工件的加工顺序及各工件的工序加工顺序均不相同的特点,对该问题的编码及邻域结构需要以9002第　11　期周　驰:基于PS O的置换流水车间调度算法工序为单位进行设计.PFSP问题中,各工件的工序加工顺序及工件在机器上的加工顺序一致.而且PFSP问题的约束较少,工件的邻域移动无任何限制即工件以任意方式的移动均不会产生非法解.因此PFSP调度的邻域移动以工件为单位,无须深入到每道工序.对车间调度问题的研究表明,关键路径上工序块内部的移动对调度的质量无任何改进.因此本文以关键块之间工序的插入作为该类问题的邻域移动策略.基于任意两个关键块的全邻域结构具有完备的邻域空间,但是基于该结构的邻域移动,在待插入的邻域位置离当前工序较远的情况下更倾向于全局搜索.此外实验证明该邻域结构往往导致算法的冗余搜索甚至迂回搜索.为提高算法的局部搜索效率,本文的邻域结构定义为当前关键块中的各工序向其邻接块内移动的集合.图1中的箭头标出移动的位置.对于块B i上的一道工序o k(k表示整个关键路径中该工序的序号).设M p k表示将工序向紧前块中的移动集合,M s k表示将工序向紧后块中的移动集合,π(m)表示经过移动m得到的新调度,则当前调度π的邻域可表示为:N(π)={π(m)|m∈(M p1∪M s1)∪(M p2∪M s2)∪…(M p n∪M s n)}.算法以N(π)中Makespan最小的邻域调度作为局部搜索的更新调度.为防止迂回搜索,算法以一定的概率选择工序的插入位置.312　PFSP调度算法本文基于PS O的PFSP调度算法采用SIS M信息共享机制.结合PS O算法特点,SIS M信息共享机制中的记忆个体对应于PS O的粒子的个体极值,记忆库即为PS O种群中最优的个体极值的集合.基于SIS M信息共享机制的PS O调度算法在挖掘自身群体智能的同时充分利用PFSP邻域知识进行局部搜索,其详细流程如图2所示.该算法采用基于工件的顺序编码方案,并选择最大完工时间Makespan作为解的评价标准. PS O算法在初始化过程中使用NEH、Palmer与C DS生成启发式初始解.初始种群中的其它粒子使用随机初始化.若算法以到达最大迭代次数或在指定迭代次数内调度的质量无改进,则算法停止.该算法的关键步骤为更新算子的设计与基于调度问题邻域知识的局部搜索.31211　更新算子的设计基于PFSP的遗传调度算法针对顺序编码设计了大量成功的遗传操作如P MX,OX,LOX等.考虑到基于P MX交叉操作的遗传算法在求解PFSP问题的成功经验.本文基于PS O的PFSP调度算法采用P MX交叉作为粒子的更新算子,用于从个体极值及记忆库中随机选择的记忆粒子获得更新信息. 31212　基于邻域知识的局部搜索粒子在从算法自身的种群中获得更新信息后,利用优化问题本身的特征设计的邻域知识进行局部搜索.针对车间调度问题的基于关键路径的邻域移动已经形成了较为系统的知识体系,在理论方面已经比较成熟.大量仿真实验验证了该邻域结构的有效性.基于该邻域结构设计的模拟退火与禁忌搜索算法已成为求解车间调度问题最有竞争力的元启发式算法.针对PFSP问题的邻域搜索的详细描述见311节.Initialize the particle population:generate randomly a set of permutation FSP schedules.D o{　F or each particle s i(t)do{ Evaluate with objective function defined as C max(si) Set individual best schedule p i(t): if C max(s i(t))≤C max(p i(t-1)) p i(t)=s i(t) Update mem ory in formation pool if rand()≤p Update PFSP schedule through PMX cross over with p i(t) else Obtain new PFSP schedule through PMX cross over with m i(t) Local search procedure: F or each operation in each critical block B i do{ Insert it before each operation in its previous critical block B i21or next one B i+1 Output the best neighbor schedule with minimum C max } }}While stopping criteria are not satis fied图2　基于SIS M信息共享机制的PS O调度算法流程4　实例仿真与结果分析 实验采用OR LI B中的PFSP实例(T aillard系列问题)进行测试.实验运行的计算机配置如下:处理器为Intel Celeron C oppermine Process or(0118μm),主频为1.0G,物理内存为128M B.实验运行获得的仿真结果如表1所示.为体现本文算法的优势,选择部分文献中有代表性的PFSP调度算法进行比较.表中PS O为本文提出的算法,T A为历史文献给出的T ail2 lard问题的C max上界.E VIS为文献[8]的遗传算法,RS A代表文献[9]的改进模拟退火算法,HS A为文献[10]的混合模拟退火算法,TS为文献[11]的禁忌搜索算法.需要说明的是所有的计算时间都根据机器类型按照同一标准进行了折算.图3以直方图的形式给出各种算法测试PFSP实例得到的相对误差性能比较.横坐标代表问题类型,纵坐标代表距离问题已知上界的相对误差.需要说明的是对于简单的测试实例如20×5与50×5问题,以上算法都可收敛到最优解.因此各种算法0102 电 子 学 报2006年表1　不同调度算法的PFSP 测试实例仿真结果Problem T AE VISRS AHS ATSPS OC maxC maxT (s )C maxT (s )C maxT (s )C maxC maxT (s )20×51278127849.01127812.4812780.06127812780.0320×101582158889.01158214.621582 3.0615821582 1.6020×2022972297211.63229721.462301 3.06229722970.0350×527242724142.962724 2.592724 2.0427*******.0250×1030253063390.25302527.4330257.143037302575.3750×2038753896901.42388654.823911211.1438863868218.43100×554935493629.33549311.025502 2.0454*******.04100×10577058621231.42577666.10577425.505776577058.25100×20628665672246.586319188.066434473.3063306258354.65200×101086810957126.7910872168.191096127.54108721087219.87200×201129411818216.1011359416.5411483435.541139311286584.27500×2026189274961271.852********.20268143674.0426316261722836.02的相对误差未能在图3中显示.由表1与图3的统计结果可知,本文基于SIS M 信息共享机制的PS O 调度算法总体性能优于其它算法.根据表1的性能指标,尽管基于个体搜索的模拟退火与禁忌搜索的计算费用指标在某些实例中略有优势,但是本文基于PS O 的PFSP 算法具有更好的全局收敛性.对于所有PFSP 测试问题,PS O 产生的最优调度的C max 指标最优,其中4个测试实例的C max 指标优于历史文献中给出的上界.与基于种群的遗传调度算法E VIS 比较,PS O 算法的调度质量与计算费用指标均有显著提高.综上所述,基于PS O 的调度算法在保证收敛速度的情况下,提高了调度质量和收敛稳定性.仿真实验的统计结果验证了本文SIS M信息共享机制与基于邻域知识的局部搜索的有效性.5　结论 针对基于种群的元启发式算法2PS O 与G A 信息共享机制的缺陷,本文提出新的基于群体智能的信息共享机制SIS M.SIS M 机制以记忆信息为核心,并引入记忆库概念,该模型每次迭代均对记忆库进行更新.通过记忆库中记忆个体的分布性及随机启发式初始化替换种群中的劣质解的策略,基于SIS M 机制的算法可保持全局搜索与局部搜索之间的良好平衡.本文将根据问题邻域知识设计的邻域结构引入PS O 调度算法的局部搜索模块中,用于指导算法的邻域搜索,避免了粒子大量盲目的更新操作.基于种群的随机搜索策略与基于知识的邻域搜索的有效融合,既保证了算法的全局优化特性,又提高了算法中有效信息的流动效率,加快了算法收敛速度.实验结果显示,基于以上策略的PS O 调度算法可在较短的时间内获得调度问题的满意解,从而验证了以上策略的有效性.本文的SIS M 信息共享机制和基于问题知识的邻域搜索可以作为通用的策略推广到其它基于种群的元启发式算法及制造领域中的其它调度问题.参考文献:[1]高海兵,周驰,等.广义粒子群优化模型[J ].计算机学报,2005,28(12):1980-1987.Gao Hai 2bing ,Zhou Chi ,et al.General particle swarm opti 2mization model [J ].Chinese J ournalof Computers ,2005,28(12):1980-1987.(in Chinese )[2]Nowicki E ,Smutnicki C.A fast tabu search algorithm for thepermutation flow 2shop problem[J ].European J ournal of Opera 2tional Research ,1996,91:160-175.[3]K im G H ,George L.Genetic reinforcement learning approachto the heterogeneous machine scheduling problem [J ].IEEE Transaction on Robotics and Automation ,1998,14(6):879-893.[4]Low C ,Y eh J Y,et al.A robust simulated annealing heuristicfor flow shop scheduling problems [J ].International J ournal of Advanced Manufacturing Technology ,2004,13:762-767.[5]Nearchou A C.A novel metaheuristic approach for the flowshop scheduling problem[J ].Engineering Applications of Arti 2ficial Intelligence ,2004,17:289-300.[6]Daya M B ,Fawsan M A.A tabu search approach for the flowshop scheduling problem [J ].European J ournal of Operational Research ,1998,109:88-95.[7]Nowicki E ,Smutnicki C.A fast tabu search algorithm for thepermutation flow 2shop problem[J ].European J ournal of Opera 2tional Research ,1996,91:160-175.[8]K im G H ,George L.Genetic reinforcement learning approach tothe heterogeneous machine scheduling problem [J ].IEEE T rans 2action on Robotics and Automation ,1998,14(6):879-893.[9]Low C ,Y eh J Y,et al.A robust simulated annealing heuristicfor flow shop scheduling problems [J ].International J ournal of Advanced Manufacturing Technology ,2004,13:762-767.[10]Nearchou A C.A novel metaheuristic approach for the flowshop scheduling problem [J ].Engineering Applications of Ar 2tificial Intelligence ,2004,17:289-300.[11]Daya M B ,Fawsan M A.A tabu search approach for the flowshop scheduling problem [J ].European J ournal of Operational Research ,1998,109:88-95.作者简介:周　驰　男,1981年生于湖北省枣阳市,华中科技大学工业工程系硕士研究生,研究方向为计算智能、运筹学与优化.E 2mail :catecheng @1102第　11　期周　驰:基于PS O 的置换流水车间调度算法。

基于粒子群优化算法的层次深度图像压缩算法

基于粒子群优化算法的层次深度图像压缩算法
一
ｘ 一 ＋、 ‘
ｆ、 卡 Ｎ Ｉ Ｉ ｅ ｏｃ ５ ０ Ｇ １ ＭＢ显 １ １ ２ ｖ ＤＡ Ｇ Ｆｒｅ ９ ０ Ｔ ５ ２ 字，Ｇ
ｌ ｔ ｎ ￣ Ｃｏ ｕ ａ ｉｎ， ｎ ｌ ｌ ， Ｈａ ｉ， ＵＳ ｕ ｉ ａｗ ｏ ｍｐ ｔｔｏ Ｈｏ ｏ ｕ ｕ ｗａ ｉ Ａ，
图结 构 消耗 的 系统 空 间。
关键词： 粒子群优化算法： 层次深度图像 ； 空间
１概 述
．
表 １ Ｓ Ｏ与 Ｏ Ｐ算法最小存储计算时间对比 Ｐ Ｏ Ｄ 最佳视线 视点计算方法（ 简称 Ｏ ） 该 ＤＰ。 层 次 深 度 图 （ａｅｅ ｅｔ ｍ ｇｓＬ Ｉ 算法首先以模型中心为原点 ，建立一个 Ｌ ｙｒｄ Ｄ ｐｈ Ｉ ａｅ， Ｄ ｓ ） 然后从 经度 和纬度方 是由Ｓ Ａ ＥＪ Ｈ Ｄ 等人在【冲 首次提 出来 的一种 半径为 Ｒ的球体 ， １ 新型的表示 和绘制复杂模型的工具。 当使 用 ２ 向把球体平均分割为 Ｎ个 片段 。每个片 Ｄ 深度纹理队列来表示模 型的 Ｌ Ｉ， Ｄ ｓ如果模 型比 段就是视点的一 个位置 ，算法通过访问 较复杂或 者顶点数 目较多的时候 ，存储 空间将 球体上的每个位 置计算 ｄ 和 ｅ ， ｓ ｓ最后为 变得很大 ， 以不得不考虑如何 减少存 纹理队 他们排序来找到最优相机位置 ，算法精 所 列的储量 。 图通过降低 Ｌ Ｉ 的深度复杂度来 度跟经度维度线 的间隔选取相关 ，复杂 试 Ｄｓ 减 少 Ｌ ｔ 的空 间 消耗 。 观 察 不 通 视 线 方 向所 度为 ０ｎ 。这是一个 比较鲁棒 的算法 ， Ｄｓ 据 （ 产生的层次深度是不同的 ，进而所 占的纹理总 在此基础上我们设计 了一种利用粒子群 单 元 数 目也 不 同 ，所 以 可 以 把 以 上 问题 转 化 为 优化算法求解最佳相机位置和保证最小 种 寻找 最 佳 视 线 方 向 的 优 化 问 题 并利 用 粒子 存储的智能算法 。也假设在模型所在的 群 优 化算 法 （ａｔ ｌ Ｓ ａｍ Ｏ ｔ ｚｔ ｎ Ｓ ） 物体坐标 系下视点是在 以模型 中心为原 Ｐｒｃｅ ｗ ｒ ｐｉ ａｏ ，Ｐ Ｏ ｉ ｍｉ ｉ 寻 找 一个 能 使 纹 理 存 储 空 间 达 到 最 小 的视 线 方 点 有 一个 半 径 为 Ｒ的 球 体 上 ， 图 ３ 视 如 ， ６／ｈ， 向。 因为模型一般可 以用相 同颜色的像元表示 ， 点在球表面坐标 为 媲蛾其 中０＝３０ ｓ 所 以再结 合传 统图像 压缩算 法如 行程 长度 编 ＝３【 ， 中 ｓ 、Ｖ分别为经度 和纬 ６， 其 ） ｈＳ 码 、Ｚ 自适应字典算法等来 压缩深度 图队列 度单位距离 。算法 中每个粒子 Ｐ的速度 Ｌｗ 可 以达 到 减 少 存 储 空 间 的 目的 。 和 位 置 由经 度 坐 标 和 纬 度 坐 标 确 定 ＠ ， Ｖ＝｛，ｌ ｘ＝Ｉ Ｒ ，粒 子 飞 行 的距 离 口妒 ， ｏ ） ， ２ 粒 子 群 优 化 算 法 粒 子 群 优 化 （ａｔ ｌ Ｓ ａｍ ｐｉ ｚｔｎ 单 位可根据需要 的精度设定。 Ｐｒｃｅ ｗ ｒ Ｏ ｔ ａｉ ， ｉ ｍｉ ｏ Ｐ Ｏ最 早 是 由心 理 学 研 究 人 员 Ｋ ｎ ｅ ｙ 士 和 Ｓ） ｅｎｄ 博 最 优 解 在 球 面 的 位 置 ｘ 也 就 是 相 计 算智能研 究人 员 Ｅ ｅｈｒ 博士 于 １９ ｂ ｒａｔ ９ ５年提 机 位置 ０ ｔ， Ｉ。我们 令每层深 度 ｏ Ｒ ＤＩ ｋ １… ｎ是 Ｈ 出的口 它是源于对鸟群觅食 过程 中的迁徙和群 图 Ｌ ｆ＝ ， ，） 大 小 为 Ｗ＊ 的 网 １ ， 图 １ 实验 模 型 居 的模拟 。 Ｓ Ｐ Ｏ是一种基于群体 的优化工具 ， 同 格 。 ＩＩ所 在 平 面 总 是 以 向量 ０ ０ 的 Ｄ 如果 采 用 的是 透 视 投 影 深度 图 ， （Ｓ） ］ Ｎ ｖｍ ｅ ０ ６ Ｇ ｘ［ ， ｏｅ ｂ ｒ２０ ． Ｒ 时也是一种基于迭代的优化工具 。系统初始化 方 向 为法 向量 。 为一组随机解 ， 通过迭代搜 寻最优值 ， 粒子 （ 潜 那 么视线是 以视点 ０ 为起点 ，以线段｛ ０ ［］ Ｅ Ｎ ＤＹ ．ａ ｄ Ｅ Ｅ ＨＡ Ｒ Ｏ ｝ ３Ｋ Ｎ Ｅ ，Ｊ ｎ Ｂ Ｒ Ｅ ￣，Ｒ ａ ｔ ．Ｐ Ｔ － ｉ 并 Ｄｋ ０ ｌ Ｓ ａｍ Ｏ ｔ ａｉ Ｅ ，Ｉ Ｅ ｎｅ ｔ ｎ ｅ ｍｉ ｏ ｎ ｒ ｉ ｌ 在 的解） 在解空间追随最优的粒子进行搜索 。 在 为 中 心 ， 经 过 深 度 图 每 个 纹 元 Ｉ ｌ 的一 组 发 ｃ ｗ ｒ ｐｉ ｚ ｔ ｎ 【 ｌ Ｅ Ｅ Ｉ ｔ ａ ｏ ａ Ｐ Ｏ 中 ， 用信 息 共 享 机 制 ， 有 着 简 单 容 易 实 散 视 线 ，而 每 层 的 有 效 纹 元 为模 型 的透 视 投 影 Ｃ ｎｅｅ ｃ ｎ ｅ ｒｌ ｅｗ ￣ｓ （ｅｔ ，Ａｕ— Ｓ 采 它 ｏ ｆ ｎ ｅ ｏ Ｎ ｕａ ｒ Ｎ ｔ ｏ Ｐ ｒ ｈ ｓ ｒ ｉ ，Ｐ ｓ ｔｗ ｙ Ｊ Ｖ １ ２ １ ４ ，９ ５ ａａ ｃ ９ 现 同 时又 有 深 刻 的智 能 背 景 的 特 点 。Ｐ Ｏ 算 所 在 纹 元 。适 应 度 函数 为 所 有 图 层 的有 效 纹 元 ｔ ｌ ） ｉ ａａ ａ ，Ｎ ，Ｉ ： ４ — ９ ８１ ９ ． Ｓ 法 一 般 是 采 用 下 面 的 公式 对 粒 子 进 行 操 作 的 。 总数 。 ［】Ｋ Ｉ Ｋ Ｔ ４ Ｒ Ｎ ，Ｖ Ｓ Ｅ Ｔ Ｏ Ｊ ，Ｒ Ｇ Ｔ Ｊ Ｅ Ｔ Ｒ Ｒ Ｍ Ｓ Ｉ Ｅ ． Ｐ ｒｉ ｌ Ｓ ｒ ａ ｃｅ ｗａ ｍ Ｏｐ ｉ ｚ ｔ ｎ ｔ ｔｍｉａ ｉ ｗｉ ｓ ａ ｉｌ ａ ｔ ｏ ｔ ｈ ｐ ｔａ ｐ ｒｉ — ｖ ＝ ＋ｃ （ ｘ ） ｃｘ２（ 一 Ｄ （） ＋ ｒ ｘ １ × ４试验与讨论 ｌ ｅ ｔｎ ｉ ｌ １ ｈ Ｅ Ｅ Ｃ ｎ ｒｓ ｎ Ｅ ｏ ｅ ｎ 测 试 平 台 是 ＷｉｄｗｓＰ，Ｉ ．Ｃ Ｕ， ｎ ｏ Ｘ ＰＶ ２２ Ｐ 显 ｃ ｘｅ ｓｏ Ｃ Ｔ ｅ Ｉ Ｅ ｏ ｇｅ ｓ ｏ ｖ —

粒子群算法在湖泊富营养化综合评价中的应用

粒子群算法在湖泊富营养化综合评价中的应用
3 实例分析
表 1 列出了全国不同地区 20 个湖泊的富 营养化 指标 数据[7]，以及应 用公式（7）计 算得到的各 湖泊 富 营 养状态综合指数值 EI 和评价结果。 为了将普适指数公 式的评价结果与其他方法的评价结果相比较， 表 2 中 列出了采 用 TSIm 和 TSIc 计算 指 数 值 的 评 价 结 果 以 及 随机评价法、模糊评价法和灰色评价法的评价结果。 从 表 3 可以看出，普适指数公式评价结果与 TSIm 评价结 果相比，除外海中有 1 级之差外，其余 19 个湖泊的评 价结果完全一致； 普适指数公式评价结果与 TSIc 评价 结果也只有外海北、外海中、外海南有 1 级之差，而实 际上，外海北、外海中和外海南只是外海湖的 3 个不同 湖区，因此可算为只有 1 个湖泊的评价结果存在差异。 此外， 用本研究的普适指数公式计算出的指数值接近 “重富”营养级的下限值，而用 TSIm 和 TSIc 指数公式计 算出的指数值接近“富”营养级上限值。 因此，无论评价 为“重富-”或“富+”营养级都是合理的，且 2 种方法评 价结果是相容的。
基于对鸟群、鱼群的仿生模拟，这些研究可称为群体智 能（Swarm intelligence）。通常单个自然生物并不是智能 的，但是整个生物群体却表现出处理复杂问题的能力。 群体智能就是这些团体行为在人工智能问题中的应 用[3]。 粒子群算法是非线性连续优化问题、组合优化问 题和混合整数非线性优化问题的有效优化工具， 其优 点是收敛速度快且需要设置的参数较少； 其缺点是易 陷入局部极小点，且搜索精度不高[4]。 假设在一个 D 维 的搜索空间中，有 m 个粒子组成 1 个粒子群，其中把 第 i 个粒子的空间位置记为 Xi=（xi1，xi2，...xiD），i=1，2，... m，代 入 优 化 目 标 函 数 ，并 计 算 出 其 相 应 的 适 应 度 值 ， 评价 Xi 的优劣。 第 i 个粒子经历的最好位置，称为个 体历史最好位置，记为 Pi=（pi1，pi2，...piD），同时每个粒子 有各自的飞行速度 Vi=（vi1，vi2，...viD）。 所有粒子经历过 的位置中最好的位置称为全局历史最好位置，记为 Pg= （pg1，pg2，...pgD）， 相应的适应度值为全局最好的适应 度 值。 对每个粒子第 d 维（1≤d≤D）的速度及位置根据 如下方程进行迭代更新：

求解作业车间调度问题的广义粒子群优化算法

求解作业车间调度问题的广义粒子群优化算法

求解作业车间调度问题的广义粒子群优化算法
彭传勇;高亮;邵新宇;周驰
【期刊名称】《计算机集成制造系统》
【年(卷),期】2006(12)6
【摘要】为克服传统粒子群优化算法在解决组合优化问题上的局限性,分析了其优化机理,并在此基础上提出了广义粒子群优化模型.按照此模型提出了一种求解作业车间调度问题的广义粒子群优化算法.在本算法中,利用遗传算法中的交叉操作作为粒子间的信息交换策略,利用遗传算法中的变异操作作为粒子的随机搜索策略,而粒子的局部搜索策略则采用禁忌搜索来实现.为了控制粒子的局部搜索以及向全局最优解的收敛,迭代过程中交叉概率以及禁忌搜索的最大步长都是动态变化的.实验结果表明,本算法可有效地求解作业车间调度问题,验证了广义粒子群优化模型的合理性.
【总页数】8页(P911-917,923)
【作者】彭传勇;高亮;邵新宇;周驰
【作者单位】华中科技大学,机械科学与工程学院,湖北,武汉,430074;华中科技大学,机械科学与工程学院,湖北,武汉,430074;华中科技大学,机械科学与工程学院,湖北,武汉,430074;华中科技大学,机械科学与工程学院,湖北,武汉,430074
【正文语种】中文
【中图分类】TP278
【相关文献】
1.基于广义遗传粒子群优化算法的供应链优化求解 [J], 胡桂武
2.求解作业车间调度问题的粒子群优化算法 [J], 张慧霞;张焱;高兴宝
3.离散粒子群优化算法求解多目标柔性作业车间调度问题 [J], 喻明让;陈云;张志刚
4.混合粒子群优化算法求解模糊柔性作业车间调度问题 [J], 蔡敏;王艳;纪志成
5.改进离散粒子群优化算法求解广义指派问题 [J], 王一川;单甘霖;童俊
因版权原因，仅展示原文概要，查看原文内容请购买。

粒子群优化算法对波束形成的效果分析

粒子群优化算法对波束形成的效果分析
由于相 控 阵天线 与传 统 的抛物 面天 线有 着本 质 的 不 同 ，这 便 造成 了诸 多 问题 ，例 如 阵列 的耦合 作 用所 造 成 的误 差 。杨金 红 、张 志 强 等 对 因阵 列 耦 合 而 产 生 误差进 行 分 析 。吴 狮 等 对 不 同 扫 描 模 式 产 生 的 误差进行了订正 。传统 的赋形波束加权方式 ，例如泰 勒加 权 、海 明加权 ，通 过数 学解 析 的方法 在抑 制 雷达 旁 瓣 上具 有 良好 的效果 ，但 是无 法 解 决 随机 方 向上 的杂 波 ，更无法起到波束展宽生成宽波束的作 用。粒子群 算法作为智能算法的一种 ，可以按 照一定需求得到优
摘要 ：相控 阵雷达 的优 势之一便是按照一定 的幅度 、相位 或者 间距对 阵元进 行加权 后在 理论上 可得 到任意形
状 的远场方 向图。但是 ，由于所需控制的参数之 间存在 互相作 用 ，导致其分 布特 性复杂 ，致使相 控阵雷达 波束形 成 性能受限 。以粒子群优化算法 为代 表的智 能算法 解决 了在 特定 场合 无法利 用数 学解 析推 导加权 项分 布 的难题 。
中，竿 ｘｍｓｉｎ ０。项作为控制相位的变化的关键项 ，常被
第 １期
滕 玉 鹏 ，等 ：粒 子群优 化 算 法对 波束 形成 的效 果分 析
２３
作 为相 位 编 码 项 。 同 时 ，有 阵 面 扫 描 角 度 的 变 化 ， 将使 雷 达 阵面产 生 耦 合作 用 ，影 响 相 控 阵 的 一 系列 参 数 。故 此 ，在实 际建 模过 程 中 ，阵因子 乘 以余 弦 函数进 行修 正 。
能较好 ，但是 收敛 速度 较慢 。
关 键 词 ：气象探测技 术 ；大 气遥感 ；相控 阵雷达 ；粒 子群 算法 ；阵列天线 ；天线方 向图

基于粒子群优化算法的高阶广义屏偏移成像（英文）

基于粒子群优化算法的高阶广义屏偏移成像（英文）

基于粒子群优化算法的高阶广义屏偏移成像（英文）何润;尤加春;刘斌;王彦春;邓世广;张丰麒【期刊名称】《应用地球物理：英文版》【年(卷),期】2017(14)1【摘要】频率-波数域单程波算子能高效地模拟地震波在复杂介质中的传播,但是在描述波的大角度传播和速度横向扰动变化较大介质中传播的问题时仍然存在一定误差。

这类误差是由于对单平方根算子使用Taylor展开式的近似程度不足所造成。

为了进一步提高泰勒展开式的精确性,本文提出一种利用粒子群智能算法优化级数展开系数的高阶广义屏算子对单平方根算子的展开级数进行优化处理。

新的偏移算法能在保持单程波偏移算法高效的前提下进一步提高偏移算子在大角度的成像精度和对强横向速度变化介质的适应性。

通过脉冲响应实验,验证了基于粒子群算法优化级数的高阶广义屏算子能够提高常规的高阶广义屏算子的成像精度和成像角度。

根据对二维SEG/EAGE盐丘模型的成像处理,基于粒子群算法优化级数的高阶广义屏算子对盐丘下面的断层取得了更高质量的成像,说明粒子群优化级数的高阶广义屏算子比常规的高阶广义屏算子具有更好的横向速度适应性。

为了检验本文所提算法对实际资料的处理能力,我们利用常规的偏移处理技术和本文所提算法对一条海上二维数据进行了偏移成像处理,对比分析成像剖面发现本文所提算法描述了更加清晰的层位信息和更高质量的偏移剖面。

本文所提算法能有效提高高阶广义屏偏移在广角度成像的能力,具有一定实际应用价值。

【总页数】11页(P64-72)【关键词】粒子群智能算法;高阶广义屏算子;Taylor级数;偏移成像;单程波算子【作者】何润;尤加春;刘斌;王彦春;邓世广;张丰麒【作者单位】中国地质大学(北京),地球物理与信息技术学院,北京100083;中国石化石油工程地球物理有限公司胜利分公司,山东东营257086;中国地质科学院,北京100037;中国石化石油勘探开发研究院,北京100083【正文语种】中文【中图分类】P【相关文献】1.起伏地表下基于高阶广义屏算子的叠前深度偏移 [J], 李振春;叶月明;仝兆岐2.稳定的保幅高阶广义屏地震偏移成像方法研究 [J], 刘定进;杨瑞娟;罗申玥;王鹏燕;郑小鹏;宋林3.波动方程的高阶广义屏叠前深度偏移 [J], 陈生昌;马在田4.基于保幅波动方程的广义高阶屏地震偏移成像方法 [J], 杨瑞娟;刘定进;吴伟;郝军;鲍峥;罗申玥5.基于粒子群优化和保幅成像条件的广义屏偏移 [J], 何润;杨午阳;王恩利;魏新建;谢春辉;闫国亮因版权原因，仅展示原文概要，查看原文内容请购买。

粒子群优化的两种改进策略

粒子群优化的两种改进策略

粒子群优化的两种改进策略
窦全胜;周春光;马铭
【期刊名称】《计算机研究与发展》
【年(卷),期】2005(042)005
【摘要】粒子群优化方法(partick swarm optimization,PSO)是由Kennedy和Eberhart于1995年提出的,并成功应用于各类优化问题.通过对PSO方法深入分析,把模拟退火和分工两种机制引入到PSO方法中,提出了模拟退火粒子群优化(PSOwSA PSO with simulated annealing)和有分工策略的粒子群优化(PSOwDOW PSO with division of work),两种不同改进方法,详细阐述了这两种方法的主要思想.测试结果表明,这两种改进方法能够克服传统PSO方法中的不足,增强了粒子群的优化能力.
【总页数】8页(P897-904)
【作者】窦全胜;周春光;马铭
【作者单位】吉林大学计算机科学与技术学院,长春,130012;吉林大学计算机科学与技术学院,长春,130012;吉林大学计算机科学与技术学院,长春,130012
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于模拟退火的自适应粒子群优化算法的改进策略 [J], 于海平;刘会超;吴志健
2.科技期刊微信公众号存在的问题及改进策略r——以两种编辑出版类科技期刊为
例 [J], 郭巧驰
3.粒子群优化算法中惯性权重改进策略综述 [J], 杨博雯; 钱伟懿
4.结合两种拓扑结构的多模态多目标粒子群优化算法 [J], 汪慎文;王佳莹;高娜;周瑶
5.一种基于粒子群优化改进策略的智能驾驶车辆路径规划方法 [J], 刘晓欢;张德干;张捷;张婷;朱浩丽
因版权原因，仅展示原文概要，查看原文内容请购买。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第28卷　第12期2005年12月计 算 机 学 报C HIN ESE J OU RNAL OF COM PU TERSVol.28No.12Dec.2005收稿日期:2004207229;修改稿收到日期:2005208204.本课题得到国家自然科学基金(50305008)资助.高海兵,男,1978年生,硕士,主要研究方向为运筹学与群体智能优化算法.E 2mail :ghbhust @.周　驰,男,1981年生,硕士研究生,主要研究方向为运筹学与群体智能优化算法.高　亮,男,1974年生,博士,副教授,主要研究方向为运筹学与优化.广义粒子群优化模型高海兵　周　驰　高　亮(华中科技大学机械科学与工程学院工业工程系　武汉　430074)摘　要　粒子群优化算法提出至今一直未能有效解决的离散及组合优化问题.针对这个问题,文中首先回顾了粒子群优化算法在整数规划问题的应用以及该算法的二进制离散优化模型,并分析了其缺陷.然后,基于传统算法的速度2位移更新操作,在分析粒子群优化机理的基础上提出了广义粒子群优化模型(GPSO ),使其适用于解决离散及组合优化问题.GPSO 模型本质仍然符合粒子群优化机理,但是其粒子更新策略既可根据优化问题的特点设计,也可实现与已有方法的融合.该文以旅行商问题(TSP )为例,针对遗传算法(GA )解决该问题的成功经验,使用遗传操作作为GPSO 模型中的更新算子,进一步提出基于遗传操作的粒子群优化模型,并以Inver over 算子作为模型中具体的遗传操作设计了基于GPSO 模型的TSP 算法.与采用相同遗传操作的GA 比较,基于GPSO 模型的算法解的质量与收敛稳定性提高,同时计算费用显著降低.关键词　广义粒子群优化模型;旅行商问题;Inver over 算子中图法分类号TP18G eneral Particle Sw arm Optimization ModelGAO Hai 2Bing ZHOU Chi GAO Liang(Depart ment of I ndust rial Engineering ,S chool of Mechanical S cience and Engineering ,H uaz hong Uni versit y of S cience and Technolog y ,W uhan 430074)Abstract Particle swarm optimization (PSO )is generic heuristic algorit hm based on swarm in 2telligence.It has been applied to many practical continuous optimization problems.However ,due to t he limitation of it s velocity 2displacement search model ,it could not be extended to solve dis 2crete and combinatorial optimization problems effectively.To solve t his p roblem ,t his paper first reviews t he applications of PSO algorit hm in integer programming problems and it s binary version discrete model ,in which t heir corresponding limitations are analyzed.Then based on t raditional velocity 2displacement operator ,mechanism of PSO algorit hm is st udied and general particle swarm optimization (GPSO )model is p roposed.Thus ,PSO algorit hm developed on t his general model can be nat urally extended to solve discrete and combinatorial optimization problems.GPSO model is still based on PSO mechanism ,but t he updating operator could integrate wit h ot her so 2lutions such as GA ,simulated annealing and taboo search easily.Travel salesman p roblem (TSP )is used to demonst rate t his extension.In view of t he success of GA in t his problem ,t his paper uses genetic operator as t he updating operator in GPSO model and f urt her proposes genetic opera 2tor based PSO model ,and select s Inver over operator as t he genetic operator in t his model.Final 2ly t he corresponding PSO algorit hm for TSP is p resented.In contrast to t he GA wit h t he same genetic operator ,GPSO based algorit hm converges consistently wit h better TSP solutions and saves comp utational cost significantly.K eyw ords general particle swarm optimization model ;travel salesman problem ;Inver over operator1　引　言粒子群优化(PSO)是基于群体智能理论的随机优化算法.算法在神经网络训练[1]、电压稳定性控制[2]、切削参数优化[3]等连续优化问题上取得了成功应用.但是该算法产生至今始终局限于连续优化领域,未能有效解决离散及组合优化问题.Parsopoulo s 等以标准函数为例测试粒子群优化算法解决整数规划问题的能力[4].Salman将任务分配问题抽象为整数规划模型并提出基于粒子群优化的解决方法[5].两者对迭代产生的连续解均进行舍尾取整后评价其质量.但是PSO算法生成的连续解与整数规划问题的目标函数评价值之间存在多对一的映射,以整型变量表示的目标函数不能准确反映算法中连续解的质量,而由此导致的冗余解空间与相应的冗余搜索降低了算法的收敛效率.Kennedy提出二进制PSO 算法[6],通过优化可连续变化的二进制概率(即二进制变量为1的概率)达到间接优化二进制变量的目的.但是该间接优化策略根据概率而非算法本身确定二进制变量,未能充分利用粒子群优化算法的性能.此外对于基于排序的组合优化问题,传统的PSO算法难以处理其中的顺序约束关系.综合相关历史文献可知,粒子群优化算法难以推广到离散及组合优化领域,已成为限制其发展的瓶颈问题.本文基于传统算法的速度2位移搜索模型分析粒子群优化机理,并在此基础上提出广义粒子群优化模型,使粒子群优化算法适用于离散及组合优化领域.针对旅行商问题(TSP)的特点及遗传算法在解决该问题的成功经验,以遗传操作作为广义模型中的更新算子,进一步提出基于遗传操作的粒子群优化模型,最后以Inver over算子作为模型中的具体遗传操作给出了基于粒子群优化的TSP解决方案.2　广义粒子群优化模型2.1　传统粒子群优化算法介绍通过对生物群落的观察和研究发现,生物群体内个体间的合作与竞争等复杂性行为产生的群体智能往往能对某些特定的问题提供高效的解决方法. Kennedy和Eberhart受鸟群觅食行为的启发,于1995年提出粒子群优化算法(Particle Swarm Optimiza2 tion,PSO)[7].其基本概念定义如下.定义1.　粒子.类似于遗传算法中的染色体(chromosomes), PSO中粒子(particle)为算法的基本组成单位,原本代表捕食的鸟的当前位置,对于优化问题则表示解空间的一个候选解.设解向量为d维变量,则当算法迭代次数为t,第i个粒子x i(t)可表示为x i(t)= [x i1(t),x i2(t),…,x i d(t)].其中,x ik(t)表示第i个粒子在第k维解空间中的位置,即第i个候选解中的第k个待优化变量.定义2.　种群.种群(swarm)由n个粒子组成,代表n个候选解.经过t次迭代产生的种群:pop(t)=[x1(t), x2(t),…,x i(t),…,x n(t)].其中,x i(t)为种群中的第i个粒子.定义3.　粒子速度.粒子速度表示粒子在单位迭代次数内位置的变化即为代表解变量的粒子在d维空间的位移.v i(t)= [v i1(t),v i2(t),…,v i d(t)],其中,v i k(t)为第i个粒子在解空间第k维的速度.定义4.　惯性权重.粒子群优化算法的全局搜索特性通过随机初始化的速度体现.惯性权重w(inertia weight)用于控制前一次迭代产生的速度对本次迭代速度的影响.粒子群优化算法的全局搜索特性通过随机初始化的速度体现.一般惯性权重w∈[0,1].Shi与Eber2 hart通过实验发现,较大的惯性权重有利于粒子种群进行全局搜索,惯性权重较小则种群更倾向于局部搜索[8].在实际的优化问题求解过程中,惯性权重随迭代次数线性递减w(t)=a×w(t-1).使粒子群在搜索的初始阶段,能够以较大的概率在整个解空间进行搜索,并能够快速收敛到最优解所在的局部区域,然后随着惯性权重的递减,粒子种群在该区域内实现局部微调.定义5.　适应度函数.适应度函数(fit ness f unction)由问题的优化目标决定,用于评价粒子的搜索性能,指导粒子种群的搜索过程.算法迭代停止时适应度函数最优的解即为优化搜索的最优解.定义6.　个体极值.个体极值p i=(p i1,p i2,…,p i d)是单个粒子从搜索初始到当前迭代所对应的适应度最优的解向量.定义7.　邻域极值.邻域极值l i=(l i1,l i2,…,l i d)是粒子对应的邻域种群从搜索初始到当前迭代所对应的适应度最优的解向量.189112期高海兵等:广义粒子群优化模型PSO首先初始化为一群随机粒子(随机解),然后通过迭代搜索最优解.在每一次迭代中,粒子通过个体极值与邻域极值更新自身的速度和位置:v i=w×v i+c1×rand()×(p i-x i)+c2×ran d()×(l i-x i)(1)x i=x i+v i(2)公式(1),(2)即为传统PSO算法核心的速度2位移更新公式.其中rand()是均匀分布在(0,1)之间的随机数.c1,c2为学习因子.通常c1=c2=2.粒子在解空间内不断跟踪其个体与邻域极值进行搜索,直到满足停止条件.粒子群优化算法的基本步骤如下:1.随机初始化粒子种群:初始化种群中所有粒子的速度和位置(可行解);2.使用根据优化问题目标定义的适应度函数对所有粒子进行评价;3.根据适应度函数更新种群中每个粒子的个体极值;4.根据适应度函数更新每个粒子所在的邻域种群的邻域极值;5.按照公式(1),(2)进行粒子速度及位置(解)的迭代;6.重复步2～5,直到满足算法的迭代停止条件为止. 212　粒子群优化机理分析传统粒子群优化算法局限于速度2位移更新算子,不能有效拓展到离散及组合优化领域.针对连续参数优化问题的速度2位移更新模型使用实数编码,编码的每一维代表独立的变量,不能反映编码中参数间的顺序或其它约束关系.该模型的本质为粒子所代表的解在连续空间跟随其个体及邻域极值以矢量运算的形式进行更新.算法应用于整数规划问题时仅通过简单的截断法将更新后的连续解映射到离散解空间.此外,算法的实数编码不适用于基于排序的组合优化问题,且速度2位移更新算子难以处理该类问题的顺序约束关系.公式(1),(2)代表单位迭代粒子的更新,为传统算法的核心实现方案,体现了粒子群优化机理.本文以该速度2位移更新公式分析粒子群优化算法的优化机理,并在此基础上提出广义粒子群优化模型.根据速度2位移迭代公式可知,粒子的更新按照以下步骤进行:1.粒子从其个体极值继承部分信息由公式(1)可知,单位迭代次数粒子更新的本质:粒子所代表的解向量在连续解空间跟踪其个体与邻域极值的向量运算.其中,粒子从个体极值获得更新信息:c1×rand()×(p i-x i),其中c1×rand()代表粒子从个体极值p i的信息继承度,反映了对p i信息的置信指标.2.粒子从其邻域极值继承部分信息粒子以相同的方式从其邻域极值l i获得更新信息:c2×rand()×(l i-x i),同样c2×rand()代表粒子从l i继承信息的程度.3.粒子进行随机或局部搜索根据公式(1),粒子在从个体与邻域极值获得更新信息后,进行如下的更新操作w×v i.其中v i初始化阶段的随机性使得粒子具有在解空间的全局探索能力.惯性权重w则具有平衡算法全局搜索与局部搜索的能力,即搜索的随机程度随迭代线性下降,在算法后期趋于局部搜索.由以上分析可知,粒子群优化机理的本质为粒子从其个体及全局极值中获得更新信息,并在此基础上进行随机或局部搜索.但是基于该机理的传统算法实现局限于具体更新操作即速度2位移更新算子,而该算子本身的局限性限制了算法在离散及组合优化领域的应用.另一方面,传统算法的核心更新公式(1)也可以理解为:针对连续问题,粒子与其个体与邻域极值进行类似于Wright等提出的启发式交叉(heuristic crossover)[9]:x i←x i+c1×rand()×(p i-x i),x i←x i+c2×rand()×(l i-x i),并在此基础上进行动态变异(dynamic mutation):x i←x i+ w×v i.鉴于遗传操作在解决离散与组合优化问题的成功经验,若将上述结论推广,即以遗传操作为粒子的更新策略,则可获得粒子群优化算法在上述领域的可行实现.因此在符合粒子群优化机理的基础上,针对特定问题设计可行的更新操作,可以将粒子群优化算法推广应用于各类优化问题.213　基于粒子群优化机理的广义优化模型基于以上对速度2位移更新算子的分析可以总结出算法的核心优化机理.根据粒子群优化机理,并忽略粒子的具体更新策略,广义粒子群优化模型(GPSO)如图1所示.Framework of General Particle Swarm Optimization(GPSO)model:Initialize randomly t he particle swarm population;Evaluate each particle wit h fitness function f(x);Do{For each particle x i{Set t he individual best solution so far as p i;Select t he best p i solution among it s neighborhood popu2lation as l i;Update the current particle using experience obtained fromthe corresponding p i;Update the current particle with information obtained fromits l i;Search randomly in balance wit h local search;}}While maximum iterations or ot her stopping criteria are notattained图1　基于广义粒子群优化模型的算法流程2891计 算 机 学 报2005年基于粒子群优化机理,本文忽略传统算法的粒子更新策略即速度2位移更新操作,提出GPSO模型.模型中粒子的更新仅为抽象概念,因此基于该模型的算法实现需要设计具体的更新算子.粒子可以以多种形式从其个体及邻域极值获得更新信息.以遗传操作为例,粒子可通过与个体极值及邻域极值进行交叉获得更新信息,并通过线性下降的变异进行随机扰动并趋于局部搜索.此外,随机搜索还可以通过模拟退火中的单步退火操作实现,使得粒子在搜索后期也可能以一定概率接受较差解,避免受个体及邻域极值的过多影响,降低局部收敛的概率.通过对粒子群优化机理的分析可知,速度2位移更新算子仅为符合粒子群优化机理的具体实现之一,该模型本质上仅适合连续问题的求解.对于离散及组合优化问题,应该选择合适的编码与更新策略实现粒子群优化机理与GPSO模型.本文以TSP问题作为组合优化问题的应用背景,采用遗传操作作为粒子更新策略.此外,TSP问题的传统启发式算法、模拟退火以及禁忌搜索的成功经验对基于GPSO模型算法更新策略的设计也有较大启发.3　基于遗传操作的粒子群优化模型TSP问题常用的优化算法主要包括:传统启发式算法以及基于人工智能的元启发式算法.传统启发式方法(如22Opt,32Opt,k2Opt与L K)利用TSP 问题本身的信息,能够较快地获得问题的优质解.但是该类算法依赖由问题局部信息设计的启发式规则,因而仅能获得问题的局部最优解.TSP的另一类元启发式算法(如遗传算法、模拟退火、蚁群优化等)受物理现象或仿生学机理的启发产生.该类算法一般采用概率或随机搜索策略,能够在可行时间内以较大概率获得问题的最优解或近似最优解,从而保证算法在解的质量与计算费用之间获得较好的平衡.鉴于元启发式算法的以上优点,该类算法已经成为TSP问题最常用的求解方法之一.粒子群优化算法是受鸟群捕食活动启发产生的仿生学算法.与其它基于种群的元启发式算法相比, PSO在算法实现方面与遗传算法更为接近.考虑到遗传算法在解决TSP问题的成功经验(尤其是针对该问题特点及编码方案设计的遗传操作可以为基于GPSO模型的算法直接借鉴),本文的GPSO模型中以遗传操作为粒子更新算子,在此基础上提出基于遗传操作的粒子群优化算法模型.1.确定算法的参数及适应度函数GPSO模型中需要设置的参数较少.一般仅需确定种群规模即粒子个数n以及算法中更新算子的相关参数.对于旅行商问题,以遍历所有城市的路径长度作为粒子的适应度函数.2.解的编码基于GPSO模型的算法对解的编码没有限制,算法理论上可采用任意编码方案,其基本原则是粒子在更新过程中不会产生非法解,而该原则一般通过算法的更新算子得到保证.如遗传算法中针对基于顺序编码而设计的PMX交叉算子.针对TSP问题,基于遗传操作的粒子群优化模型采用基于顺序表达的编码,城市顺序按照访问顺序以自然数排列.3.初始化随机生成规模为n的初始解,初始解集应保证一定的分布性,能够以较大概率覆盖整个解空间,防止种群在搜索后期陷入局部最优.为提高基于种群的元启发式算法的收敛速度,避免盲目搜索,也可以采用传统启发式方法如最近邻法(nearest neighbor)与随机初始混合的初始化策略.算法利用了问题本身的信息,可以在初始阶段即获得部分较高质量的解,同时通过随机初始化保证解的分布性,克服启发式方法容易陷入局部最优的缺陷.4.个体极值的更新根据粒子适应度更新其个体极值.比较当前粒子与粒子迭代前的个体极值的适应度函数值(即遍历TSP所有城市的路径长度):f itness(x i(t)),f itness(p i(t-1)).若粒子的当前适应值优于迭代前的个体极值,更新个体极值:p i(t)= x i(t);否则保持个体极值不变:p i(t)=p i(t-1).其中,t代表迭代次数.5.邻域极值的更新根据粒子适应度更新其邻域极值.粒子对应邻域种群中最优的个体极值即为邻域极值.邻域极值对应的TSP路径为粒子的邻域最优解.即l i(t)=p k(t),f itness(p k(t))= min{f itness(p1(t)),f itness(p2(t)),…,f itness(p l(t))}.6.粒子与其个体极值交叉粒子以给定概率与个体极值p i(t)交叉,从而实现从个体极值获得更新信息的目的.交叉后一般选择适应度较优的粒子作为更新粒子,也可以类似模拟退火机制以一定概率接受未改进粒子,该选择策略有利于防止粒子种群的早熟.交叉操作的选择不受限制,针对TSP问题可选择PMX,OX, ERX等交叉算子.需要指出,根据问题特点或利用问题本身信息设计的启发式交叉有利于改善算法的性能.7.粒子与其邻域极值交叉粒子以概率实现与其邻域极值l i(t)的交叉,具体过程与步6类似.8.粒子自身的动态变异与遗传操作结合的广义粒子群优化模型一般使用基于概率的变异实现随机或局部搜索.类似于传统粒子群优化算法的惯性权重w,变异概率动态下降,以实现算法随机搜索389112期高海兵等:广义粒子群优化模型与局部搜索的平衡.同样,变异操作可以有多种选择.针对TSP问题设计的移位(shift)、互换(exchange)与λ变异是常用的变异操作.9.算法停止条件的判断对更新后的粒子种群进行评价.若算法达到最大迭代次数Itermax或者在指定迭代次数内解无明显改进,则算法停止;否则,返回步4继续迭代.4　基于Inver over操作的粒子群优化算法Inver over是Michalewicz等针对TSP问题提出的遗传操作[10],实验证明该遗传操作优于传统交叉操作如PMX,OX,CX等以及改进的交叉操作如边重组交叉(ERX)、子路径互换交叉(SSX)等.本文提出基于Inver over操作的粒子群优化算法,并给出TSPL IB部分测试实例的仿真结果,以验证广义PSO模型的通用性与鲁棒性.Michalewicz同时指出Inver over操作需要在以下方向改进[10]:(1)针对该算法对大规模TSP问题收敛速度缓慢的缺陷,需要对算法的选择策略进行改进,从而给予算法更大的选择压力;(2)Inver over操作中用于控制随机置换变异与交叉比例的参数p一般设为常数如0101.对该参数随迭代次数或者通过跟踪种群的统计结果进行动态或自适应调整,将有利于提高算法的优化性能.411　基于Inver over更新操作的粒子群优化算法粒子群优化算法的优化机理体现了Inver over 操作的上述改进方向.基于Inver over操作的遗传算法其种群通过个体与其置换操作后的子代竞争的方式产生新个体,保证了种群的选择压力,但是文献[4]未能意识到交叉个体选择的重要性.基于Inver over的操作随机选择交叉个体,其选择压力甚至小于传统遗传算法中基于适应度的概率选择,而粒子群优化算法中粒子选择从目标函数较优的个体及邻域极值获得更新信息,保证了较大的交叉个体选择压力.此外,Inver over操作中的参数p用于控制随机置换与由交叉个体决定的置换操作的比例,类似于粒子群优化算法速度2位移更新模型中的惯性权重w.p较大则粒子趋于随机变异,从而具有探索未知解空间的能力,p较小则粒子以较大概率从优质个体(即个体或邻域极值代表的局部最优)通过交叉获得更新信息,使得算法趋于局部搜索.基于GPSO 模型的算法可借鉴速度2位移搜索模型中惯性权重的概念,使p随迭代搜索线性下降,在一定程度上维持算法全局搜索与局部搜索之间的平衡.基于以上分析,基于遗传操作的粒子群优化模型采用Inver over作为更新算子.其详细步骤如以下算法流程所示.随机初始化粒子种群PWhile(未达到迭代停止条件)Do{For种群中的每个粒子S i Do{S′=S i从S′中随机选择一个城市CRepeat{if(rand()Φp)　从S′的剩余城市中随机选择城市C′else if(rand()Φp c)　设当前个体的个体极值p i中与城市C相邻的城市为C′　else　设邻域种群的邻域极值l i中与城市C相邻的城市为C′if(S′中城市C相邻的城市即为C′) 跳出Repeat循环对S′中城市C与C′之间的部分进行置换操作(Inversion)令C=C′}if(S′目标函数值优于S i) 令S i=S′}}图2　基于Inver over更新操作的粒子群优化算法与速度2位移更新算子中的惯性权重w对应,p 随迭代次数线性下降.一般从0104线性下降到0101.与原始的速度2位移模型中c1rand(),c2rand()表示的粒子从个体与邻域极值继承信息的程度对应,基于Inver over操作的PSO使用概率p c控制粒子选择个体或邻域极值进行交叉操作的比例.需要指出,以上算法设计考虑了Inver over操作的特点.由于该操作与传统意义上的遗传操作有一定差异,因此算法并非严格符合基于遗传操作的粒子群优化模型.412　实验结果及分析为便于实验结果的分析比较,基于广义粒子群优化模型的算法与遗传算法均使用Inver over操作,并保证相应参数设置的一致性:(1)基于广义模型的PSO算法与GA的种群数目:berlin52与djibouti89问题种群个数为20,rd100问题为60,u159问题为40,其它问题均设为100.(2)粒子群优化算法中Inver over操作的相关参数:p初始为0104并随迭代次数线性下降至0101,p c=013.实验分别选择两组具有代表性的问题作为测试实例,两组问题均选自TSPL IB标准数据库.对于第一组问题,粒子群优化算法与遗传算法均在可行时间内获得问题的最优值,因此可用于比较两种算法达到最优解时的计算费用.两种算法均随机运行30次,其统计结果如表1所示.4891计 算 机 学 报2005年表1　算法达到最优解的计算费用例最优解PSO 解时间Inversion 次数GA解时间Inversion 次数berlin527542754201391　70502754211114　173463djibouti896656665611500162237665651844547355rd100791079107142177697379103415613133377u15942080420801519531094627420804418452664436pr1445853758537391375297734058537235196615449814统计结果显示,对于以上实例,GA 与PSO 均能稳定收敛到最优解,从而表明Inver over 遗传操作的有效性.需要说明的是,基于传统交叉(如PMX ,OX ,CX 等)的遗传算法甚至难以在可行时间内获得berlin52问题的最优解.表中的两种算法均以达到最优解为迭代停止条件.由统计结果可知,PSO 算法在CPU 运算时间及Inversion 操作次数两项性能指标均显著低于遗传算法.实验同时给出针对berlin52及u159问题,算法随Inversion 次数的收敛曲线,如图3与图4所示.算法以最大Inversion 次数为迭代停止条件即遗传算法稳定收敛到最优解时的Inversion 次数.由图示可知,遗传算法的收敛曲线较为平缓.作为比较,PSO 算法则可迅速收敛到最优解所在区域,并趋于收敛稳定.基于种群的元启发式算法(包括PSO 与遗传算法)为非确定性算法,其优势在于在可行时间内以较大概率获得问题的最优解或近似最优解.对于第二组较难求解的问题,若仍以达到最优解为算法停止条件则计算费用较高,且一旦出现早熟现象,算法无法停止.注意到Inversion 为两种算法的基本运算操作,这里以指定的Inversion 次数作为两种算法的停止条件.比较两者针对第二组测试实例的随机30次运行的统计结果,测试指标包括最优路径长度、平均路径长度及计算时间,实验结果见表2.由表2的统计结果可知,对于前5个实例基于PSO 的算法迭代停止时均能收敛到最优解,其30次运行的平均解与最优解较为接近,收敛稳定性较高.遗传算法则在指定停止条件下不能得到上述问题的最优解,且其多次运行解的稳定性较差.需要说明的是,以上实例中算法停止条件均为固定的Inversion 次数,一般根据经验给定,而PSO 算法稳定收敛到最优解需要的Inversion 次数一般远小于指定次数,也就是说PSO 算法的计算费用指标较表2列出的还要有所改进.对于pr226问题,表2中的统计结果为Inversion 操作达到1500E +04次得出.但是由图5的收敛曲线可知,PSO 算法收敛需要的Inversion 次数远小于指定次数.此外由表2可知,即使以相同的Inversion 次数作为停止条件,PSO 算法的CPU 运算时间指标仍优于遗传算法.589112期高海兵等:广义粒子群优化模型。