（系统工程专业论文）适合于随机优化问题的微粒群算法的研究.pdf

中文摘要 中文摘要 在管理科学、信息科学、系统科学以及工业工程等众多领域都存在着客观的或 人为的随机性，相应地存在着大量的随机优化问题。进化计算方法，如遗传算法、 进化策略、蚁群算法、微粒群算法等用于求解随机优化问题在最优性方面得到了很 好的结果，但由于其适应值估计( 随机仿真) 非常费时而限制了其实际应用。因此， 本论文研究如何在微粒群算法过程中，利用已有适应值估计的信息预测一些变量的 适应值，以减少运行随机仿真的次数，从而从总体上减少计算时间。 首先，采用广义回归神经网络作为适应值预测模型，通过对广义回归神经网络 的分析给出它与微粒群算法的结合机制、预测策略及模型更新策略，由此来决定个 体的适应值是用预测模型进行预测还是用随机仿真进行估计及何时更新预测模型， 从而提出一种将广义回归神经网络与微粒群算法相结合求解随机优化问题的智能算 法，通过实例仿真说明了该算法在保证算法性能的前提下，在适应值计算方面大大 减少了计算量从而从总体上节省了大量时间，体现了它在求解随机优化问题中优势。 其次，采用k r i g i n g 模型作为适应值预测模型，由k r i g i n g 模型与微粒群算法的结合 机制及预测策略选择部分个体的适应值进行预测，其余个体的适应值则用随机仿真 进行估计，提出一种将k r i g i n g 模型与微粒群算法相结合求解随机优化问题的算法， 为随机优化问题的处理提供了一条新的有效途径。 关键词：随机优化问题；微粒群算法；随机仿真；广义回归神经网络；k r i g i n g 模型 a b s t r a c t a b s t r a c t t h e r ei sm u c ho b je c t i v eo rm a n - m a d er a n d o m n e s smt h ef i e l d so f m a n a g e m e n ts c i e n c e ，i n f o r m a t i o ns c i e n c e ，s y s t e m ss c i e n c e ，i n d u s t r i a l e n g i n e e r i n ga n ds oo n ，w h e r eal a r g en u m b e ro fs t o c h a s t i co p t i m i z a t i o n p r o b l e m se x i s ta c c o r d i n g l y a l t h o u g he v o l u t i o n a r yc o m p u t a t i o n ( e g g e n e t i c a l g o r i t h m ，e v o l u t i o n a r ys t r a t e g y , p a r t i c l es w a r mo p t i m i z a t i o ne r e ) h a sb e e n s h o w e dt ob e p o w e r f u lg l o b a lo p t i m i z e r s f o rs t o c h a s t i c o p t i m i z a t i o n p r o b l e m s ，i th a st h ed i s a d v a n t a g eo fh i g h e rc o s tw h i c hl i m i t si t sa p p l i c a t i o n s b e c a u s ea l li n d i v i d u a l s f i t n e s si se s t i m a t e db yr a n d o ms i m u l a t i o n 。i ti s s u g g e s t e dt op r e d i c tt h ef i t n e s so fs o m ei n d i v i d u a l s ，t a k i n gt h ei n f o r m a t i o no f t h ef i t n e s st h a th a sb e e nc a l c u l a t e di n t oa c c o u n t t m sm e t h o dc a nr e d u c et h e t i m e so fr a n d o ms i m u l a t i o n ，a n da c c o r d i n g l yi tr e d u c e st h ec o m p u t i n gt i m ei n t o t a l f i r s t l y , g e n e r a l i z e dr e g r e s s i o nn e u r a ln e t w o r k ( g r n n ) i su s e da sa f i t n e s sp r e d i c t i o nm o d e la n da ni n t e l l i g e n ta l g o r i t h mc o m b i n e dg r n nw i t h p a r t i c l e s w a r mo p t i m i z a t i o ni s p r e s e n t e d i nt h i si n t e l l i g e n ta l g o r i t h m ， a c c o r d i n gt ot h ea n a l y s i so f t h eg r n n ，t h em e c h a n i s mw h i c hc o m b i n e s g r n nw i t hp a r t i c l es w a r mo p t i m i z a t i o n ，p r e d i c t i o ns t r a t e g ya n dp r e d i c t i o n m o d e lt r a i n i n ga r e p r o p o s e d ，b y w h i c hw ec a nd e c i d ew h e t h e rt h e i n d i v i d u a l sf i t n e s si sp r e d i c t e db yt h eg r n no re s t i m a t e db yr a n d o m s i m u l a t i o na n dw h e nt ou p d a t et h eg r n n r e s u l t so fs i m u l a t i o ns h o wt h a t t h ei n t e l l i g e n ta l g o r i t h mr e d u c e st h ec o m p u t a t i o n a lc o s tg r e a t l yi nt h e p r e m i s eo fp e r f o r m a n c eg u a r a n t e e d n e x t ，k r i g i n gm o d e li su s e da sa f i t n e s s p r e d i c t i o nm o d e la n dan e wa l g o r i t h mw h i c hc o m b i n e sk r i g i n gm o d e lw i t h p a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e d i nt h i sa l g o r i t h m ，a c c o r d i n gt ot h e m e c h a n i s mc o m b i n e dk r i g i n gm o d e lw i t hp a r t i c l es w a r mo p t i m i z a t i o na n d p r e d i c t i o ns t r a t e g y , s o m eo f t h ei n d i v i d u a l s f i t n e s si sp r e d i c t e da n dt h er e s ti s e s t i m a t e db yr a n d o ms i m u l a t i o n r e s u l t so fs i m u l a t i o ns h o wt h ec o r r e c t n e s s a n de f f e c t i v e n e s so ft h i sn e w a l g o r i t h m i l l 适合于随机优化问题的微粒群算法研究 k e yw o r d s ：s t o c h a s t i co p t i m i z a t i o np r o b l e m ；p a r t i c l es w a r mo p t i m i z a t i o n ； r a n d o ms i m u l a t i o n ；g e n e r a l i z e dr e g r e s s i o nn e u r a ln e t w o r k ；k r i g i n gm o d e l i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 日期：竺乏墨芝 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 导师签名： 日期： 日期： x _ 占气 第一章绪论 第一章绪论 1 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 ) 作为一种新的智能技术，它采 用基于种群的并行全局搜索策略，但不具有选择、变异等操作，仅采用简单的速度一 位置模型实现对整个空间的寻优操作。由于该算法概念简单、易于实现、优化性能 好，目前已在许多问题中得到了成功的应用，所以本文试图将p s o 算法与适应值预测 方法相结合用于解决随机优化问题。 1 2 国内外研究动态 1 2 1 适应值预测方法的研究动态 迄今为止，适应值预测方法已被广泛应用于进化计算中。 a 多项式模型 多项式模型通常称为表面响应法，是应用最广泛的一种适应值预测模型，其二 阶形式为： 1 适合于随机优化问题的微粒群算法研究 多= 风+ 卢，薯+ f l , , - l + ，+ j x , x j 1 s ” 1 s s ，s 打 ( 1 1 ) 其中系数风、卢，可用最小二乘法和梯度法进行估计【l , 3 1 。二阶多项式模型适合解决连 续、单峰问题，而多峰问题则可用多项式样条函数来解决 2 1 。 bk r i g i n g 模型 k r i g i n g 模型可看作是一个全局模型和局部偏差的结合： y ( x ) = g ( x ) + z ( x ) r 1 ，、 其中g ( x ) 为原适应值函数的全局模型，是一个关于x 的已知函数；z ( x ) 是一个期望 值为零、协方差非零的高斯随机函数，它代表偏离全局模型的局部偏差。g ( x ) 通常 是一个多项式，在很多情况下被简化为一个常数。k r i g i n g 模型中的参数可用极大似 然法来估计。在k r i g i n g 模型中只需进行少量计算便可获得估计的置信区间。然而， 随着维数的增高，其计算量会越来越大【1 1 。 高斯模型( g a u s s i a np r o c e s s e s ，g p s ) 【4 1 是一种常用的k r i g i n g 模型，它是一个给 定数据点集上的概率模型，该概率模型被用来预测新数据点上函数值的均值和标准 差。g p s 中的参数可用典型长度、噪音水平等来设置，也可用极大似然法优化得到。 由于g p s 不需要预先定义结构、拥有有意义的参数及最优化这些参数的理论框架、 能够逼近任意函数，所以比其他模型更有优势，但其计算代价比较高【2 ，5 1 。 c 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) a n n 是由大量高度互联的处理单元组成的并行分布式处理器，它具有通过学习 获取知识并解决问题的能力，且知识是分布储存在连接权中。若给予足够多的处理 单元，a n n 能逼近任何函数。通过向环境学习获取知识并改进自身性能是a n n 的 一个重要特点。一般情况下，a n n 性能的改善是按某种预定的度量通过调节自身参 数( 如权值) 而逐步达到的。误差反向传播学习算法是a n n 现在最流行的学习算法。 前馈多层感知器和径向基函数网络已被广泛应用于适应值函数估计。 多层感知器( m u l t i l a y e rp e r c e p t r o n s ，m l p ) 由三部分组成：一组感知单元( 源节 点) 组成输入层，一层或多层计算节点的隐层和一层计算节点的输出层。输入信号 在层层递进基础上前向传播通过网络。m l p 的隐节点基函数采用线性函数，它的每 个神经元模型都包括一个非线性激活函数( 一般采用s i g m o i d a l 函数或硬极限函数) 。 径向基函数网络( r a d i a lb a s i sf u n c t i o nn e t w o r k ，r b f n ) 与m l p 相比，结构更 简洁，学习速度更快。r b f n 采用距离函数( 如欧氏距离) 作为隐节点权值函数，并 使用径向基函数( r a d i a lb a s i sf u n c t i o n ，i m f )( 如高斯函数) 作为激活函数。特别 2 第一章绪论 的，r b f n 的每个隐节点都具有一个数据中心。 a n n 的主要缺点是在训练网络时产生的权值难以解释以及很难确定一个适当的 网络拓手| 、【2 ，6 ，7 8 】。 d 支持向量机 支持向量机理论是在统计学理论基础上发展起来的，它的主要优点是训练过程 中不会产生局部最小值，并且泛化的错误不依赖空间维数1 。 由于适应值预测模型的性能与所解决的实际问题有关，所以判断一个预测模型 的好坏还没有一个明确的标准，但很多文献研究表明r b f n 和g p s 的性能相对较好 1 0 ，1l ，1 2 o 适应值预测模型与进化算法的结合机制大致可以分为：( 1 ) 拓扑结构的改善 t 3 - 1 s l ；( 2 ) 初始化种群的改善陋1 9 1 ；( 3 ) 基于函数适应值的继承机制1 2 0 - 3 4 1 。第一种 方式通过引入迁移等特定算子，以提高适应值的预测准确度，但实验结果表明该策 略的效果不是很明显。而第二种方式则着眼于强化初始种群的质量，但这种策略容 易陷入局部极值。第三种策略是在算法运行过程中，动态的预测某些位置的适应值， 由于算法的随机性，因此，这种预测对于过早收敛具有一定的免疫力。而对于预测 策略而言，又分两种情况：( 1 ) 算法运行过程中，所有的适应值都预测；( 2 ) 在算 法运行的每代中，都选择部分适应值预测，而其余的适应值则使用实际的适应值， 而对于需要预测的个体的选择方式又可分为随机选择【3 5 】及代数固定选择两种。此外， 适应值预测模型的训练方法也分为两种：( 1 ) 离线训练：在预测模型用于算法之前 训练好就不再更新；( 2 ) 在线训练：在算法运行过程中，用实际的适应值来进一步 训练模型以不断更新适应值预测模型。 1 2 2 微粒群算法的研究背景和现状 微粒群算澍3 6 。3 绷是在1 9 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师 r u s s e l le b e r h a r t 受启于对鸟类群体行为的研究并利用了生物学家f r a n kh e p p n e r 的生 物群体模型而提出的一种智能算法【4 0 1 。p s o 算法同时将微粒的位置与速度模型化， 给出了一组显式的进化方程，这是p s o 算法不同于其它进化类算法的显著之处，也 是其显示出许多优良特性的关键。 基本微粒群算法的速度进化方程可以分成三个部分【4 l 】：微粒先前的速度、表示 微粒本身思考的“认知”部分及表示微粒间社会信息共享的“社会 部分。基本的 微粒群算法可分为两种基本进化模型：全局模型( g b e s t 模型) 及局部模型( l b e s t 模型) 。g b e s t 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度【4 2 1 ，但易发生过 3 适合于随机优化问题的微粒群算法研究 早收敛现象。为此，l b e s t 模型采用多吸引子代替g b e s t 模型的单一吸引子。虽然收 敛速度低于g b e s t 模型，但收敛的全局最优性明显改善。 p s o 算法常应用于复杂优化问题的求解，它最早应用于人工神经网络的训练， e n g e l b r e c h t 等【4 3 1 利用p s o 来训练神经元网络；j u a l l g 畔】将遗传算法与p s o 相结合来 设计递归模糊神经元网络；m e s s e r s c h m i d t 等【4 5 】利用基于p s o 的神经元网络来预测 t i c t a c t o eg a m e 树叶节点的状态。应用结果都显示利用p s o 设计神经元网络是一种 快速、高效并具有潜力的方法。在图像处理方面，y i n t 4 6 应用k e i l i l e d y 等的离散p s o 方法解决多边形近似问题，有效提高了多边形近似效果；p a r s o p o u l o s 等h 利用p s o 对用于放射治疗的模糊认知图的模型参数进行优化；c a o r s i 等【4 8 】利用基于p s o 的微 波图像法来确定电磁散射体的绝缘特性；w a c h o w i a k 等【4 9 j 利用结合局部搜索的混合 p s o 算法对生物医学图像进行配准。在调度问题方面，l i u 等 5 0 , 5 1 】将标准微粒群算法 扩展到离散生产调度问题，提出了针对典型流水线调度问题的一种有效混合p s o 算 法。在此基础上，结合特定问题信息，提出了解决零等待流水线调度、带有限缓冲 区的流水线调度、多目标流水线调度和加工时间随机分布的流水线调度等一系列复 杂问题的混合p s o 算法。t a s g e t i r e n 等【5 2 1 则提出置换f l o w s h o p 问题的基于可变邻域 搜索的微粒群算法。总之，p s o 算法在函数优化、约束优化、极大极小问题、多目 标优化等问题中均得到了成功的应用。在实际应用领域它己成功应用于机器人领域、 电力系统、交通运输领域、工程设计与优化领域、计算机领域、电磁学领域等【5 3 5 9 j 。 p s o 算法自提出以来，由于它概念简单、实现方便，而且容易与其它优化算法 相结合，短短十几年时间内p s o 算法已获得了很大的进展。目前主要有以下几个研 究方向：算法的改进、算法的理论基础的分析、算法的生物学基础、算法与其它优 化算法的比较和融合、算法在实际应用中的问题以及算法的应用领域的拓展。 1 3 本文的主要内容 p s o 算法具有模型简单、易于实现、收敛速度快、精度高等优点，引起了国内 外众多学者的关注，它已在各类问题的求解及应用中展现了它的特点和魅力。p s o 算法用于求解随机优化问题在最优性方面得到了很好的结果，但由于其适应值估计 ( 随机仿真) 非常费时而限制了其实际应用。因此，本文研究如何在微粒群算法过 程中，利用已有适应值估计的信息预测一些变量的适应值，以减少运行随机仿真的 次数，从而从总体上减少计算时间。本文具体研究内容为： 第二章介绍了标准p s o 算法的基本概念、基本原理、算法流程及算法的设计原 4 第一章绪论 则与步骤。然后通过与其它优化算法相比较，说明了微粒群算法所具有的优越性。 第三章采用广义回归神经网络作为适应值预测模型，通过对广义回归神经网络 的分析给出它与微粒群算法的结合机制、预测策略及模型更新策略，由此来决定个 体的适应值是用预测模型进行预测还是用随机仿真进行估计及何时更新预测模型， 从而提出一种将广义回归神经网络与微粒群算法相结合求解随机优化问题的智能算 法，通过实例仿真说明了该算法在保证算法性能的前提下，在适应值计算方面大大 减少了计算量从而从总体上节省了大量时间，体现了它在求解随机优化问题中优势。 第四章采用k r i g i n g 模型作为适应值预测模型，由k r i g i n g 模型与微粒群算法的 结合机制及预测策略选择部分个体的适应值进行预测，其余个体的适应值则用随机 仿真进行估计，提出一种将k x i g i n g 模型与微粒群算法相结合求解随机优化问题的算 法，为随机优化问题的处理提供了一条新的有效途径。 第五章对本论文工作进行了总结和展望。 5 第二章微粒群算法 第二章微粒群算法 微粒群算法是群智能理论研究领域中的一个重要分支，所谓“群智能”指一组 相互之间可以进行直接或间接通讯的主体，能通过合作对问题进行分布求解，即一 组无智能的主体通过合作可以表现出智能行为特征。e b e r h a r t 和k e n n e d y 于1 9 9 5 年 提出p s o 算法【3 6 3 7 , 3 8 , 4 ，其基本思想是受他们早期对鸟类群体行为研究结果的启发 并利用了生物学家f r a n kh e p p n e r 的生物模型。它的进化规则与“优胜劣汰，适者生 存 的遗传算法截然不同：它强调的是群体中个体之间信息的社会共享和协同进化。 2 1 标准微粒群算法 假设有如下数值优化模型： m i n f ( x ) ，x 【x 。缸，x 一】”互r ” ( 2 1 ) 设 x ，= ( xj 1 ，z ，2 ，z j 。) 为微粒，的当前位置： k = ( v j lp v 2 ，v 加) 为微粒- 的当前飞行速度； 弓= ( p 1 ，p 2 ，p 加) 为微粒7 所经历的最优位置，也就是微粒，所经历过的具有 最优适应值的位置，称为个体历史最优位置。对于最小化问题，目标函数值越小， 对应的适应值越优。 设群体中的微粒数为s ，群体中所有微粒所经历过的最优位置为r , j t ) ，称为全 局历史最优位置。 有了以上定义，标准微粒群算法的进化方程可描述为： v j t , ( t + 1 ) = z o v j 嗽( t ) + c 1 吒( p 弦( f ) 一x j 瞻( t ) ) + c 2 r 2 ( p s k ( t ) 一z 皿( f ) ) ( 2 2 ) x j k ( f + 1 ) = z 承( f ) + 秒球( f + 1 ) ( 2 3 ) 其中：下标“k ”表示微粒的第k 维，“，表示微粒j ，t 表示第t 代，w 为惯性权 重，介于0 ，1 之间，认知系数c ，与社会系数c ，称为加速度常数，通常在0 2 间取值， r , - u ( o ，1 ) ，r 2 u ( 0 ，1 ) 为两个相互独立的随机数。 从上述微粒进化方程可以看出，w 用于调节自身惯性所占的比重，g 调节微粒 飞向自身最优位置方向的步长，c ，调节微粒向群体历史最优位置飞行的步长。为了 减少在进化过程中，微粒离开搜索空间的可能性，v m 通常限定于一定范围内，即 v 承【一，z ，一】。如果问题的搜索空间限定在卜x 一，x 一】内，则可设定 = j ：( z 一，0 1 k 1 0 。 7 适合于随机优化问题的微粒群算法研究 在式( 2 2 ) 所描述的速度进化方程中，其第一部分为微粒先前的速度；其第二部 分为“认知( c o g n i t i o n ) ”部分，因为它仅考虑了微粒自身的经验，表示微粒本身的思考。 如果基本微粒群算法的速度进化方程仅包含认知部分，即 v j k ( t + 1 ) = z ) 影毋( f ) + c 1 吒( p 癣( f ) 一x 毋( f ) ) ( 2 4 ) 则其性能变差。主要原因是不同的微粒之间缺乏信息交流，即没有社会信息共享， 微粒间没有交互，使得一个规模为s 的群体等价于运行了s 个单个微粒，因而得到最 优解的概率非常小。 式( 2 2 ) 的第三部分为“社会( s o c i a l ) ”部分，表示微粒间的社会信息共享。若速度进 化方程中仅包含社会部分，即 v j k ( f + 1 ) = 加移m ( f ) + c 2 r 2 ( p s k ( f ) 一x j k ( f ) ) ( 2 5 ) 则微粒没有认知能力，也就是“只有社会( s o c i a l o n l y ) ”的模型。这样，微粒在相互作 用下，有能力到达新的搜索空间，虽然它的收敛速度比基本微粒群算法更快，但对 于复杂问题，则容易陷入局部最优点。 标准微粒群算法的初始化过程为： ( 1 ) 设定群体规模n ； ( 2 ) 对任意微粒，的任意维k 的位置分量z 诹在卜x 一，x 一】内服从均匀分布产生； ( 3 ) 对任意微粒，的任意维k 的速度分量v 承在【一v 一，1 ，一】内服从均匀分布产生； ( 4 ) 个体历史最优位置弓( o ) 取各微粒初始位置，群体最优位置b ( o ) 为适应值最优 的微粒所对应的位置。 2 2 标准微粒群算法流程 标准微粒群算法流程如图2 1 所示。 8 第二章微粒群算法 图2 - 1 标准微粒群算法流程图 f i g u r e2 - 1f l o wc h a to fs t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o n 标准微粒群算法流程如下： ( 1 ) 种群初始化：按照上述初始化过程选择，并置进化代数f 为o ； 9 n n 适合于随机优化问题的微粒群算法研究 ( 2 ) 参数初始化：设置惯性权重w 、认知系数c 。、社会系数c ：及最大速度上限1 ，一； ( 3 ) 由式( 2 2 ) 计算微粒下一代的速度； ( 4 ) 调整各微粒的速度； ( 5 ) 由式( 2 3 ) 计算微粒下一代的位置； ( 6 ) 更新个体历史最优位置及群体历史最优位置； ( 7 ) 若结束条件满足，输出得到的最优位置；否则，转步骤3 。 2 3 微粒群算法的设计原则与步骤 1 、设计p s o 算法的基本原则 ( 1 ) 适用性原则 一个算法的适用性，是指该算法所能适用问题种类，这取决于算法所需的限制 与假设。如果优化问题的性质不同，则相应的具体处理方式也不同。 ( 2 ) 可靠性原则 一个算法的可靠性，是指算法具有以适当的精度求解大多数问题的能力，即能 对大多数问题提供一定精度的解。 与其他众多的进化算法一样，p s o 同样是一种随机的优化算法，因此在求解不 同问题时，其结果具有一定的随机性与不确定性。故设计算法试验时，应尽量经过 较多样本的检验，以确定算法的可靠性。 ( 3 ) 收敛性原则 p s o 算法的收敛性是指算法能否以概率1 收敛到全局最优解，并具有一定的收 敛速度和收敛精度。通常评价算法的收敛性能，可通过比较在有限时间代内算法所 求解的精度来实现。 ( 4 ) 稳定性原则 算法的稳定性是指算法对其控制参数及问题数据的敏感程度。一个性能稳定的 算法，应该具有以下两种特性：一是对一组固定的控制参数，算法能用于较广泛的 问题求解；二是对给定的问题数据，算法的求解结果应不会随控制参数的微小扰动 而波动。 ( 5 ) 生物类比原则 微粒群算法的设计思想源于对生物群体社会行为的模拟，因此生物界中相关的 进化理论、策略、方法，均可通过类比的原则，引入到算法中以求提高算法性能。 2 、p s o 算法的设计步骤 1 0 第二章微粒群算法 ( 1 ) 确定问题的表示方案( 编码方案) 和其他的进化算法一样，p s o 算法在求解问题时，首先应将问题的解从解空间 映射到具有某种结构的表示空间，即用特定的码串表示问题的解。根据问题的特性 选择适当的编码方法，将会对算法的性能及求解结果产生直接的影响。 p s o 算法的早期研究均集中在数值优化领域中，其标准计算模型适用于具有连 续特征的问题函数，因此目前的算法大多采用实数向量的编码方案。用p s o 算法求 解具有离散特征的问题对象，正是此领域内的一个研究重点。 ( 2 ) 确定优化问题的评价函数 在求解过程中，借助于适应值来评价解的质量。因此在求解问题时，必须根据 问题的具体特性，选取适当的目标函数或费用函数来计算适应度。适应度是唯一能 够反映并引导优化过程不断进行的参量。 ( 3 ) 选取控制参数 p s o 算法的控制参数，通常包括微粒群的规模( 微粒的数目) 、算法执行的最大代 数、惯性系数、认知参数、社会参数和其他一些辅助控制参数等。针对不同的算法 模型，选取适当的控制参数，直接影响算法的优化性能。 ( 4 ) 设计微粒的飞行模型 在微粒群算法中，最关键的操作是如何确定微粒的速度。由于微粒是多维向量 来描述的，故相应的微粒的飞行速度也表示为一个多维向量。在飞行过程中，微粒 借助自身的记忆与社会信息共享，沿着每一分量方向动态地调整自己的飞行速度与 方向。 ( 5 ) 确定算法的终止准则 与其他进化算法一样，p s o 算法中最常用的终止准则是预先设定一个最大的飞 行代数，或者是当搜索过程中的解的适应度在连续多少代后不再发生明显改进时， 终止算法。 ( 6 ) 编程上机运行 根据所设计的算法结构编程，并进行具体优化问题的求解。通过所获得问题的 解的质量，可以验证算法的有效性，准确与可靠性。 2 4 与其它进化算法的比较 微粒群算法与其他进化算法，如进化规划、进化策略和遗传算法等相比，有许 多相似之处。它们都使用“种群 概念，用于表示一组解空间中的个体集合。两者 适合于随机优化问题的微粒群算法研究 都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定 的随机搜索。两个系统都不是保证一定找到最优解。如果将微粒所持有的最好位置 也看作种群的组成部分，则微粒群的每一步迭代都可以看作是一种弱化的选择机制。 在进化策略算法中，子代与父代竞争，若子代具有更好的适应值，则子代将替换父 代，而p s o 算法的进化方程式也具有与此类似的机制，其唯一的差别在于，p s o 算法 只有当粒子的当前位置与所经历的最好位置相比具有更好的适应值时，其粒子所经 历的最好位置才一会唯一地被该粒子当前的位置所替代。 微粒群算法( p s o ) 与遗传算法( g a ) 相比，还有以下异同之处： p s o 和g a 的相同点： ( 1 ) 都属于仿生算法。p s o 主要模拟鸟类觅食、人类认知等社会行为而提出；g a 主要借用生物进化中“适者生存的规律。 ( 2 ) 都属全局优化方法。在解空间都随机产生初始种群，因而算法在全局的解空 间进行搜索，且将搜索重点集中在性能高的部分。 ( 3 ) 都属随机搜索算法。p s o 中认知项和社会项前都加有随机数；而g a 的遗传操 作均属随机操作。 ( 4 ) p s o 的速度更新方程与实数编码的遗传算法的算术交又算子很类似。通常， 算术交叉算子由两个父代个体的线性组合产生两个子代个体；而在p s o 算法的速度更 新方程中，如果不考虑第一项，也就是带惯性权重的速度项，就可以将方程理解成 由两个父代个体产生一个子代个体的算术交叉运算。从另一个角度上看，同样不考 虑第一项，速度更新方程也可以看作是一个变异算子，其变异的强度大小取决于个 体最好位置和全局最好位置之间的距离，可以把个体最好位置和全局最好位置看作 父代，变异就可以看作是由两个父代到子代的变异。至于前面略去的惯性速度项， 也可以理解为一种变异的形式，其变异的大小与速度相乘的惯性因子相关，惯性因 子越接近1 ，则变异强度越小；越远离1 ，则变异强度越大。 ( 5 ) 隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体开 始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。并且由于这种并 行性，易在并行计算机上实现，以提高算法性能和效率。 ( 6 ) 根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性可 导性等。 ( 7 ) 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收 敛到最优点。 1 2 第二章微粒群算法 p s o 和g a 的不同点： ( 1 ) p s o 有记忆，好的解知识的所有粒子都保存，而g a ，以前的知识随着种群的 改变被破坏。 ( x ) p s o 具有独特的信息共享机制。g a 中，染色体之间相互共享信息，使得整个 种群比较均匀地向最优区域移动。而p s o 中的粒子仅仅通过当前搜索到最优点进行共 享信息，所以很大程度上这是一种单向信息共享机制，整个搜索更新过程是跟随当 前最优解的过程。与遗传算法比较，所有的粒子很可能更快的收敛于最优解。 ( 3 ) g a 的编码技术和遗传操作比较简单，而p s o 相对于g a ，没有交叉和变异操 作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。 ( 4 ) 在收敛性方面，g a 己经有了较成熟的收敛性分析方法，并且可对收敛速度进 行估计；而p s o 这方面的研究还比较薄弱，尽管已经有简化确定性版本的收敛性分析， 但将确定性向随机性的转化尚需进一步研究。 ( 5 ) 在应用方面，p s 0 算法主要应用于连续问题，包括神经网络训练和函数优化 等，而g a 除了连续问题之外，还可应用于离散问题，比如t s p 问题、货郎担问题、 工作车间调度等。 通常在进化类算法的分析中，人们习惯将每一步进化迭代理解为用新个体( 即 子代) 代替旧个体( 即父代) 的过程。这里，如果我们将p s o 算法的进化迭代理解 为一个自适应过程，则微粒的位置x ，( r ) 就不是被新的微粒所代替，而是根据速度向 量1 ，( f ) 进行自适应变化。这样，p s o 算法与其它进化类算法的最大不同点在于：p s o 算法在进化过程中同时保留和利用位置与速度( 即位置的变化程度) 信息，而其它 进化类算法仅保留和利用位置的信息。 另外，如果将位置进化方程看作一个变异算子，则p s o 算法与进化规划很相似。 所不同之处在于：在每一代，p s o 算法中的每个微粒只朝一些根据群体的经验认为 是好的方向飞行，而在进化规划中可通过一个随机函数变异到任何方向。也就是说， p s o 算法执行一种有“意识( c o n s c i o u s ) 的变异。从理论上讲，进化规划具有更 多的机会在优化点附近进行开发，而p s o 算法则有更多的机会更快地飞到更好解的 区域。 综上所述，p s o 算法也呈现出一些其它进化类算法所不具有的特性，特别是， 微粒群算法同时将微粒的位置与速度模型化，给出了一组显式的进化方程，是其不 同于其它进化类算法的最显著之处，也是该算法所呈现出许多优良特性的关键点。 1 3 第三章基于人工神经网络的求解随机优化问题的混合智能算法 第三章基于人工神经网络的求解随机优化问题的混合智能算法 为了寻找更有效的求解随机优化问题的算法，本章采用广义回归神经网络作为 适应值预测模型，由预测模型与p s o 算法的结合机制及预测策略选择部分个体的适 应值进行预测，其余个体的适应值则用随机仿真进行估计，提出一种将广义回归神 经网络与p s o 算法相结合求解随机优化问题的混合智能算法。 3 1 人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k , a n n ) 6 0 - 6 3 是由大量处理单元( 神经 元) 广泛互连而成的网络，其组织能够模拟生物神经系统对真实世界所做出的交互 反应。它是根植于神经科学、数学、统计学、物理学、计算机科学及工程等学科的 一种技术。由于人工神经网络具有较强的自适应性、学习能力和大规模并行计算能 力，目前已被广泛应用于各种研究及实际工程领域中，如函数逼近、模式识别、图 像处理与计算机视觉、控制与优化、预报和智能信息管理、通信、空间科学等领域。 3 1 1 神经元模型 一个神经网络由多个互连的神经元组成，人工神经网络的信息处理由神经元之 间的相互作用来实现，知识与信息的存贮表现为网络元件互连分布式的物理联系， 人工神经网络的学习和识别决定于各神经元连接权系数的动态演化过程。神经元是 神经网络的基本处理单元，一个典型的具有聆个输入的通用神经元模型如图3 1 所 示。其中j x = ( 而，恐，吒) r 为神经元输入，w = ( m ，w 29 - o - 9 以) r 为可调的输入权值， 8 为偏移信号，用于建模神经元的兴奋阂值，铭( ) 和厂( ) 分别表示神经元的基函数和 激活函数。基函数z ，( ) 是一个多输入单输出函数材= u ( x ，w ，a ) ；激活函数的一般作用 是对基函数输出u 进行“挤压 ：y = f ( u ) ，即通过非线性函数( ) 将u 变换到指定 范围内。 常用的基函数类型有线性函数、距离函数和椭圆基函数。绝大多数神经网络都 采用线性函数作为基函数，如多层感知器、h o p f i e l d 网络等。激活函数可以是线性的， 也可以是非线性的。常用的激活函数类型有硬极限函数、线性函数、饱和线性函数、 s i g m o i d a l 函数和高斯函数。高斯函数是极为重要的一类激活函数，常用于径向基函 数神经网络。高斯函数的表达式为 y = 厂( 群) = e x p ( - h 么2 ) ( 3 1 ) 1 5 适合于随机优化问题的微粒群算法研究 式中，参数6 称为高斯函数的宽度或扩展常数。6 越大，函数曲线就越平坦；反之， 6 越大，函数曲线就越陡峭。 t 屯 图3 - 1 神经元模型 f i g u r e3 - 1n e u r o nm o d e l 3 1 2 神经网络结构及工作方式 神经网络模型是一个并行和分布式的信息处理网络结构，该网络结构一般由许 多神经元组成，每个神经元有一个单一的输出，它可以连接到很多其它的神经元上， 其输入有多个连接通路，每个连接通路对应一个连接权系数。 根据连接方式，神经网络常分为两大类：没有反馈的前馈神经网络和相互结合 型神经网络。前馈神经网络由输入层、一层或多层的隐含层和输出层组成，每一层 的神经元只接受前一层神经元的输出。而相互结合型神经网络中任意两个神经元之 间都有可能连接，因此，输入信号要在神经元之间反复传递，从某一初始状态开始， 经过若干次变化，渐渐趋于某一稳定状态或进入周期振荡等其他状态。虽然目前已 有数十种神经网络模型，但常见的主要是三大类模型：前向神经网络、反馈神经网 络和自组织神经网络。 神经网络的工作过程主要分为两个阶段，一个阶段是学习期，此时各计算单元 状态不变，各连接上的权值通过学习来修改。第二阶段是工作期，此时连接权固定， 计算单元状态变化，以达到某种稳定状态。 3 ，1 3 神经网络的学习方法 通过向环境学习获取知识并改进自身性能是神经网络的一个重要特点。在一般 情况下，性能的改善是按某种预定的度量通过调节自身参数( 如权值) 逐步达到的。 学习方式有三种：监督学习、非监督学习、再励学习。监督学习方式需要外界存在 一个“教师”，他可对给定一组输入提供应有的输出结果，这组己知的输入输出数据 1 6 第三章基于人工神经网络的求解随机优化问题的混合智能算法 称为训练样本集，学习系统( 神经网络) 可根据已知输出与实际输出之间的差值( 误 差信号) 来调节系统参数。而非监督学习不存在外部教师，学习系统完全按照环境 提供数据的某些统计规律来调节自身参数或结构。再励学习介于上述两种情况之间， 外部环境对系统输出结果只给出评价信息( 奖或惩) 而不是给出正确答案，学习系 统通过强化那些受奖的动作来改善自身的性能。神经网络的学习规则有：误差纠正 学习、h e b b 学习、竞争( c o m p e t i t i v e ) 学习。 3 1 4 径向基函数神经网络 径向基函数网络( r a d i a lb a s i sf u n c t i o n n e t w o r k ,