·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 卷