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

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Fig.8

Table 2

Fig.9

Table 3

Table 4

Fig.10

Table 5

References 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

Algorithm for locating all local optimum based on fitness landscape analysis

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 26

Related Articles 1

Recommended Articles

Metrics

Comments