运筹学学报 >
2019 , Vol. 23 >Issue 1: 15 - 27
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.002
求解全局最优问题的多重点样本水平值估计的相对熵算法
Cross entropy algorithm with multiple important sample level estimation for global optimization problems
Received date: 2018-09-10
Online published: 2019-03-15
周心怡, 汪可, 邬冬华, 汪晨 . 求解全局最优问题的多重点样本水平值估计的相对熵算法[J]. 运筹学学报, 2019 , 23(1) : 15 -27 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.002
This paper studies a kind of bounded closed box-constrained global optimization problem. In this paper, we utilize the equivalence relation between the maximum root of the generalized variance function equation and the global minimum value, and the cross-entropy to design the integral level value estimation algorithm for the global optimization. To improve the algorithm, we divide the function values generated by the important sampling techniques into clusters in each iteration according to certain rules. Based on the cross-entropy method to update important samples in each cluster, a new algorithm for global searching with multiple important samples is proposed. One of the advantages of the algorithm is that the preferable function values are selected to achieve a random search for better function value information in each iteration. Meanwhile, multiple important samples make for excavating more and better global information. A series of numerical experiment results show that the algorithm is effective.
[1] Bartz-Beielstein T, Zaefferer M. Model-based methods for continuous and discrete global optimization[J]. Applied Soft Computing, 2017, 55:154-167.
[2] 吴佩佩, 高岳林. 一个新的非线性整数规划问题的单参数填充函数算法[J]. 运筹学学报, 2017, 21(3):111-118.
[3] Li J R, Shang Y L, Han P. New tunnel-filled function method for discrete global optimization[J]. Journal of the Operations Research Society of China, 2017, 5(2):291-300.
[4] 王玫婷, 张建坤, 黄有亮. 基于改进遗传算法的工程项目多目标优化研究[J]. 建筑经济, 2017, 38(11):26-31.
[5] 何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 2:219-225.
[6] Zheng Q. Robust analysis and global optimization[J]. Annals of Operations Research, 1990, 24:273-286.
[7] 黄文杰. 全局最优化中的积分-水平集方法及其最优性条件[D]. 上海大学, 2007.
[8] Phu H X, Hoffmann A. Essential supremum and supremum of summable functions[J]. Numerical Functional Analysis and Optimization, 1996, 17(1/2):167-180.
[9] Wu D H, Tian W W, Zhang L S, et al. An algorithm of modified integral-level set method for solving global optimization[J]. Acta Mathematicae Applicatae Sinica, 2001, 24:100-110.
[10] Peng Z, Wu D H, Tian W W. A level-value estimation method for solving constrained global optimization[J]. Mathematica Numerica Sinica, 2007, 29(3):281-293.
[11] Peng Z, Wu D H. A modified integral global optimization method and its asymptotic convergence[J]. Acta Mathematicae Applicatae Sinica, 2009, 25:283-290.
[12] Yu H B, Zeng W J, Wu D H. A stochastic level-value estimation method for global optimization[J]. Journal of the Operations Research Society of China, 2017, 1:1-16.
[13] 许梦杰, 张连生. 用均值-水平集求多个总极值点的方法[J]. 运筹学杂志. 1996, 15(2):26-29.
[14] Cui H Q, Wang C C, Zheng Q. Optimality conditions and algorithms for integral minimization[J]. Computers and Mathematics with Applications, 2006, 52:55-64.
[15] Rubinstein R Y. The cross-entropy method for combinatorial and continuous optimization[J]. Methodology And Computing in Applied Probability, 1999, 2:127-190.
[16] De Boer, Kroese P T, Rubinstein D P. A tutorial on the cross-entropy method[J]. Annals of Operations Research, 2005, 134:19-67.
[17] 钱振琦, 邬冬华. 一种基于相对熵(CE)方法的新的随机水平值下降算法[J]. 运筹与管理, 2013,22(01):83-87.
/
| 〈 |
|
〉 |
