基于群体信息挖掘的协同差分进化算法

基于群体信息挖掘的协同差分进化算法

1995年，stornr和价格k相继提出了分散发展算法（de）。它是一种随机的并行直接搜索算法,可以对非线性不可微连续空间函数进行最小化。DE以遗传算法为基础,所以它和遗传算法、微粒群算法等一样,都是基于群体智能理论的优化算法。DE采用实数编码,在算法中引入扰动矢量,采用基于差分的简单变异操作和一对一的竞争生存策略,具有简单易用的特性;DE可以动态跟踪当前的搜索情况,以调整其搜索策略,具有速度快、鲁棒性好、搜索能力强等优点。为了提高DE的性能,目前已提出了许多改进的方法。Chiou等提出了一种集成蚂蚁方向的差分进化算法,利用蚁群算法的概念,寻求合适的变异操作粒子来加快全局搜索的性能。Xu等提出了一种融合粒子群算法的差分进化算法,该算法分为两步:第一步用标准的粒子群算法进行优化,第二步用DE来对粒子进行差分操作,并将该算法用于神经网络的建模,得到了比较好的效果。Kaelo等使用了一种改进的差分策略来优化差分操作,并使用了一个在固定区间的F因子来代替随机产生的F因子,对几个经典函数的测试表明,算法的性能有很大的提高。DE的局部搜索能力较差,并易陷入局部最优点。为了提高DE的寻优速度和寻优效能,提出了一种基于群体信息挖掘的协同差分进化算法。该算法首先利用协同进化的思想,将种群分解成不同的子种群,每个子种群采用不同的差分策略进行独立的差分和交叉操作,再将各个子种群合并成一个种群,并根据每个个体的适应度值挑选出最优个体;为了提高差分进化算法的局部搜索能力,引入了多元回归分析和模式搜索算法,对于整个种群,利用最小二乘法求得种群的寻优方向信息,并以此来指导种群中的每一个个体进行模式搜索,大大提高了算法的寻优能力和效能。1de的变异向量DE的基本步骤如下。步骤1:初始化。生成由NP个个体组成的初始种群X0=[x10,x20,,x0NP],种群维数为D,确定变异算子F和交叉算子CR,确定最大进化代数Gmax,令G=0。步骤2:对于第G代个体xiG(i=1,2,,NP),计算每个个体的适应度值PE(xiG),并计算最优个体xGbest。步骤3:变异。对于每个目标向量xiG,i=1,2,,NP,基本DE的变异向量产生如下:生成变异后的种群VG+1=[v1G+1,v2G+1,,vNPG+1]。步骤4:交叉。为了增加干扰参数向量的多言性,引入交叉操作。向量变为式中,randb(j)为产生一个之间随机数发生器的第j个估计值;rnbr(i)∈(1,2,,D)为一个随机选择的序列,用它来确保uiG+1至少从viG+1获得一个参数。生成交叉后的种群UG+1=[u1G+1,u2G+1,,uNPG+1]。步骤5:竞争。为决定试验向量uiG+1是否会成为下一代中的成员,DE按照贪婪准则将试验向量与当前种群中的目标向量xiG进行比较。生成第G+1代种群XG+1=⎡⎣x1G+1,x2G+1,,xNPG+1⎤⎦。步骤6:G=G+1,重复步骤2到步骤5,直到满足算法的终止条件或G>Gmax。以上是最基本的DE操作程序。DE在工作时产生了几种有代表性的差分策略,并用符号DE/x/u/z加以区分,其中:x限定当前被变异的向量是“随机的”或“最佳的”;u是所利用的差向量的个数;z表示交叉程序的操作方法。式中,ri为随机整数,表示个体在种群中的序号,r1、r2、r3、r4和r5互不相同。2系统研究并取得了重要进展协同进化概念在进化计算中的应用最早可追溯到Hillis的宿主和寄生物模型及Husbands车间作业调度的多物种协同进化模型。由DeJong领导的GeorgeMason大学进化计算实验室对协同进化算法进行了系统的研究,并取得了重要的进展。传统进化算法将待求解的问题映射为单一种群或单一种群的多个子种群的进化;而协同进化算法借鉴自然界中的协同进化机制,在传统进化算法的基础上引入生态系统的概念,将复杂系统分解为一系列相互作用的各物种组成的生态子系统,每个子系统对应于生态系统的一个物种,这些物种的遗传过程是互相隔离的,即个体只与其所属物种的其它个体进行交叉操作,各子系统分别进行优化,而各物种间通过共同的系统模型相互作用,从整体上进行协调,各物种共同进化,相互合作,完成生态系统整体的进化。子系统的优化和整体协调的过程往往需要交替迭代进行,直到找到优化问题的解。3回归分析回归分析是用数理统计的方法处理相关关系,以确定变量之间是否存在相关关系。如果存在相关关系,就找出变量间的合适数学表达式,即回归方程。3.1多元线性回归分析的原理多元线性模型的一般形式为式中,NP为样本数,D为自变量个数,令多元线性回归模型简化为3.2x-1xy利用最小二乘估计可得回归系数b为b=(X′X)-1X′y。在本文中回归系数b就代表了种群整体所包含的最优解所在方向的信息,也就是为整个种群的模式搜索提供了一个具体的方向。4移动点组成模式搜索算法是Hooke和Jeeves于1961年提出的。它由两部分组成,即一个是探测移动,另一个是模式移动,就是先通过“探测性移动”寻找最佳点信息,然后利用“模式性移动”沿着找到的最佳点的信息前进,这两种移动交替进行直到步长δ小于事先给定的某个正数ε为止。4.1步长探测移动探测移动在某个已知点附近,对一个可行解x∈RD分别对其D个正反坐标轴方向ei进行步长探测移动,如探测成功(即至少有一个下降步)后,则进行模式移动,如果探测移动步失败,则缩短步长δ=0.5δ,继续探测,直到δ<ε,则认为找到了最优值。坐标轴方向ei为一个向量,其第i个值为1,其余全部为0。4.2模式移动在第g步可行解x(g)探测移动后,得到x(g+1)。如果f[x(g+1)]<f[x(g)],则进行模式移动4.3反方向探测算法步骤1:给定初始值x0,初始步长δ,中止条件ε,循环次数g=0。步骤2:记t=x(g),先在坐标轴e1方向上探测移动,如果f(t+δe1)<f(t),则沿e1正方向探测成功t=t+δe1,否则沿e1反方向探测移动,如果f(t-δe1)<f(t),则探测成功t=t-δe1,如此重复操作,直到对D个坐标轴方向全部探测完毕。步骤3:如果步骤2中探测有一次成功,即f(t)<f[x(g)],则x(g+1)=t,转到步骤4。否则缩短步长,令δ=0.5δ,重复步骤2,如果δ<ε,则算法中止。步骤4:进行模式移动,即x(g+1)=x(g+1)+[x(g+1)-x(g)],令g=g+1,转步骤2。4.4外来人口搜索本文中所应用的模式搜索是基于寻优方向的模式移动,具体说就是种群中的所有个体在一个包含最优解信息的方向上,按照一定的初始步长作模式搜索,以期望找到比目前更优的解,直到步长衰减到事先给定的某个正数阈值为止,则跳出模式搜索。5种群模式搜索算法本文将协同进化的思想引入DE,其方法是将整个种群分成s个相同大小的子种群,每个子种群采用不同的差分策略分别进化,在s个子种群完成差分和交叉操作后,再将这s个子种群合并为一个种群,从中挑选出一个最佳适应度函数值的个体,作为当前整个种群的最优个体,并提取整个种群所包含的最优解所在方向的信息,对整个种群进行模式搜索,算法的步骤如下。步骤1:生成初始种群X1,确定各个参数的值。步骤2:对于第G代种群XG,根据每个个体的适应度函数值,挑选出一个最优的个体xGbest。步骤3:将第G代种群分成s个大小相等的子种群X1G,X2G,…,XsG。步骤4:对于s个子种群,分别采用s种不同的差分策略执行变异操作,生成s个变异后的种群步骤5:执行交叉操作。分别对s个子种群分别执行交叉操作,生成s个交叉后的种群U1G+1,步骤6:将s个种群合并成一个种群UG+1,并执行竞争操作生成第G+1代种群XG+1。步骤7:对种群XG+1进行模式搜索,得到模式搜索后的种群XG+1。步骤8:G=G+1,重复式(2)～式(7),直到满足算法的终止条件或G>Gmax。6de与cde的算法比较为了验证算法的有效性,对经典的测试函数,分别用本文提出的CCDE和DE来求解函数的最优值。所选取的测试函数为Rastrigrin函数:这是一个具有多个局部最优点的多峰函数,其局部极小点成正弦坡度分布,它在{xixi∈(-5.12,5.12),i=1,2,,D}内大约有10D个局部极小点,当且仅当x=(x1,x2,,xD)=0时,其全局最小值为0。分别用DE和CCDE进行运算。其中,种群规模设为100;子种群个数选为5;变异算子F设为0.6;交叉算子CR设为0.3;最大迭代次数为2500;测试函数的变量维数为20;搜索空间门限值设为10-4,即当f(x)≤10-4时,即认为该算法已达到最优解。为减少偶然性共运行10次,每次运行时两种算法的初始种群都相同,对于DE分别采用5种不同的策略进行测试。各代的最优适应值(为10次的平均值)随代数的变化如图1所示。由图1可以看出,CCDE的寻优速度和寻优质量均优于DE。两种算法在10次运行中所得到最优解的次数、最小代数、平均代数、平均最优适应度值如表1所示。由表1可以看出,在10次的运行过程中CCDE有10次得到的最优值小于搜索空间的门限值,达到最优;而DE严重依赖于所选取的差分策略。CCDE在10次的运行中达到的平均最优适应度值为0,远远低于5种DE的平均最优适应度值。从图1和表1可以看出,本文所提出的CCDE在搜索性能和搜索质量上远远高于DE。74生理和色谱分析精对苯二甲酸(PTA)是合成聚酯纤维和塑料的重要原料,主要用来合成聚酯的中间体苯二甲酸乙二醇酯(PET)。目前世界上约80%的PTA采用美国的AMOCO工艺生产,其主要工艺路线分为对二甲苯(PX)氧化反应过程和对苯二甲酸(TA)加氢精制过程两单元。在PX氧化生成TA过程中,对羧基苯甲醛(4-CBA)是氧化反应的一个重要中间产物,它能与氧化单元产品粗对苯二甲酸(CTA)共结晶而随CTA产品析出。4-CBA含量过高将使产品着色,严重影响产品品质;4-CBA含量过低,则氧化过度,燃烧损失严重。因此应当将TA产品中4-CBA含量稳定在一个合适的水平。由于在氧化反应器中,4-CBA的测量通常都是在经过反应器、结晶器、水洗、干燥后的TA产品中进行采样测量;此外,TA中4-CBA含量的测量采用的是色谱分析,具有严重的滞后性。因此,必须开发4-CBA含量软测量模型,能够实时预报当前反应状况下的4-CBA含量,以克服人工分析值的滞后问题,为产品质量的实时控制提供依据。7.14cta产品的表征在生产过程中4-CBA含量是无法实时测量的,只能人工取样分析。由于人工分析值不可避免存在延迟,这为实时、有效地控制CTA产品的4-CBA含量带来困难。通过对氧化反应生产过程进行分析发现,在保证进料中对二甲苯浓度和第一结晶器尾氧浓度不变的情况下,CTA产品中4-CBA含量m4-CBA(质量分数)是氧化反应器进料流量Fm和第一结晶器空气流量Fair的函数,并有式中,ˆm4-CBA是4-CBA含量软测量模型估算值;α、β、γ、χ、φ是4-CBA含量软测量模型待估参数,可通过采集不同生产工况下氧化反应器进料流量Fm,第一结晶器空气流量Fair以及对应的CTA产品中4-CBA含量m4-CBA,形成样本进行估计。7.2优化目标函数及仿真结果设采集样本容量为l,第i个样本为Fmi、Fiair、mi4-CBA。在模型参数已知时,由模型式(15)可计算CTA产品中4-CBA含量mi4-CBA的估算值mˆi4-CBA,它与mi4-CBA的相对误差绝对值为所有样本数据的相对误差平方和均值为估计模型参数的原则就是使式(17)的相对误差平方和均值E达到最小。式(17)即为优化的目标函数的具体函数。用CCDE估计式(15)的5个模型参数,样本从实际生产过程中采集,共采集了462组数据,随机挑选其中345组作为样本数据,即l=345,剩余的117组数据形成校验样本。算法的参数设置为:NP为200;F为0.6;CR为0.3;最大迭代次数为1000;以式(17)的相对误差平方和均值E作为目标函数,算法进行参数估计得到的结果:α为0.101055;β为70.89833;γ为0.594662;χ为1494.785;φ为0.173599。应用4-CBA软测量模型对校验样本进行预测,以CTA产品中4-CBA含量预测值为横坐标,以其实际值为纵坐标作图,得到的结果如图2所示。图2中,有一个样本点有较大偏差,通过工艺分析,该样本为粗差数据;除此外,其他样本点分布在对角线的两侧,即模型预测值与分析值一致。可以看出,用CCDE对4-CBA软测量模型进行参数估计,所得到的预测结果比较好,模型能良好的预测CTA产品中4-CBA含量。CCDE用于4-CBA软测量模型得到的最优目标函数值和预测相对误差平方和均值如表2所示。8cde的应用CCDE利用协同进化的思想,将种群分解成不同的子种群,每个子种群采用不同的差分策略进行独立的差分和交叉操作,再将各个子种群合并成一个种群,并根据每个个体的适应度值挑选出最优个体;引入了多元回归分析和模式搜索算法,对于整个种群,利用最小二乘法求得种群的寻优方向信息,并以此来指导种群中的每一个个体进行模式搜索,提高了算法的搜索能力。仿真研究和在PTA氧化反应4-CBA含量软测量模型参数估计中的应用表明:CCDE具有较优的搜索性能,利用其建立软测量模型,能较准确地预测CTA产品中4-CBA的含量,可以为PTA氧化反应过程操作优化提供指导。符号说明b——回归系数E——样本数据相对误差平方和均值F——变异算子Fm——氧化反应器进料流量,kg/hf(G