求解约束非线性区间数规划的改进型免疫优化算法＊

李彩云，张著洪

(1.贵州大学 理学院 系统科学及信息技术研究所，贵州 贵阳 550025;2.贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

由于人为干扰、环境影响、测量偏差等因素，使得大量实际工程优化问题，如桥梁工程设计、城市公交车路线规划、项目计划管理等，均含有有界扰动参数，这类问题可描述为含有界扰动参数的区间数规划［1］。约束区间数规划是一种含约束条件的区间数规划。由于参数的不确定性和有界性，加之优化对象具有极高计算复杂性，使得对其求解具有极大挑战性。通常需首先利用模糊规划或嵌套式优化的思想将其转化为确定性的数学规划模型，进而利用数学规划方法［2－3］或智能优化方法［1，4－11］寻求其有效解。

嵌套式优化结构是非线性区间数规划问题的常规表现形式，求解方法通常有主从结构法［1，4－8］和模型近似化法［9－10］。前者是一种较为流行的嵌套式优化方法，其具有结构简单和搜索效果好的优点，但计算复杂度较高，不宜在单台PC 机上执行寻优过程。例如，文献［1，6］把非线性区间数规划问题转化为单目标嵌套优化问题，然后利用微种群遗传算法设计主从式遗传算法，求解原问题的解，但嵌套式优化使得求解的计算复杂度很高。另一方面，后者在近年也得到许多研究，主要集中在研究替代不确定目标函数和约束函数的近似函数，这种方法的优点在于搜索效率高，但结构复杂和寻优效果不佳。例如文［9］将RBF 网络的权值视为区间数，并用网络的输出区间值函数近似取代原优化问题的不确定目标函数和约束函数，获得原问题的近似化模型，这种处理方法可极大提高寻优效率，但获得的解的精度较低。文［10］利用近似化模型替代嵌套式优化模型，再用非线性区间数优化方法进行求解，能提高寻优效率。非主从结构法是利用区间自然扩张和区间数的性质，将嵌套式优化模型转化为区间自然扩张模型，进而设计智能优化算法进行求解，但研究工作较为罕见。

鉴于求解非线性区间数规划较难在搜索效果和效率之间作出合理权衡的问题，本文结合文化基因算法的思想，将经典最速下降法和一种求解非约束区间数规划的免疫优化方法［11］有机结合，提出一种改进型约束免疫优化算法(ICIOA :Improved Constrained Immune Optimization Algorithm)。在此，免疫优化算法被用于执行全局搜索，而最速下降法被用于增强算法的局部搜索能力和确定不确定函数的上下界，此有助于加速算法的寻优过程和获得高质量的解。

1 问题描述与转化

给定两个区间A=［aL，aR］和B=［bL，bR］，依据区间的中点和半径，A 和B 可表示为A=〈aC，aW〉和B=〈bC，bW〉其中aC=(aL+aR)/2，aW=(aR－aL)/2。

定义1［12－13］区间A 和B 的区间序关系和距离如下:

考虑如下非线性区间数规划:

其中x为决策向量，x∈D，D为Rn中有界闭区域，u为不确定参数向量，u=(u1，u2，…，um)∈U，U是Rm中有界闭区域，，f 关于x是非线性的不确定目标函数，gj为不确定约束函数，f 和gj关于x 和u 均连续。通常，人们期望寻找x*∈D，使得根据式(2)，满足(P1)的不等式约束的所有候选解x 都有f(x*，u)≤f (x，u) ;然而这样的x*一般不存在，为此，将该模型转化为如下形式:

其中，

则(P2)的可行域为Σ={x ∈D| V(x)=0}，从而(P2)可重新表示为:

定义2 称x*∈Σ为(P3)的有效解，如果不存在x ∈Σ，使得F(x*)＜CWF(x);特别，若存在x*∈Σ，使得在Σ 上同时达到最小，则称x*为(P1)的最优解，相应的目标区间值称为最优值间。

由于(P3)是一种嵌套式优化问题，其计算复杂度较高，需将其转化为如下区间值规划问题，再进行求解:

其中Π(x)为f(x，u)关于u 的区间自然扩张函数。将定义2 中F(x)用Π(x)取代，可获(P4)的有效解的含义。文献［11］获得如下结果:

定理1［11］1)(P4)的有效解集是Γ={z ∈D| fL(z)≤σ}，其中，σ=min fR(x)，x ∈D;2)(P3)的有效解必是(P4)的有效解。

基于定理1，本文求解(P1)的最优解的思路是首先利用优化方法求解(P4)的有效解集Λ，然后由Λ 确定(P3)的有效解集Γ，进而由Γ 确定(P1)的最优解。

2 算法描述

为便于算法描述，对于(P4)，将决策空间D 中的候选解视为抗体，抗原视为求解问题本身。利用文化基因思想，将最速下降法和免疫优化算法结合，求解含约束的区间数规划(P1)。改进型约束免疫优化算法(ICIOA)具体描述如下:

步1 参数设置:群体规模N，多项式变异概率Pm，柯西变异概率Pc，充分大的初始阈值σ0，最大迭代数Gmax，置n=0。

步2 产生初始抗体群An={x1，x2，…，xN}。

步3 利用区间运算规则，计算各抗体的目标值区间［fL(xi)，fR(xi)］，i=1，2，…，N;借助最速下降法求解约束边界:

利用式(4)计算各抗体的约束违背量，判断是否为可行解。

步4 利用式(2)和(4)，对抗体进行排序，将η%的优秀抗体在各自局部小邻域内利用最速下降法进行优化，并替代原抗体。

步5 依据σn，将群体An划分为劣质群B1={x ∈An| fL(x)≥σn}和优质群B2={x ∈An| fL(x)＜σn}。

步6 对B1中抗体进行多项式变异，获群体C1;对B2中抗体进行克隆繁殖，并进行柯西变异，获群体C2。

步7 对C1、C2中的抗体，利用区间运算规则，计算其目标值区间;借助最速下降法求解各抗体的约束边界，进而依据式(4)，计算抗体的约束违背量。步8 将B2、C2中抗体组合为群体C3，借助抗体间的欧氏距离和抑制半径将C3划分为若干子群，进而利用式(2)抽取每个子群中最好抗体与C1组合为群体C，最后依据式(2)，选择N 个抗体构成群体An+1。

步9 若n ＜Gmax，则进行阈值更新σn+1=min{σn，fR(x)，x ∈C}，并置n=n+1，返回步3;否则，则确定(P4)的有效解集Λ={x ∈An+1| fL(x)≤σn+1}。

步10 对(P4)的每个有效解，利用最速下降法，计算目标函数和约束函数的上下界，即

步11 依定义2 和Λ，确定(P3)的有效解Γ。

3 数值试验

本实验在Window XP/ CPU/3.30 GHz/RAM/2.98 GB/VC++环境下进行。将ICIOA 与IP-GA［1］进行比较;最大迭代数均为200.ICIOA 含有4 个参数:Pm=Pc=0.9，η=20，N=10;IP-GA的参数设置由文献［1］获知。

考虑以下非线性区间数规划问题:

这是一个由静态约束优化问题［14］转化而来的非线性区间数规划问题。在α=0.0，0.2，…，1.0 不同置信水平下，表1 给出各算法分别独立运行30 次后，获得的最好目标值区间、平均运行时间以及目标值区间的中点值统计结果。表1 ICIOA 与IPGA 执行30 次后获得的统计结果。

表1 ICIOA 与IP-GA 执行30 次后获得的统计结果

由表1 可以看出，除α=0.8 外，当α 取其它值时，ICIOA 获得的最好目标值区间均优于IP-GA获得的结果。当α=0.8 时，虽然ICIOA 搜索到的最好目标值区间的宽度略大于IP-GA 的区间宽度，但依据区间序关系＜CW，ICIOA 获得的最好解的质量优于IP-GA 的质量。另外，从这两种算法的目标区间中点值的统计结果看，ICIOA 的搜索效果优于IP-GA 的效果且相对稳定。进一步，在给定的每种置信水平下，此两种算法的平均运行时间表明，IP-GA 求解每种情形的最优解，需要的平均运行时间是ICIOA 的2 倍多。因此，尽管IP-GA 是一种结构简单的小种群主从式进化算法，但它求解约束区间数规划的计算复杂度仍然较高。

4 结论

针对具有主从式结构的优化算法求解约束区间数规划问题存在搜索效率低的缺陷，基于文化基因思想、免疫优化和最速下降法，设计改进型约束免疫优化算法;利用免疫优化方法执行全局搜索，且利用最速下降法对优秀抗体进行局部优化和求解约束条件的边界，加快寻优的速度。数值实验比较结果显示:该方法寻优效率高，搜索效果好且较为稳定，有一定的应用潜力。

［1］Jiang Chao，Han Xu，Liu Guirong，et al.A nonlinear interval number programming method for uncertain optimization problems［J］.European Journal of Operational Research，2008，188(1):1－13.

［2］Bhurjee AK，Panda G.Efficient solution of interval optimization problem［J］.Mathematical Methods of Operations Research，2012，76(3):273－288.

［3］Kamakar S，Bhunia AK.An alternative optimization technique for interval objective constrained optimization problems via multiobjective programming［J］.Journal of the Egyptian Mathematical Society，2014，22(2):292－303.

［4］郑泳凌，马龙华，钱积新.一类参数不确定规划的三目标规划解决方法［J］.系统工程理论与实践，2003，5(5):59－64.

［5］蒋峥，刘斌.自适应主从式并行遗传算法在区间非线性规划问题求解中的应用［J］.信息与控制，2006，35(3):314－318.

［6］Jiang Chao，Han Xu，Li Ding.A new interval comparison relation and application in interval number programming for uncertain problems［J］.Computers Materials and Continua，2012，27(3):275－303.

［7］Jiang C，Zhang ZG，Zhang QF，et al.A new nonlinear interval programming method for uncertain problems with dependent interval variables［J］.European Journal of Operational Research，2014，238(1):245－253.

［8］Hladík M.Optimal value bounds in nonlinear programming with interval data［J］.Top，2011，19(1):93－106.

［9］Okada H.Particle swarm optimization with interval-valued genotypes and its application to neuro evolution［J］.World Academy of Science，Engineering and Technology，2013，7(10):627－630.

［10］赵子衡，韩旭，姜潮.基于近似模型的非线性区间数优化方法及其应用［J］.计算力学学报，2010，27(3):451－456.

［11］张著洪，陶娟.求解非线性区间数规划的微免疫优化算法研究［J］.计算机研究与发展，2014，51(12):2633－2643.

［12］Ishibuchi H，Tanaka H.Multiobjective program-ming in optimization of the interval objective function［J］.European Journal of Operational Research，1990，48:219－225.

［13］Moore RE，Cloud MJ，Kearfott RB.Introduction to interval analysis［M］.Philadelphia:Society for Industrial and Applied Mathematics，2009.

［14］王凌.智能优化算法及应用［M］.北京:清华大学出版社，2001.