基于信息熵的改进PESA算法

doi:10.3969/j.issn.1000-436x.2013.11.005

通信学报 ›› 2013, Vol. 34 ›› Issue (11): 33-41.doi: 10.3969/j.issn.1000-436x.2013.11.005

基于信息熵的改进PESA算法

王堃¹,王琳琳¹,刘艳²,张玉华¹,吴蒙¹

¹ 南京邮电大学宽带无线通信与传感网技术教育部重点实验室，江苏南京 210003
² 南京工业大学自动化与电气工程学院，江苏南京 210009

出版日期:2013-11-25 发布日期:2017-06-23
基金资助:
国家重点基础研究发展计划(“973”计划)基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;教育部高等学校博士学科点专项科研基金资助项目;江苏省高校自然科学研究基金资助项目;江苏省高校自然科学研究基金资助项目;南京邮电大学宽带无线通信与传感网技术教育部重点实验室开放研究基金资助项目

Improved PESA algorithm based on comentropy

Kun WANG¹,Lin-lin WANG¹,Yan LIU²,Yu-hua ZHANG¹,Meng WU¹

¹ Key Lab of Broadband Wireless Communication and Sensor Network Technology, Ministry of Education, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
² College of Automation and Electrical Engineering, Nanjing University of Technology, Nanjing 210009, China

Online:2013-11-25 Published:2017-06-23
Supported by:
The National Basic Research Program of China(973 Program);The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Specialized Fund for the Doctoral Program of Higher Educa-tion;The Program of Natural Science for Universities of Jiangsu Province;The Program of Natural Science for Universities of Jiangsu Province;Open Research Fund of Key Lab of Broadband Wireless Comm and Netw Technology (NUPT) of Ministry of Education

摘要/Abstract

摘要：

针对PESA算法所需的计算运算量、计算难度及运算时间都随着解集数量的增加而急剧增加的问题，将熵值度量指标引入到PESA算法中，提出了基于信息熵的PESA算法(C-PESA, comentropy-based PESA)。该算法根据信息熵指标在量化度量Pareto解集的分布特性，判断种群进化是否到达成熟阶段，本算法迭代1300次时即到达成熟阶段，从而尽早结束了算法复杂的优化过程，在一定程度上简化了PESA算法的时间复杂度。仿真结果表明，随着进化种群数量的增长，C-PESA算法的计算量只是呈现线性增加，算法的计算时间缩短接近4倍，进化计算效率得到提高。

关键词: 进化计算, PESA算法, 多目标优化, 信息熵

Abstract:

Aiming at the issue that the computational effort the complexity and the running time of PESA algorithm are increasing rapidly with the growth of the solutions set number, a comentropy-based PESA algorithm (C-PESA) by merg-ing the entropy value metric into PESA algorithm was proposed. According to the distributed characteristic of the entropy value metric over the Pareto solution set, the proposed algorithm could determine whether the population has developed to the mature stage, which is reached when the number iterations is 1 300 in C-PESA. Thereby, the optimization process can be finished as soon as possible, and in a certain extent, the time complexity of PESA was simplified. Simula-tion results show that the computational effort of C-PESA increases linearly with the rising number of solutions. Mean-while, the computation time is improved almost four times, and the evolutionary computation efficiency is also enhanced.

Key words: evolutionary computation, PESA algorithm, multi-objective optimization, comentropy

王堃,王琳琳,刘艳,张玉华,吴蒙. 基于信息熵的改进PESA算法[J]. 通信学报, 2013, 34(11): 33-41.

Kun WANG,Lin-lin WANG,Yan LIU,Yu-hua ZHANG,Meng WU. Improved PESA algorithm based on comentropy[J]. Journal on Communications, 2013, 34(11): 33-41.

图/表 11

图1

图2

表1

实验中用到的测试问题"

测试问题	维数	变量域	目标函数
ConstrEx	2	x₁∈[0.1,1.0]	f₁(x)=x₁
		x₂∈[0,5]	f₂(x)=(1+x₂)/x₁
ZDT1	30	x_i∈[0,1]	$f_{1} (x) = x_{1}, f_{2} (x) = g (x) [1 - \sqrt{x_{1} / g (x)}]$
			$g (x) = 1 + 9 (\sum_{i = 2}^{n} x_{i}) / (n - 1)$
Kursawe	3	x_i∈[?5,5]	$f_{1} (x) = \sum_{i = 1}^{n - 1} (- 10 e^{(- 0.2) \sqrt{x_{i}^{2} + x_{i} + 1}})$
			$f_{2} (x) = \sum_{i = 1}^{n} ({\| x_{i} \|}^{a} + 5 sin (x_{i}^{b}))$
DTLZ1	k+\|xk\|-1	x_k∈[0,1]	$f_{1} (x) = \frac{1}{2} x_{1} x_{2} \dots x_{k - 1} (1 + g (x_{k}))$
			$f_{2} (x) = \frac{1}{2} x_{1} x_{2} \dots (1 - x_{k - 1}) (1 + g (x_{k}))$
			$⋮$
			$f_{k - 1} (x) = \frac{1}{2} x_{1} (1 - x_{2}) (1 + g (x_{k}))$
			$f_{k} (x) = \frac{1}{2} (1 - x_{1}) (1 + g (x_{k}))$
			$where g (x_{k}) = 100 [\| x_{k} \| + \sum_{x_{i} \in x_{k}} ({(x_{i} - 0.5)}^{2} - \cos (20 p (x_{i} - 0.5)))]$

表1

表2

图3

图4

图5

图6

表3

实验中的相关度量指标"

名称	表达式	参数说明
GD (generational distance)	$G D ≙ 1 / N_{known} \sqrt{\sum_{i = 1}^{N_{known}} d_{i}^{2}}$	N_known：进化所得前端解集的解点数量。d_i：进化解集和真实Pareto前端间的距离
		A是目标向量
HV(hypervolume)	$H V (A) : = \int_{(0, \dots, 0)}^{(1, \dots, 1)} \partial_{A} (z) d z$	Z是目标空间
HV(hypervolume)		$¶$ 是attainment方程^[23]
IGD(inverted generational distance)	${IGD}_{(p, p_{t})} = \frac{\sqrt{\sum_{\vec{x} \in p_{t}} {(d_{\min} (\vec{x}, p))}^{2}}}{\| p_{t} \|}$	P_t是Pareto 最优解前端解集，P是非支配解集，d _min(x,p)是非支配解集中的解点x到Pareto前端的最短欧几里得距离

表3

图7

表4

参考文献 25

[1]	SALEM F A , PETER J F . Diversity management in evolutionary many-objective optimization[J]. IEEE Trans on Evolutionary Compu-tation, San Jose, 2011,15 (2): 183-195.
[2]	OLIVER S , ADRIANA L , CARLOS A . On the influence of the num-ber of objectives on the hardness of a multiobjective optimization problem[J]. IEEE Transactions on Evolutionary Computatn, San Jose, 2011,15 (4): 444-455.
[3]	SCHAFFER J D . Multiple objective optimization with vec eva-luated genetic algorithms[A]. Proceedings of the International Confe-rence on Genetic Algorithms and Their Applications[C]. tsburgh,PA,USA, 1985.93-100.
[4]	CORNE D W , KNOWLES J D , OATES M J . The Pareto-envelope based selection algorithm for multi-objective optimization[A]. Pro-ceedings of the International Conference on Parallel Problem Solving from Nature[C]. Paris, France, 2000.839-848.
[5]	公茂果，焦李成，杨咚咚等. 进化多目标优化算法研究[J]. 软件学报, 2009,20 (2): 271-289. GONG M G , JIAO L C , YANG D D , et al. Research on evolutionary multi-objective optimization algorithms[J]. Journal of Software, 2009,20 (2): 271-289.
[6]	[EB/OL].
[7]	DAVID R W , ANDREA A , JOHN A C . Evolutionary improvement of programs[J]. IEEE Transactions on Ecolutionary Computation, 2011,15 (4): 515-538.
[8]	ABIDO M A . Two-level of nondominated solutions approach to mul-tiobjective particle swarm optimization[A]. Proceedings of Genetic and Evolutionary Computation Conference[C]. London, 2007.728-733.
[9]	RODRIGO P , LEANDRO N , DE C , et al. Neural network ensembles:immune-inspired approaches to the diversity of components[J]. Natu-ral Computing, 2010,9 (3): 625-653.
[10]	LOURDES A , JUAN J M . Diversity through multiculturality: assess-ing migrant choice policies in an island model[J]. IEE Transactions on Ecolutionary Computation, 2011,15 (4): 543-560.
[11]	SAXENA D K , DEB K . Non-Linear dimensionality reduction proce-dure for certain large-dimensional multi-objective optimization prob-lems: employing correntropy and a novel maximum variance unfold-ing[A]. Proceedings of the 4th International Conference on Evolutio-nary Multi-Criterion Optimization[C]. Sendai, Japan, 2007.772-787.
[12]	SHANNON C E . A mathematical theory of communication[J]. Bell System Technical Journal, 1948,27: 379-429.
[13]	TAN K C , GOH C K , MAMUN A A , et al. An evolutionary artificial immune system for multi-objective optimization[J]. European Journal of Operational Research, 2008,187: 371-392.
[14]	ALI F M , SHAPOUR A . On the entropy of multi-objective design optimization solution set[A]. Proceedings of Design En ineering Technical Conferences and Computer and Information in ngineering Conference[C]. Chicago, USA, 2002.829-838.
[15]	CORNE D W , JERRAM N R , KNOWLES J D , et al. PESA-II: re-gion-based selection in evolutionary multi-objective optimization[A]. Proceedings of the Genetic and Evolutionary Computatio Confe-rence[C]. San Francisco, USA, 2001.283-290.
[16]	MIKKEL T J . Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003,7 (5): 503-515.
[17]	ZHANG Q F , LI H . MOEA/D: a multiobjective evolutionary algo-rithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11 (6): 712-731.
[18]	[EB/OL].
[19]	[EB/OL].
[20]	KURSAWE F . A variant of evolution strategies for vector optimiza-tion[A]. Proceedings of International Conference on Parallel Problem Solving from Nature[C]. London, UK, 1991.193-197.
[21]	ZITZLER E , DEB K , THIELE L . Comparison of multi-objective evolutionary algorithms: empirical results[J]. Evoluti ry Computa-tion, 2000,8 (2): 173-195.
[22]	VAN VELDHUIZEN D A , LAMONT G B . Evolutionary computation and convergence to a pareto front[A]. Late Breaking Papers at the Ge-netic Programming 1998 Conference[C]. California, USA, 1998.221-228.
[23]	CAO Y . Matlab central file exchange: hypervolume indicator[EB/OL]. , 2008.
[24]	VELDHUIZEN D A , VAN LAMONT G B . Multiobjective Evolutio-nary Algorithm Research: A History and Analysis[R]. Techique Re-port, 1998.
[25]	DEB K , AGRAWAL R B . Simulated binary crossover for continuous search space[J]. Complex Systems, 1994,1 (9): 115-148.

C-PESA参数	参数值
交叉分布指数(distribution index for crossover)	15
交叉概率(crossover probability)	0.8
突变分布指数(distribution index for mutation)	20
突变概率(mutation probability)	1/n(n是输入数量)

符号	描述
lb_k(k=1,2,?,r)	上边界
ub_k(k=1,2,?,r)	下边界
rⁱ,i=(i₁,i₂,?,i_r)	超立方体HC
D	每个维度上的分割次数
w_k	第k维上每一个小区域的宽度
range_k	第k维的宽度
a₁,a₂,?,a_m	每一维度上网格的数量
O(l_{i? y})	目标空间的影响函数
l_{?i y}	第i个目标点和第y个目标点之间的欧几里得距离
S	分布程度的标准偏差
R	欧几里得距离
D()	密度函数
W(l(＜i₁,i₂,…,i_m＞,y))	第a_m维度上第i个目标点和第y个目标点之间的欧几里得距离
＜u₁,u₂,?,u_m,＞	超网格
u_k	网格标识
?_ij	标准化密度
i,j	网格位置索引
k₁,k₂,?,k_m	m维维度上的位置索引

基于信息熵的改进PESA算法

Improved PESA algorithm based on comentropy

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.
[2]	张忠平, 刘伟雄, 张玉停, 邓禹, 魏棉鑫. ERDOF：基于相对熵权密度离群因子的离群点检测算法[J]. 通信学报, 2021, 42(9): 133-143.
[3]	毛伊敏, 邓千虎, 陈志刚. 基于信息熵与遗传算法的并行关联规则增量挖掘算法[J]. 通信学报, 2021, 42(5): 122-136.
[4]	诸天逸,李凤华,金伟,郭云川,房梁,成林. 互操作性与自治性平衡的跨域访问控制策略映射[J]. 通信学报, 2020, 41(9): 29-48.
[5]	张沛,刘帅军,马治国,王晓晖,宋俊德. 基于深度增强学习和多目标优化改进的卫星资源分配算法[J]. 通信学报, 2020, 41(6): 51-60.
[6]	苏命峰,王国军,李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115.
[7]	鲍楠,左加阔,胡晗,鲍煦. 基于SDN的网络资源选择多目标优化算法[J]. 通信学报, 2019, 40(2): 51-59.
[8]	田俊峰, 王子龙, 何欣枫, 李珍. 基于Shamir的虚拟机放置策略[J]. 通信学报, 2019, 40(10): 90-100.
[9]	郝晓辰,王立元,刘金硕,解力霞,张文焕. WSN中基于双群体差分进化的资源分配优化算法[J]. 通信学报, 2018, 39(4): 68-75.
[10]	俞艺涵,付钰,吴晓平. 基于Shannon信息熵与BP神经网络的隐私数据度量与分级模型[J]. 通信学报, 2018, 39(12): 10-17.
[11]	孙鹏浩,兰巨龙,张少军,李军飞. 基于信息熵的匹配域裁剪算法[J]. 通信学报, 2017, 38(5): 182-189.
[12]	俸皓,罗蕾,王勇,叶苗. 无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略[J]. 通信学报, 2017, 38(3): 112-123.
[13]	马学彬,李爱丽,张晓娟. 基于多目标优化的固定中继节点唤醒策略[J]. 通信学报, 2017, 38(10): 47-59.
[14]	刘星宝,殷建平,胡春华,陈荣元. 解决动态多中心问题的自学习差异进化算法[J]. 通信学报, 2015, 36(7): 166-175.
[15]	王琪,孙毅,李军,张珺,笪斌,李志诚. 无线ad hoc网络多性能指标基本性能边界[J]. 通信学报, 2015, 36(6): 1-140.