﻿ 随机优化的改进交叉熵方法<sup>*</sup>
 文章快速检索 高级检索

Stochastic optimization method based on improved cross entropy
REN Chao, ZHANG Hang, LI Hongshuang
College of Aerospace Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
Received: 2017-01-12; Accepted: 2017-05-05; Published online: 2017-06-19 15:48
Foundation item: Foundation of Graduate Innovation Center in NUAA (kfjj20160113); National Natural Science Foundation of China (U1533109)
Corresponding author. LI Hongshuang, E-mail: hongshuangli@nuaa.edu.cn
Abstract: Cross entropy method is an efficient and adaptive stochastic optimization method and has immense potential in complex optimization problems with high dimension and nonlinear constraints. However, the traditional cross entropy method is lack of accuracy. In this study, both the concepts of current elite samples and global elite samples are introduced to extract more useful information from the whole iterative history. Then, a new parameter updating strategy is established based on these two concepts. New adaptive smoothing strategy and mutation operation are also applied to improve its computing performance. The proposed algorithm is illustrated by three numerical examples. The computational results indicate that the improved cross entropy method has higher calculation accuracy and better global search capability.
Key words: stochastic optimization     cross entropy     elite samples     parameter updating strategy     adaptive smoothing strategy     mutation operation

1 传统交叉熵方法

 (1)

 (2)

 (3)

1) 设第k次迭代中，分布参数为vk-1，从fX(x; vk-1)中生成N个随机样本{x1, x2, …, xN}，计算目标函数的值{S(xi)}={S(x1), S(x2), …, S(xN)}，并将{S(xi)}按照从大到小的次序排列，即S(x1)>S(x2)>…>S(xN)。

2) 计算目标函数的ρ分位数，使得

 (4)

3) 第k+1次迭代中的分布参数vk，可以通过式(5)的最大化问题求得

 (5)

 (6)

 (7)

2 改进的交叉熵方法

1) 改进的更新策略

 (8)

“当前精英样本”为第k次迭代中使得目标函数值最小的前ρN个样本；将第k次的“精英样本”与使得目标函数值最小的历史最优值对比，若“当前精英样本”更好，则将其作为第k次迭代的“全局精英样本”。“全局精英样本”的初值为第一次迭代的“当前精英样本”。

2) 自适应平滑参数

 (9)

3) 变异操作

“变异”是进化计算的基本思想之一，广泛应用于遗传算法、蚁群优化算法和粒子群优化算法等。变异操作的目的在于增加样本的随机性，以降低优化算法陷入局部最优的概率。通常变异操作的方法来对每次迭代过程中更新的参数施加扰动，例如在原有方差的基础上增加一个合适的数。该操作可能使得交叉熵方法的收敛出现明显的波动，但只要扰动量设置合理，就可以在保证计算效率的同时降低算法陷入局部最优的可能性。关于扰动，本文选用了如式(10)所示的扰动函数[14]

 (10)

 (11)

4) 约束处理方法

 (12)

 (13)
 (14)

 (15)
 (16)

3 算例

1) 算例1

 (17)

 图 1 算例1目标函数值和最优解迭代曲线(传统交叉熵方法) Fig. 1 Iterative curves of objective function value and optimal solution for Example 1(traditional CE method)

 图 2 算例1统计结果(传统交叉熵方法) Fig. 2 Statistical results of Example 1 (traditional CE method)

100次的重复试验中，最优值的最小值为min S(x*)=-6036.7026，最大值为max S(x*)=-4646.1624，中位数为median S(x*) =-5331.3439，方差为σ2=1.1241×105。从这一结果可以看出，尽管单次试验中交叉熵优化方法的收敛速度很快，但是其优化结果明显陷入了局部最优，且计算结果不够稳定，因此必须对传统交叉熵方法进行有效的改进。

 图 3 算例1目标函数值和最优解迭代曲线(变异操作) Fig. 3 Iterative curves of objective function value and optimum solution for Example 1 (with mutation operation)

 图 4 算例1统计结果(变异操作) Fig. 4 Statistical results of Example 1 (with mutation operation)

100次的重复试验中，最优值的最小值为min S(x*)=-6860.4566，最大值为max S(x*)=-6686.3876，中位数为median S(x*)=-6775.7076，方差为σ2=1.8001×103。从这一结果可以看出，增加了变异操作之后，计算结果跳出了局部最优，与理论值已经十分接近；但是从100次的统计结果看，增加了变异操作后，交叉熵方法精度依然不是很高，交叉熵方法的稳健性也有待提高，因此有必要进行第2步改进。

 图 5 算例1目标函数值和最优解迭代曲线(改进交叉熵方法) Fig. 5 Iterative curves of objective function value and optimal solution for Example 1(ICE method)

 图 6 算例1统计结果(改进交叉熵方法) Fig. 6 Statistical results of Example 1 (ICE method)

 μ0 SCE(x*) SICE(x*) [56.5, 50]T -5 582.658 4 -6968.5867 [100, 100]T 1.9466×1014 -6968.5868 [0, 0]T -6289.1210 -6968.5866 [150, 150]T 1.1289×1016 -6968.5867 [-150, 150]T 1.1618×1014 -6968.5868

2) 算例2

 图 7 算例2目标函数值和最优解迭代曲线(传统交叉熵方法) Fig. 7 Iterative curves of objective function value and optimal solution for Example 2(traditional CE method)

 图 8 算例2目标函数值和最优解迭代曲线(改进交叉熵方法) Fig. 8 Iterative curves of objective function value and optimal solution for Example 2 (ICE method)

 迭代次数 SCE(x*) SICE(x*) 1 3.046 0×1017 1.870 5×1017 2 1.885 2×1016 2.409 6×1016 3 4.116 8×1015 5.599 3×1015 4 8.374 1×1014 3.043 2×1015 5 1.273 0×1014 9.092 1×1014 6 -1.002 9 3.657 2×1014 9 -1.141 5 1.002 9×1013 10 -1.312 0 -0.893 3 50 -1.387 7 -1.508 1 100 -1.387 7 -1.854 4 150 -1.387 7 -1.905 2 200 -1.387 7 -1.905 2

 图 9 算例2统计结果 Fig. 9 Statistical results of Example 2

100次的重复试验中，传统交叉熵方法目标函数最小值为min SCE(x*)=-1.6175，最大值为max SCE(x*)=-1.080 6，中位数为median SCE (x*)=-1.3255，方差为σCE2=0.0234。改进交叉熵方法目标函数最小值为min SICE(x*)= -1.90520，最大值为max SICE(x*)=-1.90497，中位数为median SICE(x*)=-1.90516，方差为σICE2= 1.8415×10-9。对比改进前后的统计结果，可以明显看出改进交叉熵方法有更大的概率求得接近理论值的解。不仅如此，改进交叉熵方法比改进前的结果拥有更好的鲁棒性，因此可以认为在处理含有多个不等式约束的优化问题时，改进的交叉熵方法在计算的精确性，鲁棒性方面都具有明显的优势。

3) 算例3

 (18)

 图 10 算例3统计结果 Fig. 10 Statistical results of Example 3

4 结论

1) 提出一种增加“全局精英样本”的方法，适当降低传统交叉熵方法的计算速度，保留迭代历史中的有用信息并应用于参数的更新中，可提出计算的精确度。

2) 引入变异操作，使得改进交叉熵方法在其迭代初期尽可能在更大的范围类搜索可行解，在迭代后期逐渐趋于最优解。

3) 改进交叉熵方法，保留了传统交叉熵方法一定的高效性，提高了精确性，降低了陷入局部最优的可能性。

4) 通过多次的重复试验，证明改进交叉熵方法鲁棒性更高，尤其是对重要抽样密度函数均值的初值点不敏感，因此可以在不同的初值条件、不同的随机种子的前提下都尽可能趋于一个最优解。

 [1] HAFTKA R T, GVRDAL Z. Elements of structural optimization[M]. Dordrecht: Kluwer Academic Publishers, 1990. [2] RUBINSTEIN R Y. Optimization of computer simulation models with rare events[J]. European Journal of Operational Research, 1997, 99 (1): 89–112. DOI:10.1016/S0377-2217(96)00385-2 [3] RUBINSTEIN R Y. The cross-entropy method for combinatorial and continuous optimization[J]. Methodology & Computing in Applied Probability, 1999, 1 (2): 127–190. [4] HELVIK B E, WITTNER O. Using the cross-entropy method to guide/govern mobile agent's path finding in networks[M]. Berlin: Springer, 2001. [5] ALON G, KROESE D P, RAVIV T, et al. Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment[J]. Annals of Operations Research, 2005, 134 (1): 137–151. DOI:10.1007/s10479-005-5728-8 [6] KUO C, YEARGAIN J R, DOWNEY W J, et al. Solving the vehicle routing problem with stochastic demands using the cross-entropy method[J]. Annals of Operations Research, 2005, 134 (1): 153–181. DOI:10.1007/s10479-005-5729-7 [7] KROESE D P, POROTSKY S, RUBINSTEIN R Y. The cross-entropy method for continuous multi-extremal optimization[J]. Methodology & Computing in Applied Probability, 2006, 8 (3): 383–407. [8] HO S L, YANG S. The cross-entropy method and its application to inverse problems[J]. IEEE Transactions on Magnetics, 2010, 46 (8): 3401–3404. DOI:10.1109/TMAG.2010.2044380 [9] 丁卫平, 王建东, 陈森博, 等. 基于改进混合蛙跳算法的粗糙属性交叉熵优化约简[J]. 南京大学学报(自然科学), 2014, 50 (2): 159–166. DING W P, WANG J D, CHEN S B, et al. Rough attribute reduction with cross-entropy based on improved shuffled frog-leaping algorithm[J]. Journal of Nanjing University(Natural Sciences), 2014, 50 (2): 159–166. (in Chinese) [10] 李国成, 肖庆宪. 求解高维函数优化问题的交叉熵蝙蝠算法[J]. 计算机工程, 2014, 40 (10): 168–174. LI G C, XIAO Q X. Cross-entropy bat algorithm for solving high-dimensional function optimization problem[J]. Computer Engineering, 2014, 40 (10): 168–174. DOI:10.3969/j.issn.1000-3428.2014.10.032 (in Chinese) [11] GHIDEY H.Reliability-based design optimization with cross-entropy method[D].Trondheim:Norwegian University of Science and Technology, 2015. [12] 李洪双, 马远卓. 结构可靠性分析与随机优化设计的统一方法[M]. 北京: 国防工业出版社, 2015: 146-147. LI H S, MA Y Z. Unified methods for structural reliability analysis and stochastic optimization design[M]. Beijing: National Defense Industry Press, 2015: 146-147. (in Chinese) [13] HUI K P, BEAN N, KRAETZL M, et al. The tree cut and merge algorithm for estimation of network reliability[J]. Probability in the Engineering & Informational Sciences, 2002, 17 (1): 23–45. [14] 吴烈. 电磁场逆问题鲁棒优化设计理论和算法研究[D]. 杭州: 浙江大学, 2012. WU L.Numerical methodologies for robust optimizations of inverse problems[D].Hangzhou:Zhejiang University, 2012(in Chinese). [15] LIANG J J, RUNARSSON T P, MEZURA-MONTES E, et al.Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization[R].Singapore:Nanyang Technological University, 2006. [16] 彭宏, 杨立洪, 郑咸义, 等. 计算工程优化问题的进化策略[J]. 华南理工大学学报(自然科学版), 1997, 25 (12): 17–21. PENG H, YANG L H, ZHENG X Y, et al. A new evolutionary strategy for solving engineering optimization problems[J]. Journal of South China University of Technology(Natural Science Edition), 1997, 25 (12): 17–21. DOI:10.3321/j.issn:1000-565X.1997.12.004 (in Chinese)

#### 文章信息

REN Chao, ZHANG Hang, LI Hongshuang

Stochastic optimization method based on improved cross entropy

Journal of Beijing University of Aeronautics and Astronsutics, 2018, 44(1): 205-214
http://dx.doi.org/10.13700/j.bh.1001-5965.2017.0017