计算机论文：一种基于aea的约束优化算法

   摘 要 提出一种基于 AEA 算法的约束处理方法，该方法通过引入在迭代中自适应调整的松弛参数 μ，逐渐缩小相对可行域直至收敛到可行域，且充分考虑到不同函数具有不同的可行域大小的情况． 松弛约束的引入能允许包含有用信息的不可行解进入到子代种群中，增加算法的搜索能力． 同时，引入一种自适应惩罚函数法，它利用不同约束条件满足的难易程度来自适应地调整惩罚系数，保证惩罚力度不会过大或过小． 通过 11 个标准测试函数实验表明，该方法具有较满意的结果，在处理工程约束优化问题方面具有很大的潜力．
   关键词 AEA 算法，约束优化问题，惩罚函数法
   1约束优化问题,尤其是非线性约束优化问题在科学计算和工程优化中是常见且较难处理的优化问题. 通常这类问题具有大规模、复杂的非线性等式和不等式约束及多目标等特点.传统求解约束优化问题的方法有可行方向法和广义梯度下降法等,统称为确定性算法. 这类方法需借助函数的梯度信息,要求目标函数和约束条件可微,然而目标函数的确定和计算非常复杂和困难,尤其是高维非线性函数的确定在工程实际中无法实现. 近年来,智能优化算法如遗传算法、差分进化算法等的兴起,以其较大的概率获得全局最优解并且不需知道函数的梯度信息等优点得到较快的发展,结合合适的约束处理方法,智能优化算法在解决约束优化问题中取得一定的成果,但当针对高复杂的非线性约束,尤其是等式约束问题时,如何寻找合适的约束处理方法成为一大挑战.针对智能优化算法,目前处理约束的主要方法有惩罚函数法、单独处理约束和目标函数法及多种方法相结合的混合方法等. 前两种方法被广泛应用到约束处理中,Coello 等对惩罚函数法的运作方式作了详细的介绍,该方法简单易于实现,主要缺点是惩罚系数不易确定,随实际问题不同而取不同值.单独处理约束方法的优点是在约束处理中不需任何参数,且对不等式约束有较好的效果,通过 Deb和Lampinen( 亦称为"可行性方法")的研究发现,该方法的缺点是不易保持种群的多样性,会增加搜索陷入局部极值点的可能性. 为克服这一缺点,He将模拟退火的思想引入到其中,结合 PSO 算法来加强搜索能力,防止陷入局部极值点. Takahama 等提出一种 εDE 算法,将一种称为"ε-约束"的约束处理方法与添加了梯度变异策略的 DE 算法相结合,这种"ε-约束"及个体选择机制类似于前面提到的可行性方法,约束的松弛度通过参数 ε 来控制,随着种群迭代次数的增加而逐渐减小直至零,文献结果表明"ε-约束"的约束处理方法对可行域较小的等式约束有较好的效果,但相比其它算法具有较多的参数.针对"ε-约束"参数较多的缺点,本文对"ε-约束"的迭代方式进行改进,使其能根据种群当代"相对可行解的比例"自适应的调整约束松弛度 -μ. 利用改进的约束处理方法,基于 Li 等提出的一种AEA 智能进化算法,本文提出一种新的约束处理算法 μ-AEA,同时利用 AEA 的特点,将一种自适应惩罚函数应用到算法中,平衡目标函数与惩罚项之间的关系,避免惩罚力度过大或过小. 通过 11 个标准测试函数实验结果表明,新方法取得较好的结果,且与其它的算法相比,该算法具有较高的稳定性.
       2 约束处理方法在约束优化问题中,违约值被定义为所有约束违反值的最大值或被定义为所有约束的违反值之和. 本文采用所有约束的违反值之和来定义违约值( Total Constrained Violation,TCV) :TCVK=∑pj = 1max 0,gjXk( ( )) +∑mj = p +1hj( Xk) ,k = 1,2,…,NP( 1)其中 NP 为种群的规模.Takahama的 εDE 算法,类似于"ε-约束"的约束处理方法,本文引入松弛参数 μ 来控制迭代过程中每代的松弛违约值. 在初始化阶段,计算种群中每个个体的目标函数值和违约值 TCVK,将 μ 的初值设置为初始种群 TCV 的中值,在迭代过程中,将种群中每个个体的 TCV 与 μ 比较,从而确定每个个体是否为相对可行解. 相对可行解的定义如下. 如果个体的 TCV 小于等于 μ,则为相对可行解; 如果个体的TCV 大于 μ,则为相对不可行解. 这样,每代种群的个体根据TCV与μ大小分为相对可行解与相对不可行解,统计种群中相对可行解所占的比例,随着迭代的进行,让松弛参数 μ 根据每代相对可行解的比例自适应的减小. 经过多次尝试,本文将松弛参数 μ 定义如下:
  μ( t + 1) = μ( t)(1 - 0. 34g( t)NP)槡, ( 2)其中,t = 1,2,…,tm,tm为种群的最大迭代次数,g( t) 为第 t 代种群中相对可行解的个数,NP 为种群的规模大小.在种群迭代初期,松弛参数 μ 的引入能扩大种群的搜索范围,在下一步的迭代中有利于防止搜索陷入局部最优值,随着迭代次数的增加,μ 根据每代种群中相对可行解的比例自适应的减小,充分考虑不同函数具有不同的可行域大小的情况. 如,如果进化中某一代种群中相对可行解的比例较大,则 μ 减小的程度也较大,种群收敛加快; 相反,如果某一代种群中相对可行解的比例较小,则 μ 减小的程度较小,种群收敛减慢; 当相对可行解的比例为零时,μ保持不变; 这样的自适应调整策略不仅能在函数可8 60模式识别与人工智能 26 卷行域较大时加快收敛速度,且能考虑到在函数可行域较小的情况下,保证以较大的范围来搜索最优解,防止搜索陷入局部最优.为提高约束优化算法的稳定性和准确性,本文同时引入一种惩罚系数自适应调整的惩罚函数方法. 其主要思想是对目标函数添加适当的惩罚项来构造适应值函数,与上文提出的松弛参数 μ 相配合作为本文处理约束的主要方法. 在描述自适应惩罚机制之前,先进行如下定义.1) 定义种群中个体违反不同约束的违约值函数:
  vi( X) =max { 0,gi( X) } , if i = 1,2,…,phi( X) , if i = p+1,p+2,…,m{( 3)其中,p 为不等式约束的个数,m-p 为等式约束的个数. 如果个体 X 违反第 i 个约束,则有 vi( X) > 0,且违反程度越大对应的 vi( X) 的值越大. 如果个体 X满足第 i 个约束条件,则 vi( X) = 0. 如果 X 满足所有的约束条件,则 X 为可行解.2) 将添加惩罚项的目标函数定义为适应值函数: F ( X) =f( X) , if X is feasiblef( X) +∑mi = 1ki·vi( X) , otherwise{( 4)其中,ki为惩罚系数.按照适应值函数 F( X) 的定义,当个体为可行解时,适应值函数F( X) 等于目标函数值f ( X) . 当个体违反某一约束为不可行解时,适应值函数 F( X)根据违反的约束的不同自适应的调整惩罚项. 为平衡目标函数值与惩罚项之间大小,避免惩罚力度过大或过小,本文在惩罚系数 ki中引入当代种群中所有个体目标函数值的最大值的绝对值. 同时考虑到不同约束条件的满足程度存在难易之分,对约束条件较难满足的施加较大的惩罚,对约束条件较易满足的施加较小的惩罚,本文通过统计每代种群中所有个体对同一个约束条件的违反次数之和来判定约束满足的难易程度,即对于同一个约束,违反次数之和越大说明该约束越不易满足,反之则越易满足. 根据上述论述,定义惩罚系数 ki如下:
  ki= fmax·10siNP ,i = 1 ,2 ,…,m, ( 5 )其中,fmax为当代种群中所有个体目标函数值的最大值,即fmax= max { f( x1) ,f( x2) ,…,f( xn) } ;si为第 i 个约束条件在每代种群的所有个体中被违反的次数之和.结合式( 4) 和式( 5) 可看出,在种群进化初始阶段,种群中的可行解较少,各个约束条件被违反的次数也较大,惩罚系数较大,随着种群进化发展,可行解越来越多,各个约束条件被违反的次数减少,惩罚系数较小,算法自动将搜索的重心从寻找可行解向搜寻最优目标函数值转移.由于本文引入松弛参数 μ 来判定进化过程中个体是否为相对可行解,所以在父代种群和临时种群中选择子代个体时,将个体是否为相对可行解放在首要位置,其次再考虑目标函数值的好坏,因此,本文采用如下选择机制:
       1) 如果两个个体都满足 TCV ≤ μ,即都为相对可行解,则选择目标函数值较好的个体遗传到下一代;2) 如果两个个体只有一个为相对可行解,则为相对可行解的个体遗传到下一代;3) 如果两个个体都不是相对可行解,即都不满足TCV≤μ,则选择TCV较小的个体 遗传到下一代;4) 如果两个个体都不是相对可行解,且两个个体的 TCV 值相等,则选择目标函数 值较好的个体遗传到下一代.这种松弛参数 μ 控制下的相对可行解策略与优先考虑解的相对可行性的选择机制能提高算法的全局搜索能力,逐渐将种群向可行域逼近.3 基本 AEA 算法及其与约束处理方法的融合基于 Alopex 的进化算法( Alopex-Based Evolu-tionary Algorithm,AEA) 最早是由 Li Shaojun[6]提出的一种将 Alopex 算法与群体智能进化算法相结合的新型智能进化算法. 该算法具备基本进化算法和 Alopex 算法的优点,在一定程度上具有梯度下降法和模拟退火算法的优点[6].在 AEA 算法中,从种群中随机选择两个个体,通过计算两个个体自变量和目标函数值的变化情况确定算法进一步搜索方向的概率,逐步迭代最终收敛到全局最优. AEA 算法的计算思路: 从第 t 代种群中随机选择两个个体Xt1和Xt2,通过计算两个个体自变量之差和目标函数值之差的乘积,按照表达式( 6) 计算得到一个概率 p,该概率确定下一步的迭代9 期 王 振 等: 一种基于 AEA 的约束优化算法 μ-AEA861方向,在此方向上前进或后退一步,得到新的个体Xt3. 比较新个体 Xt3与老个体 Xt1的目标函数值,若性能改善则新个体替换老个体 Xt1,否则保留老个体Xt1. 通过无约束标准测试函数将 AEA 算法和 PSO 算法、DE 算法的结果相比较,发现 AEA 算法具有较好的全局搜索能力,且算法实现过程简单,具有随机性和并行性的特点[6,8]. 基于以上优点,本文将 AEA 算法作为约束优化问题的搜索算法.下面几个表达式描述了第 t 代种群中第 i 个个体的第 j 个变量下一步迭代方向概率 ptij的计算方法:
  ptij=11 + expαCtijTt( ), α = 1,- 1, ( 6)其中,下标 ij 表示第 i 个个体中的第 j 个变量,α 的值取决于所求解的问题,最小化函数时,α = 1,最大化函数时,α =- 1; Ctij和 Tt分别为第 t 代种群中两个个体变量的相关性表达式和退火温度:Ctij= xtij- ytij( ) ·( f( Xti) - f( Yti) ) ,Tt=1NP·n∑NPi = 1∑nj = 1Ctij,其中,NP 为种群大小,n 为变量的维数.式( 6) 描述变量下一步行走方向的概率,由式可看出,概率值能根据变量的相关性表达式 Ctij和退火温度 Tt自适应的调整. 在迭代初期,种群差异较大,因此退火温度较大式( 6) 中的概率值约为 0. 5,因此变量向着增大或减小的方向行走的概率相等,基本上属于随机移动,随着种群的不断进化,种群差异逐渐变小,因此退火温度减小,概率 p 能以一定的倾向性向着目标函数值减小( 或增大) 的方向倾斜.迭代后期,变量向相反方向行走的概率越来越小,此时,搜索逐渐由随机搜索变为几乎确定性的搜索,但由于此时变量行走方向只是概率值,仍会有一部分变量向着相反方向移动,这部分变量能使算法跳出局部最优值. 最终p 值趋于0 或1 直到算法收敛到最优值.融合 AEA 和本文提出的约束处理方法的新算法 μ-AEA,能够保持两者各自的优点. 算法 μ-AEA的具体实现思想如下,首先,随机生成初始化种群P11,计算种群中个体的目标函数值和违约值 TCVK,将 μ 的初值设置为初始种群 TCV 值的中值,将种群P11中的个体重新排序得到种群 P12,P11和 P12利用AEA 算法的思想执行 Alopex 操作并生成临时种群P13. 然后,利用式( 3) ~ ( 5) 分别计算 P11、P13的适应值函数,同时利用松弛参数 μ 控制下的相对可行解策略对种群 P11、P13的相对可行性进行评价,再由基于优先考虑解的相对可行性的选择机制,从 P11和 P13中选择优秀个体遗传到下一代,形成新的子代种群P21; 结合表达式( 1) 、( 2) 利用种群 P13中相对可行解的的比例自适应的更新松弛参数 μ 的值,重复上述步骤,种群不断迭代直至达到最大迭代次数 tm,算法结束.4 标准测试函数数值试验及实验结果分析为检验本文提出的约束优化算法 μ-AEA 的性能并与文献、提出的算法的性能做对比,本文将文献[9]、[10]中所采用的11 个标准测试函数作为试验对象. 11 个标准测试函数中 g03、g05、g11包 含 有 等 式 约 束, 为 统 一 比 较 标 准, 如 文献、中一样,将等式约束转换为如下不等式约束:
  hj( X)≤ δ ,其中,δ > 0 且一般取值为 δ = 10-4.表1对11个标准测试函数做了具体描述. 其中,n 为向量的维数,Form of f 为目标函数的类型,LI为线性不等式约束的个数,NI 为非线性不等式约束的个数,LE 为线性等式约束的个数,NE 为非线性等式约束的个数,Optimal 为目前发现的最优值.表 1 标准测试函数Table 1 Benchmark test functionsf n Form of f LI NI LE NE Optimalg01 13 quadratic 9 0 0 0 - 15g02 20 nonlinear 1 1 0 0 0. 8036g03 10 polynomial 0 0 0 1 1. 0005g04 5 quadratic 0 6 0 0 - 30665. 5g05 4 cubic 2 0 0 3 5126. 497g06 2 cubic 0 2 0 0 - 6961. 8g07 10 quadratic 3 5 0 0 24. 306g08 2 nonlinear 0 2 0 0 0. 09583g09 7 polynomial 0 4 0 0 680. 63g10 8 linear 3 3 0 0 7049. 25g11 2 quadratic 0 0 0 1 0. 75本文中的参数采用如下设置,种群大小 NP =100,最大迭代次数 tm为2 000,为减小由于随机数产生的误差并方便与文献的结果进行比较,本文对每个函数独立运行 30 次,并统计其最好值( Best) ,最差值( Worst) ,平均值( Average) 和标准8 62模式识别与人工智能 26 卷差( STD) ,统计比较结果见表 2,表 2 中最后一行给出不同算法获得的不差于其它算法的解的数目值( The number of no worse results,NNWR) . 文献[9]采用的是动态调整的改进 DE 算法结合自适应惩罚函数法( DUVDE + APM) ,种群大小为70,最大迭代次数为5 000,每个函数独立运行30 次; 文献采用的是 DE 算法结合自适应惩罚函数法 ( DE +APM) ,种群大小为 70,最大迭代次数为 5 000,每个函数独立运行 30 次.从表 2 的比较结果来看,本文提出的算法能找到全部 11 个测试函数的全局最优值,且除了函数g02 和 g10 以外,其余 9 个测试函数都能以标准差( STD) 为零或近似为零的稳定性找到最优解.DUVDE+APM 和 DE+APM 与算法 μ-AEA 结果相比,除了函数 g04,g05,g06,g08,g09 与 μ-AEA 取得一样好的效果外,其余 6 个函数的结果都不如μ-AEA 好. 从表 2 最后一行的 NNWR 结果来看,μ-AEA 在 Worst、Best、Average 和 STD 上的值分别为11、11、11、10,明显好于 DUVDE+APM 和 DE+APM 的对应值.为从整体上比较 3 种算法的性能,本文还统计算法在 11 个标准测试函数中的 MAPE 值及其平均值 AMAPE,统计结果如表3 所示,其中 MAPE 的定义如下:
  MAPE =optimal - Averageoptimal× 100% ,其中,optimal 为目前发现的最优值,Average 为函数30 次独立运行最优结果的平均值.从表 3 列出的 11 个测试函数的 MAPE 值可看出,μ-AEA 在每个测试函数的 MAPE 值都好于其它两个算法,表3 最后一列的 AMAPE 值中,μ-AEA 为3. 40E -01,小于 DUVDE+APM 的 1. 51E + 01 和 DE +APM 的 1. 47E + 01.为进一步验证本文提出的约束处理方法的有效性,尤其是在处理不等式约束时的优势. 本文分别将其与基本 PSO 算法和基本 DE 算法相结合( 结合后的算法为 μ-PSO 和 μ-DE) ,通过标准测试函数对结合后的算法进行测试,并将它们与 μ-AEA 的结果相比较,测试结果如表 4 所示. 本文选用约束条件全为不等式的标准测试函数g01、g04、g08 和g09,及同时含有等式约束和不等式约束的测试函数 g11 作为实验对象.