运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 15-27.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.002

• 运筹学 • 上一篇    下一篇

求解全局最优问题的多重点样本水平值估计的相对熵算法

周心怡1, 汪可1, 邬冬华2, 汪晨2,*   

  1. 1. 上海大学钱伟长学院, 上海 200444;
    2. 上海大学理学院, 上海 200444
  • 收稿日期:2018-09-10 出版日期:2019-03-15 发布日期:2019-03-15
  • 通讯作者: 汪晨 E-mail:2452748151@qq.com

Cross entropy algorithm with multiple important sample level estimation for global optimization problems

ZHOU Xinyi1, WANG Ke1, WU Donghua2, WANG Chen2,*   

  1. 1. Qianweichang College, Shanghai University, Shanghai 200444, China;
    2. College of Sciences, Shanghai University, Shanghai 200444, China
  • Received:2018-09-10 Online:2019-03-15 Published:2019-03-15

摘要:

研究有界闭箱约束下的全局最优化问题,利用相对熵及广义方差函数方程的最大根与全局最小值之间的等价关系,设计求解全局最优值的积分型水平值估计算法.对采用重点样本采样技巧产生的函数值按一定规则进行聚类,从而在各聚类中产生的若干新重点样本,结合相对熵算法,构造出多重点样本进行全局搜索的新算法.该算法的优点在于每次迭代选用当前较好的函数值信息,以达到随机搜索到更好的函数值信息.同时多重点样本可有利挖掘出更好的全局信息.一系列的数值实验表明该算法是非常有效的.

关键词: 广义变差函数, 多重点样本, 水平值估计算法, 相对熵算法

Abstract:

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.

Key words: generalized variance function, multiple important samples, level-value estimation, cross-entropy method

中图分类号: