第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 卷
第2期 陈杰,等:关于智能优化方法的集聚性与弥散性问题 ·53· 其中,PSO算法和GA算法以及新的算法均用 散,保持了相对较好的弥散性,它的弥散性使其可以 机制及其流程转换关系表示(省去了控制部分).嵌 探索到更优的点(如图中左下方所示),同时对下一 入式结构未在图中给出.GAPSO1型算法是一种绝 步的PSO进程进行指导,使之迅速集中到当前最优 对并行结构,实际上由于单台计算机执行能力的限 点所在的局部区域进行搜索分析(如图右上方所 制,这种算法目前只适于网络分布计算,而一般采用 示).同时PSO的集聚性也在引导GA的搜索过程 的是一种相对并行结构,即演化中交替地执行GA 使其相对较快地集聚.GA的弥散性与PSO的集聚 和PSO 性之间产生了一种互补优势,使其相互促进,提高了 在融合后产生的新算法的主体结构中,控制单 算法的整体性能.其他算法之间融合的方法和原理 元综合协调多种集聚和弥散过程,而且它与集聚过 与此相似,不同之处在于各种算法的内部机制有所 程以及弥散过程的信息交互量增大,控制依据的可 不同.需要补充的是,确定性算法一般只适于求解确 靠性增强,并且增强了多个过程(方法)的交互性,降 定性问题而且要求研究对象有较好的性质,如连续 低了任何一种方法的盲目性,不同的算法之间产生 性、可微性等,其快速性是与“它们利用了对象的特 了互补效应,因而有利于算法整体性能的提高.图5 殊性”紧密相关的.所以确定性方法本身不能简单地 具体说明了算法间互补的原理,该图表示采用相对 纳入算法的一般结构中己有算法通过机制融合可 并行结构的算法分析图中所示函数的最小点.如图 以互相结合生成新的算法.研究的目的在于结合具 中左上方所示,PSO的集聚性较强,分析点比GA 体的最优化研究方向探求与研究对象匹配的性能更 更快地集聚,而GA的弥散性较强,分析点相对分 优越的新算法 40 00 0.75 0.75 0.50 0.25 0 -0.25 0.25 -0.50 0.50 -0.75 07 100 0.75 075 0.50 25 .2 0 0.25 -0.50 -0.50 0.75 -0.75 图5PSO与GA之间的互补效应 Fig 5 Complementary effect between PSO and GA 交配机制,算法改进的2种主要方式就是提出新的 4 结束语 算法和对已有算法进行机制融合,文中对机制的生 最优化算法的发展是一个与生物种群进化相似 成和融合进行了论述与分析,挖掘出算法进化的原 的演化过程.各种己产生的算法组成了一个算法种 理,尤其是算法所应具备的集聚性与弥散性,体现了 群,它们之间通过机制融合等方式进行进化,但是从 智能优化方法与所对应的自然现象或过程之间的联 进化论和信息论角度讲,新的有效算法的产生更有 系,指出了可以用于优化的自然现象的基本特征,对 助于种群的进化,它使种群的性能得到突变,并带来 于新算法的产生具有指导意义.集聚性与弥散性在 更多的有用信息.对应于生物种群进化中的变异与 智能优化方法的理论统一方面的具体应用还有待进 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
其中 ,PSO 算法和 GA 算法以及新的算法均用 机制及其流程转换关系表示 (省去了控制部分) . 嵌 入式结构未在图中给出. GA PSO1 型算法是一种绝 对并行结构 ,实际上由于单台计算机执行能力的限 制 ,这种算法目前只适于网络分布计算 ,而一般采用 的是一种相对并行结构 ,即演化中交替地执行 GA 和 PSO. 在融合后产生的新算法的主体结构中 ,控制单 元综合协调多种集聚和弥散过程 ,而且它与集聚过 程以及弥散过程的信息交互量增大 ,控制依据的可 靠性增强 ,并且增强了多个过程(方法) 的交互性 ,降 低了任何一种方法的盲目性 ,不同的算法之间产生 了互补效应 ,因而有利于算法整体性能的提高. 图 5 具体说明了算法间互补的原理 ,该图表示采用相对 并行结构的算法分析图中所示函数的最小点. 如图 中左上方所示 ,PSO 的集聚性较强 ,分析点比 GA 更快地集聚 ,而 GA 的弥散性较强 ,分析点相对分 散 ,保持了相对较好的弥散性 ,它的弥散性使其可以 探索到更优的点(如图中左下方所示) ,同时对下一 步的 PSO 进程进行指导 ,使之迅速集中到当前最优 点所在的局部区域进行搜索分析 (如图右上方所 示) . 同时 PSO 的集聚性也在引导 GA 的搜索过程 , 使其相对较快地集聚. GA 的弥散性与 PSO 的集聚 性之间产生了一种互补优势 ,使其相互促进 ,提高了 算法的整体性能. 其他算法之间融合的方法和原理 与此相似 ,不同之处在于各种算法的内部机制有所 不同. 需要补充的是 ,确定性算法一般只适于求解确 定性问题而且要求研究对象有较好的性质 ,如连续 性、可微性等 ,其快速性是与“它们利用了对象的特 殊性”紧密相关的. 所以确定性方法本身不能简单地 纳入算法的一般结构中. 已有算法通过机制融合可 以互相结合生成新的算法. 研究的目的在于结合具 体的最优化研究方向探求与研究对象匹配的性能更 优越的新算法. 图 5 PSO 与 GA 之间的互补效应 Fig15 Complementary effect between PSO and GA 4 结束语 最优化算法的发展是一个与生物种群进化相似 的演化过程. 各种已产生的算法组成了一个算法种 群 ,它们之间通过机制融合等方式进行进化 ,但是从 进化论和信息论角度讲 ,新的有效算法的产生更有 助于种群的进化 ,它使种群的性能得到突变 ,并带来 更多的有用信息. 对应于生物种群进化中的变异与 交配机制 ,算法改进的 2 种主要方式就是提出新的 算法和对已有算法进行机制融合 ,文中对机制的生 成和融合进行了论述与分析 ,挖掘出算法进化的原 理 ,尤其是算法所应具备的集聚性与弥散性 ,体现了 智能优化方法与所对应的自然现象或过程之间的联 系 ,指出了可以用于优化的自然现象的基本特征 ,对 于新算法的产生具有指导意义. 集聚性与弥散性在 智能优化方法的理论统一方面的具体应用还有待进 第 2 期 陈 杰 ,等 :关于智能优化方法的集聚性与弥散性问题 · 35 ·
·54· 智能系统学报 第2卷 一步研究 2451. [13]TSALLIS C,STARIOLO D A.Generalized simulated 参考文献: annealing[J].Physica A,1996,233:395-406. [1]METROPOLIS N,ROSENBLUTH A,ROSENBLUTH [14]YE Hong,LIN Zhiping.Speed-up simulated annealing M,et al.Equation of state calculations by fast computing by parallel coordinates [J].European Journal of Opera- machines [J ]Journal of Chemical Physics,1953,21: tional Research,2006,173 59-71. 1087.1092. [15]TSOULOS I G,LA GARIS I E.GenAnneal:genetically [2]HOLLAND J H.Adaptation in natural and artificial sys- modified simulated annealing [J ]Computer Physics tems M].Ann Arbor:The University of Michigan Communication,2006,174:846-851. Press,1975. [16]WANG Ling,ZHANG Liang.Stochastic optimization [3]黄席樾,张著洪,何传江,等.现代智能算法理论及应用 using simulated annealingwith hypothesis test [J ]Ap- [M].北京:科学出版社,2005 plied Mathematics and Computation,2006,174:1329- [4]COLONI A,DORIGO M,MANIEZZO V.Distributed 1342 optimization by ant colonies[A].Proceeding of Ist Euro- [17]JI Mingjun,JIN Zhihong,TANG Huanwen.An im- pean Conference of Artificial Life [C].Paris,France, proved simulated annealing for solving the linear con- 1991 strained optimization problems[J].Applied Mathematics [5]KENNEDYJ,EBERHART R.Particle swarm optimi- and Computation,2006,183(1):251-259. zation[A].Proceeding of IEEE International Conference [18]CAVICCHIO DJ.Adaptive search using simulated evo- on Neural Networks[C].Piscataway,NJ,1995. lution[D].Michigan:University of Michigan,1970. [6]SUN Chengyi,SUN Yan,LI Junwei.Mind evolution [19]DE JONG K A.An analysis of the behavior of a class of based machine learning:framework and the implementa- genetic adaptive system[D].Michigan:University of tion [A].Proceedings of the IEEE International Confer- Michigan,1975. ence on Intelligent Engineering System[C].Vienna,Aus- [20]GOLDBERG D E,RICHARDSON J.Genetic algo- tria,1998. rithms with sharing for multimodal function optimization [7]STORN R,PRICE K.Differential evolutioma simple [A].Proceedings of the 2nd International Conference on and efficient adaptive scheme for global optimization over Genetic Algorithms [C].Hillsdale,NJ:Lawrence Erl- continuous spaces [R].TR-95-012,ICSI,March, baum,1987 1995. [21]GOLDB ERG D E.Real-coded genetic algorithms,vir- [8]GIDAS B.Nonstationary Markov chains and convergence tual alphabets and blocking[R].University of Illinois at of the annealing algorithm [J].Journal of Statistical Urbana-Champaign,Technical Report No.90001,1990. Physics,1985,39:73-131. [22 ]ARABAS J MICHAL EWICZ Z,MULA WLA J.Ga- [9]RUDOL PH G.Convergence analysis of canonical genetic VaPS-a genetic algorithm with varying population size algorithms[J ]IEEE Transactions on Neural Networks, [A].Proceedings of the 1st IEEE International Confer- 1994,5(1):96-101. ence on Evolutionary Computation[C].[s.1.]1994. 10 MICHAL EWICZ Z.Genetic algorithms data [23]李茂军,童调生.单亲遗传算法及其全局收敛性分析 structure=evolution programs[M].New York:Spring- [U].自动化学报,1999,25(1):69.73. er-Verlag,1996. LI Maojun,TONG Tiaosheng.A partheno-genetic al- [11]VAN DEN BERGH F.An analysis of particle swarm gorithm and analysis on its global convergence[J].Acta optimizers[D].Pretoria:University of Pretoria,2002. Automatica Sinca,1999,25(1):69 73. [12 ]AZIZI N,ZOL FA GHARI S.Adapative temperature [24]骆晨钟,邵惠鹤.采用混沌变异的进化算法U],控制与 control for simulated annealing:a comparative study[J ] 决策,2000,15(5):557-560. Computers Operations Research,2004,31:2439- LUO Chenzhong,SHAO Huihe.Evolutionary algo- 1994-2008 China Academic Joural Electronic Publishing House.All rights reserved.http://www.cnki.net
一步研究. 参考文献 : [1 ]METROPOL IS N , ROSENBLU TH A , ROSENBLU TH M ,et al. Equation of state calculations by fast computing machines[J ]. Journal of Chemical Physics , 1953 , 21 : 1087 - 1092. [2 ] HOLLAND J H. Adaptation in natural and artificial sys2 tems [ M ]. Ann Arbor : The University of Michigan Press , 1975. [3 ]黄席樾 , 张著洪 , 何传江 ,等. 现代智能算法理论及应用 [ M ]. 北京 :科学出版社 , 2005. [4 ]COLONI A , DORIGO M , MANIEZZO V. Distributed optimization by ant colonies[A ]. Proceeding of 1st Euro2 pean Conference of Artificial Life [ C ]. Paris , France , 1991. [5 ] KENNED Y J , EBERHART R. Particle swarm optimi2 zation[ A ]. Proceeding of IEEE International Conference on Neural Networks[C]. Piscataway , NJ ,1995. [6 ] SUN Chengyi , SUN Yan , L I J unwei. Mind evolution based machine learning : framework and the implementa2 tion [ A ]. Proceedings of the IEEE International Confer2 ence on Intelligent Engineering System[C]. Vienna ,Aus2 tria ,1998. [7 ] STORN R , PRICE K. Differential evolution2a simple and efficient adaptive scheme for global optimization over continuous spaces [ R ]. TR - 95 - 012 , ICSI , March , 1995. [ 8 ] GIDAS B. Nonstationary Markov chains and convergence of the annealing algorithm [J ]. Journal of Statistical Physics , 1985 , 39 :73 - 131. [9 ]RUDOL PH G. Convergence analysis of canonical genetic algorithms[J ]. IEEE Transactions on Neural Networks , 1994 ,5 (1) :96 - 101. [ 10 ] MICHAL EWICZ Z. Genetic algorithms + data structure = evolution programs[ M ]. New York : Spring2 er2Verlag , 1996. [11 ]VAN DEN BERGH F. An analysis of particle swarm optimizers[D]. Pretoria : University of Pretoria , 2002. [ 12 ] AZIZI N , ZOL FA GHARI S. Adapative temperature control for simulated annealing : a comparative study[J ]. Computers & Operations Research , 2004 , 31 : 2439 - 2451. [13 ] TSALL IS C , STARIOLO D A. Generalized simulated annealing[J ]. Physica A , 1996 , 233 :395 - 406. [14 ] YE Hong , L IN Zhiping. Speed2up simulated annealing by parallel coordinates [J ]. European Journal of Opera2 tional Research , 2006 , 173 :59 - 71. [ 15 ] TSOULOS I G, LA GARIS I E. GenAnneal : genetically modified simulated annealing [ J ]. Computer Physics Communication , 2006 , 174 : 846 - 851. [16 ] WAN G Ling , ZHAN G Liang. Stochastic optimization using simulated annealingwith hypothesis test [J ]. Ap2 plied Mathematics and Computation , 2006 , 174 : 1329 - 1342. [17 ]J I Mingjun , J IN Zhihong , TAN G Huanwen. An im2 proved simulated annealing for solving the linear con2 strained optimization problems[J ]. Applied Mathematics and Computation , 2006 ,183 (1) : 251 - 259. [ 18 ]CAVICCHIO D J. Adaptive search using simulated evo2 lution[D]. Michigan :University of Michigan , 1970. [ 19 ]DE JON G K A. An analysis of the behavior of a class of genetic adaptive system [ D ]. Michigan : University of Michigan , 1975. [ 20 ] GOLDBERG D E , RICHARDSON J. Genetic algo2 rithms with sharing for multimodal function optimization [A ]. Proceedings of the 2nd International Conference on Genetic Algorithms [ C ]. Hillsdale , NJ : Lawrence Erl2 baum ,1987. [21 ] GOLDBERG D E. Real2coded genetic algorithms , vir2 tual alphabets and blocking [ R ]. University of Illinois at Urbana2Champaign , Technical Report No. 90001 , 1990. [22 ]ARABAS J , MICHAL EWICZ Z , MULAWLA J. Ga2 VaPS2a genetic algorithm with varying population size [ A ]. Proceedings of the 1st IEEE International Confer2 ence on Evolutionary Computation[C]. [s. l. ] , 1994. [23 ]李茂军 ,童调生. 单亲遗传算法及其全局收敛性分析 [J ]. 自动化学报 , 1999 , 25 (1) :69 - 73. L I Maojun , TON G Tiaosheng. A partheno - genetic al2 gorithm and analysis on its global convergence[J ]. Acta Automatica Sinca , 1999 ,25 (1) :69 - 73. [24 ]骆晨钟 ,邵惠鹤. 采用混沌变异的进化算法[J ]. 控制与 决策 , 2000 , 15 (5) :557 - 560. LUO Chenzhong , SHAO Huihe. Evolutionary algo2 · 45 · 智 能 系 统 学 报 第 2 卷
第2期 陈杰,等:关于智能优化方法的集聚性与弥散性问题 ·55· rithms with chaotic mutations [J ]Control and Deci- 出版社,施普林格出版社,2000. sion,2000,15(5):557-560 [35]吴晓军,薛惠锋,李,等.GA-PS0混合规划算法 「25]巩敦卫,孙晓燕.变搜索区域多种群遗传算法卩].控制 [].西北大学学报(自然科学版),2005,35(1):39.42. 理论与应用,2006,23(2):256.260 WU Xiaojun,XUE Huifeng,LI Min,et al.A new pro- GON G Dunwei,SUN Xiaoyan.Multi-population genet- gramming of mixed genetic algorithm with particle ic algorithms with variational search areas [J ]Control swarm optimization[J ]Journal of Northwest Universi- Theory and Applications,2006,23(2):256-260. ty (Natural Science Edition),2005,35(1):39-42. [26]HAN K H,KIM J H.Genetic quantum algorithm and [36]王丽芳,曾建潮.基于微粒群算法与模拟退火算法的协 its application to combinatorial optimization problems 同进化方法[U].自动化学报,2006,32(4):630.634. [A].Proceedings of the IEEE Conference on Evolution- WANG Lifang,ZENG Jianchao.A cooperative evolu ary Computation,Piscataway[C].2000. tionary algorithm based on particle swarm optimization [27]PAN Feng,CHEN Jie,CAI Tao,et al.Stability,con and simulated annealing algorithm[J].Acta Automatica vergence of balloon particle swarm optimizer and its ap- Sinica,2006,32(4):630-634. plication[A].Proceedings of the 16th IFAC Congress [37]JIAO Licheng,WANG Lei.A novel genetic algorithm [C].Prague,Czech,2005. based on immunity[J].IEEE Transactions on System. [28]RIGET J,VESTERSTROEM J S.A diversity-guided Man and Cybernetics-Part A:Systems and Humans, particle swarm optimizer-the ARPSO[R].No.2002- 2000,30(5):552-561. 02,Department of Computer Science,University of [38]MEHRABIAN A R,LUCAS C.A novel numerical op- Aarhus,EVALife.2002. timization algorithm inspired from weed colonization [29 ]AN GEL INE P J.Using selection to improve particle [J ]Ecological Informatics,2006,1(4):355-366. swarm optimization[A].Proceedings of IEEE Confer- [39]EROL O K,EKSIN I.A new optimization method:big ence on Evolutionary Computation [C].Anchorage, bang-big crunch[J ]Advances in Engineering Software, USA,1998. 2006,37:106-111 [30]BERGH F V D,EN GELBRECHT A P.A cooperative [40]SOL IS F J,WETS R J B.Minimization by random approach to particle swarm optimization [J ]IEEE search techniques [J ]Mathematics of Operations Re- Transactions on Evolutionary Computation,2004,8 search,1981,6(1):19.30. (3):225.239 [41]李兵,蒋蔚孙.混沌优化方法及其应用[J].控制理论 [31]RATNAWEERA A,HAL GAMUGE S K,WATSON 与应用,1997,14(4):613.615. H C.Self-organizing hierarchical particle swarm optimi- LI Bing,JIANG Wer sun.Chaos optimization method zer with time-varying acceleration coefficients[J ]IEEE and its application[J ]Control Theory Applications, Transactions on Evolutionary Computation,2004,8 1997,14(4):613-615. (3):240-255. [42]JI Mingjun,TANG Huanwen.Application of chaos in [32]TASOULIS D K,PAVLIDIS N G,PLAGIANA KOS V simulated annealing [J ]Chaos,Solitons Fractals, P,et al.Parallel differential evolution[A].Proceedings 2004,21:933-941. of the CEC04 Congress on Evolutionary Computation [43]袁晓辉,袁艳斌,王乘,等.一种新型的自适应混沌遗 [C].Portland,USA,2004. 传算法[0].电子学报,2006,34(4):708-712. [33]PAVLIDIS N G,PLAGIANNAKOS V P,TASOULIS YUAN Xiaohui,YUAN Yanbin,WANG Cheng,et al. D K,et al.Human designed Vs.genetically pro- A novel self-adaptive chaotic genetic algorithm[J].Acta grammed differential evolution operators[A].Proceed- Electronica Sinica,2006,34(4):708-712. ings of the IEEE Congress on Evolutionary Computation [44]杨俊杰,周建中,喻菁,等.基于混沌搜索的粒子群 [C].Vancouver,Canada,2006. 优化算法0].计算机工程与应用,2005,16:69.71. [34]王凌.智能优化算法及其应用[M].北京:清华大学 YAN GJunjie,ZHOU Jianzhong,YU Jing,et al.Par- 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
rithms with chaotic mutations [J ]. Control and Deci2 sion , 2000 , 15 (5) :557 - 560. [25 ]巩敦卫 ,孙晓燕. 变搜索区域多种群遗传算法[J ]. 控制 理论与应用 , 2006 , 23 (2) :256 - 260. GON G Dunwei , SUN Xiaoyan. Multi2population genet2 ic algorithms with variational search areas[J ]. Control Theory and Applications ,2006 ,23 (2) :256 - 260. [26 ] HAN K H , KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problems [ A ]. Proceedings of the IEEE Conference on Evolution2 ary Computation , Piscataway[C]. 2000. [27 ] PAN Feng , CHEN Jie , CAI Tao , et al. Stability , con2 vergence of balloon particle swarm optimizer and its ap2 plication[ A ]. Proceedings of the 16th IFAC Congress [C]. Prague , Czech , 2005. [28 ] RIGET J , VESTERSTROEM J S. A diversity2guided particle swarm optimizer2the ARPSO [ R ]. No. 2002 - 02 , Department of Computer Science , University of Aarhus , EVALife ,2002. [29 ] AN GEL IN E P J. Using selection to improve particle swarm optimization[ A ]. Proceedings of IEEE Confer2 ence on Evolutionary Computation [ C ]. Anchorage , USA ,1998. [30 ]BERGH F V D , EN GELBRECH T A P. A cooperative approach to particle swarm optimization [J ]. IEEE Transactions on Evolutionary Computation , 2004 , 8 (3) :225 - 239. [31 ] RA TNAWEERA A , HAL GAMU GE S K , WA TSON H C. Self2organizing hierarchical particle swarm optimi2 zer with time2varying acceleration coefficients[J ]. IEEE Transactions on Evolutionary Computation , 2004 , 8 (3) :240 - 255. [ 32 ] TASOUL IS D K , PAVL IDIS N G, PLA GIANA KOS V P , et al. Parallel differential evolution[ A ]. Proceedings of the CEC04 Congress on Evolutionary Computation [C]. Portland , USA ,2004. [33 ] PAVL IDIS N G, PLA GIANNA KOS V P , TASOUL IS D K , et al. Human designed Vs. genetically pro2 grammed differential evolution operators[ A ]. Proceed2 ings of the IEEE Congress on Evolutionary Computation [C]. Vancouver ,Canada , 2006. [34 ]王 凌. 智能优化算法及其应用[ M ]. 北京 :清华大学 出版社 ,施普林格出版社 , 2000. [35 ]吴晓军 ,薛惠锋 ,李 ,等. GA2PSO 混合规划算法 [J ]. 西北大学学报(自然科学版) ,2005 ,35 (1) :39 - 42. WU Xiaojun , XU E Huifeng , L I Min ,et al. A new pro2 gramming of mixed genetic algorithm with particle swarm optimization[J ]. Journal of Northwest Universi2 ty (Natural Science Edition) , 2005 , 35 (1) :39 - 42. [36 ]王丽芳 ,曾建潮. 基于微粒群算法与模拟退火算法的协 同进化方法[J ]. 自动化学报 ,2006 ,32 (4) :630 - 634. WAN G Lifang , ZEN G Jianchao. A cooperative evolu2 tionary algorithm based on particle swarm optimization and simulated annealing algorithm[J ]. Acta Automatica Sinica , 2006 , 32 (4) :630 - 634. [37 ]J IAO Licheng , WAN G Lei. A novel genetic algorithm based on immunity[J ]. IEEE Transactions on System. Man and Cybernetics2Part A : Systems and Humans , 2000 , 30 (5) : 552 - 561. [38 ]MEHRABIAN A R , LUCAS C. A novel numerical op2 timization algorithm inspired from weed colonization [J ]. Ecological Informatics , 2006 , 1 (4) :355 - 366. [39 ] EROL O K , EKSIN I. A new optimization method : big bang2big crunch[J ]. Advances in Engineering Software , 2006 , 37 : 106 - 111. [40 ] SOL IS F J , WETS R J B. Minimization by random search techniques[J ]. Mathematics of Operations Re2 search , 1981 , 6 (1) : 19 - 30. [41 ]李 兵 ,蒋蔚孙. 混沌优化方法及其应用[J ]. 控制理论 与应用 , 1997 , 14 (4) :613 - 615. L I Bing , J IAN G Wei2sun. Chaos optimization method and its application[J ]. Control Theory & Applications , 1997 , 14 (4) :613 - 615. [42 ]J I Mingjun , TAN G Huanwen. Application of chaos in simulated annealing [J ]. Chaos , Solitons & Fractals , 2004 , 21 :933 - 941. [43 ]袁晓辉 , 袁艳斌 ,王 乘 ,等. 一种新型的自适应混沌遗 传算法[J ]. 电子学报 , 2006 ,34 (4) :708 - 712. YUAN Xiaohui , YUAN Yanbin , WAN G Cheng , et al. A novel self2adaptive chaotic genetic algorithm[J ]. Acta Electronica Sinica ,2006 , 34 (4) : 708 - 712. [44 ]杨俊杰 , 周建中 , 喻 菁 ,等. 基于混沌搜索的粒子群 优化算法[J ]. 计算机工程与应用 , 2005 ,16 : 69 - 71. YAN G J unjie , ZHOU Jianzhong , YU Jing , et al. Par2 第 2 期 陈 杰 ,等 :关于智能优化方法的集聚性与弥散性问题 · 55 ·
·56· 智能系统学报 第2卷 ticle swarm optimization algorithm based on chaos [53]XU Xiaoyan,DON Y R D.Differential evolution with searching[J].Computer Engineering and Applications, Powell's direction set method in medical image regeis- 2005,16:69.71. tration [A ]Proceedings of the IEEE International [45]SCHMIDT H,THIERAUF G.A combined heuristic Symposium on Biomedical Imaging:Macro to Nano optimization technique [J ]Advances in Engineering [C].Arlington,USA,2004. Software,2005,36:11-19. [54]SAL HI S,QUEEN N M.A hybrid algorithm for iden- [46]CHIOU Jpi,CHANG C-f,SU C-t.Ant Direction hy- tifying global and local minima when optimizing func- brid differential evolution for solving large capacitor tions with many minima[J].European Journal of Oper- placement problems[J].IEEE Transactions on Power ational Research,2004,155:51-67. System,2004,19(4):1794-1800. [55 ]CL ERK M,KENNED YJ.The particle swarm:explo- [47]ZHANG Wenjun,XIE Xiaofeng.DEPSO:hybrid parti- sion,stability and convergence in a multi-dimensional cle swarm with differential evolution operator[A].Pro- complex space[J].IEEE Transactions on Evolutionary ceedings of the IEEE International Conference on Sys- Computation,2002,6(1):58-73. tems[C].Washington,USA,2003. 作者简介: [48 ]NARA YANAN A,MOORE M.Quantumrinspired ge- 陈杰,男,1965年生,教授,博士 netic algorithm[A ]Proceedings of the IEEE Interna- 生导师,中国人工智能学会常务理事,中 国自动化学会常务理事兼副秘书长,主 tional Conference on Evolutionary Computation C]. 要研究方向为复杂系统多目标优化与决 Piscataway,1996. 策、智能控制、约束系统非线性控制、优 [49]YAN G Shuyuan,WANG Min,JIAO Licheng.A quan 化方法.获部级科技进步奖10项,完成 tum particle swarm optimization[A].Proceedings of 科研项目20余项,发表学术论文70余 CEC2004 Congress on Evolutionary Computation [C]. 篇,出版著作3部 Email:chenjie @bit.edu.cn. Portland,USA,2004. [50]KVASNICKA V,POSPICHAL J.A hybrid simplex 辛斌,男,1982年生,博士研究生 主要研究方向为计算智能、优化方法、模 method and simulated annealing[J ]Chemometrics and 式识别等 Intelligent Laboratory System,1997,39:161-173. [51 ]LIM A,RODRIGU ES B,ZHANG X.A simulated an nealing and hill-climbing algorithm for the traveling tournament problem [J ]European Journal of Opera- tional Research,2006.174:1459-1478. 窦丽华,女,1961年生,教授,博士生 [52]PENG Yehui.A hybrid algorithm combining pattern 导师,中国人工智能学会智能网络分会 委员,主要研究方向为模式识别与智能 search method and genetic algorithm for bound con- 系统.承担国家重点型号装备项目、重点 strained optimization [J ]Mathematical Theory and 预研项目和基金项目4项,获国防科工 Applications,2005,25(4):1-4. 委科技进步4项,近几年在核心期刊上 发表论文20余篇. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
ticle swarm optimization algorithm based on chaos searching[J ]. Computer Engineering and Applications , 2005 , 16 : 69 - 71. [45 ] SCHMIDT H , THIERAU F G. A combined heuristic optimization technique [J ]. Advances in Engineering Software , 2005 , 36 :11 - 19. [46 ]CHIOU Jpi , CHAN G C2f , SU C2t. Ant Direction hy2 brid differential evolution for solving large capacitor placement problems[J ]. IEEE Transactions on Power System , 2004 , 19 (4) :1794 - 1800. [ 47 ]ZHAN G Wenjun , XIE Xiaofeng. DEPSO : hybrid parti2 cle swarm with differential evolution operator[ A ]. Pro2 ceedings of the IEEE International Conference on Sys2 tems[C]. Washington ,USA ,2003. [48 ]NARA YANAN A , MOORE M. Quantum2inspired ge2 netic algorithm[ A ]. Proceedings of the IEEE Interna2 tional Conference on Evolutionary Computation [ C ]. Piscataway ,1996. [ 49 ] YAN G Shuyuan , WAN G Min , J IAO Licheng. A quan2 tum particle swarm optimization [ A ]. Proceedings of CEC2004 Congress on Evolutionary Computation [ C ]. Portland , USA ,2004. [ 50 ] KVASNICKA V , POSPICHAL J. A hybrid simplex method and simulated annealing[J ]. Chemometrics and Intelligent Laboratory System , 1997 , 39 :161 - 173. [51 ]L IM A , RODRIGU ES B , ZHAN G X. A simulated an2 nealing and hill2climbing algorithm for the traveling tournament problem [J ]. European Journal of Opera2 tional Research , 2006 , 174 :1459 - 1478. [52 ] PEN G Yehui. A hybrid algorithm combining pattern search method and genetic algorithm for bound con2 strained optimization [ J ]. Mathematical Theory and Applications , 2005 , 25 (4) :1 - 4. [53 ] XU Xiaoyan , DON Y R D. Differential evolution with Powell′s direction set method in medical image regeis2 tration [ A ]. Proceedings of the IEEE International Symposium on Biomedical Imaging : Macro to Nano [C]. Arlington , USA ,2004. [54 ]SAL HI S , QU EEN N M. A hybrid algorithm for iden2 tifying global and local minima when optimizing func2 tions with many minima[J ]. European Journal of Oper2 ational Research , 2004 , 155 :51 - 67. [55 ]CL ER K M , KENNED Y J. The particle swarm : explo2 sion , stability and convergence in a multi2dimensional complex space[J ]. IEEE Transactions on Evolutionary Computation , 2002 , 6 (1) :58 - 73. 作者简介 : 陈 杰 ,男 ,1965 年生 ,教授 ,博士 生导师 ,中国人工智能学会常务理事 ,中 国自动化学会常务理事兼副秘书长 ,主 要研究方向为复杂系统多目标优化与决 策、智能控制、约束系统非线性控制、优 化方法. 获部级科技进步奖 10 项 ,完成 科研项目 20 余项 ,发表学术论文 70 余 篇 ,出版著作 3 部. Email : chenjie @bit. edu. cn. 辛 斌 ,男 ,1982 年生 ,博士研究生 , 主要研究方向为计算智能、优化方法、模 式识别等. 65 · 窦丽华 ,女 ,1961 年生 ,教授 ,博士生 导师 ,中国人工智能学会智能网络分会 委员 ,主要研究方向为模式识别与智能 系统. 承担国家重点型号装备项目、重点 预研项目和基金项目 4 项 ,获国防科工 委科技进步 4 项 ,近几年在核心期刊上 发表论文 20 余篇. · 智 能 系 统 学 报 第 2 卷