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

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

中图分类号:

O221.2

马素霞, 高岳林, 林洪伟, 张博. 一种新的全局优化无参数填充函数方法[J]. 运筹学学报（中英文）, 2025, 29(2): 141-157.

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.

图/表 21

图1

表1

表2

表3

表4

表5

表6

表7

表8

表9

表10

表11

表12

表13

表14

表15

表16

表17

表18

表19

表20

PFFF与PFF4、PFFF5的数值计算结果对比"

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

表20

参考文献 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