分而治之多种群遗传算法

2.6.1　引言

在自然界和人类社会的体系中,一些基本的法则和模式支配着物质和精神世界的运作方式。牛顿经典力学定律的内在作用使得宏观世界和谐有序的按照各自的方式存在和演化;生命科学中的遗传学原理决定了有生命世界的多样性和统一性,筑成了物种的纷繁复杂,无限多样;而微观时空中的测不准关系则宣告了拉普拉斯决定论的一去无返……

受自然和人类社会规律的启发,获得智慧的灵感进行科学研究,生产生活,是人类不断推陈出新,生生不息的动力之源。以遗传算法[23],进化策略[24],进化规划[25]为代表的进化算法则是这种思想的体现和结晶。自它们提出以来,就因其卓异的鲁棒性能而备受关注,并越来越多的在各个领域获得重要应用。近来,进化算法的各学派互相借鉴,优势互补,已形成了“你中有我,我中有你”的格局[26]。因此有学者用公共的术语来表示所有借助进化思想的系统,而见之于各种媒体的文献报道则不断涌现。

受生物界中食物链关系,共生关系启发而提出的协同进化(co-evolution)是近来发展起来的有前途的方法[27]。1992年Hillis最早将一种寄生虫和寄主协同进化的机制应用到优化搜索的改进中,提出了协同进化遗传算法(Co-evolutionary Genetic Algorithm,CGA)的思想[28]。Paredis发展了这种方法,并在分类神经网络设计,约束优化问题的状态空间搜索方面进行一系列有意义的成功应用[29,30]。国内在协同进化算法方面也开展了一些研究,取得了较好的应用效果。王文韬等针对现有模糊系统设计中的Pittsburgh方法和Michigan方法的不足,提出了一种能扬长补短的合作式协同进化方法[31]。江瑞等和李敏强等研究者则针对函数优化问题和组合优化问题,提出了各自的协同进化算法[32,33]。

本节中作者根据“分而治之”这一在自然界和人类社会中广泛存在的法则,提出了一种新的协同进化算法。

2.6.2　“分而治之”(divide and conquer)法则

“分而治之”法则是一种广泛存在于自然界和人类社会中卓有成效的问题求解策略。它将问题分解成更小规模和更简单的子问题,通过不同专家学习(解决)各子问题,最后将各子任务集结以解决全问题[34]。作者认为其基本方式有“串行式分治”“并行式分治”两种。

“串行式分治”如图2.15所示,其特点是任务能分解为n个顺序式子任务,前一个任务的输出构成后一任务的输入。这样的一条子任务链构筑了完整的任务集。

图2.15　串行式分治示意图

“并行式分治”如图2.16所示,其特点是任务能分解为n个并行式子任务,每个子任务在时间上保持相互独立,任务的最终完成有赖于子任务的集结。一般的,各种“分而治之”形式都是上述基本方式的集成。

图2.16　并行式分治示意图

当然,尚可从多种不同角度来认识任务分解的方式。如Lv等认为任务分解大致可被分为三类[35]:

(1)直接分解,即在学习之前,让一个熟知问题先验知识以及懂得一些相关领域知识的专家来对问题进行分解,然后设计出若干模块网络与之对应。

(2)按类分解,即在学习之前,根据训练数据之间内在的类别关系将问题分解成一系列子问题。和直接分解不一样,这种方法只需了解一些关于训练数据之间类别关系的常识而已。

(3)自动分解,即边学习边分解问题。例如,混合专家结构。就计算复杂性而言,显然前两种方法效率高些,因为它们是在学习之前分解问题的。不过这种方法更一般化些,因为它不需要任何有关该问题的先验知识。

自然界和人类社会的运作蕴涵着“分而治之”的法则。这一点已被无数极富说服力的实例所证实。如美国达特茅斯学院的神经科学家最新研究表明:分辨别人和自己是由大脑不同部分承担的,右脑负责辨认别人的脸,而左脑则负责辨识认自己[36];我国的政治协商制度也体现了“分而治之”的思想:政协委员由不同界别的人士构成,各界别的人们在不同的领域从事独立的工作,而在参政议政时,他们云集一地,共同担纲为大政方针制度的制定建言献策的重任,会议结束后他们又回到各自的岗位履行各自的使命。凡此种种,不胜枚举。

“分而治之”的思想在ANN等领域中获得许多成功的应用[37,38]。本节则试图将其引入到进化算法中以获得性能优良的多种群协同进化方法。

2.6.3　算法介绍

作者提出的多种群进化算法与许多现有的算法不同。它在任务分解机进行任务分配后,独立完成所分配任务,与其他群体几乎不发生联系。在子任务完成后,各子群中的优秀分子组成新的种群,在整个问题空间完成进化。再由决策机构决定是否将最优解提交用户。如决策机构对现有最优解不满意,它将选择以下几种可能行动:①将目前前P%的最优解分配到原来隶属的子种群中再行进化直至满意。②保留最优解,而子种群重新进化。分而治之协同演化算法(DCCEA)由如下5元组定义:

其中,TDM(task decomposition machine)为任务分解机,它所求解问题的性质将任务分解为具有某种分而治之形式的子任务;SubEA(sub-evolutionary algorithm)为基于各子种群演化算法,它们可以是同构算法,也可是异构算法;Sub TIM(sub-task integrating machine)是子任务集成机,它根据不同分而治之的方式而集成各子任务的结果,产生最终或过渡性的全任务解;Opt P(optimum processor)为当前最优解处理器,它根据当前所取得的最优解(或满意解的情况来作出是否提交用户)的决策和行动;T为终止条件,它提供算法停止运行的时间或质量条件。

显然,这里的协同是任务层次意义上的。

下面针对如下问题提出一种具体的DCCEA的算法。

运用分而治之的思想,在演化算法寻优之前进行任务分解,主要算法流程如下:

(1)任务分解:①搜索空间划分——在没有先验信息时,将搜索空间进行等体积划分;当掌握先验信息时,将最大可能区域的搜索置于分而治之的重点区域,如可设置小区域、大种群＋细搜索方式等;②函数分解——将复杂函数分解为若干简单函数。一般的任务分解是上述二者之一或兼而有之。

(2)对划分后的子区域或对子函数分别采用单种群演化算法(EA);

编码方式:浮点编码;选择方式:赌轮盘(weighted roulette wheel)选择法;

适应度函数由下式计算:

交叉方式:线性交叉,即:

其中,α是(0,1)中随机数

变异方式:变异采用原解点加均匀随机干扰的方法,即:

特别的,变异后要作边界判断与处理,本文采用超出边界时取边界值的策略。

其他:本文采用5%最优保留的方法

(3)各区域或子函数进化任务完成后,将子任务最优点集组成新的种群,在整个搜索空间内采用演化算法进行搜索,进化得到最优的5%或作为结果,或进行进一步的小种群搜索。

2.6.4　仿真算例

这里举两个算例。

例1.De Jong函数F5(选自[39]):

其中,

函数在(x 1,x 2)＝(－32,－32)处有一全局最小值0.998,即1/f(x)有最大值1.002。

本算例中,分而治之演化算法有关的参数如下:搜索空间划分为如下4个区域:

在学习过程中的具体参数如下:

每个种群的基因数目为100;

交叉率＝0.8;

变异率＝0.2;

变异的范围σ为当前搜索区域的1/10。

各区域分别进化100代,然后再将各区域的5%最优点集作为全区域初始种群在整个搜索空间内进化100代,若达到精度要求则停机,否则采用小种群进行细搜索。

研究中,我们以SGA算法为对比,其相应参数设置为:

种群的基因数目为400;

交叉率＝0.8;

变异率＝0.2;

最大进化代数为100代;

采用5%最优保留

仿真实验在P2 300计算机上进行仿真,开发工具采用MATLAB6.1,设传统SGA算法学习时间为Ts(s),分而治之演化算法学习时间为Tn(s),结果如表2.2示。

De Jong函数F5是一个典型的多模态函数,函数有25个极值点,而且搜索空间相对较大。在进行的多次实验中,采用SGA训练,学习时间较长,且几乎无法达到最优值;而采用分而治之的演化算法,在多次实验中均能几乎(误差在1/1000内)达到全局最优,且学习时间较SGA短得多。实践证明,分而治之的演化算法能有效地缩小搜索空间,充分发挥了演化算法在小搜索空间寻优的优势,在学习时间和学习效果上均明显优于SGA。我们还用SGA作了最大代数为500代时的比较实验,相应的3次原函数最优结果分别为4.86106436137047,1.0105830811065,2.00292070976531。显然我们的算法结果仍然远优于之。同时这一结果优于文献[33]所报告的结果。

该函数全局最小值为－78.3323。本算例中,分而治之演化算法有关的参数如下:

搜索空间划分:8块(随机的将x i中任意三个变量的定义域进行等分);每个种群的基因数目为400;交叉率＝0.8;变异率＝0.2;变异的范围σ为当前搜索区域的1/10;各区域进化代数:100代。

各区域进化训练后,再将各区域的5%最优点集作为全区域初始种群在整个搜索空间内进化100代,若达到精度要求则停机,否则采用小种群进行细搜索。

由于搜索空间仍然很大,在仿真中发现演化算法无法搜到最优值左右,一般搜得最小值在106这个数量级上。

改进1:在分而治之演化算法中嵌入局部搜索算法,本文中采用嵌入梯度下降法。即在分块搜索中每代的前5%采用梯度下降法进行优化,梯度下降采用的步长为0.001,每次进行1000步。学习时间为1893.891s,搜到最优值－54.2999090251139、,效果仍不理想。

表2.2　算法性能比较

改进2:考虑到本算例结构的特殊性,其自变量x各分量间是相对独立的,于是本文采用函数分解和空间分解相结合的方法:即对每个f(x i)分别寻优(未加局部搜索算法),再求和得到原函数f(x)的最小值。其中针对每个f(x i)都采用空间分解的方法。10次实验的部分结果如表2.3所示:

由例2可见合理的分而治之十分关键和重要,其往往决定问题求解的成败。

表2.3　算法性能

2.6.5　结论

本节应用“分而治之”思想,提出一种有效的多种群演化算法的框架、结构和面向一类优化问题的具体实现。该算法的最大特点在于种群之间的协同是在任务层次意义上的,它们相互协同完成各自的子任务后,再提交满意解予以融合提升。仿真算例证明了该算法的有效性。