混合进化算法（精选九篇）
混合进化算法 篇1
电力系统无功优化可以有效地改善电力系统的电压质量,减少系统损耗和提高电压稳定性。无功优化的基本内容是在满足各种约束条件下利用无功控制手段,如控制发电机和无功补偿设备的无功出力及可调变压器的分接头等,提高电压水平,降低系统有功损耗。在数学上,它是一个复杂的多目标、多约束、非线性、非连续、混合整数优化问题。传统的数学优化方法,如线性规划、非线性规划、二次规划、混合整数法等,各自都有一定的优越性和适应性,但是这些方法需要假设各控制变量是连续的,而且要求目标函数可微,求解时间很长,易产生“维数灾”等问题。近年来随着计算机技术及人工智能技术的发展,产生了遗传算法GA(genetic algorithm),粒子群算法PSO(particle swarm optimization)等一系列智能优化算法用以解决电力系统优化问题,并且取得了很大的进步。
1995年Rainer Storn和Kenneth Price提出的微分进化算法(differential evolution algorithm,以下简称DE算法)是一种实数编码的基于种群进化的全局优化算法。己被证明在求优过程中具有高效性、收敛性、鲁棒性等优点[1~7]。DE基本算法的核心思想是利用随机偏差扰动产生新的中间个体。其产生中间个体的方式决定了DE算法在许多问题上都有很好的收敛表现,但搜索速度则相对缓慢,如果优化问题是计算成本很高即每计算一次目标函数值都需要很长时间的问题,那么过多次数的计算目标函数值就会使得算法不可行。因此减少算法收敛所需目标函数评价次数和收敛时间就具有很强的现实意义。
本文根据微分进化算法的搜索机理,深入分析了变异算子产生对算法的影响,并将父代与子代进行了合群处理来提高进化速度。提出一种提高算法全局搜索性能的改进算法,并通过对IEEE 30节点系统进行了仿真计算,并与单纯的微分进化算法、粒子群算法的优化结果进行比较,结果表明该算法具有收敛速度快、鲁棒性好、计算精度高等特点。
1 无功优化的数学模型
电力系统无功优化问题是一个多变量、非线性、多约束的组合问题,其控制变量既有连续变量(如节点电压),又有离散变量(有载调压分接头挡位、补偿电容器的投切组数),使得优化过程十分复杂。进行无功优化计算一般要对发电机端电压、可调变压器变比、节点补偿无功做综合调整,综合考虑目标函数和约束条件,以下式做为群体优化的目标函数:
式中:λ1、λ2分别为违反电压约束和发电机无功出力约束的惩罚因子;α、β分别为违反节点电压约束和违反发电机无功出力约束的节点集合;Vilim、Qilim分别为节点i电压和无功的限值;Vimax、Vimin分别为节点电压iV的上限和下限;Qimax、Qimin则分别为发电机节点的无功出力iQ的上限和下限。并且满足如下约束方程:
式中:x1∈Rn且x1=[VG,KT,QC]为控制变量,分别指发电机机端电压、无功补偿容量和有载调压变压器变比;x2∈Rn且x2=[VL,QG,Pref]为状态变量,分别是负荷节点电压、发电机无功出力和平衡节点的有功出力;Npq是所有PQ节点的集合;SL是支路通过的功率。
2 微分进化算法及改进
2.1 基本DE算法
2.1.1 初始化
DE算法首先在搜索空间内随机产生初始群体,然后通过将群体中两个成员间的差向量增加到第三个成员的方法来生成新的个体。如果新个体的适应度值更好,那么新产生的个体将代替原个体。通常,初始种群的生成方法是从给定边界约束内的值中随机选择,覆盖整个参数空间。设第i个体Xi=(xi,1,xi,2,…,xi,n),n为问题解空间的维数,初始种群S={X1,X2,L,XN p},Xi∈Rn为个体的集合。一般个体向量Xi的各个分量按下式产生:
式中:xi,j、xi,jmax、xi,jmin分别为个体向量Xi的第j个分量的上限和下限。
2.1.2 变异
对于第k+1代每个目标向量Xik+1,基本DE方法变异向量Vik+1=(vi1k+1,vi2k+1,…vink+1)产生方式为
其中:xkr1,j、xkr2,j、xkr3,j是从第k代除Xik之外的个体中随机选出的3个不同向量的j分量,所以DE种群数量必须大于等于4以满足上述要求,系数F≤1为控制微分量的参数。
2.1.3 交叉
为增加干扰参数向量的多样性,在DE算法中引入交叉操作,则中间向量由变异向量和源向量生成,其各个分量按下式计算
式中:qj是从(1,n)中随机选择的一个整数,用以保证本次操作必须有一位数经过交叉;ηj∈(0,1)是针对第j维分量随即选择的控制参数,交叉因子CR∈(0,1)为算法参数,需要事先确定,它控制着种群的多样性,帮助算法从局部最优解中脱离出来。
2.1.4 选择
在标准DE方法中,使用的是一种“贪婪”选择模式:当且仅当新个体的评价函数值更好时,才被保留到下一代群体中;否则,父代个体仍然保留在种群体中,再一次作为下一代的父向量。
2.2 DE算法的改进
2.2.1 合群处理
由前面对基本微分进化算法的介绍可知,进化是基于两个群体进行的,分别是父代群体和子代群体。具体过程就在父代群体里随机产生差异向量,对父代群体中的每个个体进行变异和交叉操作产生中间个体,再通过选择操作决定是保留原个体还是采用中间个体。再由子代群体作为父代群体重复上述操作,周而复始完成整个进化过程。显然这个过程存在着时间和空间的浪费。现由父代群体和子代群体两个群体的进化改为一个群体的进化。群体中对每个个体进行变异和交叉操作产生中间个体后立刻与原个体比较,如果符合要求立即替换掉原个体。这样在对下一个个体进行变异操作时,所用到的差异向量就有可能来自刚生成的新个体。新个体的优良基因将在当前群体就发挥作用,而不必留至下一代群体里才发挥作用,使得进化速度在一定程度上得以提高。
2.2.2 混合策略
DE算法还有一些其它的策略,可以用符号DE/X/Y/Z来区分,其中X是确定将要变化的向量,X是Rand或Best分别表示随机在群体选择个体或选择当前群体中的最好个体;Y是需要使用差向量的个数;Z表示交叉模式,当Z是bin表示交叉操作的概率分布满足二项式形式,当Z是exp表示满足指数形式。
一般来说,如果变异操作中的基点向量是随机抽取的,则算法全局收敛性好。不易陷入局部最优。但收敛所需目标函数评价次数和收敛时间也偏大;如果变异操作的基点向量选择了当前种群中的最优个体,则收敛速度相对较快,但搜索成功率则不高较易陷入局部最优。
基于以上思想,本文提出了基于混合优化的微分进化改进算法(hybrid Optimization differential evolution HODE)。即如果按照DE/rand/1/bin优化策略所得候选个体的适应度相对于当前个体没有得到改善。则利用DE/best/1/bin优化策略获得一个新的候选个体。并重新进行选择操作。
3 基于HODE算法的无功优化
HODE算法应用于无功优化问题时可理解为:电力系统环境下的一组初始潮流解,受各种约束条件约束,通过目标函数评价其父代、子代个体优劣,评价值低的被抛弃,评价值高的将其特征迭代至下一轮解,最后趋向优化。
无功优化问题中既包含连续变量,又包含离散的整数控制变量。HODE算法处理混合整数优化问题的一般方法是将个体归整为相近的整数,本文通过映射编码和取整的方法对离散变量进行处理。
基于HODE算法的无功优化流程图如图1所示。
4 算例分析
本文采用IEEE 30节点来验证HODE算法的优化效果。为了验证算法的有效性,分别与标准粒子群(PSO)、标准微分进化(DE)进行了比较。运用Matlab7.0进行编程计算的结果如下。
IEEE 30节点系统包括6台发电机、4台有载调压变压器,初始状态∑Pg=2.918 2、∑Ploss=0.083 24,节点和支路数据参见文献[9]。
控制参数的选择对DE算法的搜索性能有较大的影响,根据经验种群数量NP可选择在5~10倍的问题维数之间。较大的F和CR增加了算法跳出局部最优的可能性,如果F和CR过大则算法的收敛速度明显降低,过小则可能陷入局部最优。因此本文将种群数量NP设置为50,比例因数F为0.5、交叉因数CR为0.7。最大的迭代次数为100。优化结果如表1。
由表1和表2可以看出采用HODE算法进行优化后系统Ploss=0.067 32,网损下降率为18.55%。且所有约束条件均得到满足。为验证算法的稳定性,对该算例进行100次计算,由图2可以看出系统网损在0.067 32小范围内上下波动。因此该算法稳定且具有较强的鲁棒性。
由图3可见,HODE算法在开始几代下降速度很快,显示了算法寻优机制的有效性和优越性,同时,合群处理和变异算子的混合产生策略,使得算法拥有更快的收敛速度和强大的跳出局部最优的能力。从结果看出HODE迭代35次就已达到较精确的水平,因此,本文提出的基于混合优化微分进化方法应用于电力系统无功优化中是比较可行的一种方法。
5 结论
本文对微分进化算法的变异算子的产生采用不同的策略,加快了算法的搜索效率,并在进化过程中采取了父代和子代合群处理,进一步提高了算法的全局搜索能力,通过对IEEE 30典型测试系统的计算分析表明,本文提出的算法在解决电力系统无功优化问题上具有快速、高效、准确的优点。因此,该算法对求解大规模电力系统无功优化问题将有重要的启发意义。
参考文献
[1]Rainer Storn,Kenneth Price.Differential Evolution—a Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[2]梁才浩,段献忠.基于差异进化和PC集群的并行无功优化[J].电力系统自动化,2006,30(1):29-34.LIANG Cai-hao,DUAN Xian-zhong.Parallel Reactive Power Optimization Based on Differential Evolution and PC-cluster[J].Automation of Electric Power Systems,2006,30(1):29-34.
[3]Chiou J P,Chang C F,Su C T.Variable Dcaling Hybrid Differential Evolution for Solving Network Reconfiguration System[J].IEEE Trans on Power Systems,2005,20(2):668-674.
[4]Lin Y C,Hwang K S,Wang F S.Plants Scheduling and Planning Using Mixed-integer Hybrid Differential Evolution with Multiplier Updating[A].In:Proceedings of IEEE Evolutionary Computation Conference[C].La Jolla Perth:2000.593-600.
[5]Qing A Y.Dynamic Differential Evolution Strategy and Applications in Electromagnetic Inverse Scattering Problems[J].IEEE Trans on Geoscience and Remote Sensing,2006,44(1):116-125.
[6]Storn R.Designing Nonstandard Filters Differential,Evolution[J].IEEE Signal Processing Magazine,2005,22(1):103-106.
[7]冯琦,周德云.基于微分进化算法的时间最优路径规划[J].计算机工程与应用,2005,41(12):74-75.FENG Qi,ZHOU De-yun.Time Optimal Path Planning Based on Differential Evolution Algorithm[J].Computer Engineering and Application,2005,41(12):74-75.
[8]李颖,徐桂芝,等.微分进化算法在头部电阻成像的应用[J].中国生物医学工程学报,2005,24(6):672-675.LI Ying,XU Gui-zhi,et al.Application of DE Algorithm for Brain Imaging Using EIT[J].Chinese Journal of Biomedical Engineering,2005,24(6):672-675.
[9]张伯明,陈寿孙.高等电网络分析[M].北京:清华大学出版社,1996.
基于改进差分进化算法的无功优化 篇2
关键词：差分进化算法；改进；线损；无功优化
中图分类号：TM714.3 文献标识码：A 文章编号：1674-1161（2014）12-0022-03
差分进化算法是近几年来新兴的基于群体智能的随机优化算法，其原理简单，有较强的全局收敛性，适用于解决一些复杂的优化问题。目前差分进化算法已经广泛应用于电力系统的无功优化领域，并取得了较好的效果。但是该算法也存在过早收敛、易于陷入局部最优解、收敛速度慢的缺点。因此，本研究提出一种改进的差分进化算法，将群体随机动态分成多个子群体，同时采用自适应控制参数策略，以克服早熟问题，跳出局部最优解。并在IEEE 57节点测试系统上对该算法的可行性进行验证，证明该改进差分进化算法具有较高的收敛性和搜索精度，且具有较强的跳出局部最优解能力。
1 基本差分进化算法（DE）
基本差分算法是通过对种群中的个体进行变异、交叉和选择操作来实现择优进化的算法。其中：变异是指把种群中两个个体的加权差向量加到第3个个体上产生中间个体的过程；交叉是指将中间个体与当前个体按照一定的规则混合产生新的试验个体的过程；选择是指在试验个体的目标函数值小于当前个体的目标函数值的前提下，试验个体替代下一代当前个体的过程。
2 改进差分进化算法（IDE）
该改进算法将种群中的个体随机动态分成多个子种群，以增强个体间的信息交换，保持解的多样性；变异尺度因子F与交叉概率CR采用自适应机制，以平衡局部搜索与全局搜索。该算法的主要特点描述如下。
2.1 动态交换与多群体分组
为增强个体之间的信息交换，提高种群的多样性，提出将种群个体随机动态分成多个子群体小组。在每一次迭代中，种群个体被随机分成3个子群体小组；每个子群体小组中的个体按适应度从好到坏降序排列，则可得到3个子群体小组中各自的最好个体；用得到的3个最好个体更新每个子群体小组中倒数3个相对差的个体，完成一次个体间的信息交换。被分隔的3个子群体小组重新合并为1个种群，在下一次迭代中将重新随机划分为3个子群体小组，再次得到每个子群体小组中最好个体，将得到的3个最好个体与上一次迭代中得到的个体进行比较，保留优秀个体。这样可以实现不同群体间动态交换信息和增强差分进化算法跳出局部最优解的能力的目的。
2.2 自适应变异尺度因子F
自适应变异尺度因子F是根据差分向量变化的幅度来自适应调整的。如果差分向量的两个不同个体在搜索空间中距离很远，则生成的差分向量值很大，F应取较小的值，以提高全局搜索的能力；反之，如果差分向量的两个不同个体在搜索空间中距离很近，F应取较大的值。F自适应策略可表示为：
Fkji=Fn+（Fm-Fn） （1）
式中：Fkji为当前代k所处子群体j中第i个个体变异尺度因子；Fm和Fn分别为变异尺度因子的上、下限；fkja，fkjb和fkjc分别为当前代k所处子群体j中更新第i个个体F值时随机选择的3个个体中最优、次优和最差的个体适应度。
2.3 自适应交叉概率CR
自适应交叉概率CR通过对比当前代所处子群体中个体适应度与该子群体平均适应度来自适应调整CR值。在当前代所处子群体中个体适应度不小于该子群体的平均适应度，即个体适应度相对较差的情况下，CR采用式（2）中（a）的更新策略；在当前代所处子群体中个体适应度小于该子群体的平均适应度的情况下，CR采用式（2）中（b）更新策略。
式中：CRkji为当前代k所处子群体j中第i个个体交叉概率；CRm和CRn分别为交叉概率上、下限；fkji为当前代k所处子群体j中第i个个体的适应度；，fkjmin，fkjmax分别为当前代k子群体j的平均适应度、最小适应度和最大适应度。
CRk-1jix是随着进化代数k的不同而逐代更新的，其更新策略为：
3 仿真与分析
为了验证改进差分进化算法（IDE）的有效性，测试系统对IEEE 57节点进行了无功优化计算。利用仿真工具MATLAB 7.0，分别与基本差分进化算法（DE）、常规遗传算法（GA）、自适应遗传算法（AGA）、全面学习的粒子群优化算法（CLPSO），以及带惯性权重的粒子群优化算法（PSO-w）进行比较。为了验证IDE性能，比较的指标包括：有功网损最好值（Best（p.u.）），标准方差（Std.Dev），有功网损平均值（Mean（p.u.）），有功网损节省率（Psave）。表1列出了IEEE 57节点测试系统无功优化的系统有功网损结果，图1给出了基于各种算法的无功优化的系统有功网损收敛曲线。
由表1可以看出：相较其他几种算法，IDE能够搜索到全局最优或接近全局最优解，获得的有功网损最好值、有功网损平均值更小。同时，基于IDE求解的IEEE 57节点测试系统的最优网损相比系统的初始网损下降了14.654 7%，比其他算法节省率Psave高，尤其在较大系统中IDE优越性更明显。从标准方差（Std.Dev）的角度来看，IDE的方差也小于其他算法，说明IDE更具稳定性。
图1显示了基于各种算法的系统有功网损Ploss随迭代次数变化的收敛曲线，充分验证了表1中结果的正确性；同时也充分表明了IDE不仅能在寻优初期保持良好的多样性，而且在寻优后期也能具有良好的收敛性。
4 结论
本研究提出了改进差分进化算法，并将该算法应用于电网无功优化问题中。通过对IEEE 57节点测试系统的仿真，证明该算法能够在保证算法多样性的基础上，具备良好的收敛性和较强的稳定性，是解决电网无功优化问题的有效工具。
参考文献
[1] 袁晓辉，苏安俊，聂浩，等.差分进化算法在电力系统中的应用研究进展[J].华东电力，2009，27（3）：135-148.
[2] 张勇军，任震，李邦峰.电力系统无功优化综述[J].电网技术，2005，19（1）：23-34.
[3] 刘波，王凌，金以慧.差分进化算法研究进展[J].控制与决策，2007，18（5）：521-531.
[4] 赵树本，张伏生，钟继友，等.自适应差分进化算法在电力系统无功优化中的应用[J].电网技术，2010，34（6）：123-145.
[5] A.NOBAKHTI，H.WANG.A simple self-adaptive differential evolution algorithm with application on the ALSTOM gasifier[J].Applied Soft Computing，2008，4（1）：298-310.
混合进化算法 篇3
1 网络学习控制系统的调度优化
1.1 问题描述
为了达到更好的控制性、抗干扰性、适应性的目的,本文引入了如图1所示的双层网络学习控制系统体系结构[3,4]。
图中Ci,Ai和Si分别是控制器、作动器和传感器。
1.2 网络学习控制系统的调度
多目标优化方法是动态调整每一循环的取样,以最小的带宽达到优化控制性能[5]。对于每一控制循环,带宽bi和取样周期ti之间的关系由式(1)给出:
式中mi是完成每一个闭环操作传送信息所花费的时间。
对于所有的轴,如果平衡点(或者基准信号)考虑为零,在ℜn向量空间中状态向量的欧几里德范式xi=(xi,1,⋯,xi,n)T是度量在任意给定时间t>0每一轴离开平衡点的距离。这个度量定义为每个控制器针对实时带宽分配在每一次取样后将提交给带宽管理器的反馈信息:
在允许的可变取样周期范围内(动态带宽变化边界)以及无过载网络条件下,系统IAE和取样周期之间的近似线性关系可以是:
n控制被分配网络带宽b1,b2,⋯,bn的循环。减少带宽消耗以及优化带宽受限NLCS系统的多目标优化问题可被描述为:
式(4)描述系统控制性能的优化问题,mi是信息传输时间,而参数αi和βi依赖于对应控制循环中的控制器和装置。式(5)描述带宽消耗的优化问题,目标是在最好系统性能条件下降低带宽需求。式(6)是NLCS中带宽的全局可用性,其中Ud是可用的全局带宽资源,而b=[b1,b2,⋯,bn]T,C=[1,1,⋯,1]T。式(7)是对每一个控制循环动态分配带宽的允许的变化范围,也就是确保取样周期上、下行双向系统稳定用权重法混合式(4)和式(5)得到多目标优化问题求解的单目标函数:
式中γi是权重系数,用于平衡目标函数J1和J2。
为求解以上优化问题,将约束优化转换为无约束优化,建立如下拉格朗日函数:
根据KTT条件,如果b*=[b1*,b2*,⋯,bn*]T是优化问题的最优解,则:
式中:∇J是梯度向量,λ,λa=[λ1,λ2,⋯,λn]T和λb=[λn+1,λn+2,⋯,λ2n]T是拉格朗日乘子。
节省更多有限的网络资源,应用如此规则:如果eieith,则bi=bimin,i=1,2,⋯,n,其中eith表示第i个控制循环的一个足够小的误差阈值,于是满足所述规则的优化问题变为:
2 基于HQCEA方法的多目标调度优化方法
2.1 HQCEA描述
量子计算[6,7,8]中的基本信息单元是量子比特。一个量子比特是一种双级量子系统,且可以用一个二维希尔伯特空间(α,β∉₤)的单位向量表示:
用0﹥和1﹥表示基本状态,采用刃表达量子态向量。双级量子系统通过基本状态的叠加态描述,而双级经典系统只能是基本状态0或1中的一个。
量子比特的状态可以通过量子门操作改变。受量子计算概念的启发,HQCEA方法设计有新的Q比特表达、作为变异操作算子的Q门以及观察过程。作为n个Q比特的序列的单一Q比特定义为:
式中j=1,2,⋯,n。
HQCEA区别传统量子进化算法的下列要素组成:
HQCEA产生沿父本搜索空间分布的子群,增加函数求解空间的多样性以及有效地避免陷入局部最优解。因此这一算法便可以获得在深度搜索和广度搜索之间的平衡并提高其函数求解能力。
HQCEA能够应对的克隆复本是动态的,而传统方法只能应对固定的。
式中:j=1,2,⋯,n;N是每个个体在第t次迭代时的克隆级数,而种群的克隆级数是:
2.2 HQCEA求解多峰连续函数优化问题的程序
HQCEA中的每一个染色体的单个体将产生其自己的动态克隆以建立新的子群[7,8];接着每个新染色体成为低码率下的变种;最后HQCEA将使用随机策略更新整个种群。t=0时,初始化Q(t)={q1t,q2t,⋯,qnt}。观察Q(t)的状态,得到克隆的个体R(t)以及新的种群R*(t)。评价R*(t)并且将最优解存入存储空间。结果为非零时,种群通过Q门更新以得到新的种群。HQCEA使用Q门,Q比特作为变异步骤得到更新。在HQCEA中使用如下的旋转门作为Q门:
式中:Δθ是每个Q比特取决于其信号的转向0或1状态的旋转角。
3 模拟结果
HQCEA方法在NLCS中的模拟结果显示该算法是有效的[9,10]。HQCEA及控制系统的参数如下:每个群包含50个个体,每个个体用20比特编码。NLCS中的全局可用带宽为10,终止代数为40。当控制在不同的随机扰动下循环时,HQCEA方法、无优化结果和传统量子进化算法(QEA)比较,积分绝对误差(IAE)和平均网络利用(MNU)如表1所示。采用基于HQCEA的调度方法的传输周期彼此更为接近[11,12]。这表明HQCEA方法节省了尽可能多的有限网络资源,并且使得系统控制性能进一步优化。
4 结论
网络控制系统(NCS)是其传感器、作动器和控制器通过通信网络闭合的控制系统,正在成为近期控制理论和控制应用研究者的关注焦点。NCS由于具备包括更有灵活性的模块化系统设计、低实施成本、强大的系统诊断能力及易于维护等各种优势,已经被广泛地应用于控制领域。
摘要：提出了一种针对双层网络学习系统体系结构的新的混合量子克隆进化算法(HQCEA)。这种特殊的体系结构能达到更好的控制性能、更好的抗干扰能力并增强了对各种环境的适应性,优化了网络传输周期,增强了函数求解空间的多样性,并能有效地避免陷入局部最优解。因此,网络资源得到合理分配以减少延迟和丢包,改进带有通信约束的网络利用。根据结果表明:HQCEA方法克服了传统QEA方法的缺点,而且能够在更短的时间内成功处理多峰连续函数以及复杂装置。
混合进化算法 篇4
发动机不平衡惯性力和转矩波动是引发汽车振动和噪声的一个最主要振源，是降低乘坐舒适性的主要原因。发动机悬置系统除支撑发动机和变速器等部件外，还隔离发动机振动向车架的传递，并减轻路面与轮胎对车身激振所引发的动力总成振动［1］。因此，悬置系统设计的优劣直接关系到发动机振动向车体的传递，影响整车的NVH性能。发动机悬置系统的优化设计旨在合理选择悬置参数(如安装位置、角度、刚度和阻尼等)，以有效降低整车振动及噪声水平，并且保证由于各种可控和不可控因素的影响发生微小变差时，都能保证悬置系统的稳健性［2、3］。
将稳健设计思想应用于发动机悬置系统的解耦优化设计中，基于悬置系统振动解耦的能量分布建立优化目标函数，以悬置刚度参数为设计变量，根据整车性能要求添加约束，综合运用遗传算法、免疫进化算法，对悬置系统进行优化，同时利用Monte Carlo方法进行稳健分析。
1 发动机悬置系统数学模型
将车架和动力总成视为刚体；假定橡胶件的弹性是线性的，并可忽略不计其阻尼，建立如图1所示的六自由度动力总成四点悬置模型［4］。
图中O-XYZ为发动机动力总成质心坐标系，O为动力总成质心，X轴平行于发动机曲轴轴线指向发动机前端，Z轴通过发动机总成质心竖直向上，由右手定则得出Y轴；前悬置点1、2，后悬置点3、4；u、v、s为悬置的3条弹性主轴方向。则可得广义坐标 q={x，y，z，θx，θy，θz}。
由拉格朗日方程可以得到悬置系统的振动方程为：
式中：M为系统的质量矩阵；C为系统的阻尼矩阵；K为系统的刚度矩阵；q为广义坐标；F（t）为系统所受的激振力。
方程可简化成：
由式（2）可得动力总成悬置系统的固有频率ωj（j=1，2，3，4，5，6）和固有振型 φ。
2 能量解耦法
通常六自由度汽车动力总成悬置系统的6个固有振型在多个自由度方向上是耦合的，在某个自由度方向受到激振都可能引起耦合振动，这样会导致共振频带加宽，共振的机会加大。能量解耦法是在得到悬置系统的6个固有模态后，根据能量分布判断动力总成悬置系统是否解耦及其解耦的程度，然后通过修改悬置参数提高系统在某些方向上的解耦率［5，6］。
当系统以第j阶模态振动时，定义能量分布矩阵的第k行l列元素为：
式中：k，l，j=1，2，3，4，5，6；φ（k，j）、φ（l，j）分别为第 j阶振型的第k个和第l个元素；M（k，l）为系统质量矩阵的第k行、第l列元素；ωj为第j阶固有频率。
当系统以第j阶模态振动时，第k个广义坐标分配能量占系统总能量的百分比为：
若 Qa（j，k）=100%，则系统做第 j阶振动时能量全部集中在k对应的广义坐标上，此时该模态振动完全解耦。
3 优化模型
3.1 优化方法
考虑到在实际的生产与使用过程中悬置垫参数都有很大的可变性，在悬置参数的优化设计中需要结合稳健设计的思想，免疫进化算法既保证最优解的高解耦率，还能保证最优解的可行稳健性。算法流程图如图2所示。
遗传算法的编码方式采用所有变量的二进制编码串起来，组成24×n的二进制串，变异操作时分为三类，变异概率分别为 0.00，0.08，0.45，记忆种群中解的个数为20，进化代数为60。
3.2 设计变量
综合车架和动力总成设计限制，本文以悬置点处悬置橡胶的各向主刚度值 K=（k1，k2，……，kn）（n为悬置刚度个数）为设计变量。
3.3 约束条件
（1）刚度约束：既要限制发动机的位置移动;又要使系统具有较好的隔振性能，即Kimin≤Ki≤Kimax（i=1，2，…n）。
（2）频率约束：悬置系统的最大固有频率须小于发动机自身激励频率f的为了避开路面激励频率，悬置系统最小频率应大于5 Hz；各阶频率之间间隔应大于 0.5 Hz。
3.4 目标函数
作者以实现悬置系统六自由度能量解耦最大为目标进行优化设计。优化函数为：
式中：Qi为各自由度能量百分比；αi为加权因子。
3.5 优化实例
针对某款客车，发动机为六缸四冲程。四点悬置，平置式，对称分布。客车动力总成参数如表1所示，各悬置点主刚度值如表2所示。
表1 动力总成系统参数表
由以上数据可计算出该悬置系统的6个固有频率和各频率下的能量矩阵，如表3所示。
表3 优化前悬置系统固有频率和能量分布
根据表3中的数据可以看到，悬置系统固有频率满足频率约束条件，但是一阶与二阶固有频率间隔小于0.5。从能量分布上来看，除横向（y）自由度外，其余各自由度方向能量分布小于80%，各自由度之间存在严重的振动耦合。
采用免疫进化算法对以上悬置系统在matlab环境下进行稳健性优化设计。从最终的记忆种群中提取最优解结果并计算其固有特性，如表4、表5所示。
表4 优化后各悬置点主刚度值
表5 优化后悬置系统固有频率和解耦率
由表5可知，最优解的频率都在合理的频率约束的范围内，且间隔都大于0.5。各自由度上的能量分布，除了垂向（z）与俯仰（θy）方向分布较低外，其余自由度能量分布均大于95%。与原系统相比，在六个自由度上的振动能量分布均有显著提高，且平均提高 18.3%。 对于垂向（z）与俯仰（θy）自由度还可以通过改变悬置系统各悬置点的位置以及悬置安装角大小进一步优化。
4 基于Monte Carlo的稳健分析
在一系列生产与使用一段时间后的悬置垫样品中随机抽样检测发现，各向悬置主刚度基本上在±12%范围内波动，且分布曲线成正态分布。建立优化目标函数的响应面模型，以各向主刚度为服从正态分布相互独立的随机变量。优化前的悬置刚度变量分布为：U1～N（453，54.362），经过 2 000 次随机实验分析，通过计算可以得出响应面模型的概率分布为：P1～N（2.4859，0.80612），目标函数的标准差为32.43%。
根据设计要求，设计变量出现随机变化时其产品性能变化最好不超过5%，此响应面的变化明显超出了允许值，稳健性较差。
对优化后悬置系统分析，经过2 000次随机实验分析，响应面模型的概率分布为：Q1～N(0.856 1，0.023 82），标准差分别为：2.78%，小于允许值，效果明显。优化前后响应面模型概率分布和响应面拟合正态曲线分别如图3、图4所示。
采用Monte Carlo方法分别对优化后的六个自由度上的解耦率建立响应面模型进行分析，其目标函数是基于单自由度解耦率建立的，消除彼此的影响，其响应面模型概率分布如图5所示。
计算可得，图5所示的各自由度解耦率所构成响应面模型的标准差分别为：0.94%、0.6%、0.36%、3.13%、0.6%、3.17%，各自由度都有很高的稳健性。
5 结论
通过把遗传算法、免疫算法相结合，对汽车动力总成悬置系统的的解耦优化设计表明，基于遗传进化算法可以使发动机在怠速下达到比较满意的解耦程度；通过Monte Carlo验证优化解还能保证悬置系统具有较高的稳健性，能够大大的提高产品质量。在实际的生产中有着很大的实际意义。
［1］张武，陈剑，夏海.基于灵敏度分析的发动机悬置系统稳健优化模型［J］.汽车工程，2009，31（8）:728－732.
［2］李建康，郑立辉，宋向荣.汽车发动机悬置系统动刚度模态分析［J］.汽车工程，2009，31（5）:457－461.
［3］夏海，高立新，陈剑.基于伪并行遗传算法的发动机悬置系统解耦优化［J］.汽车工程，2008，30（12）：1087－1090.
［4］上官文斌，蒋学锋.发动机悬置系统的优化设计［J］.汽车工程，1992，14（2）.
［5］侯勇，赵涛.动力总成悬置系统解耦设计［J］.汽车工程，2007，29(12)：1094－1097.
［6］梁志荣.数据挖掘中聚类分析的技术方法［J］.电脑开发与应用，2007，20（6）:37－40.
［7］Johnson SR，Subhedar J W.Computer Optimization of Engine Mounting Systems［C］.SAE Paper 79094.
［8］Sorge F.A Simple Model for the Axial Thrust in V－Belt Daves ［J］.Journal of Mechanical Design，1996，l18：589－591.
［9］徐石安.汽车发动机弹性支承隔振的解耦方法［J］.汽车工程，1995，17（6）.
［10］王煦法，张显俊，曹先彬，等.一种基于免疫原理的遗传算法［J］.小型微型计算机系统，1999，20（2）：117－120.
［11］董威.基于Pareto遗传算法的起重机主梁优化设计［D］.大连：大连理工大学，2005.
混合进化算法 篇5
供水调度问题的研究有着非常大意义, 它不仅关系到居民的生活质量, 而且对工业的发展也起着重要的作用, 因此对供水调度系统的要求也越来越高。对供水系统而言, 其主要运行成本为供水泵站的能量费用和由于频繁开关水泵而早成的水泵磨损的维护费用。另外, 在满足最低的运行成本之外, 还需要维持一定的压力服务水平来保证居民的正常生活与社会生产。供水泵站的优化调度是要实现能量费用和维护费用的最小化, 以及水压服务水平的最大化。
本文利用一种基于分布的分解多目标进化算法, 先将供水调度问题分解为若干单目标, 然后根据分布估计的思想对各个单目标建立概率模型, 通过采样产生解。通过这种方法所得解不仅具有较好的多样性和均匀性, 而且明显降低了计算复杂。
1 供水调度系统问题及模型
在供水调度问题中, 在T时间内需要N个水泵。该问题是主要目标是在满足作业约束的条件下, 最小化水供应的成本, 即能量费用和维护费用, 并要最大化水压服务水平, 以保证居民的正常生活和工业的正常运行。
根据对用水量的趋势预测, 将一天的24小时化为几个调度时段, 使用基于分布估计的分解多目标进化算法来求解供水调度优化问题。实践表明, 使用这种方法求解供水调度问题可以在保持解的均匀性与多样性的条件下能够很好降低计算复杂度。
1.1 制水费用和电力费用
undefined
其中, J为供水调度期内划分的时段数, I为水源泵站数, C为换算系数, Si, j为第i泵站第j时段的单位制水费用, 单位为元/m3, Qi, j为第i泵站第j时段的水流量, SPk, j为水泵k在第j时段的单位电费, NPk, j为水泵k在第j时段的开启状态, 其中令开为1, 关为0, HPk, j为水泵k在第j时段的出口压力, QPk, j为水泵k在第j时段的供水量, αk, j为水泵k在第j时段的计算效率, K为泵站内的水泵的总数。
1.2 水泵的维护费用
水泵的维护费用主要来源为水泵频繁开关而造成磨损, 而这很难以量化。这里假设维护费用是随着开关次数的增加而增长, 所以就用水泵的开关次数来代替水泵的维护成本。水泵的开关次数如 (2) 式表示:
undefined
1.3 水压服务水平
在供水调度系统中, 供水管网各节点在满足水压最低服务水平的前提下, 需要维持一定的压力服务水平。因为水压过低会影响居民的正常生活和工业的正常运行, 但是如果水压过高就会造成不必要的浪费甚至会造成曝管, 会很大程度上提高供水调度系统的运行费用。水压服务Φ (i, t) 指标如下所示:
undefined
其中, Pr (i, t) 为第i节点在t时段的最大允许水压;Pa (i, t) 为第i节点在t时段的实际水压。
因为对供水管网而言, 既要保证泵站运行费用和维护费用的最低, 又要保证水压服务水平的最大化。但这两者不可能同时达到最优, 供水调度优化模型就是要实现这二者的平衡。
所以供水调度优化目标为:
undefined
将以上问题综合为多目标优化问题:
undefined
约束条件有以下几点:
(1) 满足管网水力平衡的方程组:
undefined
式中, undefined表示节点的压力向量, undefined表示节点的流量向量, undefined表示管段比阻。
(2) 泵站在时段内的供水能力限制:
undefined
(3) 压力控制点的供水压力要求:
undefined
式中, Pmin (i, t) 为最低的运行的服务水龙头, Pc (i, t) 为第i压力控制节点t时刻的实际供水压力, Pmax (i, t) 为允许承受的最高水压, NN为压力控制点数。
(4) 水泵的调速比范围:
nimin≤ni≤nimax (11)
2 求解供水调度问题的多目标遗传算法
(1) 染色体编码。
在泵站的优化调度中, 水泵的开关为离散型变量, 而变速泵的转速比和调速频率是连续的变量, 在这里使用二进制编码将其离散化。对于变频调速泵, 将频率转化为调速比。
(2) 分解操作。
计算每两个权重之间的欧几里得距离, 为每个权向量选出最近的T个向量作为它的邻居, 并将这T个权向量所控制的群体组成子种群。此时便将多目标问题转换为单目标问题。
(3) 建模操作。
如何建立概率模型方法很重要, 因为是根据模型选择适当的采样产生新的个体。所以概率模型的建立直接影响算法的效率和解的分布性与多样性。而一个号的模型应该具有容易构建, 采样方便并且能够指导种群进化等特征。本文首先利用 (m-1) 维局部主分量分析法划分种群, 使用聚类后的结果来建立PS流形结构的概率模型。
(4) 采样操作。
传统的多目标进化算法利用交叉变异等遗传操作产生新的种群, 在本文中, 利用蒙特卡罗方法, 对概率模型高斯采样获得新个体。因为高斯噪声采样具有旋转不变性, 平移不变性, 线性不变性和尺度不变性等, 在求解多目标问题上占有很大优势。
(5) 选择操作。
采用NSGA-Ⅱ的非支配排序的选择操作。这种操作是一种最优个体保留机制并且有效的保持群体的分布性和多样性的选择方式。这里需要构造偏序集和计算聚集距离。
偏序集就是将父代种群与子带种群的集合P∪Q依据个体之间的Pareto支配关系划分为互不相交的m层Pareto前沿面F1, F2, …, Fm, 并满足一下条件:①∪F∈{F1, F2, …, Fm}F=P∪Q;②∀i, j∈{1, 2, …, m}且i≠j, Fi∪Fj=φ;③F1F2…Fm, Fk+1中的解集直接受Fk的解集支配 (k=1, 2, …, m-1) 。
聚集距离的大小与种群的分布性与多样性有着直接的关系, 通常情况下回保留聚集密度小的个体, 个体的聚集距离是通过计算与其相邻的两个个体子目标上距离差的和来求得。
3 实现供水调度问题的多目标遗传算法过程
算法的具体步骤如下:
(1) 产生N个初始群体P (t) , 初始化外部种群, 设置初始值。
(2) 分解种群。计算每两个权向量之间的欧几里得距离, 为每个权向量选出最接近的T个权向量。由这T个权向量控制的个体组成子群体。
(3) 建立模型。根据分解的子群体建立概率模型, 并根据此概率模型得到新的样本。
(4) 将将父代种群与子带种群的集合依据个体之间的Pareto支配关系划分为互不相交的m层, 并计算聚集距离。每次去除一个聚集密度高的个体, 然后重新计算修剪后种群的个体的聚集距离。
(5) 满足终止准则, 则停止;否则P (t) =P (t+1) , 返回步骤 (2) 。
4 实例与分析
采用改进的基于分布估计的多目标进化算法与水利模拟相结合, 对下面的实例进行计算来验证这种方法的优化性能。
假设某供水系统各水泵的制水费用、电力费用等参数如下表。最小水头25m, 最大水头32m。日用水量预测曲线见图1。
仿真程序用Matlab编制, 种群规模为100, 交叉概率为0.90, 变异概率0.1。图2和图3中给出了某次的典型优化结果。
从图2中可以看出, 随着运行费用的增加, 压力服务水平也逐渐提高。从图2和图3中可以看出, 基于分解的混合多目标进化算法获得了分布较广、较为均匀的Pareto最优解。对于决策人员来说, 可以根据具体情况和个人决策偏好, 从众多Pareto最优解中挑选出平衡最优解。
为衡量基于分解的多目标进化算法的运行效率, 还选用了典型的多目标进化算法NSGA-II对上述问题进行了求解。计算显示, 在相同参数下, MOEA/D的平均运行时间为7.62s, 而NSGA-II的平均运行时间为9.71s, 这表明算法在速度方面的改进效果还是比较明显的。
5 结语
本文中将供水调度问题描述成多目标问题。利用基于分布估计的分解多目标进化算法对其进行求解。首先, 根据基于分解的多目标进化算法思想将多目标问题分解为单目标问题, 使用分布估计算法的思想建立概率模型, 然后, 随机采样产生新的种群, 利用非支配排序方法进行选择得到最优解。根据数值试验表明, 应用这种方法, 可以明显地降低计算复杂度, 提高算法的运行效率和解的分布性、均匀性。
摘要：建立了供水调度模型, 利用基于分解的多目标进化算法, 首先将供水调度问题分解为若干单目标, 然后根据分布估计的思想对各个单目标建立概率模型, 通过采样产生新的个体。利用非支配排序法进行选择, 得到最优解。实验表明, 该算法对求解供水调度优化问题具有较好的多样性和均匀性, 并且降低了算法的计算复杂度。
关键词：供水调度问题,进化算法,分解策略,分布估计
参考文献
[1]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.
[2]吕谋, 张士乔, 赵洪滨.大规模供水系统直接优化调度法[J].水利学报, 2011 (1) .
[3]IVALERMIR B CARRIJO, LUISA FERNANDA REIS R, GOD-FREY A WALTERS, et al.Operational optimization of WDSbased on multiobjective genetic algorithm and operational extrac-tion rules using date mining[C].World Water and EnvironmentalResources Congress, 2004.
[4]G SYSWERDA.Uniform crossover in genetic algorithms[C].Pro-ceedings of The Third International Conference on Genetic Algo-rithms, 1989.
[5]ZHANG QF, LI H.MOEAD:A multiobjective evolutionary algo-rithm based on decomposition.IEEE trans[C].on EvolutionaryComputation, 2007 (6) .
[6]ZHANG QF, ZHOU AM, JIN Y.RM-MEDA:A regularity mod-el based multiobjective estimation of distribution algorithm.IEEEtrans[C].Evolutionary Computation, 2007 (1) .
[7]LAUMANNS M, OCENASEK J.Bayesian optimization algorithmsfor multi-objective optimization[C].The 7th Int’l Conf.on Paral-lel Problem Solving from Nature London:Springer-Verlag, 2002.
[8]KHAN N, GOLDBERG DE, PELIKAN M.Multi-objective bayes-ian optimization algorithm technical report, No.2002009[R].U-niversity of Illinois at Urbana-Champaign, 2002.
[9]DEB K, An efficient constraint handing method for genetic algo-rithms[J].Compute methods Appl.Mech.Eng, 2000 (2) .
[10]ZHOU AM, ZHANG QF, JIN Y, SENDHOFF B, TSANG E.Global multi-objective optimization via estimation of distributionalgorithm with biased initialization and crossover[C].The Genet-ic and Evolutionary Computation Conf, GECCO 2007.NewYork:ACM Press, 2007.
混合进化算法 篇6
优化算法一般是利用梯度信息或者是利用目前比较流行的启发式算法, 求解一定约束下的最优值。基于有部分种群优化算法容易陷入局部最优, 部分收敛速度慢, 不少学者为了提高收敛速度或提高算法精度提出很多改进的方案。本文基于 (Particle Swarm Optimization, PSO) 和 (Differential Evolution Algorithms, DE) 算法的优点和缺点提出一种基于可选择进化方式的新算法, 算法中粒子可以随机选择按照PSO或DE进化方式进化, 以此来提高算法的精度和收敛速度。
2 粒子群算法 (Particle Swarm Optimization, PSO)
粒子群算法 (Particle Swarm Optimization, PSO) [1,2]是1995年美国社会心理学家James kennedy和电气工程师Russell Eberhart共同提出, 其基本思想是模拟鸟类群体行为。粒子群算法采用群体和进化的概念, 根据适应度值进行相应的操作。该算法简单易于实现、参数少、收敛速度快、具有良好的搜索性能, 引起了国内外很多学者关注[3]。算法首先初始化N个个体, 每个个体是一个D维向量, 每个向量分量代表一个飞行方向, 每个个体代表一个位置。每个个体按如下公式初始化, 同时按公式初始化飞行速度。
其中pi代表每个个体找到的最佳位置, pg代表所有个体找到的最佳位置。每个个体每次进化按照如下公式, 向最佳位置靠近。
3 差分进化算法 (Differential Evolution Algorithms, DE)
差分进化算法 (Differential Evolution Algorithms, DE) 是R.Storn和K.Price提出的一种基于群体差异的启发式随机搜索算法[4]。其基本原理是通过个体之间的差异, 实现全局优化。差分进化算法采用变异、交叉和选择的概念, 选择通常是根据适应度值进行锦标赛选择, 交叉是个体之间随机交叉, 变异是采用个体之间的差异对向量分量进行扰动。该算法原理简单、参数少、鲁棒性强, 引起国内外很多学者关注。算法首先初始化N个个体, 每个个体是一个D维向量。差分进化算法按如下公式初始化种群向量。
xij (0) 表示种群中第0代第i个个体的第j个分量i∈[1, N], j∈[1, D], rand (0, 1) 是 (0, 1) 之间的随机数。差分进化算法按如下公式实现种群向量变异。
F表示缩放因子, xi (t) 表示第t代种群的第i个个体。进化过程向量v及向量x不能超过向量的上限与下限。如果超过就重新初始化。差分进化算法按如下公式实现交叉操作。
其中CR是交叉概率, 为确保有至少一个分量发生变异, 是交叉。其余分量按照交叉概率交叉。差分进化算法按如下公式想实现选择操作。
4 基于粒子群与差分算法的双进化方式算法 (Double Evolutionalgorithm based on DE and PSO, DEDP)
PSO算法和DE算法主要区别就是进化方式不同。PSO是采用个体向最优个体飞行的方式进行变异。PSO算法在求解的前期收敛速度较快, 很快就能获得一个比较好的结果, 但由于个体都是向最优个体飞行, 在进化后期个体之间都趋近于局部最优个体, 个体的位置相差不大, 因此易于陷入局部最优, 难以获得全局最优。DE算法是采用个体之间差异进行变异, 个体采用贪婪算法进化, 变异后适应度值优于上一代适应度值时, 变异个体进入下一代种群。个体之间差异较大, 因此和PSO算法比较后期寻优能力更强一点, 速度较PSO也慢一点。DE算法变异方式单一, 进化后期同样容易陷入局部最优。针对DE和PSO算法的容易陷入局部最优的和寻优速度的特点, 本文提出一种兼顾速度和寻优能力的双进化方式的进化算法 (DEDP) 。本文提出的算法实现步骤如下:①按照差分进化方式初始化群体 (公式7) 。初始化一个选择概率CHR (CHR是0和1之间的一个随机数) , 初始化PSO, DE算法的个体个数N以及维数D, 以及权重w, 变异率, 交叉概率等。②随机生成一个N维向量r, 其中r是0和1之间的随机数。种群的每个个体每代进化使用公式 (11) 选择是按照PSO算法进化, 还是按照DE算法进化。
③选择按PSO进化方式的个体按照公式 (5, 6) 进行变异选择。④选择按DE算法进化方式的个体按照公式 (8, 9, 10) 进行变异选择。⑤在新产生的个体种群中找出最优个体。⑥检查是否满足进化要求, 不满足则返回第三步继续循环迭代。
5 三种算法比较
为了比较算法的性能, 将DEDP和标准粒子群算法和差分算法做一个比较。选择如下参数多次实验, CHR=0.5, 差分交换概率CR=0.8, 差分缩放概率F=0.5, 差分变异概率b=0.2。经多次实验发现在维数低的情况下, 三种算法精度都比较高。
6 结论
本文针对粒子群算法中的早熟收敛以及局部搜索能力差的问题, 差分进化算法收敛速度较慢的特点, 以及俩种算法的变异方式不足, 提出了一种全新的双进化方式的算法 (DEDP) 。该算法综合了粒子群算法和差分算法的变异方式, 继承了PSO算法简洁以及收敛速度快和差分进化算法的搜索能力高的优点, 同时在保证全局寻优的基础上, 很大程度地提高了搜索精度和收敛速度, 达到了其他比较算法无法达到的好效果。在进一步的工作当中, 主要研究如何使算法更为高效简洁。
摘要：差分进化算法 (Differential Evolution Algorithms, DE) 和粒子群算法 (Particle Swarm Optimization, PSO) 是一种基于种群的全局优化的通用的启发式算法, 已经用来求解很多的问题。本文提出一种基于DE和PSO的双进化方式的种群进化策略。对于种群中的每个粒子可以随机选择按照差分进化或者按照粒子群进化。为了提高进化的收敛速度, 对于每一代粒子选择一个最优的粒子提供给按照PSO算法进化的粒子使用。通过4个标准函数测试该算法并与PSO和DE算法进行比较, 实验证明该算法是一种求解精度高, 速度快, 鲁棒性好的算法。
关键词：粒子群算法,差分进化算法,双进化方式,全局最优
参考文献
[1]Poli R, Kennedy J, Blackwell T, Freitas A 2008 J.Artif.Evol.Appl.2008, 1.[1]Poli R, Kennedy J, Blackwell T, Freitas A 2008 J.Artif.Evol.Appl.2008, 1.
差分进化算法研究进展 篇7
差分进化算法(Differential Evolution,简称DE)是最近兴起的一种群智能进化算法,最早是在1995年由Rainer Storn和Kenneth Price为求解切比雪夫多项式而提出[1]。在过去的十几年中,该算法被证明为简单而又高效的启发式全局优化算法,尤其在实值参数优化中表现非凡的性能。在历年的CEC优化竞赛中,DE表现出优越的性能[2]:第一届国家演化优化大赛中,DE取得第三名;在CEC 2005实数优化竞赛中,两种DE分别取得第二名和第三名;在CEC 2006约束函数优化竞赛中,改进的DE获得第一名;在CEC 2007多目标优化竞赛中,DE获得第二名;在CEC 2008大规模全局函数优化比赛中,DE获得第三;在CEC 2009多目标优化、动态和不确定环境下优化竞赛中均获得第一;CEC 2011实值参数问题优化比赛获得第二名。由于原理简单、控制参数少、鲁棒性强等特点,DE算法受到学者们的广泛关注,在许多领域如机器人、工业设计、电力系统优化、数字滤波设计等得到很好的应用。然而,与其他群智能进化算法相比,DE算法缺乏系统性的研究成果,尤其是理论研究方面和参数选择与实际问题的相关性匮缺。因此,本文就DE算法的最新研究成果进行全面的综述,并指出未来值得关注的研究方向。
1 差分进化算法的基本原理与特点
1.1 基本原理
DE算法是一种基于群体的随机搜索算法,其主要思想是通过产生基于差异向量的变异个体,然后进行杂交得到试验个体,最后经过选择操作选择较好的个体进入下一代群体[3]。
DE算法是基于实数编码的进化算法,最初的群体是随机均匀产生的,每个个体为搜索空间中的一个实向量。令Xi(g)是第g个代的第i个个体,XiL(g)≤Xi(g)≤XiU(g),则Xi(g)=(xi1(g),xi2(g),…,xin(g)),i=1,2,…,NP;g=1,2,…,Tmax。
XiL(g)、XiU(g)为个体的上、下界,NP为种群规模,Tmax为最大进化代数。
DE算法的主要流程:
(1)生成初始种群
在维空间随机产生个NP个体,实施措施如下:
xij(0)=xijL+rand(0,1)(xijU-xijL),rand(0,1)是[0,1]上服从均匀分布的随机数。
(2)变异操作
变异操作是差异演化的关键步骤,是从种群中随机选择3个个体:Xp1,Xp2,Xp3,且p1≠p2≠p3≠i,则hij(g)=xp1+F(xp2j-xp3j),期中F为缩放因子。
(3)交叉操作
交叉操作可以增加种群的多样性,操作如下:
式(1)中,CR为交叉概率,CR∈[0,1],rand(0,1)是[0,1]上服从均匀分布的随机数。
这种交叉策略可以确保Vij(g+1)中至少有一个分量由hij(g)贡献。
(4)选择操作
由评价函数对向量Vi(g+1)和向量xi(g)进行比较。
反复执行流程(2)到(4),直到达到最大进化代数,或达到所要求的收敛精度。
1.2 主要特点
与其他进化算法相比,DE算法主要呈现了如下优缺点。
(1)优点
DE算法在求解非凸、多峰、非线性函数优化问题表现极强的稳健性,不易陷入局部最优;在同样的精度要求下,DE算法收敛的速度快;DE算法尤其擅长求解多变量的函数优化问题;结构简单,待定参数少,易编程实现。
(2)缺点
缺乏局部搜索能力,导致算法在演化后期收敛速度慢;缩放因子F和杂交概率CR设置敏感;针对不同问题需要不同变异策略,比较困难。
2 主要改进形式
DE算法的多种变形形式常用符号DE/x/y/z以示区分,其中:X限定当前被变异的向量是“随机的”或“最佳的”;Y是所利用的差向量的个数;Z指示交叉程序的操作方法。
综合现有文献,目前主要存在如下几种改进形式[4]:
3 应用研究
3.1 电力系统的应用
DE算法在电力系统中的应用非常广泛,如文献[5]—[7]提出了混合DE算法对调度进行优化,并取得了良好的效果;文献[8]—[9]提出采用DE算法实现电源滤波器以及稳定电压等。
3.2 电磁、传播、和微波工程方面的应用
DE算法在电磁、传播和微波工程方面的应用也是非常广泛,如文献[10]提出了基于MODE和NSDE实现电容分压器;文献[11]—[12]提出动态参数调整的DE算法来实现电磁逆散射;文献[13]—[14]提出了电磁成像和电线阵列设计的DE算法。
3.3 控制系统与机器人方面的应用
DE算法在控制系统与机器人方面的应用也是非常广泛,如有学者提出自适应DE算法来实现控制器的设计与整定;有学者基于改进的DE算法应用到直角坐标机器人控制的多传感器数据融合中,取得了良好的定位作用。
3.4 生命科学方面的应用
DE算法在生命科学方面应用也比较广泛,如有学者提出采用自混合DE算法和PSO算法来实现基因调控网络;许多学者应用DE算法实现了生物过程优化以及微阵列数据分析等。
3.5 化学工程方面的应用
在化学工程应用方面,有学者应用DE算法成功实现了化学过程综合优化设计以及化学过程中的参数估计等。
3.6 模式识别与图像处理方面的应用
在模式识别与图像处理应用方面,有学者应用DE算法成功实现了数据的聚类、图像像素的聚类以及图像分割、特征提取、图像匹配和数字水印等。
3.7 人工智能与神经网络方面的应用
在人工智能与神经网络应用方面,有学者应用DE算法去训练前馈神经网络、小波神经网络和BP神经网络等。
3.8 信号处理方面的应用
在信号处理应用方面,有学者应用DE算法成功实现了非线性的参数估计、数字滤波器的设计等。
3.9 其他方面的应用
除在上述几个方面外,DE算法凭借收敛速度快的优势还在其他许多领域中得到应用。许多学者还将其成功应用到如工程设计、生产优化、城市能源管理、光电以及国际象棋的评价函数优化、股票预测等方面。
4 未来的研究方向
DE算法经历了十多年的发展,在众多领域得到很好的应用,但是仍然有许多值得研究和探索的地方,概况如下:
4.1 理论应用
目前,大部分DE算法研究学者集中研究DE算法的改进以及相关应用,在理论方面的探究却很少,如迄今为止未有学者从理论上给出DE算法针对不同问题与缩放因子和交叉概率的关系。因此,DE算法的收敛性分析、支撑理论是非常值得研究的一个方向。
4.2 基于其他策略或理论的DE算法研究
针对不同的问题,DE算法的收敛非常依赖缩放因子和交叉概率,有时候DE算法还很容易陷入局部最优,因此结合其他一些策略或理论来设计新型的DE算法是一个新的研究方向。如基于机器学习方法的差分进化算法研究、基于多智能体的差分进化算法研究,都将是一个很好的课题。此外,还可以结合其他一些理论,如混沌理论、突变理论等,利用各种理论的优势,设计收敛性能更好的DE算法。
4.3 基于DE算法的应用研究
虽然DE算法的应用非常广泛,但还有许多应用非常值得研究,如在地质灾害中的应用,国土规划、土壤分析等方面也是非常值得探索的应用研究方向。
5 结束语
差分进化算法是当前国际上智能计算研究的一个热点,该算法通过向量之间的差异扰动整个种群以达到求解问题的最优解,具有简单、快速、鲁棒性好等特点。本文就差分进化算法的原理、特点、改进形式及其应用等方面的研究进展进行了全面综述,着重介绍了其应用研究,最后指出了差分进化算法的进一步研究方向。
摘要：差分进化算法是当前国际上智能计算研究的一个热点,该算法通过向量之间的差异扰动整个种群以达到求解问题的最优解,具有简单、快速、鲁棒性好等特点。本文就差分进化算法的原理、特点、改进形式及其应用等方面的研究进展进行了全面综述,着重介绍了其应用研究,最后指出了差分进化算法的进一步研究方向。
三类进化算法的基础研究 篇8
依据达尔文的“物竞天择、适者生存”进化理论 (Darwin C, 1872) , 自然界的生命的演化是一个优胜劣汰、适者生存的过程, 此过程对于物种来说为了更加适应自然界的生存, 必须不断的通过改变自己, 保留优良的个体基因使得种群延续。将物种的优化过程抽象进行数学建模, 结合计算机进行模拟自然演化得出进化算法。
进化算法 (Evolutionary Algorithms, EAs) 是一种基于自然生物进化规则的随机搜索和优化的方法。它通过模拟自然生物的进化过程来解出问题最优解的启发式搜索算法, 包括种群的生成, 个体之间的交叉、变异, 个体适应度计算等。
1 遗传算法
经典遗传算法 (Classic Genetic Algorithms, CGA) 最早由美国密歇根大学Holland J H在20世纪70年代提出, 在其最早出版的《Adaptation in Natural and Artificial Systems》 (1975) 专著中系统地介绍了人工智能与遗传算法。他在开创性的工作中模拟设计了算法的各种操作符, 并且结合了统计决策理论对算法的随机搜索机理做了详细的理论说明, 提出了著名的模式 (Schema) 定理确认了基因结构重组对隐含并行性 (Implicit Parallelism) 的重要性, 为GA算法发展奠定了基础。
De Jong首次将遗传算法应用在函数优化中, 他在其博士论文中对遗传算法做了大量的性能分析, 提出了一整套的相关遗传算法操作执行方法与性能评估标准。De Jong提出的在线与离线指标依然是评估衡量算法性能的重要标准, 而De Jong 5个实验函数 (De Jong’S five test functions) 是目前在函数性能测试中使用较多的函数。Holland的学生Goldberg在其专著《遗传算法在搜索优化与机器学习应用》系统的阐述了遗传算法的操作原理及应用范围, 使之形成了一门完整的学科。
遗传算法GA有较强的鲁棒性和全局搜索能力, 它在种群进化过程中主要采用选择、交叉、变异等操作, 具有以下方面特点。
1) 算法运行的并行性:传统的搜索算法是通过一个点的变化来求解问题的最优解, 而遗传算法初始化种群个体为N, 其搜索点为N个, 各点同时在解的空间进行搜索, 这使得算法有比较好的全局搜索能力, 可以跳出问题局部最优从而达到问题的最优解。
2) 个体的智能性:遗传算法求解问题时, 种群中个体在交叉、变异及选择方法确定后可以依据适应度评价来调整个体中染色体编码, 以使最优解的基因不断累积最后求解到问题最优解。
3) 相关辅助条件需求少:遗传算法在求解时一般只需要适应度评价函数评估结果及搜索空间目标函数控制解的搜索方向, 适应度评价函数范围与解的空间需要对应。
2 进化规划
进化规划 (Evolutionary Programming, EP) 最早由美国科学家Fogel L.J. (1966) 等提出采用有限字符集的符号序列进行环境模拟, 使用有限状态机模型 (Finite State Machine, Fs M) 建模来解决相应的预测问题, FSM的状态变化是离散的并且是有解的界限。经典的进化规划依据适应度的计算, 通过高斯变异选择搜索空间的步长和解空间的前进方向, 对父代个体产生相应的后代, 用一定的比较规则g来选取产生下一代子个体种群。Fogd D B (1992) 将连续的解空间进行离散化处理, 再使用空间离散化性质证明了进化规划的收敛性, Rudolph (1994, 1999) 分别从进化规划的高斯变异与柯西变异角度, 对于一定搜索步长的条件下, 证明了进化规划算法的收敛性。
3 进化策略
进化策略 (Evolutionary Strategy, ES) 是由德国科学家Rechenberg I f1965) 与Schwefel H P (1981) 等提出, 主要解决了多峰非线性函数问题的优化。
进化策略主要采用正态随机分布作为变异算子, 由于与初始种群无关性, 具有较好的全局搜索能力, 其主要特点有: (1) 进化策略的个体在搜索过程中包含有一定的随机扰动。 (2) 算法在运行时主要采用个体的变异操作。 (3) 进化策略的评估一般采用相应的目标函数的值。 (4) 算法在选择操作中总选择适应度最优个体, 保证了种群向最优方向搜索。
4 三种典型算法的比较
通过以上的介绍可以看出, 遗传算法GA、进化规划EP与进化策略ES在算法的总体流程基本一致的, 主要分为:初始种群个体产生;进行个体染色体间交叉、个体变异;竞争选择;种群适应度评价。以上各步迭代直到求解出问题的最优解。
5 未来研究与展望
传统遗传算法的应用领域均适用于量子遗传算法, 量子遗传算法虽然引进了量子计算中的一些概念, 但其本质仍是一种遗传算法。但由于量子遗传算法是一种新理论, 在理论研究、复杂函数优化等方面还不是很成熟。
参考文献
混合进化算法 篇9
1 文化算法介绍
文化算法(Cultural Algorithms)是一种用于解决复杂计算的新型全局优化搜索算法[4,5]。该算法模拟人类社会的演化过程,其重要思想就在于从进化的种群中获取待解决问题的知识(即信仰),并反馈这些知识用于指导搜索过程。文化算法基本框架如图1所示。
种群空间与信仰空间通过一组由接受函数accept ()和影响函数influence ()组成的通信协议联系在一起;接受函数accept ()用来收集种群中所选个体的经验知识,信仰空间通过更新函数update ()进行调整;而影响函数influence ()能够利用信仰空间中待解决问题的经验知识来指导种群空间的进化。在一个文化体系中,存在着多种类型的知识,其中规范知识(normative knowledge)和形势知识(situational knowledge)是最主要的。规范知识为个体提供行为准则和指导原则,而形势知识为个体提供学习榜样。它们都可以为种群的进化提供指导信息。
文化算法作为一种智能启发式算法,其理论研究及应用正受到广泛的关注。文献[6]首先将文化算法应用到背包问题的求解,文献[7]对比研究了文化算法在自适应进化搜索过程中,规范知识和形势知识如何发挥作用,文献[8]将文化算法应用到对服务器性能权值的进化计算中以获得优化的性能权值,文献[9]利用文化算法克服传统的K-均值算法的缺点并应用到聚类问题的求解,文献[10]利用文化算法的双层进化结构与粒子群算法结合,并用于背包问题的求解,文献[11]在模仿文化进化机制的基础上,综合Agent技术以及粒度计算、进化计算的理论和方法提出了粒度进化计算理论框架。
传统的文化算法虽然在优化应用方面已取得一些进展,但是其算法思想仅关注信仰与个体之间的相互制约和影响作用,没有体现信仰与信仰之间(或文化与文化之间)的相互作用机制;文献[11]模仿文化进化机制提出了粒度进化计算理论框架,在算法思想上比文化算法有了很大的深化,更能体现文化进化的特点,但如何进行算法实现和应用还有待进一步研究。本文基于以上研究及文化进化思想,尝试设计文化进化算法(CEA,Cultural Evolutionary Algorithms),并用于车间调度优化问题的求解。
2 文化进化算法(CEA)
2.1 CEA的特点
文化进化机制及特征在文献[11]中已有了较详细的论述,故在此不再累述。CEA的特点是上层文化空间与下层种群空间协同进化:下层种群空间包含多个种群,每个种群与文化空间之间类似文化算法执行select ()、accept ()、influence ()等操作,利用上层文化知识指导种群中个体的进化;文化空间中的文化单元(定义见下文)之间依照文化进化机制执行融合、淘汰、分化等操作,实现文化空间的进化:下层种群之间通过个体迁移等操作实现信息交流及并行进化计算。
文化空间结构采用
定义2文化空间中的文化单元可表示为一个二元组,(i=1,2,…,k),表示进化到第t代时文化空间中第i种文化单元的结构信息,表示此时该文化单元在文化空间中的影响因子,,其中、分别表示第t代时文化空间中第i种文化单元、最优势文化单元和最劣势文化单元所对应的适应值。文化单元的优劣评价函数Fs可根据优化对象构造。将在影响函数influence()中决定文化空间对种群空间中的个体施加何种影响以引导其进化。
定义3种群空间中的个体单元(在执行接受函数accept()时起作用)可表示为一个三元组,(i=1,2,…,NUM),其中,表示进化到第t代时popui中的最优个体结构信息,比如该个体的编码结构等,表示该个体的适应值,表示第t代时的平均适应值。在accept()中,和将成为能否进入上层文化空间并影响上层文化进化的决定参数。
2.2 CEA流程设计
(1)初始化种群空间
由于种群空间中包括多个种群(popu)同时参与并行进化计算,单个种群内部采取基于生物进化的遗传策略,故初始化时需要确定:
①种群空间规模NUM,即种群空间中共有NUM个种群参与并行进化;
②单个种群规模num,即每个种群中有num个个体参与遗传进化;
③个体编码策略选择,根据优化问题对象选择二进制编码、实数编码或其它编码策略。
(2)初始化文化空间
①随着文化空间的进化更新updating(),其规模k也是可变量,令kl
②根据优化对象构造文化单元适应值的评价函数Fs。
(3)接受函数accept()
个体单元能否被文化空间接受并成为影响文化空间进化的文化单元,取决于
1、0分别表示被接受和拒绝,表示t-1代时文化空间中最劣势文化单元的适应值,分别表示t代时第i个种群的平均适应值和最大适应值Fsavgt-1、Fs maxt-1,分别表示t-1代时文化空间的平均适应值和最大适应值。
(4)影响函数influence()
上层文化空间的形势知识S将根据影响因子来影响下层个体的进化步长和方向。设定只有满足(0<β<1,可根据需要设定)的文化单元才有机会进入下层种群空间,并指导个体的进化。个体对该影响的接受程度也是有选择性的,遵循文化“进化潜势法则”[12]种群中较劣的个体更容易接受影响,故设定个体接受概率p。、pb,对较劣个体,pa取0.6～1,对较优个体,pb取0～0.5。接受时,该个体将模仿进行调整,以提高适应能力。
(5)文化空间进化updating()
文化空间进化主要是各文化单元之间的相互作用,按照文化进化思想,主要执行以下几种操作:融合:;分化:;保持:;借鉴:
淘汰:;
(6)种群间个体迁移migrate()
种群间的个体迁移,表示种群之间的通讯与交流。可以选取群中最优个体,也可以选取较劣个体实现大规模迁移操作。综合考虑收敛速度和时间花费,迁移频率一般取3～5代。
(7)活动化解码
由于基于操作的编码方案产生的是半活动调度,因此需要进行活动化解码处理以生成活动化调度。
(8)进化终止
当上层文化空间进化停滞时终止进化操作;考虑时间花费,也可设定最大进化代数作为终止条件。
3 仿真测试
Job shop问题研究n个工件在m台机器上的加工,已知各操作的加工时间和各工件在各机器上的加工次序约束,要求确定与工艺约束条件相容的各机器上所有工件的加工次序,使加工性能指标最优[13]。本文中采用文献[3]中的10台机器10个工件数据进行模型求解和测试对比,Jm(i,j)为机器顺序阵,表示工件i的第j个操作的机器号;T(i,j)为加工时间阵,表示工件j在机器i上的加工时间;Mj(i,j)为工件排列阵,表示机器i上第j次加工的工件号。
算法实现部分关键参数设置如表1,基于操作进行编码,以最短完工时间构造评价函数
accept()、influence()操作隔代发生,每个下层种群均采用自适应遗传算法[14]并行进化,migrate()每隔3代进行一次,最大进化代数取max gen=n*m。本文在Pentium(R)4/3GHZ的PC机上用Matlab7.0编程模拟运算,对问题随机运行20次,统计结果对比如表2。
CEA最优解对应的加工工件排列阵为:
对应的Gantt图如图2。
表2中GA和改进微粒群算法结果均来自文献[3]。仿真结果表明,本文基于文化进化和超群进化的CEA算法,全局寻优能力及收敛速度均优于GA算法及文献[3]中的改进微粒群算法。
4 结束语
【混合进化算法】相关文章：
微进化算法05-25
混合推荐算法05-02
用自适应多点变异混合遗传算法实现智能组卷09-11
设计进化论——关于生物进化论的设计学启示09-12
进化系统发育范文05-28
现代生物进化理论07-20
产品进化论09-11
进化与遗传教案04-14
用孝行进化心灵04-19
进化**300字作文04-22