（计算机应用技术专业论文）微粒群算法在随机规划问题求解中的应用研究.pdf

中文摘要 随机规划是含有随机因素的一类不确定规划问题，它广泛存在于工程实际中。 其传统的求解方法是针对某些具有特殊结构的随机规划问题，将其转化为确定性等 价类，再用已有的确定性数学规划的理论去解决。另一种有效的方法是将随机仿真 与智能算法相结合进行求解，其中以遗传算法最为成功。因此，将微粒群算法应用 于随机规划问题的求解是值得研究的课题。 通过对随机规划问题中随机期望值、随机机会约束规划、随机相关机会规划 等三个模型的分析，给出了用随机仿真来处理随机规划中的随机变量或随机函数的 算法。在分析了随机规划模型的特点及微粒群算法的基础上，提出了随机仿真和微 粒群算法相结合的随机规划算法框架，并根据随机规划模型的特点，具体地给出了 将随机仿真和微粒群算法相结合求解随机期望值模型、随机机会约束规划、随机相 关机会规划的算法，为随机规划的求解提供了一条新的途径，拓展了微粒群算法研 究的应用领域并显示了其优势。为了提高求解随机规划问题的计算速度，本文对上 述基本算法进行了改进：利用随机仿真产生训练样本，训练b p 网络以逼近不确定 函数，然后应用微粒群算法并以逼近不确定函数的神经元网络进行适应值估计，从 而给出求解随机规划的混合智能算法，实验结果说明了算法的有效性。 关键词：随机规划；微粒群算法；随机仿真；神经元网络 s t u d yo np a r t i c l es w a r mo p t i m i z a t i o nf o rs o l v i n gs t o c h a s t i c p r o g r a m m i n gp r o b l e m s g r a d u a t en a m ex i a on i n g d i r e c t e db yp r o f e s s o rz e n gj i a n c h a o a b s t r a c t s t o c h a s t i cp r o g r a m m i n gi sac l a s so fu n c e r t a i np r o g r a m m i n gp r o b l e m s ， w h i c hw i d e l ye x i s t si nd i f f e r e n te n g i n e e r i n ga p p l i c a t i o nf i e l d s t r a d i t i o n a l w a yt os o l v es t o c h a s t i cp r o g r a m m i n gp r o b l e m si s t ot r a n s f o r ms t o c h a s t i c p r o g r a m m i n gi n t o i t s e q u i v a l e n td e t e r m i n i s t i cp r o g r a m m i n gf o rs o m e s t o c h a s t i cp r o g r a m m i n gp r o b l e m sw i t hp a r t i c u l a rs t r u c t u r e ，a n dt h e ns o l v e t h e mb yu s i n gt h et h e o r yo ft h ed e t e r m i n i s t i cp r o g r a m m i n g t h eo t h e r e f f e c t i v eo n ei s g e t t i n gt h ea p p r o x i m a t eo p t i m a ls o l u t i o no fs t o c h a s t i c p r o g r a m m i n gt h r o u g h s t o c h a s t i cs i m u l a t i o nc o m b i n e dw i t h i n t e l l i g e n t a l g o r i t h m ，i nw h i c hg e n e t i ca l g o r i t h mi se x c e l l e n ts of a r h e n c e ，i ti sa w o r t h ys u b je c tt oa p p l yp a r t i c l es w a r mo p t i m i z a t i o nt os o l v es t o c h a s t i c p r o g r a m m i n gp r o b l e m s a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h r e es t o c h a s t i cp r o g r a m m i n gm o d e l s ， s u c ha ss t o c h a s t i c e x p e c t e d v a l u em o d e l ，s t o c h a s t i cc h a n c e c o n s t r a i n e d p r o g r a m m i n gm o d e l ，s t o c h a s t i cd e p e n d e n c e c h a n c ep r o g r a m m i n gm o d e l ， t h es t o c h a s t i cs i m u l a t i o nm e t h o d st oe s t i m a t es t o c h a s t i cv a r i a b l e so r s t o c h a s t i cf u n c t i o n si ns t o c h a s t i cp r o g r a m m i n gp r o b l e m si sg i v e n b a s e do n t h ea n a l y s i so fs t o c h a s t i cp r o g r a m m i n gp r o b l e m sa n dp s o ，as t o c h a s t i c p r o g r a m m i n ga l g o r i t h ma r c h i t e c t u r ew h i c hc o m b i n e ss t o c h a s t i cs i m u l a t i o n w i t hp s oi s p r o p o s e d a n dt h e n ，t h ea l g o r i t h m sf o rd i f f e r e n ts t o c h a s t i c p r o g r a m m i n gm o d e l sa r eg i v e ni nd e t a i l ，w h i c hc a nm o r ee f f e c t i v e l ys o l v e s t o c h a s t i c e x p e c t e d v a l u e m o d e l ， s t o c h a s t i cc h a n c e c o n s t r a i n e d p r o g r a m m i n gm o d e la n ds t o c h a s t i cd e p e n d e n c e c h a n c ep r o g r a m m i n gm o d e l i nt h i sw a y , t h ea p p l i c a t i o na r e a so ft h ep s oa l g o r i t h ma r ee x t e n d e da n dt h e s u p e r i o r i t yo ft h ep s oa l g o r i t h mi se x h i b i t e df u r t h e r f o rt h ep u r p o s eo f s p e e d i n gu ps t o c n a s t i cp r o g r a m m i n gp r o b l e m s ，i nt h i sp a p e r ，a r l i m p r o v e d 引g o r i t h r nl sp r e s e n t e d ，i nw h i c hs t o c h a s t i cs i m u l a t i o ni su s e dt o p r o d u c e t r a i n i n gs a m p l e sf o rb pn e u r a ln e t w o r k s ，a n dah y b r i di n t e l l i g e n ta 】g o r i t h m i o rs t o c h a s t i cp r o g r a m m i n gc o m b i n 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 nw i t hb p n e u r a in e t w o r k sf o r a p p r o x i m a t i o no ft h ef i t n e s s劬c t i o ni s p r e s e n t e d f1 n a 儿y ，t h es i m u l a t i o nr e s u l t ss h o w t h ee f f e c t i v e n e s so ft h ea l g o r i t h k e yw o r d s ：s t o c h a s t i c p r o g r a m m i n g ；p a r t i c l es w a r m o p t i m i z a t i 。n ； s t o c h a s t i cs i m u l a t i o n ；n e u r a ln e t w o r k s 承诺书水话吊 本人郑重声明：所呈交的学位论文，是在导师指导 下独立完成的，学位论文的知识产权属于太原科技大 学。如果今后以其他单位名义发表与在读期间学位论文 相关的内容，将承担法律责任。除文中已经注明引用的 文献资料外，本学位论文不包括任何其他个人或集体已 经发表或撰写过的成果。 学位论文作者( 签章) ： 2 0 0 年月日 第一章绪论 第一章绪论 1 1 概述 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) 就是从数学方法论的观点出发，通过对优 化问题中各种因素之间的数学关系的研究，构造数学模型并进行求解，从而为决策 提供支持。简单地说，数学规划就是在一些数学等式或不等式约束条件下，求一个 ( 或一组) 函数极值的方法。作为运筹学( o p e r a t i o nr e s e a r c h ) 的一个重要分支，它 已被广泛地应用到许多领域中。然而，在普通的数学规划中，模型中除了决策变量 外，其它的都是确定的常量。但在现实世界中，相当多的情况下不是常量，而是呈 现出一定的随机性，因此人们在确定性数学规划的基础上发展了随机规划 ( s t o c h a s t i cp r o g r a m m i n g ) 1 心理论，使之更符合客观实际情况。 随机规划是含有随机因素的一类重要的不确定规划问题，它与确定性数学规划 最大的不同在于随机变量的引入，从而使随机规划比确定性数学规划更适于实际问 题。对于随机规划问题中所出现的随机变量，出于不同的管理目的和技术要求，采 用的方法也不同：最自然的方法是取这些随机变量所对应的函数的概率平均值( 数 学期望) ，在期望值的约束下，使目标函数的期望达到最优的方法即为期望值模型； 第二种方法是随机机会约束规划，主要针对约束中含有随机变量，且必须在观测到 随机变量实现之前做出决策的情况。考虑到所作决策在不利情况发生时可能不满足 约束条件而采用一种原则：即允许所作决策在一定程度上不满足约束条件，但该决 策应使约束条件成立的概率不小于某一预先给定的置信水平；第三种是随机相关机 会规划，是在不确定环境下通过极大化随机事件成立的机会从而给出最优决策的方 法。 随机规划广泛存在于管理科学、运筹学、经济学、最优控制等领域。随机规划 问题的提取并不困难，但其实现却很难，因此，探索高效的随机规划问题的求解算 法很有研究价值。 微粒群算法( 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 ) 作为一种新的优化算法，可 以解决几乎所有的优化问题，尤其是对实值连续变量具有很好的处理能力，随机规 划问题实质就是优化问题，所以本文利用微粒群算法对随机规划问题进行研究。 微粒群算法在随机规划问题求解中的应用研究 1 2 国内外研究动态 1 2 1 随机规划算法的国内外研究动态 由于引进了随机因素，随机规划比确定性数学规划更切合实际，也正因为随机 规划模型中含有随机变量，所以不能简单地套有确定性数学规划的现成理论，故随 机规划比确定性数学规划更难以求解。随机规划问题处理的传统方法是转换法，即 针对某些具有特殊结构的随机规划问题，通过各种办法将其转化为确定性等价类， 即将随机规划转化为确定性的数学规划，再利用已有的确定性数学规划的理论去解 决3 】【4 】。目前，国内外处理随机规划问题的有效方法是将随机仿真( s t o c h a s t i c s i m u l a t i o n ) 与智能算法相结合来进行。其中应用最广泛的是遗传算法( g e n e t i c a l g o r i t h m 简称g a ) 1 2 , 5 - 2 1 】，但遗传算法求解过程复杂，尤其是收敛速度缓慢、解的 精度不高等缺点也不容忽视。 随机规划实际上是确定性数学规划的延续和发展，当前，国内外对随机规划的 进一步研究主要有：第一，继续探索随机规划的新的有效算法【2 1 1 5 】【9 】【1 3 】【2 2 】，但这方 面的研究进展并不大；第二，是现有随机规划理论成果的应用。近年来的许多随机 规划方面的文献，都侧重于利用已经发展起来的随机规划理论去解决现实生活中的 规划问题，例如：配料问题、排序问题、设备选址、车辆调度问题等。实际上，当 前随机规划方面的论文基本上是这种应用性质的。 1 2 2p s 0 算法的研究动态 目前，通过模拟生物群体行为来解决各种复杂的计算问题已成为新的研究热 点，形成了以群体智能为核心的理论体系，并且已经在一些实际的应用领域取得了 突破性的进展。 微粒群算法作为其中一个重要的分支，它是于1 9 9 5 年由美国的k e n n e d y 和 e b e r h a r t 2 3 1 受启于鸟类群体行为的研究并利用了生物学家f r a n kh e p p n e r 的生物群体 模型而提出的一种智能算法。p s o 算法同时将微粒的位置与速度模型化，给出了一 组显式的进化方程是其不同于其它进化类算法的显著之处，也是该算法显示出许多 优良特性的关键。 p s o 算法自提出以来，由于它概念简单、实现方便，而且容易与其它优化算法 相结合，短短的十一年时间，p s o 算法已获得了很大的进展。目前主要有以下几个 研究方向：算法的改进、算法的理论基础的分析、算法的生物学基础、算法与其它 优化算法的比较和融合、算法在实际应用中的问题( 如解空间的表示，稳定性的研 2 第一章绪论 究等等) 以及算法的应用领域的拓展。 p s o 算法常应用于复杂优化问题的求解，它最早应用于人工神经元网络的训练， 随后，在函数优化、约束优化、极大极小化问题、多目标优化等问题中均得到了成 功的应用。在实际应用领域它已成功应用于机器人领域、电力系统、交通运输领域、 工程设计与优化领域、计算机领域、电磁学领域等【2 4 。3 7 1 。 1 3 本文的主要研究内容 微粒群算法作为最新的群智能算法，与遗传算法( g e n e t i ca l g o r i t h m 简称g a ) 等进化算法有许多共同之处，均使用“群体”概念，表示一组解空间中的个体集合。 但是p s o 算法同时呈现出其它进化算法所不具有的特性，它给出了一组显式的进化 方程，表现出了自己的优良特性。与g a 算法相比，没有遗传操作中的选择、交叉、 变异等复杂的过程，仅采用简单的速度一位置模型实现对整个空间的寻优操作。 由于p s 0 算法的这些特点，并且由于算法简单，易于实现，收敛速度快，精度 高，在短短十几年时间，p s 0 算法得到了很大的发展，并有很多学者对它的应用进 行了研究。本文将p s o 算法应用于数学规划中的随机规划这一大类不确定规划问题 的求解。目前，国内外将微粒群算法应用于这一方面的研究相当少，更没有研究者 给出利用微粒群算法进行求解这类问题的统一的算法，因此，本文一方面可以为随 机规划这一类问题的求解提供新的、更为有效的途径；另一方面促进了p s o 算法的 应用研究，进一步拓展了p s o 算法的应用领域，在应用中展现了微粒群算法的优势。 具体来说，主要完成以下几个方面的工作： ( 1 ) 通过对随机规划三个模型的分析，给出了用随机仿真来处理随机规划中 的随机变量或随机函数的算法。 ( 2 ) 在分析了随机规划模型的特点及微粒群算法的基础上，提出了随机仿真 和微粒群算法相结合的随机规划算法框架。 ( 3 ) 根据三个模型的特点，具体地给出了将随机仿真和微粒群算法相结合求 解随机期望值模型、随机机会约束规划、随机相关机会规划的算法。 ( 4 ) 通过仿真实验，以上算法在求解质量上优于g a 算法，但求解速度慢， 这主要是由于随机仿真本身的特点造成的，利用随机仿真产生训练样本 来训练神经元网络，并利用训练好的神经元网络代替随机仿真对不确定 函数进行逼近，从而给出了将随机仿真、神经元网络、p s o 算法相结合 的求解随机规划问题的混合智能算法。 第二章随机规划和微粒群算法 第二章随机规划和微粒群算法 2 1 随机规划 随机规划是处理数据带有随机性的一类数学规划或者说是随机性的数学规划。 它是解决含有随机变量的优化问题的一种有效工具，其中的随机变量是具有己知概 率分布的随机变量。通常讨论的随机规划有三种：一种是期望值模型，即在期望约 束条件下，使目标函数达到最优；第二种是机会约束规划。机会约束规划模型允许 决策者做出的决策在一定程度上不满足约束条件，但该决策应使约束条件成立的概 率不小于某一置信水平；第三种是相关机会规划，是一种使事件的机会函数在不确 定环境下达到最优的优化理论。 2 1 1 随机规划的建模思想 对于随机规划问题中所出现的随机变量( 或向量) ，假设用毛表示。一般地， 若目标函数f ( x ，毛) 及约束函数g j ( x ，写) 0 j = 1 ，2 p 含有不确定参数向量毛，则其本 身也是一个不确定变量，一个问题就是如何处理这些不确定函数。通常，有三种途 径： 途径1 ：从均值的角度出发。用目标函数和约束条件的均值分别代替原来的目 标函数和约束条件。 途径2 ：从风险的角度考虑。对约束条件g j ( x ，毛) 0 ，j = 1 ，2 p 希望其在实际中 至少以置信水平q 成立，即有约束p r g j ( x ，毛) o j = l ，2 p ) q 。对目标函数f ( x ， 毛) ，可以考虑不确定目标函数以定置信水平成立的不同关键值。对任一决策x ， 我们可以优化目标函数的乐观值( 即满足p r f ( x ，毛) 7 ) b 的最大的7 ) 。就是说， 目标函数f ( x ，写) 在置信水平q 下以概率b 达到最优值7 。同理，也可以优化其悲观 值( 即满足p r f ( x ，e ) 7 ) b 的最小的7 ) 。 途径3 ：使要完成的任务( 即事件) 实现的机会( 即概率) 尽可能地大。 2 1 2 随机规划的分类 1 随机期望值模型( s t o c h a s t i ce x p e c t e dv a l u em o d e l s 简称s e v m ) 对于随机规划问题中所出现的随机变量，由于不同的管理目标和技术要求，采 用的方法也不尽相同，而最自然的方法就是取随机变量所对应的函数的平均值( 数 学期望) ，把不确定规划问题转化为一个确定的规划问题。这种在期望值约束下使 目标函数的期望值达到最优的数学规划模型称为期望值模型。通常的表示为： 5 微粒群算法在随机规划问题求解中的应用研究 广m a xe f ( x ，毛) 】 i s t ( 2 1 ) l le g j ( x ，毛) 】o j = l ，2 p 其中：x 是决策向量，参数毛是随机向量，f ( x ，毛) 为目标函数，g 。( x ，毛) 为约 束函数，e 是期望值算子。 根据决策者给定的优先结构和目标水平，也可以把一个随机决策系统转化为一 个期望值目标规划( e v g p ) ： ，h f ，m i n e ( + 订) s t e f ( x ，考) 】+ 町一= 6 f ，i = 1 ，2 ，m 研g ( x ，考) o ，j = 1 ，2 ，p ( 2 2 ) 矿，订o ，扛1 ，2 ，m ， 其中易为优先因子，表示各个目标的相对重要性，且对所有的，有乃 马 为对应优先级- ，的第f 个目标正偏差的权重因子，v ，为对应优先级，的第f 个目标负 偏差的权重因子，吖为目标i 偏离目标值的正偏差，布为目标i 偏离目标值的负偏差， 为目标约束中的函数，g l 为系统约束中的函数，岛为目标i 的目标值，为优先级 的个数，m 为目标约束的个数，p 为系统约束的个数。 2 随机机会约束规划模型( s t o c h a s t i cc h a n c e c o n s t r a i n e dp r o g r a m m i n g 简称 s c c p ) ： 由c h a r n e s 和c o o p e r 汹1 提出，其显著特点是随机约束条件至少以一定的置信 水平成立。它实质是决策者考虑到所作决策在不利的情况下发生时可能不满足约束 条件而采用的一种原则：允许所作决策在一定程度上不满足约束条件( 不考虑违反 约束条件的惩罚) 即只要求该决策应使约束条件成立的概率不小于某一置信水平。 该模型的标准形式如下： fm a x i j s t 1 p r f ( x ，毛) 7 ) b( 2 3 ) l l p r g j ( x ，毛) o j 。1 ，2 p ) q 第二章随机规划和微粒群算法 其中：x 是决策向量，写是随机向量，p r ) 是事件的概率，a ，b 是决策者 预先给定的置信水平，也就是一个决策是可行的当且仅当事件的概率p r ) 不小于 事先给定的置信水平，于是目标函数f ( x ，毛) 在置信水平至少为b 时所取的最大值。 类似地，对极小化问题，有 m i n 圭p ，兰0 ，d ? + v 。d ，- ) j = l ，= 1 s t p r 扛( x ，善) 一6 矿 卢f + ，i = l ，2 ，m p r 移一，g ，善) 矿) 卢，- ，i = l ，2 ，朋 ( 2 5 ) p r g ，x ，考) o ) a ，= 1 ，2 ，p ，订o ，i = 1 ，2 ，m ， 其中p j 为优先因子，表示各个目标的相对重要性，且对所有的_ ，有p j p 。， “，为对应优先级的第f 个目标正偏差的权重因子，v f ，为对应优先级，的第i 个目标负 偏差的权重因子，矿为目标j 偏离目标值的正偏差，订为目标i 偏离目标值的负偏差， ，为目标约束中的函数，晶为系统约束中的函数，匆为目标i 的目标值，为优先级 的个数，m 为目标约束的个数，p 为系统约束的个数。 3 随机相关机会规划模型( s t o c h a s t i cd e p e n d e n c e c h a n c ep r o g r a m m i n g 简称 s d c p ) ： 在实际问题中，一个复杂的决策系统往往包含有多个事件( 任务) ，决策者希 望这些事件能尽可能的实现，l i u 口町提出了相关机会规划。其主要思想是在不确定 环境下，通过极大化随机事件成立的机会从而给出最优决策。不确定环境通常表示 7 微粒群算法在随机规划问题求解中的应用研究 为：g 。( x ，毛) 4 0 ，j = l ，2 p 其中：x 是决策向量，毛是一个随机向量，】【的实现需 要依赖毛的实现，虽然x 是决策向量，但由于毛的随机性从而导致x 的随机性。复 杂的决策系统中经常同时承担多项任务，需要满足一定的内在要求，将这些任务和 要求称为事件，记作：h 。( x ，毛) 0 ，k = l ，2 q 其中：x ，毛分别是决策向量和随机向 量，由于x 因毛具有随机性，因此事件h 。( x ，毛) 0 ，( k = l ，2 q ) 也具有随机性，机 会函数为满足事件的概率，记为：f ( x ) = p r h 。( x ，毛) 0 ，k = l ，2 q ) ，随机相关机会 单目标模型即在随机环境中极大化一个随机事件的机会函数。表示为 f 取 亿6 ， l g j ( x ，毛) 0 j = 1 ，2 p 其中：x 是决策向量，毛是一个随机向量，f ( x ) = p r h 。( x ，毛) 0 ，k = l ，2 q ) 。 相关机会目标规划可以看作是在一个复杂随机决策系统里目标规划的一个推 广。其主要思想是在决策者给定管理目标以后，在给定的优先级下极小化与此与目 标的偏差。标准的随机相关机会目标规划( d c g p ) 模型如下： m i n 圭p ，芝0 ，d ? + v ，d - ) j = l i = l s t + 订一矿= 匆，i = 1 , 2 m ( 2 7 ) g j ( 工，) o , j = l ，2 ，p ， 矿，町o ，i = 1 ，2 ，m ， 其中p ，为优先因子，表示各个目标的相对重要性，且对所有的，有j 口， p j + l 为对应优先级的第i 个目标正偏差的权重因子，为对应优先级_ ，的第f 个目标负 偏差的权重因子，为目标i 偏离目标值的正偏差，方为目标i 偏离目标值的负偏差， z 为目标约束中的实值函数，量为在不确定环境中的实值函数，6 为目标f 的目标值， ，为优先级的个数，胁为目标约束的个数，p 为系统约束的个数。不确定原理口1 是求 解相关机会规划的理论基础。 8 钾 o 幺 v i ，h 拈 厂lil 第二章随机规划和微粒群算法 2 2 微粒群算法 微粒群算法是群智能理论研究领域中的一个重要分支，所谓“群智能”指一组 相互之间可以进行直接或间接通讯的主体，能通过合作对问题进行分布求解，即一 组无智能的主体通过合作可以表现出智能行为特征。e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出微粒群算法，其基本思想是受他们早期对鸟类群体行为研究结果的启发并利 用了生物学家f r a n kh e p p n e r 的生物模型。它的进化规则与“优胜劣态，适者生存” 的g a 截然不同：它强调的是群体中个体之间信息的社会共享和协同进化。 2 2 1 生物群体行为模型 生物群体中社会行为一直受到研究者们的关注。研究者们尝试对生物群体( 比 如鸟群，鱼群) 的社会行为进行建模，并在计算机中进行仿真。r e y n o l d s h 叫提出了 b o i d s 鸟群模型，在这个模型中，r e y n o l d s 设定鸟群的行为遵循以下规则：( 1 ) 碰 撞的避免，即个体应避免和附近的同伴碰撞；( 2 ) 速度的匹配，即个体必须同附近 个体的速度保持一致；( 3 ) 向中心聚集，即个体必须飞向邻域的中心。b o i d s 模型 较为成功地展示了真实鸟群的飞行行为，并被成功地应用到图形学，虚拟现实等多 个学科领域。 h e p p n e r 提出的模型h 妇在模拟鸟群群体行为时，个体的运动基于如下规则：( 1 ) 向重要位置聚集，个体须飞向重要位置( 重要位置定义为食物源或者栖息地) ；( 2 ) 速度的调控，个体运动时应避免碰撞，因此必须适当调整自身的速度，同时个体的 速度也会因物理因素( 比如风的影响) 而相应改变；( 3 ) 信息共享，在一定距离范 围内的群体之间可以共享某些信息( 比如障碍物或者掠食者的位置) h e p p n e r 的模 型在计算机仿真中较好的展现了鸟群的同步飞行。 r e y n o l d s 和h e p p n e r 的两种鸟类模型都使用了一些较为基本的规则( 比如个 体之间的吸引和排斥) 来指导个体在空间中运动，并没有对它们进行集中的控制。 k e n n e d y 和e b e r h a r t 借鉴了这些生物群体行为模型中的一些思想，进一步提出了 微粒群算法。 2 2 2 微粒群算法基本原理 微粒群算法和遗传算法类似，是一种基于种群的优化算法。微粒群中的每一个 粒子定义为d 维空间( 待优化问题的解空间) 中的粒子，以一定的速度”( 形。，形。 形d ) 在搜索空间中飞行。算法开始时，初始化一组随机解：函，而瓢( n 为粒子的个 数) ，然后粒子根据自己在解空间中的飞行经验以及群体的飞行经验动态调整自己 9 微粒群算法在随机规划问题求解中的应用研究 位置、速度，并用适应值来评价解的优劣，选出个体极值：p = ( 只。，只：，p ，。) 与全 局极值：名= ( p g l 以：，p 印) 并记录它们的位置，再根据速度、位置更新方程 ( 2 8 ) 、( 2 9 ) 、( 2 1 0 ) 更新下一代粒子的速度、位置，通过迭代寻找最优值。 具体来讲，微粒i 在第d 维子空间的飞行速度k 。根据下式调整： r 订儿 亿9 ， 在( 2 8 ) 中，( i ) 为惯性权重( i n e r t i aw e i g h t ) ，它使微粒保持运动的惯性， 般取值为2 ，它们使每个微粒向p b e s t 和g b e s t 位置加速运动，分别起到了协调“勘 探( e x p l o r a t i o n ) 和“开发( e x p o i t a t i o n ) ”解之间的作用；r a n d ( ) 为 0 ，1 上 均匀分布的随机数，它们用来模拟自然界中群体行为的轻微扰动；是整个微粒群 的历史最优位置记录，其与当前微粒的位置之差被用于改变当前微粒向群体最优值 也被用于改变当前微粒向个体最优值运动的增量分量。 在( 2 9 ) 中，对微粒的速度k 进行了最大速度限制：如果当前对微粒的加速 将导致它的某维的速度分量k 。超过该维的最大速度限额v m a x ，则该维的速度被限制 为v m a x ，它决定了微粒在解空间的搜索精度，如果v m a x 过大，粒子容易飞过最优 解，反之，粒子容易陷入局部搜索空间而无法进行全局搜索，若问题的搜索空间限 总之，微粒的运动由上述方程共同作用。微粒的运动速度增量与其历史飞行经 验和群体飞行经验相关，并受最大飞行速度的限制。这样的运动模式可被用于各类 寻优问题的求解。在图2 1 中以二维空间为例描述了微粒根据公式( 2 8 ) 、( 2 9 ) 、 l o 第二章随机规划和微粒群算法 图2 1 微粒移动原理 2 2 3 算法参数分析 微粒群算法体现了信念的社会性和智能性行为，式( 2 8 ) 中，其第一部分为微粒 先前的速度乘一个权值进行加速，表示微粒对当前自身运动状态的信任，依据自身 的速度进行惯性运动。第二部分为“认知( c o g n i t i o n ) ”部分，考虑微粒自身的经验， 表示微粒自身的思考，第三部分为“社会( s o c i a l ) ”部分，表示微粒间的信息共享。 每部分都被加权，每部分在飞行中所占的比例的不同，决定了微粒的空间搜索能力， 所以在这三部分中的参数的选取对算法的性能显的很重要。 a 反映了微粒飞行过程中所记忆的最好位置对微粒飞行速度的影响，被称为“认 知系数”；c ，反映了整个微粒群所记忆的最好位置对微粒飞行速度的影响，称为“社 会学习系数”。如果选取的值g 相对大，即微粒的认知能力强于社会能力时，将导 致微粒在搜索区域内较难收敛，反过来，过高的社会能力将导致微粒早熟，所以， 对于控制g 和g 值对算法能有效精确的找到最优解是非常重要的。 文献【4 2 j 中指出，在算法的执行过程中，微粒的飞行速度应当受到适当的限制， 一方面保证微粒能够飞越局部极值，具有一定的全局探测能力；另一方面又能够使 得微粒以一定的速度步长逼近全局最优解。 在文献【4 3 】中，分析了速度限制和惯性权重对算法性能的影响，并且对它们不同 的取值做了试验比较，指出算法中的全局和局部探索能力的平衡主要通过惯性权重 来进行控制，但同时建议使用最大速度限制。 文献m 】中，分析了固定权重与时变权重的选择问题，并从问题依赖性、种群大 小和拓扑结构等方面详细分析了权重对算法性能的影响。通过实验，指出权重的问 题依赖性较小，随着种群的增大，其取值应适当减小，局部版本下，权重的选择具 有更大的自由度。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而 在后期有较高的开发能力以加快收敛速度。y s h i 和r c e b e r h a r t 通过试验表明国 微粒群算法在随机规划问题求解中的应用研究 随代数增加线性减少取值可得较好的试验结果旧2 1 为此可将惯性权重设为随时间线 性减少，如由0 9 至0 4 ，由1 4 至0 ，0 9 5 至0 2 等。 文献旧3 1 中，分析了惯性权重对微粒群算法收敛性能的影响，提出了几种对惯性 权重的调整策略，这些策略能够简便高效地提高算法的全局收敛性和收敛速度。 此外，种群拓扑结构对群体性能的影响也是客观存在的。相对孤立的微粒搜索 能力非常有限，因为其运动过程始终缺乏信息的实时沟通。微粒群算法常用的两种 种群拓扑结构是全局最优模式和局部最优模式。在全局最优模式中、每个个体均被 群体中发现最优解的个体所吸引，这种结构与完全连接的社会网络类似，每个个体 都有机会和群体中的其他所有个体进行比较，并模仿最优个体的活动。在局部最优 模式中，每个个体只被与其直接相连的k 个个体构成的邻域中的最优个体所影响。 前者与后者相比能够更快的收敛到最优解，但同时会增加收敛于局部极小的概率 h 们。此外，种群初始化和种群规模设置也会对算法性能产生一定的影响，不过在这 方面的研究成果还很少。目前比较常用的种群初始化方法是随机生成微粒的初始速 度和位置。在种群规模选择方面，还没有任何确切的原则，因为其对具体问题模型 的依赖性比较明显。 2 2 4p s o 算法的设计步骤 ( 1 ) 确定问题的表示方案( 编码方案) ：类似其它进化算法，p s o 算法在求解 问题时，首先应先将问题的解从解空间映射到具有某种结构的表示空间， 即用特定的码串表示问题的解。目前算法大多采用实数向量的编码方法。 将p s o 算法应用于离散特征的问题对象的求解，也是该领域内的一个研 究重点。 ( 2 ) 确定优化问题的评价函数：在求解过程中，借助于适应值来评价解的质 量。因此在求解问题时，必须根据问题的具体特征，选取适当的目标函 数或费用函数来计算适应度。适应度是唯一能够反映并引导优化过程不 断进行的参量。 ( 3 ) 选取控制参数：p s o 算法的控制参数，通常包括微粒群的规模( 微粒的 数目) 、算法的最大代数、惯性系数、认知参数、社会参数及其它一些 辅助参数等。针对不同的算法模型，选取适当的控制参数，直接影响算 法的优化性能。 ( 4 ) 设计微粒的飞行模型：在p s o 算法中，最关键的操作是如何确定微粒的 速度。由于微粒是由多维向量来描述的，故相应的微粒的飞行速度也表 1 2 第二章随机规划和微粒群算法 示为一个多维向量。在飞行过程中，微粒借助于自身的记忆与社会共享 信息，沿着每一分量方向动态地调整自己的飞行速度与方向。 ( 5 ) 确定算法的终止准则：与进化算法一样，p s o 算法中最常用的终止准则 是预先设定一个最大的飞行代数，或者是当搜索过程中解的适应度在连 续多少代后不再发生明显改进时终止算法。 ( 6 ) 编程上机运行：根据所设计的算法结构编程，并进行具体优化问题的求 解。通过所获得问题的解的质量，可以验证算法的有效性、准确性与可 靠性。 2 2 5 微粒群算法的流程 s t e p l ：依照初始化过程，对微粒群的随机位置和速度进行初始设定，每个微粒 的r 设为其初始位置，r 中的最好值设为只； s t e p 2 ：根据定义的适应值，计算每个微粒的适应值； s t e p 3 ：对于每个微粒，根据微粒的适应值与该微粒历史最好位置的适应值相比 较，求微粒的历史最好位置； s t e p 4 ：将全局最好位置的适应值与每个微粒的历史最好位置的适应值相比较， 求微粒群的全局最好值； s t e p 5 ：根据进化方程进化每个微粒的速度和位置； s t e p 6 ：判断终止条件是否满足：如果不满足，返回s t e p 2 ；否则算法结束。 2 2 6 微粒群算法与遗传算法的比较 微粒群算法与遗传算法都是进化计算方法。大多数进化计算技术都是用同样的 过程； ( 1 ) 群体随机初始化； ( 2 ) 计算群体的每一个体的适应值( f i t n e s sv a l u e ) 。通常适应值与最优解关联； ( 3 ) 群体按个体适应值进行复制； ( 4 ) 如果终止条件满足，就停止，返回最优个体；否则转步骤( 2 ) 。 从以上步骤，可以看到微粒群算法和遗传算法有很多共同之处：两者都是随机 初始化种群而且都使用适应值来评价个体的优劣程度并根据得到的适应值来进行 一定的随机搜索。其区别主要表现在以下方面： 首先，在进化算子上，g a 采用遗传操作算子如交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 。 p s o 算法是通过对速度的修改来完成进化和搜索的。从某种意义上讲，p s o 算法的搜 索比g a 更具随机性，因此，更不容易落入局部最优。 1 3 微粒群算法在随机规划问题求解中的应用研究 其次，与遗传算法比较，p s o 算法的信息共享机制是很不同的。在遗传算法中， 染色体( c h r o m o s o m e s ) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域 移动。在p s o 算法中，只有个体极值或全局极值给出信息给其他的微粒，这是单向 的信息流动，整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大 多数的情况下，所有的粒子可能更快的收敛于最优解。此外，微粒群算法基本不受 问题峰数增加的影响，受问题维数的影响也很小m j 。 第三，在微粒群算法中，微粒所具有的“记忆”特性，使得它们通过“自我 学习和向“同伴”学习，使下一代能从上一代继承更多的信息，从而可在较短时间 内找到最优解。 1 4 第三章随机仿真 第三章随机仿真 随机仿真也称为m o n t ec a r l o 仿真、统计试验方法【2 】【4 7 】等，是随机系统建模中 刻画抽样实验的一门技术，它主要依据概率分布对随机变量进行抽样，从而为系统 决策提供依据或对系统决策进行检验。虽然它只给出统计估计而非精确结果，且应 用其研究问题需要花费大量的计算时间，然而对那些无法用解析方法处理的复杂问 题，它也许是唯一能够获得问题答案的方法，该方法已被应用到许多领域中。 3 1 随机数的产生 随机数的产生技术是随机仿真的基础，对于大多数常用分布，通常用直接产生 法产生，下面给出一些常用概率分布的随机数产生方法。 1 均匀分布u ( a ，b ) 设随机变量x 服从 a ，b 上的均匀分布，其概率密度函数为： f 击，a x b f ( x ) = ( 3 1 ) l o ，其它， 记为u ( a ，b ) ，其中a 和b 是给定的实数，且a o ) 的指数分布其概率密度函数为 厂古e 吖加，若o x f i x ) = ( 3 2 ) l o ，其它， 记为e x p ( 卢) ，其均值、方差分别卢，卢2 。产生服从指数分布的随机数的 过程如下： s t e p l ：产生服从u ( 0 ，1 ) 的随机数u s t e p 2 ：返回一卢i n ( u ) 3 正态分布n ( u ，仃2 ) 设随机变量x 服从正态分布，其概率密度函数为 微粒群算法在随机规划问题求解中的应用研究 f 【x ) 2 赤e x p 一警】 一 x ， ( 3 3 ) 记为n ( p ，仃2 ) ，其中p 为均值，仃2 为方差产生服从正态分