一种新的全局优化无参数填充函数方法

doi:10.15960/j.cnki.issn.1007-6093.2025.02.011

Abstract

Abstract:

The filled function method is a kind of deterministic method, which is adopted to find the global optimal solution for the unconstrained optimization problem. The core technique of this method is to construct the filled function, which is such that the iterative process of the algorithm constantly jump out of the current local minimizer. Currently, the filled function generally contains parameters, and the selection of parameters has a great influence on the computation effect of the algorithm. In this paper, a new non parameter-filled function is constructed by using the definition of filled function, and a new global optimization method is developed. Numerical experiments illustrate that this method is feasible and effective, and has better global optimization ability.

Key words: global optimization, unconstrained optimization problem, filled function method, non parameter

CLC Number:

O221.2

Suxia MA, Yuelin GAO, Hongwei LIN, Bo ZHANG. A new non parameter-filled function method for global optimization[J]. Operations Research Transactions, 2025, 29(2): 141-157.

Figures/Tables 21

No.	$ n $	PFFF			PFF4			PFF5
No.	$ n $	iter	$ N_{F+P} $	$ t $/s	iter	$ N_{F+P} $	$ t $/s	iter	$ N_{F+P} $	$ t $/s
1	2	1	49	0.549 5	$ - $	$ - $	$ - $	1	259	0.522 9
2	2	2	71	0.469 8	2	310	0.523 2	1	237	0.535 2
	2	2	59	0.442 2	$ - $	$ - $	$ - $	2	347	0.483 1
	2	1	59	0.382 8	$ - $	$ - $	$ - $	2	457	0.549 4
3	2	2	82	0.005 0	2	331	0.702 3	1	279	0.589 9
4	2	3	2 905	0.913 0	3	2 963	1.015 5	$ - $	$ - $	$ - $
5	2	5	423	0.325 4	4	4 069	0.978 9	3	4 374	1.285 4
6	2	2	172	0.011 2	2	335	0.675 5	1	277	0.614 6
	2	1	164	0.461 3	$ - $	$ - $	$ - $	1	285	0.019 5
	2	1	340	0.388 6	1	269	0.589 0	1	299	0.615 8
7	2	2	403	0.526 4	$ - $	$ - $	$ - $	$ - $	$ - $	$ - $
	3	5	455	0.325 1	5	1 369	0.709 2	5	1 069	0.633 8
	5	2	2 226	0.080 1	2	2 263	0.830 3	2	2 379	0.654 7
	7	2	2 783	0.763 1	2	4 595	0.867 4	2	3 717	0.587 7
	10	6	16 024	1.372 7	10	20 475	1.620 7	7	17 860	1.552 8
	20	8	65 461	3.126 5	16	106 924	4.800 8	9	92 651	4.464 0
	30	11	174 490	7.102 7	13	189 666	7.372 0	11	198 968	7.592 7
	50	18	439 577	15.673 8	15	389 616	14.041 4	$ - $	$ - $	$ - $
	100	22	1 402 326	47.284 4	26	2 003 108	66.874 2	19	239 850	82.928 3
	200	61	18 136 009	813.053 6	$ - $	$ - $	$ - $	$ - $	$ - $	$ - $
	500	72	11 524 001	8.539 3$ \times10^{3} $	$ - $	$ - $	$ - $	$ - $	$ - $	$ - $
	1 000	83	46 048 001	4.168 9$ \times10^{3} $	$ - $	$ - $	$ - $	$ - $	$ - $	$ - $
8	2	5	705	0.659 0	3	585	0.692 9	$ - $	$ - $	$ - $
9	2	1	247	0.488 4	1	247	0.673 3	1	235	0.594 9
10	4	2	1 052	0.673 1	2	1 122	0.525 8	2	1192	0.728 1
	4	2	992	0.488 2	2	1 107	0.758 1	2	1 007	0.578 0
	4	2	1 002	0.559 5	2	1 102	0.676 4	2	1 105	0.651 5
11	2	2	395	0.433 7	6	1 115	0.722 9	5	783	0.642 5
	3	4	1 041	0.555 7	$ - $	$ - $	$ - $	10	1 441	0.639 5
	4	5	1 969	0.883 1	$ - $	$ - $	$ - $	10	6 212	1.196 5
	5	8	3 655	0.848 8	$ - $	$ - $	$ - $	14	6 541	1.222 7
	50	81	3 800 763	0.669 3	$ - $	$ - $	$ - $	106	5 391 680	201.585 7
	100	135	30 483 410	939.807 5	$ - $	$ - $	$ - $	232	52 408 248	1.753 2$ \times10^{3} $
12	8	11	37 432	2.728 8	$ - $	$ - $	$ - $	24	54 654	4.327 5
13	5	4	3 005	0.691 6	$ - $	$ - $	$ - $	8	7 252	1.334 6
	10	17	45 842	4.315 3	$ - $	$ - $	$ - $	18	57 373	6.687 3
14	2	2	532	0.669 3	$ - $	$ - $	$ - $	3	761	0.709 2
	3	2	957	0.737 8	$ - $	$ - $	$ - $	6	2 530	0.850 9
	4	2	5 304	1.010 8	$ - $	$ - $	$ - $	2	4 913	1.016 6
	5	2	7 456	1.224 4	$ - $	$ - $	$ - $	3	8 744	1.312 1

References 27

1	Ge R P . A filled function method for finding a global minimizer of a function of several variables[J]. Mathematical Programming, 1990, 46 (2): 191- 204.
2	Ge R P , Qin Y F . A class of filled functions for finding global minimizers of a function of several variables[J]. Applied Mathematic and Computation, 1987, 54 (2): 241- 252.
3	Levy A V , Montalvo A . The tunneling algorithm for the global minimization of functions[J]. The SIAM Journal on Scientific Computing, 1985, 6 (1): 15- 29. doi: 10.1137/0906002
4	申培萍. 全局优化方法[M]. 北京: 科学出版社, 2006: 19- 32.
5	Sreelaja N K . Ant colony optimization based light weight binary search for efficient signature matching to filter ransomware[J]. Applied Soft Computing, 2021, 111 (10): 107635.
6	Yeh W C , Chuang M C . Using multi-objective genetic algorithm for partner selection in green supply chain problems[J]. Expert Systems with Applications, 2011, 38 (4): 4244- 4253. doi: 10.1016/j.eswa.2010.09.091
7	黄友锐. 智能优化算法及其应用[M]. 北京: 国防工业出版社, 2008: 9- 138.
8	Gao C L , Yang Y J , Han B S . A new class of filled functions with one parameter for global optimization[J]. Computers and Mathematics with Applications, 2011, 62 (6): 2393- 2403. doi: 10.1016/j.camwa.2011.05.006
9	El-Gindy T M , Salim M S , Ahmed A I . A new filled function method applied to unconstrained global optimization[J]. Applied Mathematic and Computation, 2016, 273 (1): 1246- 1256.
10	Yang Y J , Shang Y L . A new filled function method for unconstrained global optimization[J]. Applied Mathematic and Computation, 2006, 173 (1): 501- 512. doi: 10.1016/j.amc.2005.04.046
11	Wu Z Y , Bai F S , Lee H W J , et al. A filled function method for constrained global optimization[J]. Journal of Global Optimization, 2007, 39 (4): 495- 507. doi: 10.1007/s10898-007-9152-2
12	Liu X . A class of generalized filled functions with improved computability[J]. Journal of Computational and Applied Mathematics, 2001, 137 (1): 61- 69. doi: 10.1016/S0377-0427(00)00697-X
13	Wang C , Yang Y , Li J . A new filled function method for unconstrained global optimization[J]. Journal of Computational and Applied Mathematics, 2009, 225 (1): 68- 79. doi: 10.1016/j.cam.2008.07.001
14	Lin H W , Gao Y L , Wang X L , et al. A filled function which has the same local minimizer of the objective function[J]. Optimization Letters, 2019, 13 (4): 761- 776. doi: 10.1007/s11590-018-1275-5
15	Lin H W , Wang Y P , Gao Y L , et al. A filled function method for global optimization with inequality constraints[J]. Computational and Applied Mathematics, 2018, 37 (2): 1524- 1536. doi: 10.1007/s40314-016-0407-8
16	吴佩佩, 高岳林. 一个新的非线性整数规划问题的单参数填充函数算法[J]. 运筹学学报, 2017, 21 (3): 111- 118. doi: 10.15960/j.cnki.issn.1007-6093.2017.03.012
17	He S X , Chen W L , Wang H . A new filled function algorithm for constrained global optimization problems[J]. Applied Mathematic and Computation, 2011, 217 (12): 5853- 5859. doi: 10.1016/j.amc.2010.12.070
18	Liu X . Finding global minima with a computable filled function[J]. Journal of Global Optimization, 2001, 19 (2): 151- 161. doi: 10.1023/A:1008330632677
19	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24 (4): 63- 73. doi: 10.15960/j.cnki.issn.1007-6093.2020.04.005
20	高岳林, 吴佩佩. 非线性整数规划的一个新的无参数填充函数算法[J]. 计算数学学报, 2017, 39 (3): 321- 327.
21	Ahmed A I . A new parameter free filled function for solving unconstrained global optimization problems[J]. International Journal of Computer Mathematics, 2021, 98 (1): 106- 119. doi: 10.1080/00207160.2020.1731484
22	Pandiya R , Widodo W , Salmah , et al. Non parameter-filled function for global optimization[J]. Applied Mathematic and Computation, 2021, 391, 125642. doi: 10.1016/j.amc.2020.125642
23	Liu H Y , Wang Y P , Guan S W , et al. A new filled function method for unconstrained global optimization[J]. Applied Mathematic and Computation, 2017, 94 (12): 2283- 2296.
24	Ma S Z , Yang Y J , Liu H Q . A parameter free filled function for unconstrained global optimization[J]. Applied Mathematic and Computation, 2009, 215 (10): 3610- 3619.
25	Lin H W , Wang Y P , Fan L . A filled function method with one parameter for unconstrained global optimization[J]. Applied Mathematic and Computation, 2011, 218 (7): 3776- 3785. doi: 10.1016/j.amc.2011.09.022
26	Lin H W , Gao Y L , Wang Y P . A continuously differentiable filled function method for global optimization[J]. Numerical Algorithms, 2014, 66 (3): 511- 523. doi: 10.1007/s11075-013-9746-3
27	Gao Y L , Yang Y J , You M . A new filled function method for global optimization[J]. Applied Mathematic and Computation, 2015, 268, 685- 695. doi: 10.1016/j.amc.2015.06.090

符号	解释
No.	测试函数序号
$ n $	决策变量个数
Iter	算法终止时的迭代次数
$ N_{F+P} $	迭代终止时$ F(x) $和$ P(x, x_k^*) $的总函数计算量
$ t $	CPU运行时间(单位: s)
PFF1	文献[13]中的双参数填充函数算法
PFF2	文献[1]中的双参数填充函数算法
PFF3	文献[27]中的单参数填充函数算法
PFF4	文献[24]中的无参数填充函数算法
PFF5	文献[21]中的无参数填充函数算法

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	($ - $2.000 0, 2.000 0)	(0.062 0$ \times10^{-6} $, $ - $0.526 8$ \times10^{-6} $)	3.178 4$ \times10^{-13} $

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	($ - $2.000 0, $ - $1.000 0)	($ - $1.703 6, $ - $0.796 1)	$ - $0.215 5
2	($ - $0.004 0, $ - $0.705 1)	($ - $0.089 8, $ - $0.712 7)	$ - $1.031 6

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	(2.000 0, $ - $1.000 0)	(1.607 1, $ - $0.568 7)	2.104 3
2	($ - $0.575 9, $ - $0.751 3)	($ - $0.089 8, $ - $0.712 7)	$ - $1.031 6

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	($ - $2.000 0, 1.000 0)	($ - $0.089 8, $ - $0.712 7)	$ - $1.031 6

A new non parameter-filled function method for global optimization

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 27

Related Articles 15

Recommended Articles

Metrics

Comments

$ i $	$ a_{i, 1} $	$ a_{i, 2} $	$ a_{i, 3} $	$ a_{i, 4} $	$ c_i $
1	4.0	4.0	4.0	4.0	0.1
2	1.0	1.0	1.0	1.0	0.2
3	8.0	8.0	8.0	8.0	0.3
4	6.0	6.0	6.0	6.0	0.4
5	3.0	7.0	3.0	7.0	0.5
6	2.0	9.0	2.0	9.0	0.6
7	5.0	5.0	3.0	3.0	0.3
8	8.0	1.0	8.0	1.0	0.7
9	6.0	2.0	6.0	2.0	0.5
10	7.0	3.6	7.0	3.6	0.5

No.		$ n $	Iter	$ \alpha_0/\alpha $	$ t $/s	$ N_{F+P} $
1		2	1	0.01/0.01	0.495 4	49
		2	1	0.01/0.01	0.603 5	49
2		2	2	0.3/0.3	0.469 8	71
		2	2	0.3/0.3	0.442 2	59
		2	1	0.3/0.3	0.382 8	59
3		2	2	0.4/0.4	0.005 0	82
4		2	1	0.2/0.3	0.913 0	2 905
5		2	5	0.1/0.25	6.514 0	423
6	($ c=0.5 $)	2	2	0.8/0.8	0.011 2	172
	($ c=0.05 $)	2	1	0.8/0.8	0.461 3	164
	($ c=0.2 $)	2	1	0.1/0.1	0.388 6	340
7		2	2	0.4/0.4	0.526 4	403
		3	5	1.0/1.0	0.325 1	455
		5	2	1.0/1.0	0.080 1	2 226
		7	2	1.0/1.0	0.763 1	2 783
		10	6	0.1/0.1	1.372 7	16 024
		20	8	0.1/0.1	3.126 5	58 693
		30	11	0.1/0.1	7.102 7	174 490
		50	18	1.0/1.0	15.673 8	439 577
		100	22	0.1/0.1	47.284 4	1 402 326
		200	61	0.4/0.4	813.053 6	18 136 009
		500	72	0.4/0.4	8.539 3$ \times10^{3} $	11 524 001
		1 000	83	0.4/0.4	4.168 9$ \times10^{3} $	46 048 001
8		2	5	0.1/0.1	0.659 0	705
9		2	1	0.3/0.3	0.488 4	247
10	($ m=5 $)	4	2	0.1/0.1	0.673 1	1 052
	($ m=7 $)	4	2	0.1/0.1	0.488 2	992
	($ m=10 $)	4	2	0.1/0.1	0.559 5	1 002
11		2	2	1.0/1.0	0.433 7	395
		3	4	1.0/1.0	0.555 7	1 041
		4	5	1.0/1.0	0.883 1	1 969
		5	8	1.0/1.0	0.848 8	3 655
		6	8	1.0/1.0	1.010 0	5 436
		20	48	0.1/1.0	3.507 1	126 670
		30	78	0.1/1.0	6.344 5	213 540
		50	81	1.0/1.0	132.678 7	3 800 763
		100	135	1.0/1.0	939.807 5	30 483 410
12		8	11	0.15/0.2	2.728 8	37 432
13		5	4	0.3/0.3	0.691 6	3 005
		10	17	0.1/0.1	4.315 3	45 842
14		2	2	0.1/0.1	0.669 3	532
		3	2	0.2/0.2	0.737 8	957
		4	2	0.15/0.2	1.010 8	5 304
		5	2	0.15/0.2	1.224 4	7 456

[1]	YUAN Liuyang, TANG Mengyao, CHI Xiaoni. A new class of parameter-free filled tunnel function methods [J]. Operations Research Transactions, 2025, 29(2): 214-220.
[2]	Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints [J]. Operations Research Transactions, 2024, 28(1): 89-100.
[3]	Xiaoli HUANG, Yuelin GAO, Bo ZHANG, Xia LIU. An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems [J]. Operations Research Transactions, 2022, 26(2): 83-100.
[4]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[5]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[6]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[7]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[8]	CHEN Yong, WANG Wei, XU Yifan. An stochastic algorithm for global optimization with linear constraints based on intermittent diffusion [J]. Operations Research Transactions, 2020, 24(1): 88-100.
[9]	WANG Weixiang, SHANG Youlin, WANG Duo. Filled function method for solving non-smooth box constrained global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 28-34.
[10]	TIAN Mingyu, YANG Yongjian. A global optimization algorithm for polynomial programming [J]. Operations Research Transactions, 2018, 22(4): 79-88.
[11]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[12]	ZHENG Yue, ZHUANG Daoyuan, WAN Zhongping. A global optimization method for solving the weak linear bilevel programming problems [J]. Operations Research Transactions, 2017, 21(3): 86-94.
[13]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[14]	HU Quan, WANG Wei. A filled function method based on filter for global optimization with box constraints [J]. Operations Research Transactions, 2016, 20(3): 57-67.
[15]	LV Yibing, WAN Zhongping. A global optimization method for solving the linear semivectorial bilevel programming problem [J]. Operations Research Transactions, 2015, 19(2): 29-36.

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	($ - $1.000 0, $ - $2.000 0)	($ - $1.000 0, 0.000 0)	1.000 0
2	(0.190 7, 0.000 0)	(0.761 2$ \times10^{-7} $, 0.000 0)	2.317 5$ \times10^{-14} $

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	(1.000 0, 1.000 0)	(1.040 8, 1.040 8)	0.179 8
2	(0.661 2, 1.040 8)	(0.693 8, 1.040 8)	$ - $0.425 7
3	(0.693 8, 0.661 2)	(0.693 8, 0.693 8)	$ - $1.031 2
4	($ - $0.014 2, 0.693 8)	($ - $0.000 0, 0.693 8)	$ - $1.515 6
5	(0.000 0, $ - $0.014 2)	(0.000 3$ \times10^{-15} $, 0.712 4$ \times10^{-15} $)	$ - $2.000 0

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	(0.000 0, 0.000 0)	(0.042 0, $ - $0.094 8)	0.517 5
2	(1.922 3, $ - $0.303 1)	(1.897 4, $ - $0.300 5)	5.956 0$ \times10^{-14} $

$ k $	$ x_0^k $	$ x_k^* $	$ F(x_k^*) $
1	(10.000 0, $ - $10.000 0)	(0.148 7, 0.402 1)	7.642 5$ \times10^{-14} $