·50 智能系统学报 第2卷 程.需要补充的是，在场不存在（即“零场"”）的情况 从算法的实际操作角度讲，算法经过有限时间 下，粒子彼此独立，无相互作用，所以粒子群中的个 截断后，全局优化性能会有明显的差别，向全局最优 体在不受限空间中的运动也会呈现出发散的趋势 点收敛速度快的算法性能更优异.集聚性过强的算 例如随机运动是弥散性的一种体现方式，也是随机 法往往会因为空间探索不足而陷入局部极值甚至更 优化算法相比于大多数确定性方法可能具有全局收 糟，所以弥散性在算法的构造中也具有重要意义，因 敛性的根本原因」 为它的存在使算法具有较强的空间探索能力从而摆 由于引力和斥力的形式多样，所以从形式角度 脱局部极值，这也是很多学者对优化算法改进的一 出发为二者做统一的定量分析比较困难.为了形成 个主要方式2.28J 较为直观的理解，后面将以“万有引力”为例对集聚 事实上，无论是仿生还是拟物，它们都有一个共 性与弥散性进行分析 同特点—模仿的对象具有弥散性或集聚性.具有 2.2集聚性和弥散性与寻优算法的关系 弥散性质的对象或过程往往能与算法的遍历性全 定理任何算法实现全局优化的一个充要条件 局优化性能)要求建立对应关系，而具有集聚性质的 为：至少存在一个个体x(),它与全局最优位置x 对象或过程则往往能与算法的收敛性（局部收敛性） 组成的二元群体{x(),x`}在演化中是一个绝对 要求建立对应关系（实际上由定义可知集聚性的内 集聚性主导过程 涵比收敛性更广).完善的算法在结构体制中同时具 证明：由绝对集聚性主导过程的定义可知： 有弥散性与集聚性，将这2种矛盾的机制融合，并在 一定程度上使二者达到一定的平衡.以模拟退火算 limo(=0im4x,W·xy2=0台 法为例，保优策略具有集聚性，它引导分析集聚到较 limx(w=x∴ 优点所在的局部区域中，而温控策略和状态接受机 需要说明的是，优化的最终结果往往取最后一 制则具有弥散性，把分析分散到其他区域中，减小遗 代群体中最优个体对应的取值，所以只要存在一个 漏最优点的概率.从自然现象中探求有助于优化的 个体不管具体是哪一个)满足趋于全局最优点的条 机理，就是根据寻优的基本原理从自然界中具有弥 件，就足以保证算法收敛到全局最优点如果任何个 散性或集聚性的现象中找到与寻优过程相似的特 体都不能趋于全局最优点，则算法显然不能实现全 征、挖掘规律、提取机制.一般而言，只具有集聚性的 局收敛.从本质上讲，这个定理是全局收敛性的另一 算法不一定能收敛到全局最优点或局部最优点，但 种描述，但是它从集聚性角度指出了算法全局收敛 是引入一定的弥散性后都能在一定程度上改善其全 的重要原则一“与最优点的位置建立并保持直接 局优化性能.而且自然界中具有集聚性或弥散性的 的关系”，这一原则称为保优原则（也称为基本原 过程或现象都可以经过改造后用于优化算法的改进 则).如果不采用这一原则，算法将无法保证全局收 或直接构造新型算法，如最近有学者分别提出了基 敛性或局部收敛性.因为当不采用此原则时，在比较 于野草繁殖扩张的优化算法B?和基于宇宙爆炸· 坍缩的优化算法1，尤其是文献[39]中的爆炸和坍 非最优个体和全局最优个体并进行保留时，接受最 缩子过程可以分别体现出弥散性与集聚性的意义和 优个体的概率小于1（设第n次比较时最优保留概 作用 率为P.),即使演化过程中某一次比较时最优个体 2.3集聚性与弥散性的实例分析 被确定性地保留下来，后续的演化也会以一定的概 下面以一个典型的具有集聚性和弥散性特征的 率将其随机淘汰掉，这是自然进化中体现出的规律， 过程为例分析“集聚性和弥散性”与寻优原理的对应 但是在优化中给算法带来的却是不利的影响.这是 关系.假设二维平面上有n个具有质量且体积可忽 因为，算法最终找到最优点的概率可以表示为 略的粒子可作质点研究)，只受彼此间的万有引力 P=limpa.(n→og (3) 作用.给定初始状态，包括初速度和初始位移，求经 式中：a。为第n次比较时群体中全局最优个体的比 过时间1后各粒子的位置 例.只有1imPn(n→cg=1和lima.(n→cg=1同时 简单情况下研究2个质点的运动规律，系统可 成立，才能保证算法实现全局最优化.对于大多数非 以由下列方程表示： 保优算法而言，limo(n→网<1，所以有P<1,因 cGm△stl didt.(4) 而无法保证算法实现全局最优化 s1(t=s01+ o1d1+ 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net程. 需要补充的是 ,在场不存在 (即“零场”) 的情况 下 ,粒子彼此独立 ,无相互作用 ,所以粒子群中的个 体在不受限空间中的运动也会呈现出发散的趋势. 例如随机运动是弥散性的一种体现方式 ,也是随机 优化算法相比于大多数确定性方法可能具有全局收 敛性的根本原因. 由于引力和斥力的形式多样 ,所以从形式角度 出发为二者做统一的定量分析比较困难. 为了形成 较为直观的理解 ,后面将以“万有引力”为例对集聚 性与弥散性进行分析. 212 集聚性和弥散性与寻优算法的关系 定理 任何算法实现全局优化的一个充要条件 为 :至少存在一个个体 xi ( t) ,它与全局最优位置 x 3 组成的二元群体{ xi ( tk ) , x 3 } 在演化中是一个绝对 集聚性主导过程. 证明 :由绝对集聚性主导过程的定义可知 : limt →∞ σ( t) = 0 Ζ limt →∞ 1 4 ( xi ( t) - x 3 ) 2 = 0 Ζ limt →∞ xi ( t) = x 3 . 需要说明的是 ,优化的最终结果往往取最后一 代群体中最优个体对应的取值 ,所以只要存在一个 个体(不管具体是哪一个) 满足趋于全局最优点的条 件 ,就足以保证算法收敛到全局最优点. 如果任何个 体都不能趋于全局最优点 ,则算法显然不能实现全 局收敛. 从本质上讲 ,这个定理是全局收敛性的另一 种描述 ,但是它从集聚性角度指出了算法全局收敛 的重要原则 ———“与最优点的位置建立并保持直接 的关系”, 这一原则称为保优原则 (也称为基本原 则) . 如果不采用这一原则 ,算法将无法保证全局收 敛性或局部收敛性. 因为当不采用此原则时 ,在比较 非最优个体和全局最优个体并进行保留时 ,接受最 优个体的概率小于 1 (设第 n 次比较时最优保留概 率为ρn ) ,即使演化过程中某一次比较时最优个体 被确定性地保留下来 ,后续的演化也会以一定的概 率将其随机淘汰掉 ,这是自然进化中体现出的规律 , 但是在优化中给算法带来的却是不利的影响. 这是 因为 ,算法最终找到最优点的概率可以表示为 P = limρnαn ( n → ∞) . (3) 式中 :αn 为第 n 次比较时群体中全局最优个体的比 例. 只有 limρn ( n →∞) = 1 和limαn ( n →∞) = 1 同时 成立 ,才能保证算法实现全局最优化. 对于大多数非 保优算法而言 ,limρn ( n →∞) < 1 ,所以有 P < 1 ,因 而无法保证算法实现全局最优化. 从算法的实际操作角度讲 ,算法经过有限时间 截断后 ,全局优化性能会有明显的差别 ,向全局最优 点收敛速度快的算法性能更优异. 集聚性过强的算 法往往会因为空间探索不足而陷入局部极值甚至更 糟 ,所以弥散性在算法的构造中也具有重要意义 ,因 为它的存在使算法具有较强的空间探索能力从而摆 脱局部极值 ,这也是很多学者对优化算法改进的一 个主要方式[27 - 28 ] . 事实上 ,无论是仿生还是拟物 ,它们都有一个共 同特点 ———模仿的对象具有弥散性或集聚性. 具有 弥散性质的对象或过程往往能与算法的遍历性 (全 局优化性能) 要求建立对应关系 ,而具有集聚性质的 对象或过程则往往能与算法的收敛性(局部收敛性) 要求建立对应关系 (实际上由定义可知集聚性的内 涵比收敛性更广) . 完善的算法在结构体制中同时具 有弥散性与集聚性 ,将这 2 种矛盾的机制融合 ,并在 一定程度上使二者达到一定的平衡. 以模拟退火算 法为例 ,保优策略具有集聚性 ,它引导分析集聚到较 优点所在的局部区域中 ,而温控策略和状态接受机 制则具有弥散性 ,把分析分散到其他区域中 ,减小遗 漏最优点的概率. 从自然现象中探求有助于优化的 机理 ,就是根据寻优的基本原理从自然界中具有弥 散性或集聚性的现象中找到与寻优过程相似的特 征、挖掘规律、提取机制. 一般而言 ,只具有集聚性的 算法不一定能收敛到全局最优点或局部最优点 ,但 是引入一定的弥散性后都能在一定程度上改善其全 局优化性能. 而且自然界中具有集聚性或弥散性的 过程或现象都可以经过改造后用于优化算法的改进 或直接构造新型算法 ,如最近有学者分别提出了基 于野草繁殖扩张的优化算法[38 ] 和基于宇宙爆炸 - 坍缩的优化算法[39 ] ,尤其是文献[39 ]中的爆炸和坍 缩子过程可以分别体现出弥散性与集聚性的意义和 作用. 213 集聚性与弥散性的实例分析 下面以一个典型的具有集聚性和弥散性特征的 过程为例分析“集聚性和弥散性”与寻优原理的对应 关系. 假设二维平面上有 n 个具有质量且体积可忽 略的粒子(可作质点研究) ,只受彼此间的万有引力 作用 ,给定初始状态 ,包括初速度和初始位移 ,求经 过时间 t 后各粒子的位置. 简单情况下研究 2 个质点的运动规律 ,系统可 以由下列方程表示 : s1 ( t) = s01 +∫ t 0 v01 dt +∫ t 0∫ t 0 Gm2Δs( t) | Δs( t) | 3 dtdt , (4) · 05 · 智 能 系 统 学 报 第 2 卷