（控制科学与工程专业论文）微粒群算法及其在离散优化问题中的应用研究.pdf

摘要 随着计算机科学与技术的迅速发展，人们对科学技术提出了新 的更高的要求，其中高效的优化技术和智能计算的要求日益迫切。 微粒群优化算法( p s o ) 是一种新兴的智能优化算法，由于其概念 简单、收敛速度较快、没有很多参数需要调整且不需要梯度信息， 在工程实践中表现出巨大的潜力，并在诸多领域获得了成功应用。 但其应用大多是连续优化问题，很少被用来解决离散问题，而现实 生活中的许多工程实例只能抽象出离散模型。为此本文在对p s o 算 法原理进行深入分析的基础上，研究了其在各类离散问题中的应用。 首先，采用线性离散时间系统的研究方法对p s o 算法的收敛性 作了分析，导出了p s o 算法的收敛条件。在定性分析p s o 参数基础 上，提出了一种惯性权重非线性下降策略，并通过仿真实验，得到 惯性权重和加速系数的参数确定的指导性规律。 其次，以氧化铝生料浆优化调配问题为例研究了p s o 算法在o 1 组合优化问题中的应用。为提高算法的自适应性，引入收敛率和进 化率，自适应动态地调整惯性权值使其非线性下降。将离散二进制 p s o 和惯性权重改进策略相结合对生料浆优化调配问题进行了求 解，仿真结果证实了改进算法的优越性。 然后，以交通运输领域中的装卸货任务分配问题为例研究了 p s o 算法在随机组合优化问题中的应用。提出了一种求解该类问题 的离散微粒群算法，通过对标准p s o 所求得的微粒位置进行反正切 函数变化再取整，保证算法寻优的公平性与合理性。求解实例证实 了所提算法有效可行。 最后，以企业铁路取送车作业优化问题为例研究了p s o 算法在 排序问题中的应用。采用引入交换子和交换序的p s o 对该类问题求 解，由于该算法在求解大规模问题时易陷入局部最优，提出了一种 p s o s a 混合算法，通过使用s a 对p s o 算法的全局最优位置进行 优化调整来引导算法跳出局部最优，实例求解比较证实了所提 p s o s a 求解大规模问题时切实有效。 关键词微粒群算法，离散问题，生料浆优化调配，任务分配，取送 车作业优化 a b s t r a c t 瞄t h e r a p i dd e v e l o p m e n to ft h ec o m p u t e rs c i e n c ea n dt e c h n o l o g y , t h ed e m a n df o rs c i e n c ea n d t e c h n o l o g y i si ni n c r e a s e t h e r e f o r e h i g h - p e r f o r m a n c eo p t i m i z a t i o nt e c h n o l o g ya n di n t e l l i g e n tc o m p u t a t i o ni s i nu r g e n tn e e d p a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m ( p s o ) i sak i n do f r i s i n gi n t e l l i g e n c eo p t i m i z e r , w h i c hs t e m sf r o mt h es i m u l a t i o no fb i r d s f l o c k sl o o k i n gf o rf o o d p s oi ss i m p l ei nc o n c e p t ，f e wi np a r a m e t e r sa n d e a s yi ni m p l e m e n t a t i o n ，s oi ts h o w sg r e a tp o t e n t i a li np r a c t i c ea n dh a s b e e nw i d e l ya p p l i e di nm a n y a r e a s h o w e v e r , m a n yp r o b l e m sw h i c ha r e s o l v e db yp s 0a r en o td i s c r e t eo n e s ，i nr e a l l i f e ，aw i d ev a r i e t yo f p r o b l e m sc a nb er e p r e s e n t e db yd i s c r e t eo p t i m i z a t i o nm o d e l s i nt h i s p a p e r , t h ep r i n c i p l eo fp s 0i sa n a l y z e da n di t sa p p l i c a t i o n si nv a r i o u s d i s c r e t ep r o b l e m sa r es t u d i e d f i r s t l y , b a s e d o nt h el i n e a rd i s c r e t e t i m e s y s t e mt h e o r y , t h e c o n v e r g e n c e b e h a v i o ro fp s 0i s p r e s e n t e d ，a n dt h ec o n d i t i o no f c o n v e r g e n c ef o rp s 0i sd e d u c e da sw e l l o nt h eb a s i so fq u a l i t a t i v e a n a l y s i so fp s op a r a m e t e r s ，t h en o n l i n e a r l yd e c r e a s i n gw e i g h to fp s oi s p r o p o s e d t h e nt h ee x p e r i m e n t a la n a l y s i s o fi n e r t i a w e i g h t a n d a c c e l e r a t i o nc o n s t a n t si sd o n e ，a n dt h eg u i d e l i n eo fb e t t e rc h o o s i n gt h e s e p a r a m e t e r si ss u m m a r i z e d s e c o n d l y , t h ea p p l i c a t i o no fp s oi i l 0 一lc o m b i n a t i o no p t i m i z a t i o n p r o b l e mi ss t u d i e db ys t u d y i n gi t sa p p l i c a t i o ni nr a wm i xs l u r r yo p t i m a l a r r a n g e m e n to fa l u m i n ap r o c e s s t oi m p r o v et h ea d a p t a b i l i t yo fp s o ， c o n v e r g e n c er a t ea n de v o l u t i o n a r yr a t ea r ei n t r o d u c e dt oa d j u s ti n e r t i a w e i g h td e c r e a s i n gn o n l i n e a r l y , a d a p t i v e l ya n dd y n a m i c a l l y ，n l ei m p r o v e d s t r a t e g yo f i n e r t i aw e i g h ti si n t r o d u c e di n t od i s c r e t eb i n a r yp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mt os o l v er a wm i xs l u r r yo p t i m a la r r a n g e m e n t p r o b l e m ，t h es i m u l a t i o nr e s u l t ss h o wi t ss u p e r i o r i t y ，n l i r d l y , t h ea p p l i c a t i o no fp s 0i nr a n d o mc o m b i n a t i o no p t i m i z a t i o n p r o b l e mw a ss t u d i e db ys t u d y i n gi t sa p p l i c a t i o ni np i c k u pa n dd e l i v e r y t a s ka s s i g n m e n tp r o b l e mi nt r a n s p o r t a t i o n an e wd i s c r e t ep a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mf o rs o l v i n gt h i sp r o b l e mi s p r o p o s e d ，a n a r c t a n g e n tf u n c t i o ni si n t r o d u c e dt of u r t h e ra d j u s tt h ep o s i t i o nf o r m u l ao f s t a n d a r dp s ot oe n s u r et h ee q u i t y e x p e r i m e n t a lr e s u l t sp r o v et h a tt h e f e a s i b l e a n dr a t i o n a l i t yo fo p t i m i z a t i o n t h e p r o p o s e da l g o r i t h mi se f f e c t i v ea n d 一一一 f i n a l l y , a p p l i c a t i o no fp s o i ns o r t i n gp r o b l e mi ss t u d i e db ys t u d y i n g i t s a p p l i c a t i o ni no p t i m a lo p e r a t i o nf o rp l a c i n g - i na n dt a k i n g o u t o f w a g o n sa te n t e r p r i s er a i l w a y t h i sp r o b l e mi s s o l v e db yt h ep s ot h a t p r e s e n t i n gt h ec o n c e p t so fs w a po p e r a t o ra n ds w a ps e q u e n c e f o rt h i s a l g o r i t h mi se a s yt o e n c o u n t e rl o c a lo p t i m u m ，ah y b r i da l g o r i t h m p s o s ai s p r o p o s e d ，i nw h i c ht h eg l o b a lo p t i m a lp o s i t i o no fp s oi s a d j u s t e db yo p t i m i z a t i o no fs a ，t h u st h ea l g o r i t h mc a l ls k i pt h el o c a l o p t i m u m s o l v i n gt h eo p t i m a lo p e r a t i o nf o rp l a c i n g i na n dt a k i n g o u to f w a g o n sb yp s o - s a ，t h er e s u l t ss h o wt h a tp s o - s ai se f f e c t i v et os o l v e l a r g e s c a l ep r o b l e m k e yw o r d s p a r t i c l es w a mo p t i m i z a t i o na l g o r i t h m ，d i s c r e t ep r o b l e m ， r a wm i xs l u r r yo p t i m a la r r a n g e m e n t ，t a s ka s s i g n m e n t ，o p t i m a lo p e r a t i o n f o rp l a c i n g - i na n dt a k i n g o u tw a g o n s 1 i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：一至宝 日期：j 盟啦月监日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 e t 期：绌年互月监日 硕士学位论文第一章绪论 研究背景及意义 第一章绪论 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 优化的目的是对于给出的一个实际问题，从众多备选方案中选择出最优方案【1 1 。 例如，工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能降低成 本；资源分配中，怎样有效分配有限的资源，使得分配方案既能满足各方面的基 本要求，又能获得好的经济效益。在人类活动的各个领域中都有优化问题的身影。 优化问题按照不同的角度可以分为不同的类型，大致有如下几种分类情况： ( 1 ) 按照是否有约束条件，分为约束优化和无约束优化问题；( 2 ) 按照自变量是否 为随机，分为确定性和随机性优化问题；( 3 ) 按照目标函数或者约束条件是否非 线性，分为非线性优化和线性优化问题；( 4 ) 按照自变量是否为离散，分为连续 优化和离散优化问题；( 5 ) 按照自变量是否为时间的函数，分为动态和静态优化 问题：( 6 ) 按照目标函数的多少，分为单目标和多目标优化问题。 长期以来，人们对优化问题进行了探讨和研究。早在1 7 世纪，英国n e w t o n 和德国l e i b n i t z 发明的微积分就蕴含了优化的内容。而法国数学家c a u c h y 则首 次采用最速梯度下降法解决无约束优化问题。后来针对约束优化问题又提出了 l a g r a n g e 乘数法旧j 。近年来，由于计算机的日益广泛应用以及其它相关学科的 迅猛发展，使优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。 因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、 整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。 这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、 模式识别、生产调度、v l s i 技术、计算机工程等等。 但是随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，现实 中碰到的许多科学、工程和经济问题呈现复杂化、多极化、非线性、强约束、建 模困难等特点。这就使人们对科学技术提出了新的和更高的要求，其中对高效的 优化技术和智能计算的要求尤为迫切。 上述的这些经典的优化算法通常采用局部搜索方法，这些局部搜索方法要么 是与特定问题相关，要么是局部搜索方法的变型，它们有一个共同的特点就是通 过迭代来提高问题域中唯一的候选解。这就决定了经典算法只能适用于求解小规 模且定义非常明确的问题。解决实际工程问题，这些算法要么是解的精度，要么 是执行时间，总是不能令人十分满意。寻求一种适合于大规模并行且具有智能特 硕士学位论文第一章绪论 征的算法已经成为人们研究的曩标和方向。 二十世纪八十年代以来，一些新颖的优化算法得到了迅速发展。人工神经网 络( 砧州) 在一定程度上模拟了人脑的组织结构【4 。7 1 ；遗传算法( g a ) 借鉴了自然界 优胜劣汰的进化思想刚翻；蚁群优化算法( a c o ) 受启发于自然界蚂蚁的寻径方式 【l l 】；摸拟退火( s a ) 思路源于物理学中圈体物质的退火过程1 2 ，1 3 1 ；禁忌搜索一s ) 模拟了人类有记忆过程的智力过程【1 4 d 7 】。这些算法有个共同点：都是通过模拟或 揭示某些自然界的现象和过程得到发展，在优化领域，称之为智能优化算法 ( i n t e l l i g e n to p t i m i z a f i o na l g o r i t h m s ) 或现代启发式算法( m e t a - h e u r i s t i ca l g o r i t h m s ) 【1 8 j 。智能优化算法是一类具有自适应调节功熊的搜索寻优技术，耳前己经被广泛 地应用到组合优化问题、机器学习、人工生命、自动控制以及动态系统的故障诊 断等领域中。 本文研究的微粒群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是一种新兴 的智能优化算法，它是巍美国社会心理学家k e n n e d y 和电气工程师e b e r h a r t 受鸟 群觅食行为的启发于1 9 9 5 年提出的。尽管最初的设想是仿真简单的社会系统， 研究并解释复杂的社会行为，但后来发现p s o 是解决复杂优化问题的有效技术 【1 9 】。p s o 算法同遗传算法类似，也是基于群体的，通过群体中微粒闻的合作与 竞争产生的群体智能指导优化搜索。但相比遗传算法，p s o 保留了基于种群的 全局搜索策略，采用简单的速度位移模型，避免了复杂的交叉和变异操作，同 时它特有的记忆使其可j 以动态跟踪当前的搜索情况以调整其搜索策略，具有较强 的全局收敛能力和鲁棒性，且不需要借助| 司题的特征信息。因此，p s o 作为一 种更高效的并行搜索算法，非常适于对复杂环境中的优化问题的求解，对其进行 理论和应用研究具有重要的学术意义和工程价值，p s o 算法从诞生起，就引起了 国内外学者的广泛关注，并掀起了该方法的研究热潮，虽在诸多领域得到了成功 应用。但是，相对其它智能优化算法而言，p s o 算法的发展历史尚短，在理论基 础与应用推广上都还存在一些问题，有待解决。 第一，算法理论研究不深入，无法彻底剖析算法的行为。p s o 算法收敛模型 的建立和收敛性的分析是p s o 算法的基础，曼蓠收敛模型的建立和收敛性的分 析都困难。p s o 算法的运行过程与它所采用的参数取值有较大的关系，参数选取 仍然是一个值得研究的问题。通常认为，对不同的问题应选取相应的参数。如果 能对p s o 算法参数选取规律有一个定性的认识，必将对不固的问题域的参数选 取有很大的帮助。 第二，关于p s o 算法早熟收敛的问题。p s o 算法应用予高维或超高维复杂 问题优化时，往往会遇到早熟收敛的问题，也就是种群在还没有找到全局最优点 时已经聚集到一点停滞不动。早熟收敛不麓保证算法收敛到全局最优点，这是由 2 硕士学位论文第一章绪论 于p s o 算法早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想，即 缺乏有效的机制使算法逃离局部最优点。因而，算法早熟收敛研究也是一个值得 的研究问题。 第三，关于p s o 算法的应用局限性问题。对任何一个算法，都有自己的应 用局限性，p s o 算法也不例外。目前p s o 算法主要应用于连续问题中，而在离 散问题中应用较少。如何对其进行适当的改进使其应用于各种离散问题，以及如 何克服其局限性，结合其它优化算法去解决实际问题，也是大量学者研究的课题。 1 2 微粒群算法的研究现状 1 2 1 理论研究现状 在算法的理论研究方面，目前该领域的研究者主要致力于研究算法的收敛性 能、参数分析、拓扑结构、微粒的多样性保持和算法融合等等。 在收敛性研究方面，c l e r c 和k e n n e d y 将p s o 基本公式简化为一维空间中的 单个微粒，分析了其在离散时间和连续时间的移动情况，并提出了完全描述系统 的五维模型，里面包含的参数能够控制系统收敛的趋势1 2 0 1 。o z c a n 和m o h a n 在 假设惯性权重w 为l ，加速因子c l 和q 为常数，个体最好位置和全局最好位置 均为固定点的情况下，通过理论将一个微粒随时间变化描述为波的运行，并对不 同区域进行了轨迹分析【2 l 】。t r e a l e a 应用离散动态系统理论对简化p s o 模型的动 态行为和收敛性进行了分析，推导出对参数选择的参考准则瞄l 。 p s o 的早期版本没有惯性权重，文献【2 3 】中，s h i 等提出惯性权重的概念， 并对基本模型的粒子速度更新公式进行修正，以获得更佳的全局优化效果。在这 篇文献中，作者还提出随迭代进行惯性权值线性下降策略以提高算法的有效性和 可靠性。文献 2 4 q a 又提出了使用模糊控制系统自适应调整惯性权值和针对动态 优化问题的随机惯性权值等方法。c l e r e 于1 9 9 9 年在进化方程中引入收缩因子以 保证算法的收敛性，同时使得速度的限制放松【2 5 】。在文献【2 6 ，2 7 】中，k e i i c h i r o y a s u d a 等人根据种群的速度信息提出了适应性的微粒群算法。该算法根据对标 准微粒群算法动态的分析，提出采用适应性策略调整算法参数使种群的理想速度 线性递减，由此来控制平均速度的方法。标准算法中的参数会随着平均速度大小 的变化而进行调整，从而达到保持种群多样性和收敛性的目的。 文献 2 8 】中，e i - g a l l a d 等针对算法的种群规模、迭代次数和最大速度的选择 进行了详细分析，利用统计实验方法论证了这三个参数对算法性能的基本影响， 并给出了具有一定通用性的三种参数选择原则。文献 2 9 中对加速因子做了一些 较为深入的研究并提出了相应的改进算法。实验结果表明了改进算法确实加快了 算法的收敛，在单峰函数的测试中表现优异，却付出了算法容易陷入局部最优的 硕士学位论文第章绪论 代价，且在多峰丞数的测试中容易早熟收敛。 在算法的拓扑结构研究方面，文献 3 0 1 系统地分析了不同的种群拓扑结构对 p s o 算法效能的影响，以说明构造种群结构的基本原则。文中分析了影响种群结 构的节点连接方式、节点聚合问题、节点闯最短平均距离，以及拓扑结构与具体 优化闻题的相关性等问题，为具体优化阀题的p s o 算法种群结构调整提供了理 论基础。文献【3 l 】使用了不同连接拓扑的p s o 进行实验。实验结果都表明了选择 一种合适的邻近群拓扑，对算法性能的影响是明显的，然而没有一种邻近群拓扑 对所有基准溺数都是最合适的，具体选择哪一种邻近群拓扑与具体的问题有关。 为克服早熟收敛现象，保持微粒群体的多样性是提高算法性能的重要途径， 很多学者对此进行了研究。s u g a n t h a n 在标准p s o 中引入了空间邻域的概念，将 处于同一空间邻域的微粒构成一个子微粒群分别进化，并随着进化动态地改变选 择阙值以保证群体的多样性。r i g c t 和v e s t e r s t r o m 将排斥过程孳l 入标准p s o ，通 过多样性度量控制种群特征，从而实现微粒间吸引和排斥平衡以避免早熟现象 陬j 。k r i n k 等还提出一种微粒空间扩展的方法来解决微粒间的冲突和聚集问题， 并增强了微粒逃脱局优的能力团】。x i e 等将负熵概念雩l 入标准p s o ，通过将混沌 因素加入到微粒更新过程建立了开放消耗系统，两个多蜂函数的优化实验结果表 明了其有效性【划。 微粒群算法与其他优秀算法相结合，可以利用其他算法的优势来突破自身的 局限，从而提高算法性能。在p s o 和其他算法的融合方面，也有很多研究成果 出现。a n g e l i n a 将选择算子引入p s o 中，选择每次迭代后的较好微粒复制到下 一代，以保证每次迭代的微粒群都具有较好的性能，这种算法对某些单峰函数效 果良好f 3 5 j 。文献【3 6 】在微粒群每次迭代后，按几率在微粒间交换各维，通过交叉 来生成更优秀的微粒，算法对菜些多蜂螽数效果较好。h i t a c h i 等人分别提趱了 自己的变异算法，基本思路均是希望通过引入变异算子跳出局部极值点的吸引， 从而提高算法的全局搜索能力，得到较高的搜索成功率 3 7 1 。在文献 3 8 】中，s 1 1 i 等人也提出混合g a 与p s o 的思想，并介绍了两种混合算法：p s o g a 并行混 合进化算法p g p h e a 和p s o 。g a 串行混合进化算法p g s h e a 。h e n & l a s s 逶过将 微分进化算法( d i f f e r e n t i a le v o l u t i o n ，d e ) 融入p s o 当中，产生新的算法s d e a 3 9 1 ， p s o 算法始终运行，然后通过设定一个参数来判断是否进行微分进化算法，该参 数是微分进化算法运行次数与微粒群算法运行次数的比值。w a c h o w i a k 等人提出 将p o w e l l 方法嵌入p s o 算法当中i ：4 0 】，以提高解的精度。p a r s o p o u l o s 等人提出采 用非线性单纯形方法( n o i l l i n e a rs i m p l e xm e t h o d , n s m ) 来初始化p s o 种群【4 1 1 。 n a t a s u l ( i 等提出了带有高斯变异的p s o 算法瞰l 。除此之外，还出现了免疫p s o 4 3 】、 协霹p s 0 1 4 4 、梯度p s o t 4 5 】等混合算法。 4 硕士学位论文 第一章绪论 1 2 2 应用研究现状 p s o 算法从提出至今，国内外的学者们已经做了大量的工作，目前p s o 已 在诸多领域得到了应用。 p s o 最早应用于复杂多峰非线性函数的优化和神经网络的训练 4 6 , 4 7 1 ，后来也 被用于解决约束优化问题【4 8 】。a n g e l i n e 经过大量的实验研究发现，微粒群优化算 法在解决一些典型的函数优化问题时，能够取得比遗传算法更好的优化结果【4 9 】。 e b e r h a r t 采用经过p s o 算法优化的神经网络实现对人体肢体颤抖现象的分析，并 完成了对正常颤抖和帕金森氏症的诊断功能 s o l 。将p s o 算法与b p 算法相结合 训练神经网络已用于对电动汽车燃料电池组实时充电情况的模拟，对电动汽车燃 料电池带电状况的模拟是电动汽车以及混合动力汽车技术发展过程中的重大课 题。 p s o 算法也被成功地应用于电力系统领域。文献 5 1 】研究了p s o 算法在输电 网络扩展规划中的应用，以投资回收效益、设备成本和电能损耗费用之和最小为 目标函数，建立了扩展输电网的最小费用模型。文献【5 2 】综合考虑了诸如发电机 组的爬坡率限制、禁止运行区域和系统网络损失等更多的非线性约束条件，使应 用p s o 算法解决的负荷经济分配问题更接近于实际电力系统的运行情况。文献 【5 3 1 将p s o 算法应用于电力系统负荷模型的参数辨识中，与遗传算法进行了对 比，得出了p s o 在计算时间、全局优化性方面均比遗传算法有明显优势的结论。 日本的f 哂i 电力公司的研究人员将电力企业著名的r p v c ( r e a c t i v ep o w e ra n d v o l t a g ec o n u 0 1 ) l h - j 题简化为函数的最小值问题，并使用改进的p s o 算法进行优 化求解。与传统方法如专家系统、敏感性分析相比，实验结果证明了p s o 算法 在解决该问题上的优势。 在控制领域方面，文献【5 4 】利用p s o 算法进行混沌控制，使混沌系统产生预 期的运动，文献【5 5 】将p s o 算法应用于高阶带时滞对象的p i d 控制器设计中，研 究表明了所提出算法的有效性和所设计控制器的优越性。此外，p s o 还被用于优 化模糊控制系统，设计模糊控制器，以及对粗轧宽展控制模型的优化等等。 除了以上领域外，p s o 在自动目标检测、生物信号识别、决策调度、系统辨 识以及游戏训练、分类、信号处理、机器人应用等方面也取得了一定的成果。目 前在模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、语 音识别、烧伤诊断、探测移动目标、时频分析和图像分割等方面已经有成功应用 的先例。并且该算法也越来越多地应用于企业，英国联合利华公司已率先利用这 种技术改善其一家牙膏厂的运转情况，美国通用汽车公司、法国液气公司、荷兰 公路交通部和美国一些移民事务机构也都采用相应技术以改善其运转的机能。 p s o 最初多用于解决连续优化问题，e b e r h a r t 和k e n n e d y 于1 9 9 7 年提出了 5 硕士学位论文第一章绪论 p s o 的离散二迸制版本【5 q ，用于解决组合优化闻题。m o h a n 等提出了几种二进 制方法，但是实验有限，没有锝到确定性的结论【5 7 】。h u 等介绍了解决数列问题 的改进p s o 5 8 】。国内黄岚等人针对t s p 问题提出了引入交换子和交换序的 p s o l 5 w ，对于解空闻不是很大的闷题比较有效，僵是当所求 蠢题空间较大时容易 陷入局部最优。总丽言之，p s o 的应用主要在连续问题中，丽在离散问题中的应 用相当有限。 1 3 算法比较 。3 。 微粒群算法与遗传算法比较 遗传算法( g a ) 是一种基于自然选择与遗传机理的随机搜索算法。p s o 与g a 存在许多相似之处，但是算法思想和具体实现方式的不同使得它们各具特点。为 了更清楚地认识p s o 和g a ，下面对两者做个简单比较。 p s o 和g a 的相同点： 一一一 ( 1 ) 两者都属于仿生算法。p s o 主要模拟鸟类觅食、人类认知等社会行为 丽提出；g a 主要借用生物进化中搿适者生存一的规律。 ( 2 ) 两者都属于全局优化方法。在解空间都随机产生初始种群，因而算法 在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。 ( 3 ) 两者都属随机搜索算法。p s o 中认知项和社会项前都加有随机数：1 嚣 g a 的遗传操作均属随机操作。 ( 4 ) 两种算法都隐含并行性。搜索过程是从问题解的一个集合开始的，而 不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部 极小的可能性，并且由于这种并行性，易在并行计算机上实现，以提 高算法性能和效率。 ( 5 ) 两种算法都是根据个体的适应值进行搜索，因此不受函数约束条件的 限制，妇连续性、可导性等。 ( 6 ) 对于高维复杂闽题，往往会遇到早熟收敛和收敛性能差的缺点，两种 算法都无法保证收敛到最优点。 p s o 和g a 的不同点： ( 1 ) p s o 有记忆，好的解的知识所有微粒都保存，而在g a 中，以前的知 识随着种群的改变被破坏。 ( 2 ) p s o 中的微粒仅仅通过当前搜索到最优点进行共享信息，所以很大程 度上这是一种单项信息共享机制。而g a 中，染色体之间相互共享信 息，使得整个种群都向最优区域移动。 6 硕士学位论文 第一章绪论 ( 3 ) g a 的编码技术和遗传操作比较简单，而p s o 相对于g a ，没有交叉 和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参 数更少、实现更容易。 ( 4 ) 在收敛性方面，g a 已经有了较成熟的收敛性分析方法，并且可对收 敛速度进行估计；而p s o 这方面的研究还比较薄弱。尽管已经有简化 模型的确定性版本收敛性分析，但将确定性向随机性的转化尚需进一 步研究。 ( 5 ) 在应用方面，p s o 算法主要应用于连续问题，包括神经网络训练和函 数优化等，而g a 除了连续问题之外，已广泛应用于离散问题，比如 t s p 问题、货郎担问题、工作车间调度等。 1 3 2 微粒群算法与蚁群算法比较 p s o 和蚁群算法( a c o ) 都是群体智能算法，为更清楚地认识p s o 和a c o ， 下面对两者也做简单比较。 p s o 和a c o 的相同点： ( 1 ) 都属于仿生算法。p s o 和a c o 主要模拟觅食、人类认知等社会行为 而提出。 ( 2 ) 都属全局优化方法。算法在全局的解空间进行搜索，且将搜索重点集 中在性能高的部分。 ( 3 ) 都属随机搜索算法。 ( 4 ) 都有记忆，对好的解的知识所有微粒都保存。 ( 5 ) 隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个 个体开始的，具有隐含并行搜索特性，从而减小了陷入局部极小的可 能性。并且由于这种并行性，易在并行计算机上实现，以提高算法性 能和效率。 ( 6 ) 根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连 续性、可导性等。 ( 7 ) 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法 保证收敛到最优点。 p s o 和a c o 的不同点： ( 1 ) p s o 中的微粒通过当前搜索到最有点进行共享信息，所以很大程度上 这是一种单项信息共享机制。而a c o 中，每个个体只能感知局部的 信息，不能直接使用全局信息。 ( 2 ) p s o 的编码技术和a c o 操作比较简单，而p s o 相对于a c o ，微粒 7 硕士学位论文第一章绪论 只是通过内部速度进行更新，毽此原理更篱单、参数更少、实现更容 易。 ( 3 ) 在收敛性方面，a c o 已经有了较成熟的收敛性分析方法，并且客队收 敛速度进行估计，丽p s o 算法这方面的研究还比较薄弱。尽管已经有 简化确定性版本的收敛性分析，但将确定性囱随机性的转化必需进一 步研究。 ( 4 ) 在应用方面，p s o 主要应用于连续问题，包括神经网络训练和函数优 化等，两全局a c o 除了连续阎题之外，还可应用于离散闯题，比如 t s p 问题、王作车间调度等。 。4 论文研究内容和结构安排 本论文是在国家自然科学基金“具有信息不完备的有色冶炼过程满意不确定 优化方法研究 ( 6 0 5 7 4 0 3 0 ) 和湖南省骞然科学基金“基于不完备信息的有色冶 炼过程智能集成操作优化方法研究( 0 6 f d 0 2 6 ) 资助下开展研究，针对1 1 节所 提出的问题，对p s o 算法进行了深入的研究。对算法的收敛性能和参数选择进 行分析，重点研究p s o 算法在各类离散优化问题中的应用，并且针对不同问题 提出了相应的改进。本文酶主要研究内容与结构安排如下： 第一章介绍课题的研究背景及意义，从理论和应用两个方面介绍p s o 算法 的国内外研究现状，并将p s o 算法与遗传算法和蚁群算法进行全面比较，最后 是研究内容和论文的章节安排。 第二章首先介绥基本微粒群算法的原理、实现过程和特点，及嚣个常用的标 准微粒群算法模型。接着利用离散时间系统理论对p s o 算法进行了分析，并导 出了p s o 收敛的条件。最后对标准p s o 中的参数进行了定性和定量分析，并提 出了一种惯性权值非线性下降策略。 第三章以氧化铝生料浆优化调配阀题为例介绍微粒群算法在0 1 组台优化闯 题中的应用。首先给出氧化铝生料浆优化调配的模型，并且基于满意优化原理将 其由多目标多约束的o 1 组合优化问题转化为求所有目标和约束综合满意度最大 的满意优化闻题。其次对离散二迸制微粒群算法进行了简单介绍。为提高p s o 算法的自适应性，在第二章对惯性权重改进的基础上，引入收敛率和进化率自适 应动态改变惯性权值非线性下降的曲率，来保证算法的收敛速度和寻优精度。最 后用离散二遴制p s o 结合惯性权重改进策略对某氧化铝厂的生料浆优化调配问 题进行求解。 第四章以交通运输领域中的任务分配问题为例介绍微粒群算法在随机组合 优化问题中的应用。首先以交通运输领域中的装卸货任务分配问题为例，给出任 硕士学位论文第一章绪论 务分配问题的数学描述。其次提出一种求解任务分配问题的离散微粒群算法，在 标准p s o 算法基础上对其位置进行一系列函数变化处理，使其位置的取值能始 终为任务分配问题的可行解，即取值均为实际问题范围内的整数，并且要保证算 法寻优的公平性与合理性。最后将所提算法与第二章所提惯性权值非线性下降策 略相结合对任务分配问题进行求解。 第五章以工矿企业铁路取送车优化问题为例介绍微粒群算法在排序问题中 的应用。首先介绍工矿企业铁路取送车作业的特点，建立送取分离作业方式下的 取送车作业优化数学模型。接着介绍用于求解这类排序问题的微粒群算法一引 入交换子和交换序的p s o ，针对该算法在求解大规模问题时容易陷入局部最优难 以求出全局最优解的缺陷，结合模拟退火算法概率突跳的特性，提出一种p s o s a 混合算法，利用s a 对p s o 算法的全局最优位置优化调整，来引导算法跳出局部 最优。最后将所提p s o s a 混合算法对铁路取送车优化问题进行求解。 第六章是总结与展望。对全文进行总结，指出了本文的主要特色和创新之处， 并对今后的工作进行展望。 9 硕士学位论文 第二章微粒群算法原理及性能分析 2 1 引言 第二章微粒群算法原理及性能分析 自然界中有许多现象令人惊奇，鸟群优美而协调的运动便是其中之一。鸟群 的排列看起来似乎是随机的，其实它们有着惊人的同步性，这种同步性使得鸟群 的整体运动非常流畅，有着舞蹈的美感。有凡位科学家对鸟群的运动进行了计算 机仿真 6 0 1 。他们让每个个体按照特定的规则运动，形成鸟群整体的复杂行为。所 提模型成功的关键在于对个体间距离的操作，也就是说群体行为的同步性是因为 个体努力维持自身与邻居之间的距离为最优，为此每个个体必须知道自身位置和 邻居的信惠。生物社会学家懿o w i l s o n 也曾说过1 6 h ，“至少从理论上，在搜索 食物的过程中群体中的个体成员可以 | 寻益于所有其他成员的发现和先前的经历。 当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食 物的竞争带来的劣势。”以上两例说明，群体中个体之闻信息的社会共享有助子 进化。这正是开发微粒群优化算法( p s o ) 的核心思想。 基于上述思想，k e n n e d y 和e b e r h a r t 在1 9 9 5 年提出了微粒群优化算法的最 初形式闻。p s o 是一种基于群体智能的优化技巧，它用无质量无体积的微粒作 力个体，并为每个微粒规定简单的行为规则，从而使整个微粒群表现出复杂的特 性，可用来求解复杂的优化问题。 2 。2 基本微粒群优化算法 2 2 1 基本原理 自然界中一些生物的行为特征呈现群体特征，可以焉简单的几条规剐将这种 群体行为( s w a r mb e h a v i o r ) 在计算机中建模，实际上就是在计算机中用简单的几 条规则来建立个体的运动模型，但这个群体的行为可能很复杂。例如，r e y n o l d s 使用了下列三个规则作为简单的行为规则【1 9 1 ： ( 1 )向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 这即是著名的b o i d ( b i r d o i d ) 模型。在这个群体中每个个体的运动都遵循这 三条规燹| l ，透过这个模型来模拟整个群体的运动。p s o 算法的基本概念也是如此， 每个微粒的运动可用几条规则来描述，因此p s o 算法简单，容易实现，越来越 多地引起人们的注意。 硕士学位论文 第二章微粒群算法原理及性能分析 设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物， 所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远，那么 找到食物的最优策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟的 周围区域。如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中飞行 觅食的一只“鸟 就是p s o 算法在解空间中进行搜索的一个“微粒 ( p a r t i c l e ) ， 也就是优化问题的一个可行解，“食物 就是该优化问题的最优解。“微粒 的概 念是一个折衷的选择，它只有速度和加速度用于自身状态的调整，没有质量和体 积。“群 ( s w a r m ) 的概念来自于人工生命，满足人工生命的五个基本原则【1 8 】。 因此，p s o 算法也可以看作是对简化的社会模型的模拟，而种群中的信息共享是 推动算法进化的主要机制。 与其他进化算法相类似，p s o 算法也是通过个体间的协作与竞争，实现复杂 空间中最优解的搜索。p s o 生成初始种群，即在解空间中随机初始化一群微粒， 每个微粒都是优化问题的一个可