基于改进边际优化的离散变量优化设计算法

doi:10.12305/j.issn.1001-506X.2021.02.16

摘要/Abstract

摘要：

针对传统离散变量优化方法存在的目标函数测算次数多、收敛性不佳等问题,借鉴边际优化理论和模式搜索算法,设计了一种基于改进边际优化的离散变量优化设计算法。借鉴边际效用优化原理,通过引入周围单位步长空间的概念,在初始点选择、边际增量设计、禁忌搜索策略等方面进行了改进,并设计了变异操作以跳出局部最优。实例分析表明,所提算法能够快速准确地收敛到局部最优解,实现以尽可能少的目标函数测算得到问题的满意解或最优解,适合于求解高维离散变量优化问题和仿真优化问题。

关键词: 离散变量, 边际优化, 局部最优, 优化算法

Abstract:

Aiming at the problems of the traditional discrete variable optimization method such as too many times of objective function calculation and poor convergence, a discrete variable optimization design algorithm based on improved marginal optimization learning from marginal optimization theory and pattern search algorithm is designed. Based on the principle of marginal utility optimization, the concept of unit step space is introduced to improve the selection of initial point, marginal increment design, tabu search strategy, and mutation operation is designed to jump out of local optimum. Case studies show that the proposed algorithm can quickly and accurately converge to the local optimal solution, and the satisfactory solution or optimal solution can be obtained with as few objective functions as possible, which is suitable for solving high-dimensional discrete variable optimization problems and simulation optimization problems.

Key words: discrete variable, marginal optimization, local optimum, optimization algorithm

中图分类号:

O224

吴诗辉, 李正欣, 刘晓东, 周宇, 贺波. 基于改进边际优化的离散变量优化设计算法[J]. 系统工程与电子技术, 2021, 43(2): 410-419.

Shihui WU, Zhengxin LI, Xiaodong LIU, Yu ZHOU, Bo HE. Discrete variable optimization design algorithm based on improved marginal optimization[J]. Systems Engineering and Electronics, 2021, 43(2): 410-419.

图/表 11

图1

图2

图3

图4

表1

图5

图6

表2

表3

表4

图7

参考文献 24

1	陈刚, 杨成昱, 梁志君. 对置式凸轮发动机配气机构参数优化[J]. 四川兵工学报, 2010, 31 (3): 89- 92.
	CHEN G , YANG C Y , LIANG Z J . Parameter optimization of valve mechanism of opposite cam engine[J]. Journal of Sichuan Ordnance, 2010, 31 (3): 89- 92.
2	何大阔, 王福利, 毛志忠. 遗传算法在离散变量优化问题中的应用研究[J]. 系统仿真学报, 2006, 18 (5): 1154- 1156. doi: 10.3969/j.issn.1004-731X.2006.05.018
	HE D K , WANG F L , MAO Z Z . Study on application of genetic algorithm in discrete variables optimization[J]. Journal of System Simulation, 2006, 18 (5): 1154- 1156. doi: 10.3969/j.issn.1004-731X.2006.05.018
3	张永存, 张飞, 李晓彬. 基于MSC Nastran的离散变量优化算法的实现[J]. 计算机辅助工程, 2013, 22 (S1): 463- 469.
	ZHANG Y C , ZHANG F , LI X B . Implementation of discrete variable optimization algorithm based on MSC Nastran[J]. Computer Aided Engineering, 2013, 22 (S1): 463- 469.
4	郭惠昕, 张龙庭. 混合离散变量优化设计的复合遗传算法[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.
5	韩继光, 李瑰贤, 吴俊飞. 混合离散变量的遗传算法及其应用[J]. 机械设计与研究, 2001, 17 (3): 16- 18.
	HANG J G , LI G X , WU J F . Genetic algorithm of mixed discrete variables and its application[J]. Machine Design and Research, 2001, 17 (3): 16- 18.
6	KRISHNAMOORTHY R S . Discrete optimization of structures using genetic algorithm[J]. Journal of Structural Engineering, 1999, 12 (2): 175- 184.
7	金树, 任宗栋, 李宏男, 等. 输电塔结构离散变量优化设计方法[J]. 工程力学, 2016, 33 (11): 84- 94.
	JIN S , REN Z D , LI H N , et al. Discrete variable optimal design method of transmission tower structure[J]. Engineering Mechanics, 2016, 33 (11): 84- 94.
8	魏畅, 杜文莉. 改进的多目标混合整数优化算法及其在蒸汽动力系统优化中的应用[J]. 华东理工大学学报(自然科学版), 2016, 42 (6): 827- 834.
	WEI C , DU W L . Improved multi-objective mixed integer optimization algorithm and its application in the optimization of steam power system[J]. Journal of East China University of Science and Technology (Natural Science Edition), 2016, 42 (6): 827- 834.
9	DATTA D , FIGUEIRA J R . A real-integer-discrete-coded particle swarm optimization for design problems[J]. Applied Soft Computing, 2011, 11 (4): 3625- 3633. doi: 10.1016/j.asoc.2011.01.034
10	ROSEN S L , HARMONOSKY C M . An improved simulated annealing simulation optimization method for discrete parameter stochastic systems[J]. Computers & Operations Research, 2005, 32 (2): 343- 358.
11	GANDOMIA A H , YANG X S , ALAVIC A H . Mixed variable structural optimization using firefly algorithm[J]. Computers and Structures, 2011, 89 (23/24): 2325- 2336.
12	BLAND J A . Discrete-variable optimal structural design using Tabu search[J]. Structural Optimization, 1995, 10 (2): 87- 93.
13	SHARIF B , WANG G G , ELMEKKAWY T Y . Mode pursuing sampling method for discrete variable optimization on expensive black-box functions[J]. Journal of Mechanical Design, 2008, 130 (2): 021402.
14	吴诗辉, 张发, 李正欣, 等. 基于神经网络的仿真优化算法设计[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.
15	吴诗辉, 刘晓东, 邵悦, 等. 一种基于神经网络的仿真优化方法[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.
16	郭强, 蒋里强, 高建军, 等. 基于边际效应分析的防空武器系统可靠性优化研究[J]. 运筹与管理, 2013, 22 (4): 106- 110.
	GUO Q , JIANG L Q , GAO J J , et al. Research on reliability optimization of antiaircraft weapon system based on marginal effect analysis[J]. Operations Research and Management Science, 2013, 22 (4): 106- 110.
17	陈满意, 陈定方. 基于Matlab的齿轮减速器的可靠性优化设计[J]. 机械传动, 2002, 26 (3): 34- 36.
	CHEN M Y , CHEN D F . Reliability optimization design of gear reducer based on Matlab[J]. Journal of Mechanical Transmission, 2002, 26 (3): 34- 36.
18	SHERBROOKE C C . Optimal inventory modeling of system: multi-echelon techniques[M]. 2nd ed Boston: Artech House, 2004.
19	MENG X H, XU Z C, WANG S H. Research on turnover parts optimization based on improved spares fill rate[C]//Proc.of the 9th International Conference on Reliability, Maintainability and Safety, 2011: 1201-1207.
20	WU S H , XIE J , LIU X D , et al. A marginal optimization method to improve the inconsistent comparison matrix in the analytic hierarchy process[J]. Journal of Systems Engineering and Electronics, 2017, 28 (6): 1141- 1151.
21	吴诗辉, 杨建军, 郭亚坤. 基于模式搜索的导弹目标分配方法研究[J]. 战术导弹技术, 2009, (3): 29- 32.
	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.
22	徐锦康. 机械优化设计[M]. 北京: 机械工业出版社, 1996.
	XU J K . Mechanical optimization design[M]. Beijing: China Machine Press, 1996.
23	MCCARE B , STACEY K . More test examples for nonlinear programming codes[M]. SCHITTKOWSKI K. Heidelberg: Springer, 1987.
24	NG C K , ZHANG L S , LI D , et al. Discrete filled function method for discrete global optimization[J]. Computational Optimization and Applications, 2005, 31 (1): 87- 115.

迭代次数	x₁	x₂	f(X)
0	3*	6	-54
1	3.25*	6	-54.875
2	3.5*	6	-55.5
3	3.75	6*	-55.875
4	3.75	5.9*	-56.065
5	3.75	5.8*	-56.235
6	3.75	5.7*	-56.385
7	3.75*	5.6	-56.515
8	4	5.6*	-56.64
9	4	5.5*	-56.75
10	4	5.4*	-56.84
11	4	5.3*	-56.91
12	4	5.2*	-56.96
13	4	5.1*	-56.99
14	4	5	-57

变量/ 函数值	文献[4] x_m1	文献[5] x_m2	文献[22] x_m3	文献[2] x_m4	本文方法(最优解和部分局部最优解)
变量/ 函数值	文献[4] x_m1	文献[5] x_m2	文献[22] x_m3	文献[2] x_m4	x_a1	x_a2	x_a3	x_a4	x_a5
x₁	13	14	13	13	13	14	12	11	12
x₂	24	23	19	24	24	23	26	28	22
x₃	0.6	0.6	0.9	0.6	0.6	0.6	0.6	0.6	0.7
x₄	23.75	29.33	23.6	23.5	23.5	24.5	22.5	21.5	22.5
x₅	10	12	10	10	10	10	10	10	10
x₆	13	13	13	13	13	13	13	13	13
-g₁(X)	15.6	16.2	12.9	15.6	15.6	16.2	14.4	13.2	14.6
-g₂(X)	5.666 7	7.333 3	-1.555 6	5.666 7	5.666 7	7.333 3	4	2.333 3	1.142 9
-g₃(X)	13.333 3	11.666 7	20.555 6	13.333 3	13.333 3	11.666 7	15	16.666 7	17.857 1
-g₄(X)	0.25	4.83	0.1	0	0	0	0	0	0
-g₅(X)	10.353 4	5.690 3	143.718 6	10.353 4	10.353 4	5.690 3	43.489 8	67.947 7	32.950 7
-g₆(X)	35.139 1	40.059 1	127.033 7	35.139 1	35.139 1	40.059 1	38.942 2	39.259 8	60.976 5
-g₇(X)	3.875 4	10.424 8	95.449 3	3.875 4	3.875 4	10.424 8	3.598 2	0.374 8	31.473 4
-g₈(X)	0.071 2	0.088	0.070 8	0.070 5	0.070 5	0.073 5	0.067 5	0.064 5	0.067 5
-g₉(X)	4.539 1	18.113 5	11.894 1	5.017 7	5.017 7	1.049 8	10.208 9	14.591 5	9.699 5
-g₁₀(X)	16.719 8	6.646 3	33.199 6	17.082 9	17.082 9	14.072 8	21.021	24.345 7	25.543 9
f(X)	30 675	33 540	40 459	30 622	30 622	31 022	31 239	31 590	31 956

变量/ 函数值	文献[2] x_m1	文献[17] x_m2	本文算法
变量/ 函数值	文献[2] x_m1	文献[17] x_m2	x_a1	x_a2	x_a3	x_a4
x₁	2	2	2	2	2	2
x₂	17	17	17	17	17	17
x₃	0.96	0.96	0.97	1.12	0.95	1.02
x₄	6	6	19	19	19	19
-g₁(X)	0.558 6	0.558 6	0.147 3	0.701 2	0.067	0.340 9
-g₂(X)	3.258 5	3.258 5	3.049 5	3.672 8	2.959 2	3.267 4
-g₃(X)	106.231	106.231	103.165	103.165	103.165	103.165
f(X)	106.231	106.231	103.165	103.165	103.165	103.165

方法	指标		n=25	n=50	n=100
文献[24]	FN	max	271 472	18 634	15 686 480
文献[24]	T/s	max	332.53	11.82	20 252.79
本文算法(单点变异)	FN	min	3 500	13 400	52 800
		max	35 000	301 000	728 600
		mean	14 040	161 720	208 880
	T/s	max	12.47	107.83	266.8

[1]	余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.
[2]	张勇, 李常久, 苏析超, 崔荣伟. 基于HTLBO算法的舰载机机群机库维修任务调度[J]. 系统工程与电子技术, 2022, 44(9): 2858-2868.
[3]	杨建峰, 肖和业, 李亮, 白俊强, 董维浩. 基于模糊聚类和专家评分机制的无人机多层次模块划分方法[J]. 系统工程与电子技术, 2022, 44(8): 2530-2539.
[4]	赵建磊, 李海阳. 稀疏轨道信息下的非合作飞行器机动识别方法[J]. 系统工程与电子技术, 2022, 44(6): 1950-1956.
[5]	张佳唯, 钱凤臣, 杨俊强, 赵骞, 张峥嵘. 弹性光网络中路由与频谱分配算法综述[J]. 系统工程与电子技术, 2022, 44(6): 2001-2010.
[6]	高永琪, 马威强, 张林森, 王鹏, 赵苗. 分布式多AUV协同搜索方法[J]. 系统工程与电子技术, 2022, 44(5): 1670-1676.
[7]	杜思予, 全英汇, 沙明辉, 方文, 邢孟道. 基于进化PSO算法的稀疏捷变频雷达波形优化[J]. 系统工程与电子技术, 2022, 44(3): 834-840.
[8]	陈都, 孟秀云. 基于自适应郊狼算法的无人机离线航迹规划[J]. 系统工程与电子技术, 2022, 44(2): 603-611.
[9]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[10]	董庆, 李本威, 闫思齐, 钱仁军. 基于BSO-ELM的涡轴发动机加速过程性能参数预测[J]. 系统工程与电子技术, 2021, 43(8): 2181-2188.
[11]	杨卫星, 朱岱寅. 稀疏场景下SAR方位向随机丢失数据的迭代成像算法[J]. 系统工程与电子技术, 2021, 43(7): 1748-1755.
[12]	周晶, 赵晓哲, 许震, 林众, 张晓盼. 基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法[J]. 系统工程与电子技术, 2021, 43(5): 1240-1247.
[13]	刘傲, 周正, 李双明. 基于优化序列提取的相控阵雷达识别方法[J]. 系统工程与电子技术, 2021, 43(3): 656-665.
[14]	王坤, 侯树贤, 王力. 基于自适应变异PSO-SVM的APU性能参数预测模型[J]. 系统工程与电子技术, 2021, 43(2): 526-536.
[15]	田春明, 杨安, 叶乐, 李建星, 贺雨晨. 基于贝叶斯算法的天线端到端优化[J]. 系统工程与电子技术, 2021, 43(12): 3413-3419.