软计算的混合算法综述

软计算是一类在目标层次上高度一致,而在方法层次上各具特色的方法集合,它的这一特征决定了软计算成员间具有天然的互补性和集成性。其成员的有机结合往往能兼顾问题的不同层面和视角,优势互补,协同一致,取得很好的效果。

混合算法的提出还有其哲学基础。辩证唯物主义认为[23]:内容和形式的相互作用,构成了它们的矛盾运动。在这种矛盾运动中,内容相对于形式是比较活跃,易变的;形式相对于内容则显得比较保守。随着内容发展到一定阶段,原来相对稳定的形式越来越落后于内容发展的客观要求,二者就由适合变为基本不适合,原来就存在的矛盾不断激化,甚至形成尖锐的冲突。这时,在客观上提出了变革原有形式以适应内容需要的任务。这种由基本适合到基本不适合再到基本适合的不断发展过程,构成了内容和形式的矛盾主线。针对活跃的内容,采用相对丰富的形式,以适应内容的需要,是消除和缓和上述矛盾的有效途径。全新方法的创新和已有方法的创新性融合,都是这种有效途径的体现。从本质上看,软计算混合算法属于后者,它的成员间及与其他求解策略的有效混合,产生的丰富的求解模式客观上符合了适应纷繁复杂的问题空间的要求,也符合了内容对形式的客观需要。

1.3.1　混合算法的分类

王凌提出如下基于结构的三种混合算法分类方法[24]:

(1)串联结构;

(2)镶嵌结构;

(3)并联结构。

图1.1－1.3分别表征了这三种混合方式。

图1.1　混合算法的串联结构

图1.2　混合算法的镶嵌结构

图1.3　混合算法的并联结构

作者认为:基于不同角度,混合算法至少还有如下几种基本分类方法(基本分类指类型的基类,所有的混合都是基类的组合):

(1)按混合的主体分,可分为算法和算法的结合、算法和算法的部分结合以及算法的部分与算法的部分结合3种情形。

(2)按混合的程度分,可分为积木块式组合型和合金式融合型2类情形。

(3)按混合的时序分,有同步型和异步型2种情形。

(4)按面临的问题性质分,有面向同一问题的混合与面向不同子问题的混合2种情形。

1.3.2　软计算的典型混合方式[6]及发展

1.3.2.1　通过NN调节FL

张智星(J.R.S.Jang)等人提出的ANFIS是此类系统的典型[25]。ANFIS共由6层神经元构成:第一层为输入层;第二层定义了输入空间的模糊分划(TS型一项集termset);第三层执行可微T－型运算——如乘积型或软析取(soft minimum);第四层规范化每条规则左手边(即前件)评价,以满足其可应用度之和为1;第五层计算规则的后件多项式系数;第六层为输出层。其工作基于:前向驱动机制产生输出(TS参数不变),后向驱动校正第二层的模糊划分,它们交替作用直至收敛。另外,Lin C T等人也在构建基于人工神经网络的模糊系统方面做了有益的工作[26]。

Wang等人和Tsai等人则研究了模糊神经网络的鲁棒性算法,旨在提高网络在存在离群样本点的情况下正确逼近真实映射的能力[27,28]。其中,Tsai等人的方法有以下特点:①逼近过程中能拒绝离群点以减小总误差;②能训练多输出模糊神经网络;③能推广到多学习率情形。

1.3.2.2　通过EC调节FL

目前关于这方面的研究工作因其可观的应用前景吸引了大量研究者,成为软计算混合算法领域的一大热点。从决策的角度来看,模糊推理系统虽有优异的知识表达能力,但其学习能力的欠缺制约了不确定环境下的决策进程的展开。如何在保留模糊推理系统的长处的同时引入学习机制,就成为了决策领域的重要命题;从控制的角度来看,作为一个模糊控制器设计的一部分,优化性能函数评价闭环系统状态轨迹是相对容易的;而用监督学习方法优化理想的控制器行为却一直十分困难。而EC作为一种有效的全局优化的工具,可以在上述瓶颈问题的解决上发挥重要作用。

Gonzalez[29]等对使用迭代方法学习模糊规则的遗传学习算法——不确定环境结构学习算法(SLAVE)作了改进,提出一种个体遗传算法的特色选择模型,这种个体(代表个体规则)由两个结构组成:一个结构代表规则中有关变量的相关状态,另一个结构代表了指定变量。对这种一般的表示法,他们研究了第一种结构的信息代码的两种选择方法。与最初的算法相比,这种新的SLAVE方法减少了规则数,简化了规则结构提高了整体精度。

Lee和Takagi同时调节模糊规则和项集(TS’s)[30]。他们对三角形隶属函数特征进行二进制编码。每个染色体表征一条TSK规则——包括规则前件的隶属度函数(关键参数)和后件的多项式系数。

Li和Zhang提出以二次型指标为适应度函数,用遗传算法学习Sugeno模糊规则中前件模糊变量隶属函数的参数及后件表达式的参数的方法[31],并成功应用于二级倒立摆稳定控制中。

Bonissone等[32],按照Zheng[33]等提出的手工调节次序,在首先使用标准一致的TS宽度和均匀规则基的前提下(宏观尺度意义),调节FLC状态和控制变量的尺度因子(SF’s)。在得到最优尺度因子后,他们调节TS’s以获取中等尺度意义上的效应。最后,如果需要有进一步的性能提高,他们调节规则基获取微观尺度效应。

1.3.2.3　用EC构造NN’s

Bonissone等最近指出用EC构造NN’s的如下具体表现[6]:

(1)学习已知拓扑结构的权值;

(2)进化拓扑结构(如隐层数,隐层结点数等);

(3)同时进化结构和权值;

(4)进行自适应奖励函数;

(5)为NN选择关键的输入特征。

此外,还有训练算法参数的进化设计、进化学习规则、进化训练样本等混合方式。

1988年,Jurick针对梯度方法的代表——BP算法的严重缺陷(如局部极小值问题等),提出批评并成为最早的建议使用包括进化方法在内的鲁棒调节法的人员之一[34]。

Montana和Davids提出给定拓扑结构情形下前向NN的GA训练法。他们使用的是带直接编码和变异的实值稳态GA’s[35]。由于GA’s不是一种很好的细粒度搜索方法(寻找最优点),尽管它堪称优秀的粗粒度方法(寻找最优点的所在区域),Kitano等人于是提出了一种混合了GA和BP的方法[36]:用GA寻找权值的较优初始值,继而用BP寻优。与此类似,Gu,Chen和Wang提出了GA－BP－CGA(conjugate gradient algorithm)算法[37];而McInereny和陈等则提出了另一种方法:在BP陷入局部极小值时启动GA’s以跳出[38,39]。

进化网络拓扑和学习规则是NN和EC融合的另外两个也许是更为重要的研究重点。在Bonissone等的综述[6]中,介绍了进化网络拓扑的三种方法:直接法、参数化法和语法编码法。何的文章中,介绍了进化网络学习规则(如delta规则和delta规则的派生等)的若干方法[40]。限于篇幅,这里不再详述。

Yao在一篇综述中,给出了关于进化神经网络(包括用GA,ES,EP等方法)研究进展的全面详尽的论述[41]。

1.3.2.4　由FL控制的NN

NN学习过程中,一些参数的选取无一般适用的原则和方法,这时往往需借助经验和知识根据学习进程的实际情况进行实时调整。FL是指导此类调整(这样的调整还包括确定性规则等)的有效手段之一。

具体地说,由FL控制NN学习就是将经验和知识转化为可操作的规则集。完备的模糊规则集涵盖了学习过程若干关键性能的各种情况,并据此给出相应的调整方向和大小。模糊规则基和模糊算法已用于监督NN’s或EC之性能以及修正其控制参数。FLC’s已用于控制NN’s的学习中以改善在近最优点时的慢收敛性[6]。

学习率和冲量因子是两个可模糊调整的重要参数。前者的选择将影响到逼近精度和收敛速度——它的值越小,逼近效果越好,然而收敛越慢;后者则可以兼顾原来权向量改变量的方向以防止误差平面狭窄区域中的振荡及可望有更快的收敛[6]。一般来说,大值学习率和大冲量一般可导致快速收敛,但精度差;相反,小值却有较高精度和缓慢的训练过程。

Jacobs提出了一种名为delta-bar-delta的启发式规则:当连续几步误差梯度符号不变时,增加学习率[42]。

Arabshahi则进一步提出一种用以修正学习率的模糊控制器,它是误差和误差变化的函数[43]。

1.3.2.5　由FL控制的EC

Michalewicz指出:EC的资源管理源于以下两条动因:EC有许多策略性参数——交叉和变异算子及概率、选择机制与压力(如锦标赛规模)、种群大小等,而参数的选取是决定算法性能的关键之一;经典EC方法的参数是刚性的而EC本质上是动态、自适应的[50]。在对EC资源的管理的诸多方法中,FL是行之有效的一种策略。江将基于模糊逻辑控制器的自适应遗传算法归纳为[44]:

(1)动态参数遗传算法[45];

(2)模糊遗传算法[46,47];

(3)模糊管理[48];

(4)模糊自适应实编码遗传算法[49]。

Herrera和Lozano提出用于GA’s的参数设置的一种方法,遗传算子的选择,解的表达以及适应度函数见文献[51]。该方法的关键在于发现分配到综合推理(如fuzzy控制器)计算资源与目标等级问题求解之间的正确平衡。所举例子证明了EC资源的有效管理方法能产生提高效率和收敛速度。University of Washington的Streifel等人根据一代中的最优解与搜索空间的距离提出模糊变搜索空间的遗传算法动态参数编码的模糊控制方法,研究表明该方法具有很快的收敛速度和精度[52]。

1.3.2.6　NN作为EC的种群进化机

目前,EC参与NN学习(如上所述)是NN和EC混合方面研究工作的主流;而将NN作为EC的一部分参与进化过程,利用NN的鲁棒性和良好的自学习性能学习父代对子代的映射的研究极少,虽然这项工作同样有助于提高算法的整体性能。

Furaya提出用BP网络完全替代原算法中父代向子代的进化过程的混合策略[53]。曹等则进一步提出根据学习的质量来有条件的选择NN充当实现父代对子代映射的种群进化机的方法,当NN学习效果不佳时,仍然采用传统的EC进化模式[54]。

最后,应该指出:软计算的混合除上面综述所介绍的成员间的混合外,还有一大类混合是软计算与其他方法(人工智能方法,数值计算方法等)的混合。这种混合的重要性决不逊于前者,因为一种方法体系在纷繁复杂的问题世界面前都不是万应灵药,这时除要求体系内部的方法元素的最优协同外,还需要与其他方法体系的有机协同,各尽所能,优势互补。限于篇幅,本节对这一重要问题不再综述。

在本章最后的附录中,作者给出新近完成的具有一般意义的方法集成研究结果。