软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/a813648418.html,
Journal of Software,2013,24(10):2251?2266 [doi: 10.3724/SP.J.1001.2013.04341] https://www.doczj.com/doc/a813648418.html,
+86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax:
?
基于免疫算法和EDA的混合多目标优化算法
戚玉涛1,2, 刘芳1,2, 刘静乐1,2, 任元1,2, 焦李成2
1(西安电子科技大学计算机学院,陕西西安 710071)
2(智能感知与图像理解教育部重点实验室(西安电子科技大学),陕西西安 710071)
通讯作者: 戚玉涛, E-mail: qi_yutao@https://www.doczj.com/doc/a813648418.html,
摘要: 在免疫多目标优化算法的基础上,引入了分布估计算法(EDA)对进化种群进行建模采样的思想,提出了一
种求解复杂多目标优化问题的混合优化算法HIAEDA(hybrid immune algorithm with EDA for multi-objective
optimization).HIAEDA的进化过程混合了两种后代产生策略:一种是基于交叉变异的克隆选择算子,用于在父代种
群周围进行局部搜索的同时开辟新的搜索区域;另一种是基于EDA的模型采样算子,用于学习多目标优化问题决
策变量之间的相关性,提高算法求解复杂多目标优化问题的能力.在分析两种算子搜索行为的基础上,讨论了两者在
功能上的互补性,并利用有限马尔可夫链的性质证明了HIAEDA算法的收敛性.对测试函数和实际工程问题的仿真
实验结果表明,HIAEDA与NSGAII算法和基于EDA的进化多目标优化算法RM-MEDA相比,在收敛性和多样性
方面均表现出明显优势,尤其是对于决策变量之间存在非线性关联的复杂多目标优化问题,优势更为突出.
关键词: 多目标优化算法;人工免疫系统;分布估计算法;混合算法
中图法分类号: TP301文献标识码: A
中文引用格式: 戚玉涛,刘芳,刘静乐,任元,焦李成.基于免疫算法和EDA的混合多目标优化算法.软件学报,2013,24(10):
2251?2266.https://www.doczj.com/doc/a813648418.html,/1000-9825/4341.htm
英文引用格式: Qi YT, Liu F, Liu JL, Ren Y, Jiao LC. Hybrid immune algorithm with EDA for multi-objective optimization.
Ruan Jian Xue Bao/Journal of Software, 2013,24(10):2251?2266 (in Chinese).https://www.doczj.com/doc/a813648418.html,/1000-9825/4341.htm
Hybrid Immune Algorithm with EDA for Multi-Objective Optimization
QI Yu-Tao1,2, LIU Fang1,2, LIU Jing-Le1,2, REN Yuan1,2, JIAO Li-Cheng2
1(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)
2(Institute of Intelligent Information Processing and Key Laboratory of Intelligent Perception and Image Understanding of Ministry of
Education (Xidian University), Xi’an 710071, China)
Corresponding author: QI Yu-Tao, E-mail: qi_yutao@https://www.doczj.com/doc/a813648418.html,
Abstract: The estimation of distribution algorithm (EDA) is a new type of evolutionary computation approach which reproduces
offspring individuals by modeling and sampling the probability distribution of the evolving population. In this paper, the idea of EDA is
introduced into the immune multi-objective optimization algorithm to form a hybrid algorithm termed as HIAEDA (hybrid immune
algorithm with EDA for multi-objective optimization). It is proposed for solving complex multi-objective optimization problems (MOPs).
In HIAEDA, two types of reproducing strategies are combined. One is a recombination and mutation based immune clonal selection
operator. It performs a local search around the parent population and develops new searching areas. The other is a EDA based modeling
and sampling operator. It learns the variable linkages and promotes the algorithm’s capability of solving complex problems. By analyzing
the searching behavior of the two operators, the paper comes to the conclusion that their functions are complementary to each other. The
?基金项目: 国家自然科学基金(61303119); 国家教育部博士点基金(20090203120016, 20100203120008); 博士后面上基金
(20090461283, 20090451369, 200801426, 20080431228, 201104658); 陕西省自然科学基础研究计划(2011JQ8010, 2009JQ8015); 中
央高校基本科研业务费专项资金(K5051203007, K5051203002)
收稿时间:2011-07-07; 定稿时间: 2012-10-19
2252 Journal of Software 软件学报 V ol.24, No.10, October 2013
convergence of HIAEDA is proved using the theory of the finite Markov chain. Experimental results on benchmarking and real problems show that HIAEDA outperforms the outstanding NSGAII and the EDA based RM-MEDA in terms of both convergence and diversity, especially when solving complex MOPs with nonlinear relationship between decision variables.
Key words : multi-objective optimization algorithm; artificial immune system; estimation of distribution algorithm; hybrid algorithm
无论是在科学研究还是工程应用上,多目标优化都是非常重要的研究课题,因为许多现实世界中的优化问题涉及到多个相互冲突的优化目标.一个具有n 个决策变量、m 个最小化目标的多目标优化问题(multi-objective
optimization problem,简称MOP)可描述为
12Minimize )((),(),...,())
Subjec (t to m f f f Ω=∈F x x x x x (1) 其中,Ω∈R n 是n 维决策空间的可行区域,x ={x 1,x 2,…,x n }∈Ω为可行区域内的决策向量,目标函数F (x )定义了一个由n 维决策空间向m 维目标空间的映射函数.由于MOP 往往涉及到优化若干个相互冲突的目标,因此MOP 不存在一个可使所有目标同时达到最优的解.多目标优化算法的目的是获得一组具有代表性的Pareto 最优解的集合(Pareto set,简称PS),使得这些Pareto 最优解在目标空间Pareto 前端(Pareto front,简称PF)上的分布具有尽可能好的逼近性、宽广性和均匀性.
传统的多目标优化算法将各个子目标聚合成一个带正系数的单目标函数,其共同缺点就是一次运行只能得到一个Pareto 最优解.进化算法是一种基于群体进化的随机搜索方法,由于一次运行就可以产生一组Pareto 最优解集,进化多目标优化算法受到了越来越多研究者的关注,并在实际工程应用中发挥着越来越重要的作用
[1]
.自从1985年Schaffer 把进化算法用于求解多目标问题[2]之后,过去20多年中,各国学者相继提出了不同的进
化多目标优化算法,如NSGAII [3],SPEAII [4],PESAII [5]等,基于非支配排序的个体选择机制和基于外部种群的多样性保持机制是这类进化多目标优化算法的主要特征[6].
人工免疫系统(artificial immune system,简称AIS)是受生物免疫系统启发而产生的一种全新的计算智能方法.越来越多的研究结果表明,用于求解优化问题的免疫优化算法与进化算法相比具有更好的种群多样性保持能力,因而算法不容易陷入局部最优[7].近年来,免疫优化算法逐渐被用于求解多目标优化问题.Yoo 和Hajala 首先将免疫机理引入进化多目标优化算法之中[8].Coello 等人基于免疫克隆选择模型提出了第一个真正意义上的免疫多目标优化算法MISA [9].基于免疫网络模型,Freschi 和Repetto 提出了一种矢量人工免疫系统(vector
artificial immune system,简称VAIS)求解多目标优化问题.Gong 等人在克隆选择模型的基础上提出了一种基于非支配邻域选择的多目标优化算法NNIA [10]及其改进算法NNIA2[11],实验结果表明,NNIA 和NNIA2具有良好的求解性能,在Pareto 最优解集合的逼近性、宽广性和均匀性上与NSGAII 等经典算法相比,具有明显的优势.
然而与现有的进化多目标优化算法一样,人工免疫多目标优化算法更多地关注了目标空间上的选择机制,而在决策空间的搜索上则只是简单继承了单目标进化算法的策略.与单目标优化问题不同,多目标优化的任务不是要找到一个或多个相互独立的全局最优解,而是获得一组在决策空间上满足一定分布特性的Pareto 最优解的集合[12].因此,多目标优化问题的Pareto 最优解之间不是相互独立的.在设计进化多目标优化算法时,有必要关注当前种群中个体之间的相关性,统计种群的宏观分布特性.NNIA 和NNIA2虽然具有良好的种群多样性保持能力,且求解精度较高,但是由于没有考虑种群个体间的相关性,对于决策变量之间存在非线性相关的复杂多目标优化问题的求解能力欠佳.
分布估计算法(estimation of distribution algorithm,简称EDA)是统计学习方法与进化计算相结合的产物,算法中没有传统的交叉、变异等遗传操作,采用了不同于进化算法的全新的进化模式[12].EDA 通过统计方法建立种群个体分布的概率模型,再对概率模型随机采样产生新的群体,如此反复进行,实现种群的进化.一些研究者尝试采用EDA 求解连续多目标优化问题[13?19],其中,Zhang 等人提出的RM-MEDA [18]及其推广算法MMEA [19]是最具代表性的工作.RM-MEDA 充分利用了连续多目标优化问题的特点,即对于目标个数为m 的连续多目标问题,由Karush-Kuhn-Tucker 条件可知,PS 在决策空间上的分布呈现分段连续的(m ?1)-维流形
(manifold)[20].RM-MEDA 算法的基本思想是建立多个线性(m ?1)-维流形分布的概率模型来分段逼近整个非线
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法
2253
性的PS 流形,再对各个线性模型进行随机采样产生后代种群.由于RM-MEDA 充分考虑了Pareto 最优解之间的相关性,该算法对于求解决策变量之间非线性相关的复杂多目标优化问题十分有效.然而,RM-MEDA 也存在着不足之处:在进化初期,由于种群没有充分收敛,算法建立的概率模型准确性不够;在进化后期,通过对概率模型随机采样产生的后代逼近精度不高.
本文将基于种群分布模型进化的EDA 引入人工免疫多目标优化算法之中,提出了一种求解复杂多目标优化问题的混合算法HIAEDA(hybrid immune algorithm with EDA for multi-objective optimization).HIAEDA 在迭代进化过程中采用两种后代产生策略:一种是基于交叉变异的克隆选择算子,另一种是基于EDA 的模型采样算子.HIAEDA 结合两类算子的优势,利用统计学习方法分析种群中个体的宏观分布特性,利用交叉变异策略提高算法收敛速度和精度,防止算法陷入局部最优而早熟收敛.仿真实验结果表明,HIAEDA 与免疫多目标优化算法和RM-MEDA 相比均表现出明显优势,尤其是对决策变量之间存在非线性相关的复杂多目标优化问题,其优势尤为突出.
本文第1节介绍对种群个体分布的统计建模方法.第2节描述HIAEDA 算法的流程,从理论上证明算法的收敛性,并分析两种算子的搜索行为特性.第3节展示仿真实验的结果,并对算法的求解性能、稳定性和算子发挥作用的时机进行分析.第4节总结全文并展望进一步工作.
1 种群的概率分布模型
Zhang 等人利用分段连续的线性概率模型对当前种群进行建模,提出了一种适合求解复杂多目标优化问题的EDA 算法RM-MEDA [18].本文采用RM-MEDA 算法中的建模方法,对免疫多目标优化算法的当前抗体种群建立如下概率统计模型.对于m 个优化目标的n 维多目标优化问题,当前种群的PS 可以看作是如下概率模型的独立观测:
ξ=ζ+ε (2)
其中,概率模型ξ的中心ζ是n 维决策空间上的(m ?1)-维分段连续流形,ε是n 维零均值随机噪声向量.RM-MEDA 用K 个分段线性的概率模型来近似逼近ξ的中心流形ζ,即
ζ=Ψ 1+Ψ 2+…+Ψ K (3)
每个分段线性的概率模型Ψ j (j =1,2,…,K )是n 维空间上的一个(m ?1)-维分段连续流形.如图1所示,对于两目标优化问题,Ψ j 是n 维决策空间上的线段.在建模过程中,首先采用Local PCA 聚类算法[21]将当前种群划分为K 个聚类S 1,S 2,…,S K ,然后对每个聚类S j 建立线性模型Ψ j 来刻画S j 的中心.
Fig.1 Illustration of the piecewise linear probability distribution model
图1 分段线性概率模型
记j x 为S j 的均值向量,j i U 为S j 的第i 个主分量(即S j 中所有抗体协方差矩阵的第i 个最大特征值对应的 特征向量),将S j 中的所有抗体向S j 的(m ?1)-维主子空间投影,将涵盖了所有投影点的最小线段或超平面记为Φ j ,那么,
Pareto set S 1
Ψ 1
Ψ2
Ψ3
Φ3Φ2
Φ1
2254 Journal of Software 软件学报 V ol.24, No.10, October 2013
1
1
|,,1,...,1m j n j j j j i i i i i i x R x x U a b i m Φαα?=??=∈=+=????
?
∑≤≤ (4)
其中, min()j
j j T j i i x S a x x U ∈=? (5)
max()j
j
j T j i i x S
b x x U ∈=? (6) 进一步地,将模型Φ j 沿着m ?1个主分量的121,,...,j j j m U U U ?方向两端各扩展25%,得到Ψ j
:
1
1
|,0.25()0.25(),1,...,1m j n j j j j j j j j i i i i i i i i i i x R x x U a b a b b a i m Ψαα?=?
?=∈=+??+?=????
?
∑≤≤ (7)
图1以两目标优化问题为例描述了根据当前种群建立分段线性概率模型的过程.在图1所示的例子中,当前种群被聚为3类,Φ1,Φ2和Φ3分别是根据3类子群体建立的分段逼近1维PS 流形的最短线段.Ψ 1,Ψ 2和Ψ 3分别是Φ 1,Φ 2和Φ 3沿着主分量方向两端各扩展25%后的模型.可以看出,与Φ 1,Φ 2,Φ 3相比,Ψ 1,Ψ 2和Ψ 3可以更好地逼近图中的1维PS 流形.
2 HIAEDA 算法
HIAEDA 算法的抗体编码采用了0~1之间的实数编码方式.抗体A =(a 1,a 2,…,a n )的每一个基因位a i (i =1,2,…,n )表示决策向量的一维.在已知每一维决策变量取值范围[min i ,max i ]的前提下,决策变量的取值可以解码为v i =min i +a i (max i ?min i ). 2.1 HIAEDA 算法流程描述
在迭代过程中采用了两种不同类型的子代繁殖策略产生后代抗体:一种是基于交叉变异的子代产生策略,另一种是基于建模采样的子代产生策略.算法的主要流程描述如下:
算法1. HIAEDA 算法流程.
Step 1. 初始化:设置种群规模N ,子种群个数K ,变异概率p m ,设置算法停止条件.令迭代次数t =1,随机初始
化种群P (t )并计算初始种群中抗体的目标函数值;
Step 2. 判断停止条件:若算法停止条件满足,则输出种群P (t );否则,转Step 3; Step 3. 繁殖:
Step 3.1. 分组建模:采用Local PCA 聚类算法[21]将当前种群P (t )中的抗体聚为K 类,分别构成K 个子
种群S 1,S 2,…,S K ,采用第1节中所述的建模方法对各个子种群建立概率模型Ψ 1,Ψ 2,…,Ψ K ;
Step 3.2. 分配繁殖数量:假设第i 个子种群产生后的个数为N i ,其中,i =1,2,…,K ,并且1,K
i i N N ==∑则N i
可从以下公式获得:
1
()
(),K
i j i j N N vol vol ΨΨ=?
?=×???
?
∑
其中,vol (Ψ i )表示种群S i 中所有抗体在前m ?1个主分量方向上投影的线段长度(两目标问 题)、面积(三目标问题)、体积(四目标问题)或超体积(众目标问题),?x ?表示对实数x 取下整.
Step 3.3. 采用克隆选择算子产生后代:对于每个子种群S i (i =1,2,…,K ),采用下面的算法2所述的克隆
选择算子产生后代种群i S ′,记i S ′中抗体个数为1i N ;
Step 3.4. 采用模型采样算子产生后代:对于每个子种群S i (i =1,2,…,K )建立的概率模型Ψ 1,Ψ 2,…,Ψ K
进行随机采样产生后代种群i S ′′,采样抗体个数为21i i i N N N =?;
Step 4. 变异:记1211,K
K
i i i i S S S S ==′′′==∪∪,令S =S 1∪S 2.对S 中的每一个抗体,采用基于ε区间分割的变异算子
进行变异操作,变异概率为p m ,得到后代种群S ′;
Step 4.1. 将多目标优化问题决策空间的每一维子空间[min r ,max r ](r =1,2,…,n )等分为n r ?1个子区间:
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法 2255
12231[,],[,],...,[,],r r
r r r r r r
n n ωωωωωω? 其中,min r 和max r 分别为第r 维决策变量的取值下界和取值上界,1min ,max r r r
r n r ωω==,且 1||r r j j ωωε??≤,j =2,…,n r ;
Step 4.2. 对于被选中变异的抗体A =(a 1,a 2,…,a n ),对其每一个基因位以概率p m 进行变异.若抗体A 的第
r (r =1,2,…,n )个基因位被选中变异,则在第r 维决策子空间[min r ,max r ]的n r ?1个子区间中随机 选中一个,记为1[,]r r s s ωω+,s =1,2,…,n r ?1;然后,令1()r r r s s s rand ωωωω+=+×?,其中,rand 为0到1 之间的实数;再将抗体A 的第r 个基因位a r 变异为a r =ω/(max r ?min r );
Step 4.3. 将所有变异后得到的新抗体构成后代种群S ′;
Step 5. 选择:令Q =P (t )∪S ′,采用基于m 最近邻列表(m -nearest neighbor list)的选择方法[11]从Q 中选出N 个
抗体,构成新的种群P (t +1),令t =t +1,转Step 2.
在HIAEDA 算法的步骤3.3中,采用了基于免疫克隆选择的子代产生策略.克隆选择算子中的免疫基因操作包括重组和变异两个部分,具体流程如下:
算法2. 克隆选择算子.
输入:K 个抗体子种群S i ,i =1,2,…,K ;
输出K 个后代种群.i S ′
对于每个抗体子种群S i (i =1,2,…,K ),分别执行如下克隆选择算子:
Step 1. Pareto 选择:对抗体子种群S i 进行Pareto 选择,记S i 中Pareto 最优解构成的集合为P i ,集合规模为
M i .若M i >?N i /2?,则转Step 2;否则,转Step 3;
Step 2. 子种群规模控制:计算子种群S i 中每个抗体的拥挤距离[3],从中删除拥挤距离最小的抗体,令
M i ←M i ?1,若M i >?N i /2?,则转Step 2;否则,转Step 3;
Step 3. SBX 重组:依次对子种群S i 中的每个抗体A P (p =1,2,…,M i )执行如下重组操作:从S i 中任意选择一个
不同于A P 的抗体A q (q =1,2,…,M i 且q ≠p ),以A P 和A q 为父代执行模拟二进制交叉(simulated binary
crossover,简称SBX)[22],从两个交叉子代中随机选择一个保留,记为P
A ′; Step 4. PM 变异:依次对子种群S i 的每个重组操作子代P
A ′进行多项式变异操作(polynomial mutation,简称 PM)[22],产生后代P
A ′′; Step 5. 返回结果:1
2{,,...,}i i M
S A A A ′′′′′′′←,返回所有的i S ′. 在算法2中,模拟二进制交叉操作和多项式变异操作是求解连续优化问题的进化算法中有效且常用的交叉和变异算子.这两个算子在经典的进化多目标优化算法NSGAII [3]中被使用,并取得了良好的效果.
在HIAEDA 算法的步骤5中,采用了一种基于邻近距离(vicinity distance)的m 最近邻列表的选择方法保持
非支配种群的均匀性,其中,m 为目标函数个数.抗体的邻近距离定义为2
1i
m
NN mnn i V L ==∏,其中,2i NN L 是抗体距离 第i 最近抗体之间的欧氏距离.HIAEDA 算法中,步骤5的选择操作的具体流程如下:
算法3. 基于m 最近邻列表的选择方法.
输入:种群Q ;
输出:规模为N 的新种群P (t +1)).
Step 1. 建立m 最近邻列表:对于种群Q 中的每一个抗体,计算其在种群Q 中的邻近距离,并对每一个抗体
建立基于邻近距离的m 最近邻列表;
Step 2. 判断停止条件:记当前种群Q 中的抗体数量为S Q ,若S Q ≤N ,则令P (t +1)=Q ,并返回P (t +1);否则,转
Step 3;
Step 3. 删除最拥挤抗体:删除当前种群Q 中邻近距离最小的抗体A w ,重新计算m 最近邻列表中包含了被
删除抗体A w 的抗体的邻近距离,令S Q =S Q ?1;
Step 4. 更新m 最近邻列表:对m 最近邻列表中包含了被删除抗体A w 的抗体,更新其m 最近邻列表,转
2256 Journal of Software 软件学报 V ol.24, No.10, October 2013
Step 2.
文献[11]从理论上证明了基于m 最近邻列表的选择方法能够获得均匀分布的Pareto 最优解集,并通过大量实验结果验证了,基于邻近距离的非支配排序方法与基于拥挤距离(crowding distance)的非支配排序方法[3]相比具有明显的优势.
2.2 HIAEDA 算法的收敛性分析
对于有无限多个Pareto 最优解的多目标优化问题,基于有限种群的进化多目标优化算法无法获得所有的
Pareto 最优解.因此,进化多目标优化算法的优化任务是要获得Pareto 最优解集合的一个子集.利用有限马尔可夫链的性质,本文证明了HIAEDA 算法以任意精度ε收敛到Pareto 最优解集合的一个子集上.
定义1(有限齐次马尔可夫链). 如果S 是一个有限集且{x t :t =0,1,2,…}是一个从S 中取值的随机序列.如果对
于所有的t ≥0和所有的(i ,j )∈S ×S 有以下性质:
P {x t +1=j |x t =i ,x t ?1=i t ?1,…,x 0=i 0}=P {x t +1=j |x t =i }=p ij (8)
则称序列{x t :t =0,1,2,…}是一个在状态空间S 上的齐次有限马尔可夫链.齐次有限马尔可夫链在某一时刻的状态仅与其前一时刻的状态相关,且状态转移矩阵P =[p ij ]S ×S 与时间t 无关.
定义2(不可约转移矩阵). 称有限齐次马尔可夫链的转移矩阵P =[p ij ]S ×S 是不可约的,如果有
?i ,j ∈S ,k ∈{1,2,…},p ij (k )>0 (9)
其中,p ij (k )=p {x k =j |x 0=i }=e i P k
e j 表示通过k 步从状态i 转换到状态j 的概率,e i 和e j 别表示第i 维和第j 维为1的单位向量.从不可约矩阵的定义可以看出,如果有限齐次马尔可夫链的转移矩阵P =[p ij ]S ×S 为正矩阵,则它一定是不可约的.
定义3(ε精度可达). 称任意抗体A *是从抗体A ∈P (t )通过免疫基因操作ε精度可达的,当且仅当
P {||IG (A )?A *||∞≤ε}>0 (10)
其中,IG (A )表示抗体A 通过免疫基因操作得到的后代抗体,||?||∞是欧氏空间上的无穷范数,ε是任意非负常数. 引理1. 一个具有有限状态空间与不可约转移矩阵的齐次马尔可夫链以概率1无限次地访问每一状态而
与它的初始分布无关.证明见文献[23].
定理1. 抗体编码空间中的任意一个抗体A *是从抗体A ∈P (t )通过免疫基因操作ε精度可达的.
证明:记A 为抗体A ∈P (t )经过算法1中Step 3的繁殖操作后得到的后代抗体,若A 经过Step4的变异操作
能够ε精度可达抗体A *,则抗体A *是从抗体A 通过免疫基因操作ε精度可达的.对于1
2(,,...,)n A a a a ????=的任意一个基因位i a ?(i =1,2,…,n ),不妨假设i a ?经解码后对应的决策变量的取值min max min ()i i i i i x a ??=+?落入第i 维决策子空间[min i ,max i ]的第s 个子区间1[,]i i s s ωω+中,s =1,2,…,n i ?1.若12(),,...,n A a a a =的第i 个基因位i a 经解码后对应的决策变量()min max min i i i i i x a =+?没有落入第s 个子区间1[,]i i s s ωω+中,则通过算法1中Step 4的变异操作选
定A 的第i 个基因位进行变异,并且变异后代12(),,...,n A
a a a = 的第i 个基因位i a 经解码后对应的决策变量i x 落入第s 个子区间1[,]i i s s ωω+中的概率为p m /(n i ?1).此时,由于i x
落入与i x ?相同的子区间1[,]i i s s ωω+,则 1.i i i i s s x
x ωωε?+?? ≤≤ 记A 与A *有h 个基因位经解码后对应的决策变量未落入相同的子区间中,则
11
11{||||}()(1)1011h n h n h m m i j h i i P A A p p n n ε??∞==+???=??>??????
∏∏ ≤ (11) 根据定义3可知,A 经过Step 4的变异操作能够ε精度可达抗体A *.因此,抗体编码空间中的任意一个抗体 A *是从抗体A ∈P (t )通过免疫基因操作ε精度可达的. □
定理2. 在任意精度ε下,HIAEDA 算法的种群序列P (t ),t ≥0以概率1渐近收敛到多目标优化问题理想
Pareto 最优解集合的一个子集上.
证明:对于求解连续多目标优化问题,如果在ε精度的意义下,其状态空间S 可以视作为有限集.由于算法中
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法
2257
的参数不随时间t 而变化,即种群序列P (t )的转移矩阵P 与时间t 无关,因此根据定义1可知,种群序列P (t )是在状态空间S 上的齐次有限马尔可夫链.由定理1可知,从种群P (t )中的抗体A 通过免疫基因操作可以ε精度可达抗体编码空间中的任意一个抗体A *,则转移矩阵P 为正矩阵.因此,HIAEDA 算法的种群序列P (t ),t ≥0是具有正转移矩阵的齐次有限马尔可夫链.
记多目标优化问题的理想Pareto 最优解集合为PS ,HIAEDA 算法的种群序列P (t )概率1渐近收敛到PS 的一个子集等价于当t →+∞时,对于P (t )中的任意一个元素A ,都有A ∈PS .假设A ?PS ,则在PS 中必然存在一个
Pareto 最优解?A
,满足?A 支配A .定理1已经证明了HIAEDA 算法的种群序列是齐次有限马尔可夫链,且转移矩 阵P 是正矩阵.由P 是正矩阵可知,P 一定是不可约的.由引理1可知,HIAEDA 算法的种群序列以概率1无限次
地访问每一状态而与它的初始分布无关,于是,当t →+∞时,Pareto 最优解?A
以概率1出现在P (t )中.由HIAEDA 算法的选择算子只保留Pareto 最优解的特性可知,A 会以概率1被?A
淘汰,与前提A ∈P (t )矛盾. 因此,在任意精度ε下,HIAEDA 算法的种群序列P (t ),t ≥0以概率1渐近收敛到多目标优化问题理想Pareto 最优解集合的一个子集上.
□
2.3 HIAEDA 算法中算子搜索行为特性分析
HIAEDA 算法采用了两种进化算子产生后代抗体,图2采用数值实验的方法分析了两种进化算子的搜索特性.考虑到直观性,图2以二维决策空间为例,从一组固定的父代抗体(9个)出发,分别采用两种算子产生了相同数量(900个)的子代抗体,通过观察子代抗体在决策空间中的分布情况考察算子的搜索特性.
Fig.2 Searching behavior of the two types of evolutionary operators
图2 两种进化算子的搜索特性分析
从图2中两种进化算子产生后代抗体的分布可以看出,模型采样算子会沿着父代种群构成的线性PS 流形方向进行搜索,搜索范围不仅仅局限于当前种群个体围成区域的内部,而且沿着当前线性PS 流形方向朝着两端进行扩展.基于EDA 的模型采样算子对于决策变量之间线性相关的多目标优化问题十分有效;对于决策变量之间非线性相关的情况,该算子通过建立分段线性模型逼近非线性的PS 流形.基于SBX 交叉和PM 变异的算子在父代种群周围进行随机搜索,交叉变异算子产生的后代具有良好的多样性,能够在父代种群所在的空间进行局部搜索的同时开辟更为广阔的搜索空间.在实验中我们还发现,两种算子由于搜索特性各有不同,能够在进化的不同阶段发挥各自的作用,且作用的大小与求解的多目标优化问题有关.
3 仿真实验结果与分析
本文对当前已有的8个标准测试函数进行了实验,其中包括Zitzler 等人提出的ZDT 系列函数[24]以及Zhang 等人在RM-MEDA [18]提出的F7,F9,F10(在本文中分别记为F1,F2,F3).各个测试函数的表达式见表1.
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
模型采样算子产生的后代交叉变异算子产生的后代父代个体
模型采样算子产生的后代
交叉变异算子产生的后代父代个体 1.0
0.90.80.7
0.6
0.50.40.30.2x 2
x 1
2258 Journal of Software 软件学报 V ol.24, No.10, October 2013
Table 1 Multi-Objective optimization test problems
表1 多目标优化测试问题
在8个标准测试函数中,ZDT 系列函数的部分决策变量之间存在简单的线性关联,除了ZDT3的PS 是分段连续外,其他ZDT 函数的PS 为0≤x 1≤1,x 2=x 3=…=x n .F1,F2,F3这3个函数的决策变量之间存在复杂的非线性 关联.F1的PS 是一个有界连续曲线,决策变量间的非线性关系为21,2,...,,i x x i n ==0≤x 1≤1,且Pareto 最优解分 布不均匀.函数F2和F3有许多局部最优解,求解较为困难.
在实验中,采用一种综合评价指标Inverted Generational Distance(IGD)[25]来评估算法的性能.假定P *为MOP 的理想PF 上的一组均匀采样,P 为多目标优化算法求得的一组对理想PF 的逼近解,则解集P 的IGD 指标定义如下:
*
**(,)(,)||
v P d v P IGD P P P ∈=
∑ (12)
其中,d (v ,P )为v 与种群P 中与之距离最近的点之间的欧氏距离;|P *|表示种群P *中Pareto 最优解的个数,本文实验中设置为500个.IGD 指标可以综合衡量多目标优化算法求得Pareto 最优解集P 的收敛性和多样性,IGD 值越小,算法的求解性能越好.
在第3.1节和第3.2节的实验中,各种对比算法的种群规模都设为100.算法的停止条件均设置为当函数评价次数达到上限Max FunEval 时算法停止.对于ZDT6,F1,F2和F3,Max FunEval 设置为100 000;对于ZDT4,
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法
2259
Max FunEval 设置为30 000;对于ZDT1,ZDT2和ZDT3,Max FunEval 设置为10 000.RM-MEDA 算法中,聚类个数为5;NSGAII 中,变异概率p m =0.1,SBX 交叉概率p c =1;HIAEDA 中,聚类个数为5,变异概率p m =0.1,SBX 交叉概率p c =1.
3.1 算法求解性能对比
这部分的实验比较HIAEDA 与其他两种对比算法NSGAII 和RM-MEDA 的求解性能.其中,NSGAII 是经典的进化多目标优化算法,RM-MEDA 是一种有效求解多目标优化问题的EDA.图3给出了3种对比算法对8个测试函数求得的Pareto 最优解集,图中的数据为20次独立实验得到的最优结果.
Fig.3 Performance comparisons between the three comparing algorithms on the eight testing problems (1)
图3 3种对比算法对8个测试函数的求解性能比较(1)
0 0.2 0.4 0.6 0.8 1
1.00.80.60.40.20.0
f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1PF
PFtrue 0 0.2 0.4 0.6 0.8 1
RMMEDA-ZDT1
f 2
f 1
1.00.80.60.40.20.0
PF PFtrue
0 0.2 0.4 0.6 0.8 1f 2
f 1
PF
PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1PF
PFtrue 0 0.2 0.4 0.6 0.8 1
f 2
f 1
1.00.50.0
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1
?PF PFtrue
?0 0.2 0.4 0.6 0.8 1
f 2
f 1?1.0
0.50.0
?0.5PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1
??PF PFtrue
0 0.2 0.4 0.6 0.8 1 RMMEDA-ZDT4
PF PFtrue
43210
f 2
f 1
0 0.2 0.4 0.6 0.8 1
HIAEDA-ZDT4
f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1f 2
f 1PF PFtrue
1.51.00.50.0
2260 Journal of Software 软件学报 V ol.24, No.10, October 2013
Fig.3 Performance comparisons between the three comparing algorithms on the eight testing problems (2)
图3 3种对比算法对8个测试函数的求解性能比较(2)
从图3的实验结果可以看出,对于ZDT1,ZDT2和ZDT3这些较为简单的测试函数,3种算法找到的Pareto 最优解集都收敛到了理想的PF,均匀性、宽广性都较好,算法性能区别不明显.
对ZDT4和ZDT6这两个测试问题,RM-MEDA 没有收敛到理想的PF,HIAEDA 和NSGAII 能够很好地收敛,且对ZDT6函数,HIAEDA 的均匀性更好.这是因为ZDT4测试函数多达219个局部最优解,越靠近理想PF,局部最优解分布越密集.ZDT6的Pareto 最优解在理想PF 上分布不均匀,距离理想PF 越近,解的密度越低. RM-MEDA 只用随机采样的方法产生子代,导致算法陷入局部最优之后难以跳出.
F1,F2,F3这3个函数变量之间存在非线性关联,从图3可以看出,NSGAII 在测试F1函数时陷入局部最优,而RM-MEDA 和HIAEDA 则可以收敛到理想PF,因为这两种算法把握了种群的宏观信息,可以挖掘出变量之间
0 0.2 0.4 0.6 0.8 1
HIAEDA-ZDT6
1.00.80.6
0.40.20.0
f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 11.00.80.60.40.20.0
0 0.2 0.4 0.6 0.8 1
f 2
f 1
0 0.2 0.4 0.6 0.8 1f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1f 2
f 1
PF
PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1PF
PFtrue 0 0.2 0.4 0.6 0.8 1
RMMEDA-F2
f 2
f 1
1.00.50.0
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1PF PFtrue
0 0.2 0.4 0.6 0.8 1
NSGAII-F3
f 2
f 1
PF PFtrue
0 0.2 0.4 0.6 0.8 1
f 2
f 1
PF PFtrue
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法
2261
的关联.对于F2函数,3种算法都可以较好地收敛到理想PF.对于F3函数,3种算法的解都无法覆盖整个理想PF,但是可以看出,HIAEDA 的求解性能明显优于其他两种算法.
综上所述,本文提出的HIAEDA 算法结合了两类算法的优势,对8个测试函数的求解性能均不差于或明显优于其他两种类型的对比算法NSGAII 和RM-MEDA.尤其对于决策变量间非线性关联的复杂测试问题, HIAEDA 的优势尤为明显. 3.2 算法稳定性分析
这部分的实验通过IGD 指标的统计分析,对比了3种算法的稳定性.图4给出了算法RM-MEDA,NSGAII, HIAEDA 对8个测试问题求解结果的IGD 指标盒图,图中数据是20次独立运行的统计结果.
Fig.4 Comparisons of the IGD box plots obtained by the three comparing algorithms
图4 3种对比算法的IGD 指标的统计盒图
盒图可以很好地反映数据的统计分布情况,其中,盒子的上下两条线分别是样本的上下四分位数,盒子中间的水平线为样本的中位数.盒子上下的虚线表示样本的其余本分(野值除外),样本的最值分别为虚线两端,“+”表示野值,盒子的切口为样本的置信区间.图中算法1表示RM-MEDA 算法,算法2表示NSGAII 算法,算法3表示HIAEDA 算法.
从图4可以看出,对于ZDT 系列函数,HIAEDA 无论是求解性能还是算法稳定性都表现得最好,NSGAII 次
I G D
ZDT2
5.45.04.64.2×10?323
2
3
1
I G D
?3
231I G D
6.05.55.0
×10?3 2
3
231
46
I G D 6
54
×10?3
2
3
2
3
1 0.030.020.01
0.04I G D
4.03.53.0×10?3
232
31
2.5
I G D
0.120.100.080.06
1 3 2
31I G D 231
I G D F3
0.7
0.50.3
2 3
2262 Journal of Software 软件学报 V ol.24, No.10, October 2013
之,RM-MEDA 最差.对于决策变量之间非线性相关的函数F1,F2和F3,HIAEDA 在F1和F3函数上表现的性能最好,对于F2函数,NSGAII 所求解的性能最好.对于F1函数,HIAEDA 和RM-MEDA 明显优于NSGAII,这说明HIAEDA 和RM-MEDA 更适合求解决策变量非线性相关的MOP.对于F2和F3函数,HIAEDA 和NSGAII 明显优于RM-MEDA,这说明HIAEDA 和NSGAII 不容易陷入局部最优而提前收敛.
综上所述,HIAEDA 算法综合了RM-MEDA 和NSGAII 两类算法的优点,不仅适合求解决策变量非线性相关的复杂多目标优化问题,而且不容易陷入局部最优.算法对各种类型的测试函数求解性能稳定. 3.3 两种算子发挥作用的时机分析
这部分实验通过对每次迭代中两种算子产生后代的质量进行考察,分析两种算子在进化过程中发挥作用的时机.在实验中,将每次迭代过程中产生的新抗体放入一个临时种群,并删除其中被支配的抗体,构成一个新的Pareto 最优抗体种群.在这个新种群中,由基于EDA 的模型采样算子产生的子代抗体的比例记为R EDA ,那么由基于交叉变异的克隆选择算子产生的子代抗体的比例为1?R EDA .图5给出了R EDA 随着迭代的进行而变化的曲线,图中数据是20次独立运行的统计结果.从图5可以看出,R EDA 曲线没有收敛到边界值0或1,这说明在整个进化过程中,两种算子均发挥了一定的作用,只是对不同的问题,在进化的不同阶段发挥作用的大小不同.
Fig.5 Variation of R EDA with function evaluations 图5 R EDA 随着函数评价次数的变化曲线
对于ZDT1和ZDT2,R EDA 曲线先上行后下降,并收敛到0.5附近.在进化初期,由于种群中抗体的分布规律不明显,建立模型的准确性较差;到了进化的中期,基于EDA 的模型采样算子发挥的作用明显,因此,R EDA 曲线在
Function evaluations (×10000)
0 0.2 0.4 0.6 0.8 1
1.00.80.60.40.20.0
R E D A
Function evaluations (×10000)
0 0.2 0.4 0.6 0.8 1R E D A
Function evaluations (×10000)
0 0.2 0.4 0.6 0.8 1
ZDT3
R E D A
Function evaluations (×30000)
0 0.2 0.4 0.6 0.8 1R E D A
Function evaluations (×105)
0 0.2 0.4 0.6 0.8 1R E D A
Function evaluations (×105)
0 0.2 0.4 0.6 0.8 1 R E D A
Function evaluations (×105)
0 0.2 0.4 0.6 0.8 1R E D A
Function evaluations (×105)
0 0.2 0.4 0.6 0.8 1 F3
R E D A
戚玉涛 等:基于免疫算法和EDA 的混合多目标优化算法
2263
这一阶段呈现上行趋势.随着种群收敛到理想PS 附近,基于EDA 的模型采样算子由于精度不够,有效性下降,此时,交叉变异算子的随机性能够带来良好的逼近性能,因此,R EDA 曲线呈现下降趋势.对于PF 不连续的函数ZDT3,在进化前期,R EDA 曲线与ZDT1和ZDT2相同,但是由于PF 是不连续的,基于EDA 的模型采样算子产生的后代以一定的几率落入不连续的区域,因此,R EDA 曲线收敛到低于0.5的值.
对于多峰函数的ZDT4和非均匀函数的ZDT6,其收敛的难度远大于ZDT1和ZDT2.对于这两个复杂函数, R EDA 曲线波动明显,说明基于EDA 的模型采样算子和交叉变异算子能够相互合作跳出局部最优解.R EDA 的值始最终收敛到0.5以上,尤其是ZDT6函数的R EDA 曲线后期有上行的趋势,说明基于EDA 的模型采样算子对于求解复杂的多目标优化问题有明显的贡献.F1,F2和F3是决策变量非线性相关的函数,其理想的PS 是一个有界连续曲线.对于这类复杂问题,R EDA 曲线呈上升趋势并收敛到大于0.5的值,说明基于EDA 的模型采样算子适合求解决策变量非线性相关的复杂多目标优化问题.
综上所述,在HIAEDA 算法中,基于EDA 的模型采样算子和基于交叉变异的克隆选择算子相互合作,对于不同类型的问题,两个算子在进化的不同阶段发挥作用,从而使得算法具有更好的稳定性. 3.4 求解实际问题:水库防洪调度
水库防洪调度(reservoir flood control,简称RFC)问题要优化调度周期内各个调度时段的水库下泄流量序列,使得水库的下泄流量既不能过大,威胁下游防洪对象安全,同时也不能过小,威胁大坝安全或造成上游淹没损失.RFC 问题是决策变量高度相关的连续多目标优化问题,数学模型如下:
1212Minimize {,}
max( )min() ,1,2,...,max t T FL t f f f Z Z Z t T f Q α=??
=+???=??
=??
F (13)
s.t. Z min ≤Z t ≤Z max (14)
Q t ≤Q max (15)
1112()
t t t t t t V V Q I I Q t
????=+??
Δ (16) 其中,目标函数f 1的优化目标是要使库前最高水位最低,且调度期末水位尽量回到防洪限制水位.其中,T 为总的调度时段数,Z t 为第t 个调度时段的库前水位,Z T 为调度期末水位,Z FL 为防洪限制水位,α为调度期末水位约束的
惩罚因子.
第2个目标函数f 2的优化目标是要使水库的最大下泄流量最小.其中,Q t 为第t 个调度时段的下泄流量. 约束式(14)是库容(水位)上下限约束,其中,Z min 和Z max 分别为水库水位上下界.约束式(15)是枢纽下泄能力
约束,其中,Q max 为枢纽的最大下泄能力.约束式(16)是水量平衡方程约束,其中,V t 和V t ?1分别为第t 和t ?1个调度时段的库容,I t 和Q t 分别为第t 个调度时段的上游入库流量和下泄流量,Δt 为调度时段长,计算时换算成秒.
本文对陕西省安康水库2003年8月28日的一场典型的洪水进行了调度实验.图6给出了这场洪水25个调度时段的入库流量曲线和安康水库的水位库容曲线.安康水库的调度初始水位为325m,防洪限制水位为325m,库前水位约束为300m~330m,水库枢纽的最大下泄流量为37474m 3/s.算法采用枢纽下泄流量编码方式,种群中的个体的第i 个基因位的取值表示第i 个调度时段的下泄流量.种群规模为100,算法停止条件中的Max FunEval 设置为50 000.
图7给出了3种算法10次独立实验中获得超体积指标最大的Pareto 最优调度方案的PF.超体积指标(hyper-volume)是一种衡量多目标优化方法求解质量的综合指标,尤其是在理想Pareto 前端未知的情况下,超体积也能较为客观地评价算法获得Pareto 前端的收敛性、宽广性和均匀性[26].超体积指标越大,算法的性能越好.
从图7示例的数据可以看出,HIAEDA 和RM-MEDA 算法的性能明显优于NSGAII.这说明对于RFC 这样的复杂多目标优化问题,基于EDA 的模型采样算子发挥的作用明显.从超体积指标的盒图可以看出,HIAEDA 算法的稳定性比RM-MEDA 更好,这说明HIAEDA 中基于交叉变异的克隆选择算子发挥了开发和探索的辅助 作用.
2264 Journal of Software 软件学报 V ol.24, No.10, October 2013
Fig.6 Water level to volume curve of the Ankang reservoir and the inflow volume on August 28, 2003
图6 安康水库的水位库容曲线和2003年8月28日的洪水数据
Fig.7 Pareto optimal dispatch obtained by three compared algorithms and box plots of the hypervolume metric
图7 各种算法的Pareto 最优调度结果和超体积指标的盒图对比
4 结 论
本文在免疫多目标优化算法的基础上引入了分布估计算法对进化种群进行建模采样的思想,提出了一种求解复杂多目标优化问题的混合优化算法HIAEDA.HIAEDA 结合了两类进化思想的优点,利用统计学习方法分析种群中抗体的宏观分布,学习多目标优化问题决策变量之间的相关性;利用交叉变异策略,在父代种群周围进行局部搜索的同时开辟新的搜索区域.通过对不同类型测试函数和水库防洪调度问题的仿真实验结果表明, HIAEDA 算法中的两种算子能够相互合作,在进化的不同阶段发挥不同的作用.HIAEDA 算法的求解性能均不差于或明显优于其他两种类型的对比算法NSGAII 和RM-MEDA,不仅适合求解决策变量非线性相关的复杂多目标优化问题,而且不容易陷入局部最优.HIAEDA 算法对各种类型的测试函数求解性能稳定.
本文算法和RM-MEDA 算法均采用了固定的子种群个数建立确定数量的线性概率模型,对于更为复杂的多目标优化问题,建立模型的个数应该是与问题相关的.因此,如何根据问题的特点自适应地确定建立模型的个数,是进一步研究的重点. References :
[1] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. New York: Wiley, 2001. 51?71.
[2] Fonsecay CM, Fleming PJ. Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In:
Proc. of the 1st Int’l Conf. on Genetic Algorithms. 1993. 416?423.
[3] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on
Evolutionary Computation, 2002,6(2):182?197. [doi: 10.1109/4235.996017]
290 300 310 320 330 340
水位(单位:m)
库容(单位:百万立方米)
陕西省安康水库水位库容曲线0 5 10 15 20 25
周期(时间间隔:1h)
水库入库流量(m 3/s )
安康水库,2003.08.28
320 322 324 326 328 330
RFC problem
HIAEDA NSGAII RMMEDA
f 1:最高上游水位(m)
f 2:最大下泄流量(m 3/s )
HIAEDA NSGAII RMMEDA
RFC problem
超体积值
×104
戚玉涛等:基于免疫算法和EDA的混合多目标优化算法2265
[4] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. In:
Giannakoglou KC, et al., eds. Proc. of the Evolutionary Methods for Design, Optimisation and Control with Applications to Industrial Problems (EUROGEN 2001). Athens: National Technical University of Athens, 2002. 95?100.
[5] Knowles J, Corne D. The Pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimization. In:
Proc. of the Congress on Evolutionary Computation. Washington: IEEE, 1999. 98?105. [doi: 10.1109/CEC.1999.781913]
[6] Gong MG, Jiao LC, Yang DD, Ma WP. Research on evolutionary multi-objective optimization algorithms. Ruan Jian Xue
Bao/Journal of Software, 2009,20(2):271?289 (in Chinese with English abstract). https://www.doczj.com/doc/a813648418.html,/1000-9825/3483.htm [doi:
10.3724/SP.J.1001.2009.03483]
[7] Castro LD, Timmis J. Artificial Immune Systems: A New Computational Intelligence Approach. Heidelberg: Springer-Verlag, 2002.
57?86.
[8] Yoo J, Hajela P. Immune network simulations in multicriterion design. Structural and Multidisciplinary Optimization, 1999,18(2-3):
85?94. [doi: 10.1007/BF01195983]
[9] Coello Coello CA, Cortes NC. Solving multiobjective optimization problems using an artificial immune system. Genetic
Programming and Evolvable Machines, 2005,6(2):163?190. [doi: 10.1007/s10710-005-6164-x]
[10] Gong MG, Jiao LC, Du HF, Bo LF. Multi-Objective immune algorithm with nondominated neighbor-based selection: NNIA.
Evolutionary Computation, 2008,16(2):225?255. [doi: 10.1162/evco.2008.16.2.225]
[11] Yang DD, Jiao LC, Gong MG, Feng J. Adaptive ranks and K-nearest neighbor list based multiobjective immune algorithm.
Computational Intelligence, 2010,26(4):359?385. [doi: 10.1111/j.1467-8640.2010.00363.x]
[12] Zhou SD, Sun ZQ. A survey of estimation of distribution algorithm. ACTA Automatic Sinica, 2007,33(2):113?124 (in Chinese
with English abstract). [doi: 10.1360/aas-007-0113]
[13] Larranaga P, Lozano JA. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic
Publishers, 2002. 101?142.
[14] Costa M, Minisei E. MOPED: A multi-objective parzen-based estimation of distribution algorithm for continuous problems.
Evolutionary Multi-Criterion Optimization Lecture Notes in Computer Science, 2003. 282?294. [doi: 10.1007/3-540-36970-8_20] [15] Zhou A, Zhang Q, Jin Y, Tsang E, Okabe T. A model-based evolutionary algorithm forbi-objective optimization. In: Proc. of the
2005 IEEE Congress on Evolutionary Computation. Edinburgh: Incorporate, 2005. 2568?2575. [doi: 10.1109/CEC.2005.1555016] [16] Zhou A, Jin Y, Zhang Q, Sendhoff B, Tsang E. Combining model-based and genetics-based offspring generation for multi-
objective optimization using a convergence criterion. In: Proc. of the IEEE Congress on Evolutionary Computation (CEC 2006).
Vancouver, 2006. 892?899. [doi: 10.1109/CEC.2006.1688406]
[17] Pe?a JM, Robles V, Larra?aga P, Herves V, Rosales F, Pérez MS. GA-EDA: Hybrid evolutionary algorithm using genetic and
estimation of distribution algorithms. Innovations in Applied Artificial Intelligence Lecture Notes in Computer Science, 2004, 3029(1):361?371. [doi: 10.1007/978-3-540-24677-0_38]
[18] Zhang Q, Zhou A, Jin Y. A regularity model-based multiobjective estimation of distribution algorithm: RM-MEDA. IEEE Trans.
on Evolutionary Computation, 2008,12(1):41?63. [doi: 10.1109/TEVC.2007.894202]
[19] Zhou A, Zhang Q, Jin Y. Approximating the set of pareto-optimal solutions in both the decision and objective spaces by an
estimation of distribution algorithm. IEEE Trans. on Evolutionary Computation, 2009,13(5):1167?1189. [doi: 10.1109/TEVC.2009.
2021467]
[20] Ehrgott M. Multicriteria optimization. In: Lecture Notes in Economics and Mathematical Systems. New York: Springer-Verlag,
2005. 31?41.
[21] Kambhatla N, Leen TK. Dimension reduction by local principal component analysis. Neural Computation, 1997,9(7):1493?1516.
[doi: 10.1162/neco.1997.9.7.1493]
[22] Deb K, Agrawal RB. Simulated binary crossover for continuous search space. Complex Systems, 1995,9(2):115?148.
[23] Iosifescu M. Finite Markov Processes and Their Applications. Chichester: Wiley, 1980.
[24] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation,
2000,8(2):173?195. [doi: 10.1162/106365600568202]
2266 Journal of Software软件学报 V ol.24, No.10, October 2013
[25] Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG. Performance assessment of multiobjective optimizers: An analysis
and review. IEEE Trans. on Evolutionary Computation, 2003,7(2):117?132. [doi: 10.1109/TEVC.2003.810758]
[26] Knowles J, Corne D. Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Trans. on Evolutionary
Computation, 2003,7(2):100?116. [doi: 10.1109/TEVC.2003.810755]
附中文参考文献:
[6] 公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究.软件学报,2009,20(2):271?289. https://www.doczj.com/doc/a813648418.html,/1000-9825/
3483.htm [doi: 10.3724/SP.J.1001.2009.03483]
[12] 周树德,孙增圻.分布估计算法综述.自动化学报,2007,33(2):113?124. [doi: 10.1360/aas-007-0113]
戚玉涛(1981－),男,河南潢川人,博士,副教授,主要研究领域为进化计算,人工免疫系统,高性能计算.
E-mail: qi_yutao@https://www.doczj.com/doc/a813648418.html,
任元(1988－),男,硕士生,主要研究领域为进化多目标优化.
E-mail: julyhurt@https://www.doczj.com/doc/a813648418.html,
刘芳(1963－),女,教授,博士生导师,CCF
高级会员,主要研究领域为网络智能信息
处理,智能图像处理,模式识别.
E-mail: f63liu@https://www.doczj.com/doc/a813648418.html,
焦李成(1959－),男,博士,教授,博士生导
师,CCF高级会员,主要研究领域为智能图
像处理,神经网络,进化计算,机器学习.
E-mail: lchjiao@https://www.doczj.com/doc/a813648418.html,
刘静乐(1987－),女,硕士生,主要研究领域
为进化计算及其应用.
E-mail: liule870720@https://www.doczj.com/doc/a813648418.html,
多目标优化算法 ——11级计算一班 20113745 陆慧玲 近年来,多目标优化问题求解已成为演化计算的一个重要研究方向,而基于Pareto 最优概念的多目标演化算法则是当前演化计算的研究热点。多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。 最优化问题是工程实践和科学研究中主要的问题形式之一，其中，仅有一个目标函数的最优化问题称为单目标优化问题，目标函数超过一个并且需要同时处理的最优化问题称为多目标优化问题(multiobjectiveoptimizationprob- lems，简称MOPs)。对于多目标优化问题，一个解对于某个目标来说可能是较好的，而对于其他目标来讲可能是较差的，因此，存在一个折衷解的集合，称为Pareto 最优解集(Pareto optimal set)或非支配解集(nondominated set)。起初，多目标优化问题往往通过加权等方式转化为单目标问题，然后用数学规划的方法来求解，每次只能得到一种权值情况下的最优解。同时，由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的，传统的数学规划方法往往效率较低，且它们对于权重值或目标给定的次序较敏感。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索，这种从种群到种群的方法对于搜索多目标优化问题的Pareto 最优解集是很有用的。 第一代进化多目标优化算法以Goldberg 的建议为萌芽。1989 年，Goldberg 建议用非支配排序和小生境技术来解决多目标优化问题。非支配排序的过程为：对当前种群中的非支配个体分配等级1，并将其从竞争中移去；然后从当前种群中选出非支配个体，并对其分配等级2，该过程持续到种群中所有个体都分配到次序后结束。小生境技术用来保持种群多样性，防止早熟。Goldberg 虽然没有把他的思想具体实施到进化多目标优化中，但是其思想对以后的学者来说，具有启发意义。随后，一些学者基于这种思想提出了MOGA，NSGA 和NPGA。 从20 世纪末期开始，进化多目标优化领域的研究趋势发生了巨大的变化，l999 年，Zitzler 等人提出了SPEA。该方法使精英保留机制在进化多目标优化领域流行起来。第二代进化多目标优化算法的诞生就是以精英保留策略的引入为标志。在进化多目标优化领域，精英保留策略指的是采用一个外部种群(相对于原来个体种群而言)来保留非支配个体。(1)SPEA 和SPEA2 SPEA 是Zitzler 和Thiele 在1999 年提出来的算法。在该算法中，个体的适应度又称为Pareto 强度，非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比
MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况：
1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数
MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???>
当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数
基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法 关键字：布谷鸟搜索、元启发式算法、多目标、最优化 摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。 1.简介 在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及
设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。 另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。 从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些
用于约束多目标优化问题的双群体差分进化算 法精编 Document number：WTT-LKK-GBB-08921-EIGG-22986
用于约束多目标优化问题的双群体差分进化算法 孟红云 1 张小华2刘三阳1 (1.西安电子科技大学应用数学系，西安，710071； 2.西安电子科技大学智能信息处理研究所，西安，710071)摘要：首先给出一种改进的差分进化算法，然后提出一 种基于双群体搜索机制的求解约束多目标优化问题的差分 进化算法．该算法同时使用两个群体，其中一个用于保存 搜索过程中找到的可行解，另一个用于记录在搜索过程中 得到的部分具有某些优良特性的不可行解，避免了构造罚 函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字：差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算 法的出现和发展，用进化算法求解优化问题已成为一个研 究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结 为求解一个带有约束条件的函数优化问题，因此研究基于 进化算法求解约束优化问题是非常有必要的．不失一般
性，以最小化问题为例，约束优化问题（Constrained Optimization Problem ，COP ）可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ （1） 其中)(x F 为目标函数，)(),(x h x g j i 称为约束条件， n n R x x x x ∈=),,,(21 称为n 维决策向量．将满足所有约束条件的 解空间S 称为(1)的可行域．特别的，当1=k 时，(1)为单目 标优化问题；当1>k 时，（1）为多目标优化问题．)(x g i 为 第i 个不等式约束，)(x h j 是第j 个等式约束．另一方面，对于等式约束0)(=x h j 可通过容许误差（也称容忍度）0>δ将它转 化为两个不等式约束： ?????≤--≤-0)(0)(δδx h x h j j （2） 故在以后讨论问题时，仅考虑带不等式约束的优化问题．进一步，如果x 使得不等式约束0)(=x g i ，则称约束() x g i 在x 处是积极的．在搜索空间S 中，满足约束条件的决策变量x 称为可行解，否则称为不可行解． 定义1（全局最优解）()**2 *1*,,,n x x x x =是COP 的全局最优解，是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标 函数)(y F ，表示为)( )(*y F x F ． 对于单目标优化问题， )( )(*y F x F 等价为)()(*y F x F ≤，而对于多目标优化问题是指不 存在y ，使得)(y F Pareto 优于)(*x F ． 目前，进化算法用于无约束优化问题的文献居多，与 之比较，对约束优化问题的研究相对较少[4-6]。文[7] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类：基于 罚函数的约束处理技术和基于多目标优化技术的约束处理
高维多目标进化算法 二、文献选读内容分析及思考 （一）Borg算法 Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。 1.创新点 1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。 2）提出了ε归档进程，能提高算法计算效率和防止早熟。 3）种群大小的自适应调整。 4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。 2. Borg算法原理 1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。 2）ε归档进程 如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。 图1 ε支配网格 在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。 3）重启 自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。 4）交叉算子的自适应选择 摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K
浅析多目标优化问题 【摘要】本文介绍了多目标优化问题的问题定义。通过对多目标优化算法、评估方法和测试用例的研究，分析了多目标优化问题所面临的挑战和困难。 【关键词】多目标优化问题；多目标优化算法；评估方法；测试用例 多目标优化问题MOPs （Multiobjective Optimization Problems）是工程实践和科学研究中的主要问题形式之一，广泛存在于优化控制、机械设计、数据挖掘、移动网络规划和逻辑电路设计等问题中。MOPs有多个目标，且各目标相互冲突。对于MOPs，通常存在一个折衷的解集（即Pareto最优解集），解集中的各个解在多目标之间进行权衡。获取具有良好收敛性及分布性的解集是求解MOPs的关键。 1 问题定义 最小化MOPs的一般描述如下： 2 多目标优化算法 目前，大量算法用于求解MOPs。通常，可以将求解MOPs的算法分为两类。 第一类算法，将MOPs转化为单目标优化问题。算法为每个目标设置权值，通过加权的方式将多目标转化为单目标。经过改变权值大小，多次求解MOPs 可以得到多个最优解，构成非支配解集[1]。 第二类算法，直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局搜索法，对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目标进化算法。根据其特性，多目标进化算法可以划分为两代[2]。 （1）第一代算法：以适应度共享机制为分布性策略，并利用Pareto支配关系设计适应度函数。代表算法如下。VEGA将种群划分为若干子种群，每个子种群相对于一个目标进行优化，最终将子种群合并。MOGA根据解的支配关系，为每个解分配等级，算法按照等级为解设置适应度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值，在进化过程中，算法根据虚拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法，当解的支配关系相同时，算法使用小生境技术选择最优的解进入下一代。 （2）第二代算法：以精英解保留机制为特征，并提出了多种较好的分布性策略。代表算法如下。NSGA-II降低了非支配排序的复杂度，并提出了基于拥挤距离的分布性策略。SPEA2提出了新的适应度分配策略和基于环境选择的分布性策略。PESA-II根据网络超格选择个体并使用了基于拥挤系数的分布性策略。
NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations', 200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)
x 是第 t 代种群中个体，其 rank 值定义为： rank (x ,t ) =1+p (t ) p (t )为第t 代种群中所有支配x 的个体数目 适应值 (fitness value )分配算法： 1、 将所有个体依照 rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值(从 rank1 到 rank n * N )，一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一 rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme )： 向量y a =(y a ,1,,y a ,q )和y b =(y b ,1,,y b ,q )比较 分为以下三种情况： k =1,,q -1; i =1,,k ; j =k +1,,q ; (y a ,i g i )(y a ,j g j ) i =1, ,q ; (y a ,i g i ) 当 y a 支配 y b 时，选择 y a 3、j =1, ,q ; (y a ,j g j ) 当 y b 支配 y a 时，选择 y b 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的 大小影响 理论上给出了参数share 的计算方法 goal vector ： g = (g 1, ,g q ) 1、 2、
基本思想： 1、初始化种群 Pop 2、锦标赛选择机制：随机选取两个个体 x 和 x 和一个 Pop 的 子集 CS(Comparison Set)做参照系。若 x 被 CS 中不少于一 个个体支配，而 x 没有被 CS 中任一个体支配，则选择 x 。 3、其他情况一律称为死结(Tie )，采用适应度共享机制选择。 个体适应度： f i 小生境计数(Niche Count )： m =j Pop Sh d (i , j ) 共享适应度(the shared fitness )： 选择共享适应度较大的个体进入下一代 优点：能够快速找到一 些好的非支配最优解域 能够维持一个较长的种群更新期 缺 点：需要设置共享参数 需要选择一个适当的锦标赛机制 限制 了该算法的实际应用效果 1- 共享函数： Sh (d ) = d share 0, d share d share
多目标优化算法与求解策略 2多目标优化综述 2.1多目标优化的基本概念 多目标优化问题(Multi-objective Optimization Problem，MOP)起源于许多实际复杂系统的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目标的优化，这些目标并不是独立存在的，它们往往是祸合在一起的互相竞争的目标，每个目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。 多目标最优化是近20多年来迅速发展起来的应用数学的一门新兴学科。它研究向量目标函数满足一定约束条件时在某种意义下的最优化问题。由于现实世界的大量问题，都可归结为含有多个目标的最优化问题，自70年代以来，对于多目标最优化的研究，在国内和国际上都引起了人们极大的关注和重视。特别是近10多年来，理论探索不断深入，应用范围日益广泛，研究队伍迅速壮大，显示出勃勃生机。同时，随着对社会经济和工程设计中大型复杂系统研究的深入，多目标最优化的理论和方法也不断地受到严峻挑战并得到快速发展。近几年来，将遗传算法(Genetic Algorithm，GA)应用于多目标优化问题成为研究热点，这种算法通常称作多目标优化进化算法或多目标优化遗传算法。由于遗传算法的基本特点是多方向和全局搜索，这使得带有潜在解的种群能够一代一代地维持下来。从种群到种群的方法对于搜索Pareto解来说是十分有益的。 一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中
多目标进化算法综述
多目标进化算法综述 作者：梅志伟 来源：《软件导刊》2017年第06期 摘要：基于种群的进化算法在一次运行中能够产生一组近似的 Pareto 最优解集，因此多目标进化算法成为处理多目标优化问题中的主流方法。介绍了多目标优化问题中的数学模型以及相关定义，根据多目标进化算法的特点，将现有算法分为4类并分别进行阐述，同时分析了它们的优缺点。 关键词：多目标优化；进化算法；支配；分解 DOIDOI：10.11907/rjdk.171169 中图分类号：TP301 文献标识码：A 文章编号：1672-7800（2017）006-0204-04 0 引言 在人们的实际生活中，大多数优化问题都是多目标优化问题，广泛存在于经济管理、工程实践和科学研究等领域中。当前，多目标优化在理论和应用方面均取得了不少进展，但是由于多目标优化问题的复杂性，因此仍存在大量挑战。 多目标优化问题中往往存在多个彼此相互冲突的目标。与单目标优化不同，在多目标优化中，提高一个目标的性能会引起其它一个或多个目标性能的下降。因此，多目标优化问题中不存在一个单独的最优解，而是存在一组表示各个目标间权衡和折中关系的解集，称该解集为Pareto最优解集。Pareto最优解集在目标域的投影被称为Pareto前沿。 由于很多现实工程问题中的优化问题是NP难，传统的数学规划方法将会变得异常困难。而具有自然界规律启发式特征的求解方法往往适合近似求解这些困难问题，这些方法被称为进化计算[1]。进化算法基于种群的特性使其十分适合多目标优化问题的求解。同时，进化算法还具有鲁棒性强的特点。因此，进化算法被广泛应用在多目标优化问题的求解上。 1 多目标进化问题概述 多目标优化问题同时优化多个目标，这些待优化的目标包含最大化、最小化或者两者都有的问题。在实际处理时，为了简化问题，可以将最大化或最小化问题取反，使所有优化目标全部转化成最小化或最大化问题。本文中将讨论最小化问题。 2 多目标进化算法一般流程 生物进化是一个不断优化的过程，在不断的变化过程中增加自身的适应性。进化计算以生物进化为启发，对一个解进行抽象编码，模拟生物进化中的基因。进化算法以种群为基础，是一个黑盒的搜索、优化方法，进化算法不需要优化问题具备一定的前提条件，例如连续性、可微性等，且一次运行能够产生一组解。因此，进化算法特别适合处理多目标优化问题。
基于分解的多目标进化算法
摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的 应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目 标优化问题分解为一组？？？单目标优化问题并对它们同时优化。通过利用与每一个子问题 相邻的子问题的优化信息来优化它本身，这是的该算法比 MOGLS 和非支配排序遗传算法 NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在 0-1 背包问题和连续的多目标优化问 题上，利用一些简单的分解方法本算法就可以比 MOGLS 和 NSGA-Ⅱ表现的更加出色或者 表现相近。实验也表明目标正态化的 MOEA/D 算法可以解决规模围相异的多目标问题，同 时使用一个先进分解方法的 MOEA/D 可以产生一组分别非常均匀的解对于有 3 个目标问题 的测试样例。最后，MOEA/D 在较小种群数量是的性能，还有可扩展性和敏感性都在本篇 论文过实验经行了相应的研究。
I. 介绍
多目标优化问题可以用下面式子表示：
其中 Ω 是决策空间， 以得到的目标集合成为
，包含了 m 个实值目标方法， 被称为目标区间。对于可 。
如果
，并且所有的目标函数都是连续的，那么 Ω 则可以用
其中 hj 是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获
得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义 Pareto 最 优。
令 u, v∈Rm，如果
对于任意的 i，并且至少存在一个
，那
么 u 支配 v。如果在决策空间中，没有一个点 F(y)能够支配 F(x)点，那么 x 就是 Pareto 最优， F(x)则被称为 Pareto 最优向量。换句话说，对于 Pareto 最优点在某一个目标函数上的提高， 都会造成至少一个其余目标函数的退化。所有 Pareto 最优解的集合称为 Pareto 集合，所有 最优向量的集合被称为 Pareto 前沿。
在许多多目标优化的实际应用中，通过选择器选择一个接近 Pareto 最优前沿的解作为 最后的解。大多数多目标优化问题都有许多甚至是无穷个 Pareto 最优向量，如果想要获得 一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一 个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往 往是获得一个均匀分布在 Pareto 最优前沿周围的最优解向量，这样就具有更好的代表性。 许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。
一般来说，在温和控制下多目标优化问题的 Pareto 最优解，可以看做是一个标量优化 问题的最优解(其中目标函数是 fi 的集合)。因此，Pareto 最优前沿的近似求解可以被分解为
摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。 I.介绍 多目标优化问题可以用下面式子表示： Maximize F(x)=((f1(f)…...f f(f))f subject to x∈Ω 其中Ω是决策空间，F：Ω→f f，包含了m个实值目标方法，f f被称为目标区间。对于 可以得到的目标集合成为{F(x)|x∈Ω}。 如果x∈R m，并且所有的目标函数都是连续的，那么Ω则可以用 Ω={x∈f f|h f(x)≤0,j=1……m} 其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。 令u, v∈Rm，如果f f≥f f对于任意的i，并且至少存在一个f f≥f f(i,j∈{1…..m})，那么u支配v。如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。换句话说，对于Pareto最优点在某一个目标函数上的提高，都会造成至少一个其余目标函数的退化。所有Pareto最优解的集合称为Pareto集合，所有最优向量的集合被称为Pareto前沿。 在许多多目标优化的实际应用中，通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量，如果想要获得一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量，这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。 一般来说，在温和控制下多目标优化问题的Pareto最优解，可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此，Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法，最流行的是切比雪夫法和加权法。最近，边界交叉方法也引起了许多的关注。 如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中，所有的解都可以通过他们的目标函数值进行对比，而挑战
龙源期刊网 https://www.doczj.com/doc/a813648418.html, 多目标优化进化算法比较综述 作者：刘玲源 来源：《决策与信息·下旬刊》2013年第07期 摘要多目标优化是最优化领域的一个重要研究方向，本文简要介绍了多目标优化的模型和几种多目标优化的进化算法，并对算法进行了简要比较。 关键词多目标优化粒子群遗传算法蚁群算法人工免疫系统 中图分类号：TP391 文献标识码：A 一、背景 多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。 二、不同算法介绍 （一）多目标遗传算法。 假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。 （二）人工免疫系统。 人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。 （三）多目标PSO约束算法。
i x 是第t 代种群中个体，其rank 值定义为： ()(,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j P o p m S h dij ∈ = ??? ?∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果
第九章多目标优化算法习题与答案 1. 填空题 （1）多目标优化问题由于存在目标，使得同时优化的对象增多。由于目标之间往往相互冲突，某一目标性能的提高会引起其他目标性能的，因此只能通过的方法使所有目标尽可能达到最优。 （2）多目标优化问题需要求解一个由不同程度折中的组成的解集，并且需要保证解集的和，这就导致多目标优化问题的求解难度远远大于单目标优化问题。 解释： 本题考查多目标优化算法的基础知识。 具体内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： （1）多个，降低，权衡折中 （2）最优解，收敛性，均匀性 2.如何理解多目标优化问题？ 解释： 本题考查多目标优化问题的形式和实质。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 多目标优化问题由于存在多个目标，优化对象增多，且目标之间往往是相互冲突的，某一目标性能的提高会引起其他目标性能的降低，因此只能通过权衡折中的方法使所有目标尽可能达到最优。不同于单目标优化只需求得一个最优解，多目标优化需要求解一个由不同程度折中的最优解组成的解集，且需同时保证解集的收敛性和均匀性。例如，购买汽车时考虑到汽车性能和价格两个方面，往往
当性能较好时性能优良且价格昂贵，而性能较差时价格低廉，人们总是想得到价格便宜同时性能又好的汽车，但这两方面往往不能同时兼优，只能在某一方面有所偏重，这就形成了一个以汽车性能（比如百米加速时间）和价格为两个冲突目标的多目标优化问题。 3. 试举例说明Pareto 支配关系具有传递性。 解释： 本题考查Pareto 支配关系的性质。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 假设两目标最小优化的三个个体，123=(2,2)=(3,3)=(4,4)C C C ，，，则1 2C C ， 2 3C C ，又因为1 3C C ，所以Pareto 支配关系具有传递性。 4. 考虑一个具有两个目标最小化问题，20个个体的进化群体，进行Pareto 非支配排序分层。20个个体定义如下：C 1=(9,1)，C 2=(7,2)，C 3= (5,4)，C 4=(4,5)，C 5=(3,6)，C 6=(2,7)，C 7=(1,9)，C 8=(10,1)，C 9=(8,5)，C 10=(7,6)，C 11=(5,7)，C 12=(4,8)，C 13=(3,9)，C 14=(10,5)，C 15=(9,6)，C 16=(8,7)，C 17=(7,9)，C 18=(10,6)，C 19=(9,7)，C 20=(8,9) 解释： 本题考查基于Pareto 支配的排序方法。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 由于{}18C C ；{}2349,,C C C C ；{}234510,,,C C C C C ；{}345611,,,C C C C C ； {} 45612 ,,C C C C ； {} 56713 ,,C C C C ； {} 12348914 ,,,,,C C C C C C C ；{} 1234591015 ,,,,,,C C C C C C C C ； {} 234569101116 ,,,,,,,C C C C C C C C C ；
多目标优化的求解方法 多目标优化（MOP）是数学规划的一个重要分支，是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下： 多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。目前主要有以下方法： （1）评价函数法。常用的方法有:线性加权和法、极大极小法、理想点法。评价函数法的实质是通过构造评价函数式把多目标转化为单目标。 （2）交互规划法。不直接使用评价函数的表达式，而是使决策者参与到求解过程，控制优化的进行过程，使分析和决策交替进行，这种方法称为交互规划法。常用的方法有：逐步宽容法、权衡比替代法，逐次线性加权和法等。 （3）分层求解法。按目标函数的重要程度进行排序，然后按这个排序依次进行单目标的优化求解，以最终得到的解作为多目标优化的最优解。 而这些主要是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。
在工程应用、生产管理以及国防建设等实际问题中很多优化问题都是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其他若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少和总的运输费用最低, 这是含有两个目标的优化问题。利用首次适配递减算法和标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺的优化。Chung等人也成功应用遗传算法对锻件工艺进行了优化。 3)投资 假设某决策部门有一笔资金要分配给若干个建设项目, 在确定投资方案时, 决策者总希望做到投资少收益大。Branke等人采用基于信封的多目标进化算法成功地解决了计划投资地选择问题。 4)模拟移动床过程优化与控制 一个工业化模拟移动床正常运行时, 一般有七股物料进、出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值的变化。根据实际生产要求通常包括生产率、产品纯度、吸附剂消耗量等多个目标。模拟移动床分离过程由于其过程操作变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁多性, 需要众多学者对其操作优化和过程控制进行深入的研究。Huang等人利用TPS 算法解决了模拟移动床多个冲突目标的最大最小的问题, 并与NSGA2 算法的结果进行了比较。吴献东等人运用粒子群算法开发出一种非线性模拟移动床( SMB )色谱分离过程的优化策略。 5)生产调度 在离散制造生产系统中, 一个工件一般经过一系列的工序加工完成, 每道工序需要特定机器和其他资源共同完成, 各工件在各机器上的加工顺序(称技术约束条件)通常是事先给定的。车间调度的作用