基于适应值曲面分析的全部局部极值搜索算法

doi:10.3969/j.issn.1001-506X.2020.02.13

摘要/Abstract

摘要：

为求得类似仿真函数的黑箱函数优化问题的全部局部极值点,提出了一种基于适应值曲面分析的新算法。首先,对适应值距离相关系数(fitness distance correlation, FDC)进行了改进,探讨了改进FDC指标与适应值曲面崎岖度的对应关系。在此基础上,设计了基于FDC的重复对分区域法(FDC based repeated split region, FRSR),对可行域依据崎岖度进行分解,得到满足崎岖度要求的若干子区间,并在这些子区间上依据FDC指标设置初始点,然后利用模式搜索算法进行寻优。通过对比FRSR法与传统的均匀分配初始点法以及其他现有方法,验证了FRSR法能够以较少的初始点得到全部局部极值,在速度上和解的质量上都优于传统方法。

关键词: 适应值曲面, 适应值距离相关系数, 局部极值点, 黑箱函数

Abstract:

To locate all local optimum of the black box function, such as the simulation function, a method based on fitness landscape analysis is proposed. Firstly, the fitness distance correlation (FDC) is modified according to the characteristics of our problem, and the relationship between the modified FDC and the roughness grade of the fitness landscape is explored. Based on the relationship, an FDC based repeated split region method (FRSR) is designed to breakdown the whole feasible region into several acceptable sub-regions according to the FDC value, and a certain number of initial search points are assigned in each sub-region based on the FDC value of the sub-region, followed by an optimization procedure using the pattern search algorithm. Experimental results show that the proposed method can locate all local optimum with feuer initial points, and comparison study shows that it performs better than traditional methods, such as the uniformly generating initial points method and other known methods, both in speed and in quality of the solution.

Key words: fitness landscape, fitness distance correlation (FDC), local optimum, black box function

中图分类号:

TP391.9

吴诗辉, 李正欣, 张发, 刘晓东, 周宇. 基于适应值曲面分析的全部局部极值搜索算法[J]. 系统工程与电子技术, 2020, 42(2): 346-355.

Shihui WU, Zhengxin LI, Fa ZHANG, Xiaodong LIU, Yu ZHOU. Algorithm for locating all local optimum based on fitness landscape analysis[J]. Systems Engineering and Electronics, 2020, 42(2): 346-355.

图/表 15

图1

图2

图3

图4

图5

图6

图7

表1

图8

表2

图9

表3

表4

图10

表5

参考文献 26

1	TÖRN A , ŽILINSKAS A . Global optimization[M]. Lecture Notes in Computer Science, Berlin: Springer, 1989: 1- 216.
2	SALHI S , QUEEN N M . A hybrid algorithm for identifying global and local minima when optimizing functions with many minima[J]. European Journal of Operational Research, 2004, 155 (1): 51- 67.
3	TSOULOS I G , LAGARIS I E . Minfinder: locating all the local minima of a function[J]. Computer Physics Communications, 2006, 174 (2): 166- 179. doi: 10.1016/j.cpc.2005.10.001
4	TSOULOS I G , STAVRAKOUDIS A . On locating all roots of systems of nonlinear equations inside bounded domain using global optimization methods[J]. Nonlinear Analysis: Real World Applications, 2010, 11 (4): 2465- 2471. doi: 10.1016/j.nonrwa.2009.08.003
5	LAGARIS I E , TSOULOS I G . Stopping rules for box-constrained stochastic global optimization[J]. Applied Mathematics and Computation, 2008, 197 (2): 622- 632. doi: 10.1016/j.amc.2007.08.001
6	刘杰, 王宇平. 一类求多变量函数所有局部极小点的算法[J]. 软件学报, 2013, 24 (10): 2267- 2274.
	LIU J , WANG Y P . Algorithm for locating all lcal minima of multidimensional function[J]. Journal of Software, 2013, 24 (10): 2267- 2274.
7	吴诗辉, 刘晓东, 邵悦, 等. 一种基于神经网络的仿真优化方法[J]. 系统仿真学报, 2018, 30 (1): 36- 44.
	WU S H , LIU X D , SHAO Y , et al. Optimization via simulation based on neural network[J]. Journal of System Simulation, 2018, 30 (1): 36- 44.
8	吴诗辉, 张发, 李正欣, 等. 基于神经网络的仿真优化算法设计[J]. 系统工程与电子技术, 2019, 41 (6): 1324- 1335.
	WU S H , ZHANG F , LI Z X , et al. Design of algorithm for neural network based optimization via simulation[J]. Systems Engineering and Electronics, 2019, 41 (6): 1324- 1335.
9	谢红侠, 马晓伟, 陈晓晓, 等. 基于多种群的改进粒子群算法多模态优化[J]. 计算机应用, 2016, 36 (9): 2516- 2520.
	XIE H X , MA X W , CHEN X X , et al. Enhanced multi-species -based particle swarm optimization for multi-modal function[J]. Journal of Computer Applications, 2016, 36 (9): 2516- 2520.
10	FAN D C, SHENG W G, CHEN S Y. A diverse niche radii niching technique for multimodal function optimization[C]// Proc.of the Chinese Automation Congress (CAC), 2013: 70-74.
11	陈娟, 徐立鸿. 动态小生境遗传算法在多模函数优化中的应用[J]. 同济大学学报(自然科学版), 2006, 34 (5): 684- 688. doi: 10.3321/j.issn:0253-374X.2006.05.024
	CHEN J , XU L H . A dynamic niche genetic algorithm for multimodal function optimization[J]. Journal of Tongji University (Natural Science), 2006, 34 (5): 684- 688. doi: 10.3321/j.issn:0253-374X.2006.05.024
12	LI Y K , CHEN Y L , ZHONG J H , et al. Niching particle swarm optimization with equilibrium factor for multi-modal optimization[J]. Information Sciences, 2019, 494 (c): 233- 246.
13	HAGHBAYAN P , NEZAMABADI-POUR H , KAMYAB S . A niche GSA method with nearest neighbor scheme for multimodal optimization[J]. Swarm and Evolutionary Computation, 2017, 35, 78- 92. doi: 10.1016/j.swevo.2017.03.002
14	PASSARO A , STARITA A . Particle swarm optimization for multimodal function: a clustering approach[J]. Journal of Artificial Evolution and Application, 2008, (2008): 1- 15.
15	CHANG W D . Multimodal function optimizations with multiple maximums and multiple minimums using an improved PSO algorithm[J]. Applied Soft Computing, 2017, 60 (c): 60- 72.
16	PENG X G , JIN Y C , WANG H D . Multimodal optimization enhanced cooperative coevolution for large-scale optimization[J]. IEEE Trans.on Cybernetics, 2019, 49 (9): 3507- 3520. doi: 10.1109/TCYB.2018.2846179
17	王文国, 吴宗月. 一种基于"拥挤度"概念的人工蜂群算法改进[J]. 通信技术, 2016, 49 (7): 867- 871. doi: 10.3969/j.issn.1002-0802.2016.07.014
	WANG W G , WU Z Y . Improved artificial bee colony algorithm based on congestion concept[J]. Communications Technology, 2016, 49 (7): 867- 871. doi: 10.3969/j.issn.1002-0802.2016.07.014
18	唐莉.人工鱼群行为及其拥挤度因子的研究[D].南京:南京理工大学, 2017.
	TANG L. The research of artificial fish school's behavior and congestion factor[D]. Nanjing: Nanjing University of Science & Technology, 2017.
19	宋万祯, 雷晓辉, 黄晓敏, 等. 考虑拥挤度的多目标粒子群优化算法在马斯京根参数估计中的应用[J]. 水电能源科学, 2013, 31 (1): 38- 41.
	SONG W Z , LEI X H , HUANG X M , et al. Application of multi-objective particle swarm optimization in Muskingum parameter estimation considering crowding distance[J]. Water Resources and Power, 2013, 31 (1): 38- 41.
20	郭惠昕, 张龙庭. 混合离散变量优化设计的复合遗传算法[J]. 机械设计, 2005, 22 (3): 9- 11.
	GUO H X , ZHANG L T . Compound genetic algorithm on optimization design of hybrid discrete variables[J]. Journal of Machine Design, 2005, 22 (3): 9- 11.
21	WEINBERGER E D . Correlated and uncorrelated fitness landscapes and how to tell the difference[J]. Biological Cybernetics, 1990, 63, 325- 326. doi: 10.1007/BF00202749
22	陈晔, 李有梅. 约束P-中位问题的适应值曲面分析[J]. 山西大学学报(自然科学版), 2005, 28 (2): 138- 141. doi: 10.3969/j.issn.0253-2395.2005.02.010
	CHEN Y , LI Y M . Fitness landscape analysis for capactitated P-median problem[J]. Journal of Shanxi University (Natural Science Edition), 2005, 28 (2): 138- 141. doi: 10.3969/j.issn.0253-2395.2005.02.010
23	DAVID M . Visualizing fitness landscapes[J]. Evolution, 2011, 65 (6): 1544- 1558. doi: 10.1111/j.1558-5646.2011.01236.x
24	JONES T, FORREST S. Fitness distance correlation as a measure difficulty for genetic algorithms[C]//Proc.of the 6th International Conference on Genetic Algorithms, 1995: 184-192.
25	VANNESCHI L, TOMASSINI M, COLLARD P, et.al. Fitness distance correlation in genetic programming: a constructive counterexample[C]//Proc.of the Congress on Evolutionary Computation, 2004.
26	吴诗辉, 杨建军, 郭亚坤. 基于模式搜索的导弹目标分配方法研究[J]. 战术导弹技术, 2009, (3): 29- 32. doi: 10.3969/j.issn.1009-1300.2009.03.007
	WU S H , YANG J J , GUO Y K . Research on the method of missile target assignment based on pattern search[J]. Tactical Missile Technology, 2009, (3): 29- 32. doi: 10.3969/j.issn.1009-1300.2009.03.007

子区间	fdc				初始点数量n_i
子区间	h=0.5	h=0.2	h=0.1	h=0.01	初始点数量n_i
S₁	0.920 78	0.934 77	0.938 16	0.940 28	5
S₂	0.888 98	0.888 53	0.903 4	0.905 77	6
S₃	0.839 98	0.833 64	0.831 25	0.828 99	6
S₄	0.664 07	0.506 58	0.453 12	0.451 77	-
S₅	0.497 29	0.323 93	0.330 25	0.303 6	-
S₆	0.494 75	0.506 58	0.453 12	0.451 77	-
S₇	0.839 98	0.833 64	0.831 25	0.828 99	6
S₈	0.888 98	0.888 53	0.903 4	0.905 77	6
S₉	0.920 78	0.934 77	0.938 16	0.940 28	5
取样数量	25	121	441	40 401	-

序号	fdc	初始点数量n_i	序号	fdc	初始点数量n_i
SS₁	0.809 39	6	SS₇	0.687 36	7
SS₂	0.790 23	6	SS₈	0.571 54	9
SS₃	0.940 09	5	SS₉	0.923 5	5
SS₄	0.923 5	5	SS₁₀	0.940 09	5
SS₅	0.571 54	9	SS₁₁	0.790 23	6
SS₆	0.687 36	7	SS₁₂	0.809 39	6

局部极小	x₁	x₂	y_min	初始点个数
P₁	-1.703 6	0.796 1	-0.215 5	5
P₂	-1.607 1	-0.568 7	2.104 3	2
P₃	-0.089 8	0.712 7	-1.031 6	33
P₄	0.089 8	-0.712 7	-1.031 6	30
P₅	1.607 1	0.568 7	2.104 3	2
P₆	1.703 6	-0.796 1	-0.215 5	4

局部极小	x₁	x₂	y_min	初始点个数
P₁	-1.703 6	0.796 1	-0.215 5	10
P₂	-0.089 8	0.712 7	-1.031 6	45
P₃	0.089 8	-0.712 7	-1.031 6	43
P₄	1.703 6	-0.796 1	-0.215 5	10

方法	平均FEVALS	平均GEVALS	平均用时	初始点个数	找到全部局部极值的概率%
Multistart算法	11 138	10 741	0.04	300	76
Minfinder算法	1 598	21 587	0.02	251	84
GLLMA算法	6 371	983	0.02	123	90
本文方法	4 220	0	0.023	110	96