·280· 智能系统学报 第3卷 现了PSO算法对这一大类连续空间的随机规划问 行经验动态调整自己位置速度，并用适应值来评价 题的求解 解的优劣，选出Pea个体极值)与Gt佺局极值) 并记录它们的位置，再根据速度、位置更新方程 1随机期望值模型 (1)、(2)、(3)更新下一代粒子的速度、位置，通过 一般地，随机期望值模型可表示为 迭代寻找最优值.P9O算法的数学描述为 max E[f(x.)1. Vi =0 XV +q Xrand()X(P-Xid)+ stE[gxξ)J≤0，j=1,2.…p. G Xrand()X(Pgd-Xi). (D 式中：x、分别是决策向量和随机向量，f(x)为目 标函数，g(x,)为一组随机约束函数，j=1,2, Va =Vmxx,if V Vmaxi gE是期望值算子 (2) Va =Vmax,if Va <Vmax 2 随机仿真 Xu =Xu +V (3) 式中：ω为惯性权重，它使微粒保持运动的惯性，使 随机仿真也叫随机模拟或Monte Carlo模拟， 其有能力探索新的区域：q、Q为正的加速度常数， 主要是依据概率分布来对随机变量进行抽样，从而 通常取值为2，它们使每个微粒向Pe和G.e位置加 为系统决策提供依据或对系统决策进行检验.虽然 速运动，分别起到了协调“勘探和“开发解之间的 它只给出统计估计而非精确结果，且应用其研究问 作用：rand()为[0.1止均匀分布的随机数，它们用 题需要花费大量的计算时间，然而它的确是处理解 来模拟自然界中群体行为的轻微扰动：P、P分别 析方法行不通的复杂问题的有效工具，该技术己被 为个体极值、全局极值的第d维分量：在式(2中对 应用到许多领域中.针对本文的需要，下面给出随机 微粒的最大速度进行了最大限制：如果当前对微粒 仿真的期望值估计算法 的加速将导致它的某维的速度分量'超过该维的 设为定义在概率空间2，A,P)上的n维随 最大速度限额Vmx,则该维的速度被限制为Vmax,它 机向量，￡R”→R为可测函数，则f)为随机变量. 决定了微粒在解空间的搜索精度，如果'm过大，粒 利用随机仿真计算E[f)的步骤如下： 子容易飞过最优解，反之，粒子容易陷入局部搜索空 算法1：随机仿真算法之期望值估计算法： 间而无法进行全局搜索，若问题的搜索空间限制在 1)置L=0: [-尤，Xx内，则可设定mx=k化x,0≤k≤16 2)根据概率测度Pr从Q中产生样本o: 3)L-L+f5@): 4随机仿真与PSO算法相结合的随 4)重复2)和3)共N次 机期望值模型算法 5)E[f)1=LN. 在利用P9O算法求解随机期望值模型问题时 3微粒群算法 其核心是对随机函数进行计算，这显然可以利用随 微粒群算法是最新的群智能算法，它由Eberhart 机仿真的方法进行，它主要体现在为了检验解的可 和Kennedy于I995年正式提出仞，其基本思想是受他 行性、估计目标函数的适应值上 们早期对鸟类群体行为的研究结果的启发并利用了生 随机仿真与P9O算法相结合的求解随机期望 物学家Frank Heppner的生物模型.它的进化规则与 值模型算法具体步骤描述如下： 优胜劣态，适者生存的GA截然不同它强调的是群 1)在d维问题空间上对微粒群进行初始化：设 体中个体之间信息的社会共享和协同进化， 定群体规模为pop size,在决策向量x的可行域中产 微粒群中的每一个粒子定义为d维空间待优 生一随机数，利用随机仿真的期望值估计算法计算 化问题的解空间)中的粒子，以一定的速度V,(Wa, E[g(x)併检验该随机数的可行性卿判断x是 V2,Va在搜索空间中飞行.算法开始时，初始化 否满足E[g(x)J≤0)，重复该过程pop size次，从 一组随机解(x,,,,N为粒子的个数，然后 而得到pop size个初始可行的微粒：x,=(x1,xa, 粒子根据自己在解空间中的飞行经验以及群体的飞 xa),i=L,2,popsize,然后再对速度等进行初始 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net现了 PSO算法对这一大类连续空间的随机规划问 题的求解. 1 随机期望值模型 一般地 ,随机期望值模型可表示为 max E[ f ( x,ξ) ], s. t. E[ gj ( x,ξ) ] ≤ 0, j = 1, 2, …, p . 式中 : x、ξ分别是决策向量和随机向量 , f ( x,ξ)为目 标函数 , gj ( x,ξ)为一组随机约束函数 , j = 1, 2, …, p; E是期望值算子. 2 随机仿真 随机仿真也叫随机模拟或 Monte Carlo模拟 , 主要是依据概率分布来对随机变量进行抽样 ,从而 为系统决策提供依据或对系统决策进行检验. 虽然 它只给出统计估计而非精确结果 ,且应用其研究问 题需要花费大量的计算时间 ,然而它的确是处理解 析方法行不通的复杂问题的有效工具 ,该技术已被 应用到许多领域中. 针对本文的需要 ,下面给出随机 仿真的期望值估计算法. 设 ξ为定义在概率空间 (Ω, A, Pr)上的 n维随 机向量 , f: R n → R为可测函数 ,则 f (ξ)为随机变量. 利用随机仿真计算 E[ f (ξ) ]的步骤如下 : 算法 1:随机仿真算法之期望值估计算法 : 1)置 L = 0; 2)根据概率测度 Pr,从 Ω中产生样本 ω; 3) L←L + f (ξ(ω) ) ; 4)重复 2)和 3) 共 N 次; 5) E[ f (ξ) ] =L /N. 3 微粒群算法 微粒群算法是最新的群智能算法,它由 Eberhart 和 Kennedy于 1995年正式提出 [5 ] ,其基本思想是受他 们早期对鸟类群体行为的研究结果的启发并利用了生 物学家 Frank Heppner的生物模型. 它的进化规则与 “优胜劣态,适者生存 ”的 GA截然不同:它强调的是群 体中个体之间信息的社会共享和协同进化. 微粒群中的每一个粒子定义为 d维空间 (待优 化问题的解空间 )中的粒子 ,以一定的速度 Vi (Vi1 , Vi2 , …, Vid )在搜索空间中飞行. 算法开始时 ,初始化 一组随机解 ( x1 , x2 , …, xN , N 为粒子的个数 ) ,然后 粒子根据自己在解空间中的飞行经验以及群体的飞 行经验动态调整自己位置、速度 ,并用适应值来评价 解的优劣 ,选出 Pbest (个体极值 )与 Gbest (全局极值 ) 并记录它们的位置 , 再根据速度、位置更新方程 (1)、(2)、(3)更新下一代粒子的速度、位置 ,通过 迭代寻找最优值. PSO算法的数学描述为 Vid =ω ×Vid + c1 ×rand ( ) ×( Pid - Xid ) + c2 ×rand ( ) ×( Pgd - Xid ). (1) Vid = Vmax , if Vid > Vmax; Vid = - Vmax , if Vid < - Vmax . (2) Xid = Xid +Vid . (3) 式中 :ω为惯性权重 ,它使微粒保持运动的惯性 ,使 其有能力探索新的区域; c1、c2 为正的加速度常数 , 通常取值为 2,它们使每个微粒向 Pbe st和 Gbest位置加 速运动 ,分别起到了协调“勘探 ”和“开发 ”解之间的 作用; rand ( )为 [0, 1 ]上均匀分布的随机数 ,它们用 来模拟自然界中群体行为的轻微扰动; Pid、Pgd分别 为个体极值、全局极值的第 d维分量;在式 ( 2)中对 微粒的最大速度进行了最大限制 :如果当前对微粒 的加速将导致它的某维的速度分量 Vid超过该维的 最大速度限额 Vmax , 则该维的速度被限制为 Vmax ,它 决定了微粒在解空间的搜索精度 ,如果 Vmax过大 ,粒 子容易飞过最优解 ,反之 ,粒子容易陷入局部搜索空 间而无法进行全局搜索 ,若问题的搜索空间限制在 [ - Xmax , Xmax ]内,则可设定 Vmax = kXmax , 0≤k≤1 [6 ] . 4 随机仿真与 PSO 算法相结合的随 机期望值模型算法 在利用 PSO算法求解随机期望值模型问题时 , 其核心是对随机函数进行计算 ,这显然可以利用随 机仿真的方法进行 ,它主要体现在为了检验解的可 行性、估计目标函数的适应值上. 随机仿真与 PSO 算法相结合的求解随机期望 值模型算法具体步骤描述如下 : 1)在 d维问题空间上对微粒群进行初始化 :设 定群体规模为 pop size,在决策向量 x的可行域中产 生一随机数 ,利用随机仿真的期望值估计算法计算 E[ gj ( x,ξ) ]并检验该随机数的可行性 (即判断 x是 否满足 E[ gj ( x,ξ) ]≤0) ,重复该过程 pop size次 ,从 而得到 pop size个初始可行的微粒 : xi = ( xi1 , xi2 , …, xid ) , i = 1, 2, …, pop size,然后再对速度等进行初始 ·280· 智 能 系 统 学 报 第 3卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net