基于非劣排序的多目标优化免疫遗传算法

郭志刚, 邹书蓉

(成都信息工程学院计算机学院,四川成都610225)

0 引言

解决含多目标和多约束的优化问题称为多目标优化问题(Multi-objective Optimization Problem,MOP)。MOP问题的本质在于大多数情况下各子目标可能是相互冲突的,某子目标的改善可能引起其他子目标性能的降低,因此MOP的解不是唯一,而是存在一个最优解集合,集合中的元素称为Pareto最优解。传统的多目标优化方法有加权法、约束法、目标规划法和极大极小法等[1]。这类算法的特点是将各个子目标聚合成一个带正系数的单目标函数,系数由决策者决定,或者由优化方法自适应调整,这类算法存在的一个关键问题就是获得Pareto最优解集合必须多次运行优化过程,由于多次优化过程相互独立,往往得到的结果很不一致,令决策者很难有效的决策。进化算法的优点在于可以处理大规模的搜索空间、在单轮优化期间可以产生多个均衡解、能够有效地克服传统方法的局限性。典型的多目标进化算法主要包括MOGA、NPGA、NSGA、PAES和NSGA2[2-6]算法等。这些算法各有优点,但也存在不足。例如,NSGA的优点是优化目标个数任选,非劣最优解分布均匀,缺点是由于Pareto排序要重复多次,计算效率较低,未采用精英保留策略,共享参数σshare需要预先确定。

1 多目标优化问题

1.1 多目标优化问题的定义

在MOP中,抗原定义为目标函数,即寻找决策向量x=(x1,x2,…,xn)∈X⊂Rn(通常有多个),使向量函数f(x)最优,最优标准一般取最小值。其数学描述为

式(1)中,x=(x1,x2,…,xn)∈X⊂Rn称为决策向量,X是n维的决策空间;y=(y1,y2,…,yn)∈Y⊂Rm称为目标矢量。

1.2 Pareto最优解的定义

对于向量 x*,当且仅当不存在其他 x,在满足约束条件的情况下使式(2)成立,则称x*为Pareto最优解(或非劣解)。所有Pareto最优解的集合称为Pareto最优集,相应的目标向量的图形表示则被称为Pareto最优前端(Front)或曲面(Surface)。

2 免疫遗传算法

遗传算法(Genetic Algorithms,GA)是进化算法中应用最多的一种,目前已在很多复杂的工程优化问题中得到应用。在遗传算法中,如果根据适应度函数选择的双亲基因非常相似,那么其产生的后代相对双亲也比较接近,所期待的改善就比较小,这样基因模式的单一性不仅减慢进化过程,而且可能到时进化停滞,过早收敛于局部最优点。而免疫系统的一个最重要的特点是抗体多样性,可使用这种多样性来提高遗传算法的全局搜索能力而不至出现“早熟”现象。在免疫调节中,那些与抗原亲和度大并且浓度较低的抗体会受到促进,而与抗原亲和度小或浓度较高的抗体会受到抑制,以此保证抗体的多样性。免疫遗传算法(Immune Genetic Algorithm,IGA)正是结合了遗传算法和免疫算法的优点,从提高种群多样性角度来确保收敛到全局最优点。为工程优化设计中遇到的问题,不仅在局部层次提供了相当出色的自适应处理模型,而且在全局层次,也显示出许多有用的性能,找到解决实际工程优化设计的一种智能方法。

2.1 免疫遗传算法的基本概念

(1)抗体:一般指问题的候选解,与进化算法中的个体相似。一个抗体代表一个候选解,即a=(a1,a2,…,an)。

(2)抗体-抗原亲和度:表示抗体对抗原的识别程度。

(3)信息熵:算法为了表明种群中全体抗体的多样性引入了信息熵[7]H(N)(N为抗体个数)。

(4)抗体-抗体亲和度:这一概念反映了抗体与抗体之间的结合能力。根据熵的定义,得到两个抗体Xi和Xj的亲和度,其中Aij的取值范围是(0,1],Aij越大表示抗体间相似度越高,Aij等于1表示两者完全相同。

(5)抗体浓度Ci是指群体中相似个体所占的比例,即其中N表示抗体总数,为抗体之间的亲和度,Tacl为设定的抗体亲和力阈值,一般取值0.9≤Tacl≤1。

2.2 免疫遗传算法的执行过程

免疫遗传算法的一般流程如图1所示。免疫遗传算法是在遗传算法中引入了抗体浓度概率计算、抗体抑制与促进以提供算法的全局收敛性。图1中,抗原为待优化问题及其约束。免疫遗传算法的具体执行步骤如下:

(1)确定编码方案、初始化参数。当决策变量的取值范围明确时,可采用二进制编码;当决策变量的取值范围不明确或精度要求高时,应采用实值编码。

(2)抗原识别,即输入工程优化问题及其约束。确定初始种群规模 N、算法迭代次数最大值 MaxT、交叉概率Pc、变异概率Pm、决策变量的取值范围及其维数和子目标函数的个数。

(3)产生初始抗体种群Pt,令t=0。首先编码产生抗体a(问题的候选解)a=(a1,a2,…,an)。然后产生规模为N的抗体种群Pt。采用小区间生成法:首先把每个待优化参数的取值范围分成群体总数即N个小区间,再在各个小区间中分别随机生成一个初始个体。这样生成的初始群体将会均匀地分布在整个解空间上,并能保证随机产生的各个个体间有明显的差别,保证了初始群体含有较丰富的模式,增强了搜索收敛于全局最优解的可能。

图1 免疫遗传算法流程图

(4)种群非劣排序和抗体浓度的计算对种群Pt按非劣解的定义(对多目标最小优化问题采用式(2)进行排序,每个抗体被赋予秩r(r=1,2,…,N);计算种群Pt中每个抗体的浓度。

(5)保留种群Pt并优选Pt执行免疫克隆操作。优选及克隆过程为:对初始种群Pt进行二元锦标赛选择,得到种群 Qt(抗体个数 NQ=「N/2」);对 Qt进行免疫克隆操作[8]RPC得到种群Q′t(抗体个数为 NQ′,NQ′=2NQ)。其中,二元锦标赛选择的过程为:①从Pt中随机选择2个个体a1和a2;②选择 a1和a2中秩较小、浓度较低者进入 Qt:比较 a1和 a2的秩 r1和 r2。若 r1＜r2,则选择 a1;若 r1＞r2则选择 a2;若 r1=r2则选择 a1和 a2中浓度较小者(如果r1=r2且a1和a2的浓度相等则随机选择二者中的一个)。③重复上述①和②直到Qt中的个体总数等于NQ。对种群Qt={a1(t),a1(t),…,aNQ(t)}执行克隆操作RPC定义为:

(6)对种群 Q′t执行交叉、变异操作得到种群 St(抗体个数NS=2NQ′)。具体操作为:从 Q′t中随机选择2个个体按交叉概率Pc进行交叉,交叉方式为模拟二进制交叉(Simulated Binary Crossover,SBX)[9];从种群 Q′t中随机选择一个抗体,按变异概率Pm进行变异操作,变异方式为实数编码的变异方式[6]。

(7)生成匹配池。将群体Pt和St放入匹配池,得到新的群体Rt=Pt∪St(抗体个数NR=N+NS),对种群Rt进行非劣排序,并计算Rt中每个抗体的浓度,得到非劣前端F1,F2,…。

(8)生成子代群体P(t+1)优先选择非劣前端Fi(i=1,2,…)小的个体进入子代群体;对相同Fi按抗体浓度排序,选择其中抗体浓度较小的个体进入子代群体,直到得到规模为N的子代种群P(t+1)。

(9)终止条件判断,如果终止条件 t=MaxT成立,则结束;否则,t=t+1,转到(5)。

3 免疫遗传算法的仿真实验及其分析

为评价算法的性能,分别对文中算法与NSGA-II多目标优化算法进行仿真实验,最后对实验结果进行分析。测试函数选用2个著名的两目标问题:KUR[10]和ZDT1[11]。在多目标优化的文献中经常选用这些测试问题对算法的性能进行测试[12-14]。

3.1 实验设置

表1给出了实验中用到的2个测试函数的数学定义。第一个目标测试函数分别由Kursawe提出,第二个目标测试函数由Zitzler,Thiele和Deb提出。

表1 文中用到的测试函数

为了评估解的分布性与收敛性,采用文献[14]、[15]中的Spacing metric指标、Convergence metric指标。

3.2 文中算法与NSGA-II的性能比较

文中算法与NSGA-II算法的参数设置见表2。

表2 文中算法与NSGA-II算法参数设置

3.2.1 关于测试问题KUR的性能比较

图2给出了由文中算法和NSGA-II得到的测试问题-KUR的最优解。

对比图2(a)和图2(b)可以看出,对于子目标函数 f1,NSGA-II算法所得的最优解在区间(-19,-18.5)出现了缺失,而对于子目标函数f2,NSGA-II算法所得的最优解在区间(-1,0)出现了缺失。从而说明NSGA-II算法所得的最优解较好地保持了所得的最优解在Pareto-前端上分布的均匀性,但是不能很好的保持分布的宽广性;而文中算法很好的保持了所得最优解在Pareto-前端上分布的宽广性和均匀性。

利用盒图[16]来表示各算法对每个测试函数的统计结果。盒图在判断数据的分布性方面具有重要作用,能形象地表示数据的分布情况。使用工具统计文中算法和NSGA-II算法得到的解的特性。

图3(a)给出了文中算法与NSGA-II算法的分布性指标spacing metric的统计盒图。可以看出算法得到的S值的上四分位数和中位数比NSGA-II得到的结果小,算法得到的S值的下四分位数与NSGA-II得到的结果相同。这说明算法得到的最优解的分布比NSGA-II得到的最优解的分布的均匀性稍好。

图3(b)给出了文中算法与NSGA-II算法的收敛性指标convergence metric的统计盒图。可以看出算法得到的S值的下四分位数、上四分位数和中位数小于NSGA-II得到的结果。这说明算法得到的最优解的收敛性优于NSGA-II。

3.2.2 关于测试问题ZDT1的性能比较

图4给出了由文中算法和NSGA-II得到的测试问题-ZDT1的最优解。

对比图4(a)和图4(b)可以看出,对于子目标函数 f2,NSGA-II算法所得的最优解在区间(0.84,0.85),(0.61,0.62),(0.44,0.45)出现了严重缺失。而算法所得到的解没有出现严重缺失现象,从而说明算法所得到的最优解的均匀性优于NSGA-II。

图5(a)给出了文中算法与NSGA-II算法的分布性指标spacing metric的统计盒图。从图5(a)中可以看出算法得到的S值的上四分位数、中位数和下四分位数比NSGA-II得到的结果小。这说明算法得到的最优解的分布的均匀性比NSGA-II得到的最优解的分布的均匀性好。

图5(b)给出了文中算法与NSGA-II算法的收敛性指标convergence metric的统计盒图。从图5(b)中可以看出算法得到的S值的下四分位数、上四分位数和中位数小于NSGA-II得到的结果。这说明算法得到的最优解的收敛性优于NSGA-II。

3.3 实验结论

综合以上实验分析,得到以下结论:文中算法得到的最优解在分布的均匀性方面比NSGA-II稍好;算法在所得到的最优解的收敛性方面明显好于NSGA-II。

4 结束语

基于非劣排序提出了一种多目标免疫遗传算法,算法模拟生物免疫系统的克隆繁殖过程提高了算法的搜索效率和收敛性;基于浓度对个体生成进行促进与抑制,保持了问题解的多样性,能避免早熟现象。算法只与NSGA-II算法进行了比较,还需与其他典型的多目标优化算法进行比较,以期进一步完善算法。

致谢:感谢成都信息工程学院科研项目(KYTZ200901)对本文的支持

[1] Steuer,R E.Multiple Criteria Optimization:Theory,Computation,and Application[M].New York:Wiley,1986.

[2] Fonseca C M,Fleming P J.Genetic algorithmsfor multi-objective optimization:Formulation,discussionand generalization//Proceedings of the Fifth International Conference on Genetic Algorithms[M].San Mateo and California,1993:416-423.

[3] Zitzler E,Thiele L.Multi-objective evolutionary algorithms:A comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

[4] Srinivas N,Deb K.Multi-objective optimization using non-dominated in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.

[5] Knowles J D,Corne D W.Approximating the non-dominated front using the Pareto archive evolutionary strategy[J].Evolutionary Computation,2000,8(2):149-172.

[6] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multi-objective genetic algorithms:NSGA2[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[7] Dasgupta D.Artificial Immune Systems and their Applications[M].New York:Springer-Verlag,1999.

[8] 焦李成,尚荣华,公茂果,等.多目标优化免疫算法、理论和应用[M].北京:科学出版社,2010.

[9] Deb K,Agrawal,R B Simulated binary crossover for continuous search space[J].Complex Systems,1995,9:115-148.

[10] Kursawe F.A variant of evolution strategies for vector optimization.In:Schwefel HP,Manner R.Parallel Problem Solving from Nature-PPSN I[M].Berlin:Spring-Verlag,1991.193-197.

[11] Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[12] Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems//Congress on Evolutionary Computation[J].Piscataway:IEEE Press,2002:825-830.

[13] Deb K.Multi-objective genetic algorithms:Problem difficulties and construction of test problem[J].Evolutionary Computation,1999,7(3):205-230.

[14] Zitler E,Thiele L,Laumanns M,et al.Performance assessment of multi-objective optimizers:An analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

[15] Schott,JR.Fault tolerant design using single and multicriteria genetic algorithm optimization[M].Cambridge:Massachusetts Institute of Technology,1995.

[16] Deb K,Jain S.Running performance metricsfor evolutionary multi-objective optimization[R].Technical Report,No.2002004,Kanpur:Indian Institute of Technology Kanpur,2002.

[17] Chambers J M,Cleveland W S,Kleiner B,et al.Graphical Methods for Data Analysis[M].Pacific Grover:Wadsworth Brooks/Cole,1983.