第2卷第2期 智能系统学报 Vol.2 Na2 2007年4月 CAAI Transactions on Intelligent Systems Apr.2007 关于智能优化方法的集聚性与弥散性问题 陈杰，辛斌，窦丽华 (北京理工大学信息科学技术学院，北京100081) 摘要：在简要叙述智能优化方法中机制产生的原理和方式的基础上，引入了智能优化算法所应具有的2种基本属 性集聚性和弥散性.描述了二者与算法收敛性的关系，指出了二者对于分析和构造算法的重要性，并结合实例 进行了分析.最后根据算法的集聚性与弥散性，从算法群体进化角度研究了算法中的机制融合方法并结合实例进行 了说明」 关键词：智能优化方法；集聚性与弥散性；机制融合：算法进化 中图分类号：TP18文献标识码：A文章编号：16734785(2007)02004809 Centralization and decentralization of intelligent optimization CHEN Jie,XIN Bin ,DOU Li-hua (School of Information Science and Technology,Beijing Institute of Technology,Beijing 100081,China) Abstract On the basis of a brief analysis of principles and means for the generation of mechanisms in intelli- gent optimization,centralization and decentralization,that are basic properties of intelligent optimization, are introduced.The relationship between these two properties and convergence is described.The signifi- cance of these two properties to analysis and construction of algorithms is proposed.Finally,using an ex- ample based on the centralization and decentralization of intelligent optimization,the mechanism combina- tion of algorithm is explored from the point of view of population evolution.The practical examples are given. Key words :intelligent optimization;centralization and decentralization;mechanism combination;algorithm evolution 随着20世纪80年代计算智能的兴起，智能优 收敛的原始算法川做出改进使其全局收敛或局 化方法作为优化方法的一个新的分支得到了飞速发 部收敛.其中文献[12-17]对SA进行了一系列改 展.目前关于智能优化方法的定义尚无明确的结论， 进，文献[18-27]从不同角度出发对GA进行了各 但是涉及自然机理和生物智能的各种“模拟”型优化 种改进，具体的改进方式如小生境技术.0]、编码 方法大多属于智能优化方法的研究范畴，这些方法 方式2、种群规模控制221、单亲遗传231、引入混沌 包括模拟退火算法(SA)山、遗传算法(GA)I、免疫 机制2]、多种群并行计算2)、结合量子计算261等； 算法(IA)BI、蚁群算法(ACO)、粒子群算法 文献[27-32]也从相似的角度对PS0进行了改进 (PSO))、思维进化算法6、差分进化算法)等，这 其中包括缩放策略27.2、引入选择算子29)、多种群 些基本方法源于不同的思想，性能上也各有千秋.关 协同o01、参数时变控制3等.文献[32·33]则对 于它们的基本理论研究包括稳定性、收敛性和快速 DE进行了改进.改进的方法各式各样，其中具有代 性等，不同的学者们从马尔可夫链8.)、压缩映射定 表性的一种是多机制协调方法（混合型方法），相应 理1等角度对这些算法进行了收敛性分析，并对不 的改进型算法包括GASAI4)、GA PSO!35)、SAP- SO36]、IAGA川等.虽然各种算法自身的性质都得 收稿日期：20061013. 基金项目：因家自然科学基金资助项目(60374069) 到了较好的研究，但是目前缺乏统一性的理论来解 释具有何种特征的自然过程或现象可以借鉴从而产 C 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
收稿日期 :2006210213. 基金项目 :国家自然科学基金资助项目(60374069) 第 2 卷第 2 期 智 能 系 统 学 报 Vol. 2 №. 2 2007 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2007 关于智能优化方法的集聚性与弥散性问题 陈 杰 ,辛 斌 ,窦丽华 (北京理工大学 信息科学技术学院 ,北京 100081) 摘 要 :在简要叙述智能优化方法中机制产生的原理和方式的基础上 ,引入了智能优化算法所应具有的 2 种基本属 性 ———集聚性和弥散性. 描述了二者与算法收敛性的关系 ,指出了二者对于分析和构造算法的重要性 ,并结合实例 进行了分析. 最后根据算法的集聚性与弥散性 ,从算法群体进化角度研究了算法中的机制融合方法并结合实例进行 了说明. 关键词 :智能优化方法 ;集聚性与弥散性 ;机制融合 ;算法进化 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0220048209 Centralization and decentralization of intelligent optimization CH EN Jie ,XIN Bin ,DOU Li2hua (School of Information Science and Technology , Beijing Institute of Technology , Beijing 100081 , China) Abstract :On t he basis of a brief analysis of principles and means for the generation of mechanisms in intelli2 gent optimization , centralization and decentralization , t hat are basic properties of intelligent optimization , are introduced. The relationship between t hese two properties and convergence is described. The signifi2 cance of these two p roperties to analysis and construction of algorithms is propo sed. Finally , using an ex2 ample based on the centralization and decentralization of intelligent optimization , the mechanism combina2 tion of algorit hm is explored from t he point of view of pop ulation evolution. The practical examples are given. Keywords :intelligent optimization ; centralization and decentralization ; mechanism combination ; algorit hm evolution 随着 20 世纪 80 年代计算智能的兴起 ,智能优 化方法作为优化方法的一个新的分支得到了飞速发 展. 目前关于智能优化方法的定义尚无明确的结论 , 但是涉及自然机理和生物智能的各种“模拟”型优化 方法大多属于智能优化方法的研究范畴 ,这些方法 包括模拟退火算法(SA) [1 ] 、遗传算法( GA) [2 ] 、免疫 算法 ( IA ) [3 ] 、蚁 群 算 法 ( ACO ) [ 4 ] 、粒 子 群 算 法 (PSO) [ 5 ] 、思维进化算法[6 ] 、差分进化算法[7 ] 等 ,这 些基本方法源于不同的思想 ,性能上也各有千秋. 关 于它们的基本理论研究包括稳定性、收敛性和快速 性等 ,不同的学者们从马尔可夫链[8 - 9 ] 、压缩映射定 理[10 ]等角度对这些算法进行了收敛性分析 ,并对不 收敛的原始算法[9 - 11 ] 做出改进使其全局收敛或局 部收敛. 其中文献[ 12 - 17 ]对 SA 进行了一系列改 进 ;文献[18 - 27 ]从不同角度出发对 GA 进行了各 种改进 ,具体的改进方式如小生境技术[18 - 20 ] 、编码 方式[21 ] 、种群规模控制[22 ] 、单亲遗传[23 ] 、引入混沌 机制[24 ] 、多种群并行计算[ 25 ] 、结合量子计算[26 ] 等 ; 文献[ 27 - 32 ]也从相似的角度对 PSO 进行了改进 , 其中包括缩放策略[27 - 28 ] 、引入选择算子[29 ] 、多种群 协同[30 ] 、参数时变控制[31 ] 等. 文献 [ 32 - 33 ]则对 DE 进行了改进. 改进的方法各式各样 ,其中具有代 表性的一种是多机制协调方法 (混合型方法) ,相应 的改进型 算法包括 GASA [34 ] 、GAPSO [ 35 ] 、SA P2 SO [36 ] 、IA GA [37 ] 等. 虽然各种算法自身的性质都得 到了较好的研究 ,但是目前缺乏统一性的理论来解 释具有何种特征的自然过程或现象可以借鉴从而产
第2期 陈杰，等：关于智能优化方法的集聚性与弥散性问题 ·49· 生新的性能优异的优化算法，以及怎样才能更好更 化的机制形成新的思想方法.ACO和PSO都是对 快地向自然学习、向环境学习.从算法的集聚性与弥 群体行为的模仿，而另一种群体演化方法—遗传 散性出发来分析和理解各种算法可以得到较为直观 算法则是对群体演化过程的模拟.拟物的典型代表 的认识，有助于吸取自然界中蕴含的各种优化机理 是模拟退火方法，它是一种对自然界中的系统演化 来构造新型算法.另外，作为智能优化方法研究方向 规律进行模拟的方法. 的共性规律，机制融合成为了一种趋势和规律.所以 2集聚性与弥散性的定义与分析 研究新机制产生方式的意义除了有利于产生新的思 想方法外，还有助于迅速提高己有算法的性能，产生 2.1集聚性与弥散性的定义 性能优异的混合算法，这实质上是一个优化算法的 设x1,2,xN为算法每次迭代产生的N个 优化或进化问题 个体，N表示每一代的个体数目，固定或可变.设x 和o()分别表示群体的平均位置和位置方差，表示 1智能优化方法中的机制产生 如下： N(0 1.1寻优基本原理 X= (1) 1)全局收敛性：由遍历性保证.算法的全局收敛 N(0 性针对任意可寻优对象或函数而言，对象和函数的 0()= wt fo 多样性和复杂性使得算法只有保证具有可以遍历所 算法的集聚性与弥散性可以基于群体的统计特 有点的能力时才能够确保随着算法的进行可以找到 性定义 全局最优值 1)集聚性：群体的位置方差o()随时间递减的 2)收敛性与快速性：分别由搜索空间的压缩及 性质称为集聚性.这是一种由某种引力场的作用使 压缩效率保证.搜索必定具有未知性，否则搜索失去 位于场中的粒子受到引力作用而表现出的向群体中 意义.好的算法能够相对迅速地定位到最优值所在 心聚集的性质，它的直接表现是大多数个体到群体 的区域，缩小搜索范围，减少在非最优点上的时间耗 中心的距离随时间增长呈现出缩小的趋势，从而导 费.在最优点位于压缩区域的前提下，搜索区域压缩 致局部空间粒子密集.它的本质是引力作用 得越小，算法的收敛速度越快，但是由于对象的复杂 2)弥散性：群体的位置方差o()随时间递增的 性和未知性，使得压缩不能保证前提成立，所以压缩 性质称为弥散性.这是一种由某种斥力场的作用使 过大反而容易丢失最优点 位于场中的粒子受到斥力作用而表现出的群体离心 3)矛盾原理：遍历性与快速性是一对矛盾.算法 扩张的性质，它的直接表现是大多数个体到群体中 不具有遍历性就无法从理论上保证算法的全局收敛 心的距离随时间增长呈现出增长的趋势.从而导致 性，不具有快速性，实用价值就会大大降低，尤其是 空间中粒子稀疏 在求解复杂非线性问题时.因此完善的算法中应至 由于集聚性与弥散性强调的都是一种单调演 少能够分离出2种机制，分别保证遍历性和快速性. 化，所以并未包含所有可能的演化模式.由集聚性的 1.2拟物与仿生 定义可知集聚性过程的方差极限存在，但是极限不 纵观各种现代最优化方法不难发现它们的思想 一定等于零.特别地，当1imo()=0(t·网时，称相 大多来源于自然规律，自然界中存在很多自主优化 应的集聚性为绝对集聚性.弥散性过程的方差极限 的现象挖掘其隐含的规律可以在算法中引进新的 有可能存在，当方差极限存在时称其为有界弥散性 机制，对于研究最优化问题具有重要意义.以观察和 否则为无界弥散性.较为复杂的情况是非单调情况， 思考为主要方式挖掘某种自然现象与优化问题的内 这种情况中存在引力和斥力2种作用力，二者此消 在联系，找到它们之间的相似性与联系，促进了各种彼长共同控制着过程的演化.对于这种情形，由系统 新思想方法的产生.仿生包括模仿个体智能或模仿 的初态和末态可以判断演化到当前时刻2种作用的 群体智能2种基本方式.个体智能的模仿，如模仿 强弱关系.如果末态方差比初态方差小，则说明在引 人，从人搜索目标的方法中挖掘规律；群体智能的模 斥力的较量中，引力占有优势，相反则斥力占有优 仿，如蚁群算法和粒子群算法分别是对蚂蚁和鸟类 势.方差极限不存在的演化过程为弥散性主导过程 群体的活动行为进行了简单的模拟，从中提取出优 方差极限为零的演化过程称为绝对集聚性主导过 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
生新的性能优异的优化算法 ,以及怎样才能更好更 快地向自然学习、向环境学习. 从算法的集聚性与弥 散性出发来分析和理解各种算法可以得到较为直观 的认识 ,有助于吸取自然界中蕴含的各种优化机理 来构造新型算法. 另外 ,作为智能优化方法研究方向 的共性规律 ,机制融合成为了一种趋势和规律. 所以 研究新机制产生方式的意义除了有利于产生新的思 想方法外 ,还有助于迅速提高已有算法的性能 ,产生 性能优异的混合算法 ,这实质上是一个优化算法的 优化或进化问题. 1 智能优化方法中的机制产生 111 寻优基本原理 1) 全局收敛性 :由遍历性保证. 算法的全局收敛 性针对任意可寻优对象或函数而言 ,对象和函数的 多样性和复杂性使得算法只有保证具有可以遍历所 有点的能力时才能够确保随着算法的进行可以找到 全局最优值. 2) 收敛性与快速性 :分别由搜索空间的压缩及 压缩效率保证. 搜索必定具有未知性 ,否则搜索失去 意义. 好的算法能够相对迅速地定位到最优值所在 的区域 ,缩小搜索范围 ,减少在非最优点上的时间耗 费. 在最优点位于压缩区域的前提下 ,搜索区域压缩 得越小 ,算法的收敛速度越快 ,但是由于对象的复杂 性和未知性 ,使得压缩不能保证前提成立 ,所以压缩 过大反而容易丢失最优点. 3) 矛盾原理 :遍历性与快速性是一对矛盾. 算法 不具有遍历性就无法从理论上保证算法的全局收敛 性 ;不具有快速性 ,实用价值就会大大降低 ,尤其是 在求解复杂非线性问题时. 因此完善的算法中应至 少能够分离出 2 种机制 ,分别保证遍历性和快速性. 112 拟物与仿生 纵观各种现代最优化方法不难发现它们的思想 大多来源于自然规律 ,自然界中存在很多自主优化 的现象 ,挖掘其隐含的规律可以在算法中引进新的 机制 ,对于研究最优化问题具有重要意义. 以观察和 思考为主要方式挖掘某种自然现象与优化问题的内 在联系 ,找到它们之间的相似性与联系 ,促进了各种 新思想方法的产生. 仿生包括模仿个体智能或模仿 群体智能 2 种基本方式. 个体智能的模仿 ,如模仿 人 ,从人搜索目标的方法中挖掘规律 ;群体智能的模 仿 ,如蚁群算法和粒子群算法分别是对蚂蚁和鸟类 群体的活动行为进行了简单的模拟 ,从中提取出优 化的机制形成新的思想方法. ACO 和 PSO 都是对 群体行为的模仿 ,而另一种群体演化方法 ———遗传 算法则是对群体演化过程的模拟. 拟物的典型代表 是模拟退火方法 ,它是一种对自然界中的系统演化 规律进行模拟的方法. 2 集聚性与弥散性的定义与分析 211 集聚性与弥散性的定义 设 x1 , x2 , …, x N 为算法每次迭代产生的 N 个 个体 , N 表示每一代的个体数目 ,固定或可变. 设 x 和σ( t) 分别表示群体的平均位置和位置方差 ,表示 如下 : x = 1 N ( t) ∑ N ( t) i = 1 xi ( t) , (1) σ( t) = 1 N ( t) ∑ N ( t) i =1 xi ( t) - x 2 . 算法的集聚性与弥散性可以基于群体的统计特 性定义. 1) 集聚性 :群体的位置方差σ( t) 随时间递减的 性质称为集聚性. 这是一种由某种引力场的作用使 位于场中的粒子受到引力作用而表现出的向群体中 心聚集的性质 ,它的直接表现是大多数个体到群体 中心的距离随时间增长呈现出缩小的趋势 ,从而导 致局部空间粒子密集. 它的本质是引力作用. 2) 弥散性 :群体的位置方差σ( t) 随时间递增的 性质称为弥散性. 这是一种由某种斥力场的作用使 位于场中的粒子受到斥力作用而表现出的群体离心 扩张的性质 ,它的直接表现是大多数个体到群体中 心的距离随时间增长呈现出增长的趋势 ,从而导致 空间中粒子稀疏. 由于集聚性与弥散性强调的都是一种单调演 化 ,所以并未包含所有可能的演化模式. 由集聚性的 定义可知集聚性过程的方差极限存在 ,但是极限不 一定等于零. 特别地 ,当limσ( t) = 0 ( t →∞) 时 ,称相 应的集聚性为绝对集聚性. 弥散性过程的方差极限 有可能存在 ,当方差极限存在时称其为有界弥散性 , 否则为无界弥散性. 较为复杂的情况是非单调情况 , 这种情况中存在引力和斥力 2 种作用力 ,二者此消 彼长共同控制着过程的演化. 对于这种情形 ,由系统 的初态和末态可以判断演化到当前时刻 2 种作用的 强弱关系. 如果末态方差比初态方差小 ,则说明在引 斥力的较量中 ,引力占有优势 , 相反则斥力占有优 势. 方差极限不存在的演化过程为弥散性主导过程. 方差极限为零的演化过程称为绝对集聚性主导过 第 2 期 陈 杰 ,等 :关于智能优化方法的集聚性与弥散性问题 · 94 ·
·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 卷
第2期 陈杰，等：关于智能优化方法的集聚性与弥散性问题 ·51· (W=如+md+ 'rGm△sdd,(5) 间的演化一定会体现出集聚特性，当粒子数相对较 gJ△s(3 多时，系统的外在表现往往是个体的无规则运动和 △s()=2(·3() 6) 随时间增长显现出的集聚特征， 式中：1为时间；o1、2为第1个和第2个粒子的初 将引力计算器去掉，则各子系统独立，粒子维持 速度：012为第1个和第2个粒子的初始位移：m、 原速度状态运动.而将引力计算器改为斥力计算器， 为第1个和第2个粒子的位移：△s为两粒子的位 则系统的外在表现为随时间增长显现出的弥散特 移差；G为万有引力常数：m、m为第1个和第2个 征，这种弥散性使粒子能够扩散到更为广阔的空间 粒子的质量 区域中.PSO方法可以从这个模型中得到一定的解 二者组成的系统可以由图1表示 释，其核心的迭代公式为 v格=w·v克+a.rand·(psd-xa)+ a·randp·(pia-xa), 7) x=点+ (8) 式中：k为迭代次数：w为惯性权值，一般取值范围 为(-1，)；a、a为加速度因子，Clerks5/建议取值 (1 为0.72,9 rand和randgd0,l)内的随机数：pa为第 k次迭代时总体最优位置的第d维分量；p临为第k 次迭代时第ⅰ个粒子运动历史中自身的最优位置的 图1两粒子运动规律示意图 第d维分量：x为第k次迭代时第1个粒子位置的 Fig I Sketch map of movement law of two particles 第d维分量：为第k次迭代时第i个粒子速度的 该系统主要由二阶积分器和引力计算器（主要 第d维量。 完成粒子间相对位移和加速度的计算)组成，是一个 与多粒子运动模型相同的是，PS0模型的位移 典型的双环反馈系统.当初始条件确定后，系统按照 也由速度累加（积分）求得，而速度的变化也与相对 固定的轨迹运行.系统运行的状态由初始状态唯一 位移有关，但是相对位移的参考点有2个，一是群最 决定.将粒子数扩展到n个，系统的框图如图2所 优点P则，二是各粒子运动过程中的最优点Pa.所以 示 PSO模型与上述多粒子运动模型的主要区别在于 PS0模型中系统结构的中心不是力场a(),而是群 最优点，同时各粒子运动过程中的最优点也参与控 制 图2粒子群运动的控制结构 Fig 2 Structure of movement control of particles 这是一个以引力计算器为核心构成的星形结 构.引力计算器接受来自各子系统提供的信息，完成 数据的交互与处理，并将加速度反馈给各子系统.各 图3标准PSO引力示意图 子系统都是单环反馈系统.该结构的复杂性主要由 Fig 3 Sketch map of gravitation in PSO 交互性造成的高度耦合引起，这种交互使系统的整 如图3所示，图中最右边的点是当前群最优点， 体性能由其核心—引力计算器决定，只要各粒子 与其相连的点是上一代的群最优点，其连接线表示 初始状态不超越引力束缚的边界，尽管单个粒子的 的是系统演化的主方向.小圆圈表示各粒子运动过 运动可能非常复杂，但由于引力场的存在，群体随时 程中的最优点.群最优点之外的其他点同时受到群 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
s2 ( t) = s02 +∫ t 0 v02 dt +∫ t 0∫ t 0 Gm1Δs( t) | Δs( t) | 3 dtdt , (5) Δs( t) = s2 ( t) - s1 ( t) . (6) 式中 :t 为时间; v01 、v02 为第 1 个和第 2 个粒子的初 速度;s01 、s02为第 1 个和第 2 个粒子的初始位移;s1 、 s2 为第 1 个和第 2 个粒子的位移;Δs 为两粒子的位 移差; G为万有引力常数; m1 、m2 为第 1 个和第 2 个 粒子的质量. 二者组成的系统可以由图 1 表示. 图 1 两粒子运动规律示意图 Fig11 Sketch map of movement law of two particles 该系统主要由二阶积分器和引力计算器 (主要 完成粒子间相对位移和加速度的计算) 组成 ,是一个 典型的双环反馈系统. 当初始条件确定后 ,系统按照 固定的轨迹运行. 系统运行的状态由初始状态唯一 决定. 将粒子数扩展到 n 个 ,系统的框图如图 2 所 示. 图 2 粒子群运动的控制结构 Fig1 2 Structure of movement control of particles 这是一个以引力计算器为核心构成的星形结 构. 引力计算器接受来自各子系统提供的信息 ,完成 数据的交互与处理 ,并将加速度反馈给各子系统. 各 子系统都是单环反馈系统. 该结构的复杂性主要由 交互性造成的高度耦合引起 ,这种交互使系统的整 体性能由其核心 ———引力计算器决定 ,只要各粒子 初始状态不超越引力束缚的边界 ,尽管单个粒子的 运动可能非常复杂 ,但由于引力场的存在 ,群体随时 间的演化一定会体现出集聚特性 ,当粒子数相对较 多时 ,系统的外在表现往往是个体的无规则运动和 随时间增长显现出的集聚特征. 将引力计算器去掉 ,则各子系统独立 ,粒子维持 原速度状态运动. 而将引力计算器改为斥力计算器 , 则系统的外在表现为随时间增长显现出的弥散特 征 ,这种弥散性使粒子能够扩散到更为广阔的空间 区域中. PSO 方法可以从这个模型中得到一定的解 释 ,其核心的迭代公式为 v k+1 id = w ·v k id + c1 ·randid ·( p k g d - x k id ) + c2 ·randpd ·( p k id - x k id ) , (7) x k+1 id = x k id + v k+1 id . (8) 式中 : k 为迭代次数; w 为惯性权值 ,一般取值范围 为( - 1 , 1) ; c1 、c2 为加速度因子 ,Clerk [55 ] 建议取值 为 0172 ,9randid和 randgd (0 ,1) 内的随机数; p k gd为第 k 次迭代时总体最优位置的第 d 维分量; p k id 为第 k 次迭代时第 i 个粒子运动历史中自身的最优位置的 第 d 维分量; x k id为第 k 次迭代时第 i 个粒子位置的 第 d 维分量; v k id为第 k 次迭代时第 i 个粒子速度的 第 d 维量。 与多粒子运动模型相同的是 ,PSO 模型的位移 也由速度累加(积分) 求得 ,而速度的变化也与相对 位移有关 ,但是相对位移的参考点有 2 个 ,一是群最 优点 pgd ,二是各粒子运动过程中的最优点 pid . 所以 PSO 模型与上述多粒子运动模型的主要区别在于 PSO 模型中系统结构的中心不是力场 a( t) ,而是群 最优点 ,同时各粒子运动过程中的最优点也参与控 制. 图 3 标准 PSO 引力示意图 Fig13 Sketch map of gravitation in PSO 如图 3 所示 ,图中最右边的点是当前群最优点 , 与其相连的点是上一代的群最优点 ,其连接线表示 的是系统演化的主方向. 小圆圈表示各粒子运动过 程中的最优点. 群最优点之外的其他点同时受到群 第 2 期 陈 杰 ,等 :关于智能优化方法的集聚性与弥散性问题 · 15 ·
·52 智能系统学报 第2卷 最优点和自身运动过程中的最优点产生的2种“场” 制融合一定能产生比2种算法更好的新算法，生物 的“吲引力作用”，所以当速度控制在“引力束缚作用” 种群中对应的进化规律正是如此.但是从协调学的 之内时，系统演化的最终结果会使各粒子向群最优 角度分析，各种不同算法往往都有独立的思想体系 点集聚，从而使该算法具有收敛性.同时容易看到的 和有别于其他方法的优缺点，研究不同算法机制融 是：尽管随机数的引入使PS0有一定的弥散性，但 合的目的在于发挥各种算法独有的优势，使各种算 是基于式(4)、(5)的PS0缺乏一种充足的弥散机 法机制协调、优势互补，进而获得一种“组合优势” 制，在某些情况中会陷入局部极值从而难于实现全 研究机制融合的方法关键是根据寻优的基本原 局最优.在PS0中加入一种可产生遍历性的弥散机 理找到不同算法的优势所在和缺陷所在.找到优势 制后，就可以保证PS0的全局收敛性，如BPSO21 产生的本源，利用一种方法的优势去弥补另一种方 更为简单的方法是将全局随机搜索方法与PSO混 法的缺陷，反之亦然.根据算法的集聚性与弥散性原 合，则随机搜索产生的子序列可以保证算法总体的 理以及算法进化原理，机制融合应当遵循互补原则， 全局收敛性a,,而PS0则相当于局部搜索方法，接 如果一种算法具有较好的弥散性而集聚性（快速性） 受全局随机搜索方法提供的最优信息，由于PS0知 不够好（如标准模拟退火算法、标准混沌算法、蒙特 识利用能力较强，所以令其负责较小范围的快速搜 卡罗方法等)，收敛速度较慢，则可以与集聚性较好 索.从无限迭代的角度讲，全局随机搜索法与任何其 的算法（如搜索空间渐缩法、粒子群算法等）融合，反 他优化方法结合都可以保证算法的全局收敛性，但 之亦然 是由于全局随机搜索方法收敛缓慢，所以混合算法 3.2机制融合的方法 的收敛速度往往取决于与全局随机搜索法结合的另 机制融合主要有2种方法：一是与纯数学理论 外一种方法 结合，二是与其他智能优化方法中的机制融合.第 3智能优化方法中的机制融合方法 一种方法在于利用优化问题求解的数学理论，如传 统的优化方法虽然不适于求解全局最优化问题，但 3.1机制融合的原理 是大多数全局最优化问题经过一定分析后最终可 在GA方法产生后产生了GASA方法B4],将2 以转化为局部优化问题，这样就可以发挥传统优化 种方法的机制有机地结合起来.PS0提出后又产生 方法在收敛速度方面的优势.下面以GA和PSO 了SA PSOU6、GA PSO351,在COA的基础上又产 的融合为例分析算法融合的原理与方法.融合类似 生了COASA1421、COA GA)、COAPSO]等混合 于一种化学反应，反应生成新的结构，新结构分为 型算法.DE与SA、ACO、PSO结合分别产生了 并行、串行和嵌入3种基本类型.相比而言，PS0的 SADE45]、ACODE61、PSODE47),IA与GA结合 集聚性较强，而GA的弥散性较强，融合过程如图 产生了IA GA37),量子计算(QC)与GA、PSO结合 4所示 产生了QGA41、QPSO91,此外还有SA与单纯形 GA PSO 法o1、爬山法等算法的结合，GA与模式搜索 随机因子 随机因子 融合 法2I结合，DE与Powell方向集法的结合[]，在两 变卑交配度制 ⊕ 双引力控制 两结合之外还出现了更多方法的结合，如SA与TS 选择] 选择 (禁忌搜索)、梯度下降法三者的结合5.各种新算 GAPSO: 班机因子 GAPSO 法的提出呈现出一个共同规律：它们都迅速促进了 变园厦制 随机因子 选挥 新的混合型算法的产生，而且混合型算法往往比原 废克交配复制风力控制 ⊕ 始算法具有更好的性能.把算法与生物个体建立对 随机因子田GAPSOn 选择 嵌入式结构 双引力控捌 应关系，算法中的机制与基因建立对应关系，各种算 绝对并行结构 选择 法组合成的算法群体也呈现出“种群进化”的规律」 串行结构 优化中的机制融合是指在同一种方法中以串 行、并行或嵌入[34的方式使用多种方法的机制，通 图4GA与PSO的融合示意图 过交互协调寻优.这种方法与遗传算法中的交叉操 Fig 4 Sketch map of the combination of GA and PSO 作相似.目前没有理论能够证明2种不同算法的机 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
最优点和自身运动过程中的最优点产生的 2 种“场” 的“引力作用”,所以当速度控制在“引力束缚作用” 之内时 ,系统演化的最终结果会使各粒子向群最优 点集聚 ,从而使该算法具有收敛性. 同时容易看到的 是 :尽管随机数的引入使 PSO 有一定的弥散性 ,但 是基于式 (4) 、(5) 的 PSO 缺乏一种充足的弥散机 制 ,在某些情况中会陷入局部极值从而难于实现全 局最优. 在 PSO 中加入一种可产生遍历性的弥散机 制后 ,就可以保证 PSO 的全局收敛性 ,如 BPSO [27 ] . 更为简单的方法是将全局随机搜索方法与 PSO 混 合 ,则随机搜索产生的子序列可以保证算法总体的 全局收敛性[40 ] ,而 PSO 则相当于局部搜索方法 ,接 受全局随机搜索方法提供的最优信息 ,由于 PSO 知 识利用能力较强 ,所以令其负责较小范围的快速搜 索. 从无限迭代的角度讲 ,全局随机搜索法与任何其 他优化方法结合都可以保证算法的全局收敛性 ,但 是由于全局随机搜索方法收敛缓慢 ,所以混合算法 的收敛速度往往取决于与全局随机搜索法结合的另 外一种方法. 3 智能优化方法中的机制融合方法 311 机制融合的原理 在 GA 方法产生后产生了 GASA 方法[34 ] ,将 2 种方法的机制有机地结合起来. PSO 提出后又产生 了 SAPSO [36 ] 、GAPSO [35 ] ,在 COA [41 ]的基础上又产 生了 COASA [42 ] 、COA GA [43 ] 、COAPSO [44 ] 等混合 型算法. DE 与 SA 、ACO、PSO 结合分别产生了 SADE [45 ] 、ACODE [46 ] 、PSODE [47 ] , IA 与 GA 结合 产生了 IA GA [37 ] ,量子计算 (QC) 与 GA 、PSO 结合 产生了 Q GA [48 ] 、Q PSO [49 ] ,此外还有 SA 与单纯形 法[50 ] 、爬山法[51 ] 等算法的结合 , GA 与模式搜索 法[52 ]结合 ,DE 与 Powell 方向集法的结合[53 ] ,在两 两结合之外还出现了更多方法的结合 ,如 SA 与 TS (禁忌搜索) 、梯度下降法三者的结合[54 ] . 各种新算 法的提出呈现出一个共同规律 :它们都迅速促进了 新的混合型算法的产生 ,而且混合型算法往往比原 始算法具有更好的性能. 把算法与生物个体建立对 应关系 ,算法中的机制与基因建立对应关系 ,各种算 法组合成的算法群体也呈现出“种群进化”的规律. 优化中的机制融合是指在同一种方法中以串 行、并行或嵌入[34 ] 的方式使用多种方法的机制 ,通 过交互协调寻优. 这种方法与遗传算法中的交叉操 作相似. 目前没有理论能够证明 2 种不同算法的机 制融合一定能产生比 2 种算法更好的新算法 ,生物 种群中对应的进化规律正是如此. 但是从协调学的 角度分析 ,各种不同算法往往都有独立的思想体系 和有别于其他方法的优缺点 ,研究不同算法机制融 合的目的在于发挥各种算法独有的优势 ,使各种算 法机制协调、优势互补 ,进而获得一种“组合优势”. 研究机制融合的方法关键是根据寻优的基本原 理找到不同算法的优势所在和缺陷所在. 找到优势 产生的本源 ,利用一种方法的优势去弥补另一种方 法的缺陷 ,反之亦然. 根据算法的集聚性与弥散性原 理以及算法进化原理 ,机制融合应当遵循互补原则 , 如果一种算法具有较好的弥散性而集聚性(快速性) 不够好(如标准模拟退火算法、标准混沌算法、蒙特 卡罗方法等) ,收敛速度较慢 ,则可以与集聚性较好 的算法(如搜索空间渐缩法、粒子群算法等) 融合 ,反 之亦然. 312 机制融合的方法 机制融合主要有 2 种方法 :一是与纯数学理论 结合 ,二是与其他智能优化方法中的机制融合. 第 一种方法在于利用优化问题求解的数学理论 ,如传 统的优化方法虽然不适于求解全局最优化问题 ,但 是大多数全局最优化问题经过一定分析后最终可 以转化为局部优化问题 ,这样就可以发挥传统优化 方法在收敛速度方面的优势. 下面以 GA 和 PSO 的融合为例分析算法融合的原理与方法. 融合类似 于一种化学反应 ,反应生成新的结构 ,新结构分为 并行、串行和嵌入 3 种基本类型. 相比而言 ,PSO 的 集聚性较强 ,而 GA 的弥散性较强 ,融合过程如图 4 所示. 图 4 GA 与 PSO 的融合示意图 Fig14 Sketch map of the combination of GA and PSO · 25 · 智 能 系 统 学 报 第 2 卷