基于正态分布和自适应变异算子的ε截断算法

doi:10.6040/j.issn.1672-3961.0.2018.194

摘要/Abstract

摘要：

针对约束优化算法不能很好协调收敛性及分布性的问题,提出一种基于正态分布和自适应变异算子的ε截断算法。将正态分布引入模拟二进制交叉算子中,使算法可搜索的空间范围更广,更易跳出局部最优;利用自适应变异算子,将种群个体当前信息与变异算子结合起来,引导种群向真实的Pareto前沿进行进化;结合自适应的ε截断策略,保留Pareto最优解和一定数量的不可行解,同时利用不可行解的信息,加大对搜索空间的探索力度,从而提高种群多样性。采用3种标准测试函数对算法进行测试,试验结果表明:本研究所求解集能够很好的跟踪真实的Pareto解集。该方法可以有效地协调算法的收敛性及分布性。

关键词: 约束, 正态分布算子, 自适应变异算子, 自适应ε截断策略

Abstract:

It was hard for constrained optimization algorithm to maintain a good balance of convergence and distribution. To solve this problem, a ε-truncation algorithm based on the normal distribution crossover (NDX) and adaptive mutation operator was proposed, which introduced the normal distribution into the simulated binary crossover (SBX) operator, so that the algorithm could search wider space and easily jump out of local optimum. The proposed algorithm combined the adaptive mutation operator with the current information of the individual in the population, and guided the population evolving toward the real Pareto front. Moreover, it preserved the Pareto optimal solutions and a certain number of infeasible solutions with the adaptive ε truncation strategy. At the same time using the information of these infeasible solutions, it increased the search intensity of space and improved the diversity of population. According to three standard test functions experimental results, the solution set in this study could well track the real Pareto solution set. The proposed method could effectively coordinate the convergence and distribution of the algorithm.

Key words: constrained, NDX operator, adaptive mutation operator, adaptive εtruncation strategy

中图分类号:

TP273

李进,李二超. 基于正态分布和自适应变异算子的ε截断算法[J]. 山东大学学报 (工学版), 2019, 49(2): 47-53.

Jin LI,Erchao LI. Epsilon truncation algorithm based on NDX and adaptive mutation operator[J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 47-53.

图/表 10

表1

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 21

1	ASAFUDDOULA M , RAY T , SARKER R . A decomposition-based evolutionary algorithm for many objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19 (3): 445- 460. doi: 10.1109/TEVC.2014.2339823
2	YANG S , LI M , LIU X , et al. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17 (5): 721- 736. doi: 10.1109/TEVC.2012.2227145
3	MATIAS J , CORREIA A , MESTRE P , et al. Adaptive penalty and barrier function based on fuzzy logic[J]. Expert Systems with Applications, 2015, 42 (19): 6777- 6783. doi: 10.1016/j.eswa.2015.04.070
4	ELHOSSINI A , AREIBI S , DONY R . Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization[J]. Evolutionary Computation, 2014, 18 (1): 127- 156.
5	YANG D , JIAO L , GONG M . Adaptive multi-objective optimization based on nondominated solutions[J]. Computational Intelligence, 2010, 25 (2): 84- 108.
6	LIN C H . A rough penalty genetic algorithm for constrained optimization[J]. Information Sciences, 2013, 241 (241): 119- 137.
7	MEZURAMONTES E , COELLO C A C . A simple multimembered evolution strategy to solve constrained optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2005, 9 (1): 1- 17.
8	WANG Y , CAI Z , GUO G , et al. Multiobjective optimization and hybrid evolutionary algorithm to solve constrained optimization problems[J]. IEEE Transactions on Systems Man & Cybernetics Part B, 2007, 37 (3): 560- 575.
9	LEMONGE A C C , BARBOSA H J C , BERNARDINO H S . Variants of an adaptive penalty scheme for steady-state genetic algorithms in engineering optimization[J]. Engineering Computations, 2015, 32 (8): 2182- 2155. doi: 10.1108/EC-07-2014-0158
10	DEB K . An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics & Engineering, 2000, 186 (2): 311- 338.
11	CAI Zixing , WANG Yong . A multiobjective optimization-based evolutionary algorithm for constrained optimization[J]. Evolutionary Computation, IEEE Transactions on, 2006, 10 (6): 658- 675. doi: 10.1109/TEVC.2006.872344
12	WANG Yong , CAI Zixing , ZHOU Yuren , et al. An adaptive tradeoff model for constrained evolutionary optimization[J]. Evolutionary Computation, IEEE Transactions on, IEEE Transactions on, 2008, 12 (1): 80- 92.
13	WOLDESENBET Y G , Yen G G , TESSEMA B G . Constraint handling in multiobjective evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13 (3): 514- 525. doi: 10.1109/TEVC.2008.2009032
14	王勇, 蔡自兴, 周育人, 等. 约束优化进化算法[J]. 软件学报, 2009, 20 (1): 11- 29.
	WANG Yong , CAI Zixing , ZHOU Yuren , et al. Constrained optimization evolutionary algorithms[J]. Journal of Software, 2009, 20 (1): 11- 29.
15	李智勇, 黄滔, 陈少淼, 等. 约束优化进化算法综述[J]. 软件学报, 2017, 28 (6): 1529- 1546.
	LI Zhiyong , HUANG Tao , CHEN Shaomiao , et al. Overview of constrained optimization evolutionary algorithms[J]. Journal of Software, 2017, 28 (6): 1529- 1546.
16	张敏.约束优化和多目标优化的进化算法研究[D].合肥:中国科学技术大学, 2008.
	ZHANG Min. Research on evolutionary algorithms for constrained optimization and multiobjective optimization[D]. Hefei: University of Science and Technology of China, 2008.
17	肖易寒, 李明逵, 陈立伟. 基于改进NSGA-Ⅱ算法的多光谱测温数据处理[J]. 应用科技, 2017, 44 (1): 33- 39.
	XIAO Yihan , LI Mingkui , CHEN Liwei . Multispectral temperature measurement based on improved adaptive NSGA-Ⅱ algorithm[J]. Applied Science and Technology, 2017, 44 (1): 33- 39.
18	毕晓君, 张磊. 基于自适应ε截断策略的约束多目标优化算法[J]. 电子与信息学报, 2016, 38 (8): 2047- 2053.
	BI Xiaojun , ZHANG Lei . Constrained multi-objective optimization algorithm with adaptive ε truncation strategy[J]. Journal of Electronics & Information Technology, 2016, 38 (8): 2047- 2053.
19	DEB K, PRATAP A, MEYARIVAN T. Constrained test problems for multi-objective evolutionary optimization[C]//Proceedings of First International Conference on Evolutionary Multi-Criterion Optimization, EMO 2001, Zurich, Switzerland: EMO, 2001: 284-298.
20	韩红艳.基于Pareto支配的高维多目标进化算法研究[D].大连:大连理工大学, 2016.
	HAN Hongyan. Research of Pareto dominance based many-objective evolutionary algorithm[D]. Dalian: Dalian University of Technology, 2016.
21	JIANG S , YANG S . A steadystate and generational evolutionary algorithm for dynamic multi-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21 (1): 65- 82.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

测试函数	SP				IGD
	NDXAMAENSGA-Ⅱ		FRNSGA-Ⅱ		NDXAMAENSGA-Ⅱ		FRNSGA-Ⅱ
	均值	方差	均值	方差	均值	方差	均值	方差
SRN	0.093 2	0.001 4	1.176 2	0.072 3	0.002 8	0.002 5	0.022 3	0.028 6
BNH	0.421 4	0.050 6	0.802 4	0.049 8	0.009 3	0.007 1	0.038 5	0.018 9
CON	0.039 7	0.078 6	0.078 5	1.265 8	0.010 5	0.020 7	0.076 4	0.124 6

[1]	胡建平,李鑫,谢琪,李玲,张道畅. 基于Delaunay三角化的二维无约束优化EMD方法[J]. 山东大学学报 (工学版), 2018, 48(5): 9-15, 37.
[2]	钱淑渠,武慧虹,徐国峰,金晶亮. 计及排放的动态经济调度免疫克隆演化算法[J]. 山东大学学报(工学版), 2018, 48(4): 1-9.
[3]	曹雅,邓赵红,王士同. 基于单调约束的径向基函数神经网络模型[J]. 山东大学学报(工学版), 2018, 48(3): 127-133.
[4]	刘志清,高浩瀚,安沫霖,张学凯. 基于完工概率修正的关键链法项目进度优化[J]. 山东大学学报(工学版), 2018, 48(1): 104-111.
[5]	刘大琨,谭晓阳. 基于流形的约束局部模型拟合[J]. 山东大学学报(工学版), 2016, 46(3): 31-36.
[6]	韩忠明, 吴杨, 谭旭升, 刘雯, 杨伟杰. 社会网络结构洞节点度量指标比较与分析[J]. 山东大学学报(工学版), 2015, 45(1): 1-8.
[7]	王兴良,王立宏*,李海军. 谱聚类中特征向量的Bagging选取方法[J]. 山东大学学报(工学版), 2013, 43(2): 35-41.
[8]	张潇丹,赵力,邹采荣*. 一种改进的混合蛙跳算法求解有约束优化问题[J]. 山东大学学报(工学版), 2013, 43(1): 1-8.
[9]	何荣福1,肖民卿2*. 圆形区域极点约束下的δ算子时滞系统鲁棒L2-L∞控制[J]. 山东大学学报(工学版), 2013, 43(1): 69-79.
[10]	徐姗姗,刘应安*,徐昇. 立体匹配中边界信息的强化算法[J]. 山东大学学报(工学版), 2012, 42(6): 43-49.
[11]	丁彦,李永忠*. 基于PCA和半监督聚类的入侵检测算法研究[J]. 山东大学学报(工学版), 2012, 42(5): 41-46.
[12]	潘志远1, 韩学山1*, 刘超男2. 交流潮流约束下的机组组合求解[J]. 山东大学学报(工学版), 2012, 42(2): 130-137.
[13]	张友新,王立宏. 两阶段近邻传播半监督聚类算法[J]. 山东大学学报(工学版), 2012, 42(2): 18-22.
[14]	颜子夜,陆耀,李建武,马跃. 一种基于核主成分分析的图像超分辨率算法[J]. 山东大学学报(工学版), 2011, 41(4): 101-105.
[15]	李军辉. 一种实现延时无源宏模型的快速方法[J]. 山东大学学报(工学版), 2011, 41(3): 59-61.