1、 引言 微粒群算法（PSO）的进化方程为： ))(())(()() 1( 2211 txprctxprctwvtv igiiii ++=+ (1a) ) 1()() 1(++=+tvtxtx iii (1b) 其中表示第i个微粒所经历过的最好位置，表示所有微粒所经历过的最好位置， w、 c i p g p 1、 c2为 常数，均匀分布的随机数 1 , 0, 21 rr PSO算法自提出以来， 其收敛性问题一直是研究的重要方面 早期的研究大多采用代数方法， 分析、保持不变时，PSO算法进化方程的收敛性条件 g p i p 12，即PSO算法收敛时参数w、c 1、 c2应 满 足 的 条 件 理 论 上 已 证 明 3 ： 假 设、在 进 化 中 保 持 不 变 ， 则 当 g p i p 2412 2 <+ww）（（ 21 +=， 111 rc=， 222 rc=）时，PSO算法的收敛 于与的加权中心，即 )(txi g p i p gi i pp tx 21 )( + 而在实际上，、在进化过程中根据其 适应值而不断更新，可以证明 g p i p 2，只要参数满足上述条件，PSO算法的收敛是完全保证的，但收 敛的全局最优性或局部最优性则无法保证。
有关PSO算法的全局收敛性研究，大多针对典型优化问题进行仿真实验研究，给出全局最优 性的实验结果 F.Solis和R.Wets对随机优化算法提出了其全局收敛须满足的条件4， Frans Van Den Bergh博士利用该条件对基本PSO算法和保证收敛的PSO算法（GCPSO）的全局收敛性和局部收 敛性进行了研究5，指出基本PSO算法不能保证全局或局部收敛，而GCPSO则属于局部收敛 本文在对基本 PSO 算法进行分析的基础上，提出了一种能够保证以概率 1 全局收敛的 PSO 算法变型，并利用 F.Solis 和 R.Wets 的研究结果对其全局收敛性进行了证明最后以典型优化问 题的实例仿真对该算法进行了验证 2、 PSO 算法的变型 在（1a） 、 （1b）所描述的基本 PSO 算法中，当 w=0 时，微粒的飞行速度只取决于微粒的当 前位置、历史最好位置和微粒群的历史最好位置，速度本身无记忆性这样，对于 位于全局最好位置的微粒将保持静止， 而其它微粒则趋向它本身最好位置和全局最好位置 的加权中心也就是说，微粒群将收缩到当前的全局最好位置，更像一个局部算法；当 w0 时， 使得微粒具有了扩展搜索空间的趋势， 即具有一定的全局搜索能力。
w 越大， 全局搜索能力越强 )(txi i p g p i p g p 根据上述分析，当 w=0 时， （1a） 、 （1b）描述的进化方程为 ))(())(()() 1( 2211 txprctxprctxtx igiiii ++=+ （2） 与基本 PSO 算法相比， （2）式描述的进化方程使得全局搜索能力减弱，而局部搜索能力加强 2 同时，当时，第 j 个微粒将停止进化为了改善（2）式的全局搜索能力，可保 留作为微粒群的历史最好位置，而在搜索空间 S 重新随机产生微粒 j 的位置，其它 微粒 i 以（2）式进化产生（ij）,则 gj t j ppx== )( g p) 1( +txj ) 1( +txi ) 1( +=txp jj ， ++ +< = ))1(()(),1( ))1(()(, txfpftx txfpfp p iii iii i (3) , 1| )(minarg ==Sipfp ig )(),(minarg ggg pfpfp= （4） 若，则随机产生的微粒 j 处于历史最好位置，无法按（2）式进化，继续在搜索空间 S 随机产生，其它微粒在更新、后按（2）式进化；若 jg pp = g p i p jg pp ，且未更新，则所有微粒 均按（2）式进化；若，且已更新，即存在 kj,使得 g p jg pp g p gkk pptx==+ ) 1(，则微粒 k 停止进化，在搜索空间 S 重新随机产生，其余微粒在更新、后按（2）式进化。
这样在进 化的某些代，至少有一个微粒 j 满足 g p i p gjj pptx==)(，也就是说，至少有一个微粒需在 S 中重 新随机产生，这样就势必增强了全局搜索能力为了与基本 PSO 算法相区别，上述算法称之为 随机 PSO 算法（SPSO） 3、 SPSO 算法的收敛性分析 对于任意优化算法， 其收敛性分析主要包括算法所产生的解序列是否收敛、 收敛速度以及收 敛的全局最优性或局部最优性等 3.1 SPSO算法的微粒进化轨迹分析 由（2）式可得： giii pptxtx 21 )()1 () 1(++=+（5） 当、固定时，上式为一简单的线性差分方程，当 g p i p 0 )0( ii xx=时，其解为： t ii kxktx)1)(()( 0 += （6） 其中， gi pp k 21 + = （7） 3 （6）式是在假设随着t的变化而、固定不变的情况下得到的但在SPSO算法的进化过程 中，、则随时可能更新，因此， （6） 、 （7）式仅在新的更好位置产生之前有效一旦产生 新的更好位置（或者） ，微粒的运动轨迹方程将按照新的、，并将当前位置作为初 始点重新计算，也就是说（6）式中k,x g p i p g p i p g p i p g p i p i0的值重新设置。
从（6）式可以看出，当1|1|<时， （5）式所描述的进化方程线性收敛，即当时，t gi i pp tx 21 )( + 根据1|1|<，可得：20 21 <+
为了满足假设 2，规模为 S 的微粒群的样本空间的并必须包含 S，即 U S i ti MS 1 , = 其中为 t 代时微粒 i 的样本空间的支撑集对于满足 ti M ,gkj pptx==)(的微粒 j, =S而 对于其它微粒 i: ti M , ))1(( ))1(() 1( 2 1, + += txp txptxM ig iiiti 由于 2211 0 , 0cc，则为一具有顶点 ti M , 0 21 ==和 2211 ,cc==的超矩形 体，且当 )(5 . 0 |)) 1(||,) 1(|max( 21 Sdiam txpctxpc igii N 时，vUS
但这样也使得在进化的每一代均至少有一个微 5 粒由于处于微粒群的历史最好位置而停止进化，利用停止进化的微粒改善全局搜索能力是 SPSO 算法的基本思想在收敛性方面，SPSO 算法与 PSO 算法具有几乎完全相同的性质，即在参数的 一定范围内均能保证收敛于群体历史最好位置对于收敛的全局最优性，基本 PSO 算法无 法保证，而 SPSO 算法当进化代数 )(txi t时能保证依概率 1 收敛于全局最优解但是，在实际 应用中， 如何改善停止进化微粒的产生方式， 以达到在有限进化代数内搜索到全局最优解的目的 是值得研究的问题 4、 停止进化微粒的产生 为了使微粒j以较大概率位于最优点附近，可采用其它一些非群体随机优化方法进行生成， 如模拟退火方法6，遗传算法7等 （1）利用模拟退火方法产生停止进化微粒 模拟退火算法 （simulated annealing） 是基于 Mente Carlo 迭代求解策略的一种随机优化算法， 其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性 模拟退火算法在 某一出温下， 伴随温度参数的不断下降， 结合概率突跳特性在解空间中随机寻找目标函数的全局 最优解，即在局部最优解能概率性的跳出并最终趋于全局最优。
以当前代历史最好位置为初始状态，即 g p gj ptx=)(，并选择初始温度，采用下 式产生下一状态： 0 TT= +=+)() 1( txtx jj （10） 其中为扰动幅值参数，为随机变量，一般可服从柯西分布、正态分布或均匀分布计算 ，， ))(()),1(( txfftxff jjjj =+= jj ff = + =+ otherwisetx etx tx j j T j j k ),( , 1min),1( ) 1( / （11） 其中 1 , 0 j 均匀分布的随机变量 1 0 , 1 <<= + kk TT （12） （2）利用遗传算法产生停止进化微粒 停止进化微粒的产生还可以利用遗传算法在整个搜索空间进行搜索， 在给定的进化代数内得 到的最优解作为其的位置在我们的实验中，遗传算法为最优保存遗传算法，其中，杂交、变异、 选择算子分别为算术杂交、均匀性变异、转轮法选择它们分别为： A) 算术杂交算子 设和是两个父向量，结果为),...,,( 21n xxxx =),...,,( 21n yyyy =),...,,( 21n wwww =、 ，且),...,,( 21n vvvv = j 为介于 0，1 之间的随机数，则有 jjjjj yxw)1 (+= （13） 6 jjjjj xyv)1 (+= （14） B) 均匀性变异算子 设为父向量，),...,,( 21n xxxx =),...,,( 21n yyyy =为其变异结果。
均匀性变异是先在父向 量中随机选择一个分量， 假设为第 k 个， 然后， 在其定义域区间中均匀随机取一个数 来代替，即 , jj ba k x k x = = kix kix y k i k , , （15） C) 转轮法选择算子 先计算个体的相对适应值 j j f f 记为，随机生成数 j p 1 , 0r，若 jj ppprppp+++<+++ ...... 21121 （16） 则选择个体 j 为了进一步提高算法效率，我们引入了混沌随机数发生器混沌是一种普遍的非线性现象， 具有很独特的性质： （1）随机性，即混沌具有类似随机变量的杂乱表现； （2）遍历性，即混沌能 够不重复的历。