﻿ 动态调整策略改进的和声搜索算法
 文章快速检索 高级检索

Dynamic adjustment strategy for improving the harmony search algorithm
TUO Shouheng , YONG Longquan, DENG Fang'an
School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong 723001, China
Abstract: A dynamic adjustment strategy is used to improve the harmony search algorithm for solving high-dimensional multimodal global optimization problems. It chooses the worst harmony vector from the harmony memory (HM) as an optimization objective vector. With the process of iteration, the adjustment probability of decision variables is reduced step by step. It can achieve the balance effectively between the global exploration powers and local exploitation competence, and can increase the success rate of evolution. Finally, the experimental results of 16 high-dimension benchmark functions demonstrated that the proposed method can enhance the performance and robustness of the harmony search algorithm obviously in solving large scale multimodal optimization problems.

1 标准和声搜索算法

1.1 标准和声搜索算法

1)设置参数值(D,HMS,Tmax,HMCR,PAR,BW)。各参数含义如下：

D为问题的维数，HMS为和声记忆库大小，Tmax 为算法迭代次数；HMCR为和声记忆库选择概率，PAR为局部微调概率，BW为局部微调步长值。

2)随机初始化和声记忆库HM

3)利用3种和声调节规则创作新和声

①和声记忆库选择。新和声向量xnew的决策变量xinew(i=1,2,…,D) 以概率HMCR从和声记忆库的第i维[xi1    xi2    …    xiHMS]T中随机选取。

②局部微调。局部微调是将①中产生的xinew(i=1,2,…,D)以概率PAR进行再次微调。微调方法如下：

③搜索空间内随机产生。新和声向量xnew的决策变量xinew(i=1,2,…,D) 以概率1-HMCR在搜索空间内随机产生。产生方法如下：

4)更新操作

2 动态降维和声调整策略 2.1 2种和声调整策略分析与比较

1)如果完全利用规则①产生一个新和声xnew=[x1*    x2*    …    xD*]。那么，xinew(i=1,2,…,D)取到xi*(i=1,2,…,D)的概率为，则xnew=[x1*    x2*    …    xD*]的概率为

2)选取HM中一个和声作为调整目标，然后，随机的将其中某一决策变量利用规则①重新生成。假设选取x1作为优化调整目标xnew,则xnew=[y1    x2*    x3*    …    xD*]，随机选取一个决策变量进行调整，选取到y1的概率为1/D,并且利用规则①能够将其调整为x1* 的概率为(HMS－1)/HMS,因此，优化调整后，xnew=[x1*    x2*    …    xD*]的概率为(1/D)·((HMS－1)/HMS)。

 图 1 2种方法在维数不同时的更新成功率曲线图 Fig. 1 The update-success rate curve of two methods on different dimensioalities

2.2 基于动态降维调整的和声搜索算法

 图 2 基于动态降维调整的和声搜索算法流程图 Fig. 2 The flow chart of HS algorithm based on dynamic dimensionality reduction strategy
 图 3 调整概率TP变化曲线 Fig. 3 Adjustment curve of TP

3 仿真实验

 函数名称 Benchmark函数表达式 搜索范围 参数值 F1 Ackley Function [－15,30]D x*=(0,0,…,0)F1(x*)=0 F2 Griewank Function [－600,600]D x*=(0,0,…,0)F2(x*)=0 F3Levy Function [－10,10]D x*=(1,1,…,1)F3(x*)=0 F4Michalewics Function [－10,π]D n=5F4(x*)=－4.687 658 F5Rastrigin Function [－5.12,5.12]D x*=(0,0,…,0)F5(x*)=0 F6Schwefel 2.26 Function [－512,512]D x*=(420.968 7,420.968 7,…,420.968 7)F6(x*)=0

3.1 实验环境和算法参数设置

 算法 HMS HMCR PAR BW TP HS 10 0.99 0.33 (xU-xL)/2 000 / HS2 10 0.99 0.33 (xU-xL)/2 000 TPmax=0.6，TPmin=5/D IHS 10 0.99 PARmax=0.99,PARmin=0.1 BWmax=(xU-xL)/20 / BWmin=(xU-xL)/(1e+8) IHS2 10 0.99 PARmax=0.99,PARmin=0.1 BWmax=(xU-xL)/20 TPmax=0.6，TPmin=5/D BWmin=(xU-xL)/(1e+8) GHS 10 0.90 PARmax=0.99,PARmin=0.01 / / GHS2 10 0.90 PARmax=0.99,PARmin=0.01 / TPmax=0.6，TPmin=5/D EHS 50 0.99 0.33 / / EHS2 50 0.99 0.33 / TPmax=0.6，TPmin=5/D ITHS 10 0.99 PARmax=1,PARmin=0 / / ITHS2 10 0.99 PARmax=1,PARmin=0 / TPmin=0.6，TPmin=5/D
3.2 实验结果与分析

 算法 F 1 F 2 F 3 Best Mean Std Runtime Best Mean Std Runtime Best Mean Std Runtime HS 2.34×10 0 2.50×10 0 6.67×10 -2 2.52×10 2 6.32×10 -1 6.75×10 -1 2.39×10 -2 3.06×10 2 8.04×10 -2 9.70×10 -2 1.80×10 -2 1.61×10 3 HS 2 1.39×10 -1 1.61×10 -1 1.14×10 -2 1.89×10 2 4.20×10 -1 5.31×10 -1 8.25×10 -2 2.48×10 2 1.09×10 -4 1.24×10 -4 7.07E-06 1.53×10 3 GHS 1.57×10 1 1.64×10 1 2.75×10 -1 2.67×10 2 1.88×10 3 2.11×10 3 1.49×10 2 3.45×10 2 7.11×10 2 7.96×10 2 4.40×10 1 9.03×10 2 GHS 2 1.24×10 -2 4.29×10 -2 2.86×10 -2 2.42×10 2 9.85×10 -3 2.83×10 -1 2.72×10 -1 3.06×10 2 1.30×10 -3 8.25×10 -3 9.63×10 -3 8.86×10 2 IHS 6.57×10 -1 1.10×10 0 1.74×10 -1 3.79×10 2 5.92×10 -2 7.60×10 -2 8.85×10 -3 4.64×10 2 5.27×10 -2 1.05×10 -1 4.09×10 -2 1.24×10 3 IHS 2 8.71×10 -7 8.81×10 -7 6.81×10 -9 3.16×10 2 2.69×10 -11 3.70×10 -4 1.65×10 -3 4.00×10 2 1.17×10 -12 1.19×10 -12 2.75×10 -14 9.71×10 2 ITHS 7.90×10 -3 2.95×10 -2 1.18×10 -2 3.17×10 2 6.41×10 -3 1.92×10 -1 9.97×10 -2 3.87×10 2 1.35×10 -3 4.75×10 -3 2.16×10 -3 1.70×10 3 ITHS 2 1.50×10 -13 3.49×10 -13 1.75×10 -13 2.16×10 2 6.66×10 -16 7.72×10 -16 5.67E-17 2.62×10 2 1.50×10 -32 1.50×10 -32 0.00×10 0 1.62×10 3 EHS 4.55×10 0 4.70×10 0 8.66×10 -2 5.02×10 2 2.12×10 1 2.47×10 1 1.58×10 0 5.75×10 2 1.11×10 2 1.26×10 2 7.58×10 0 2.04×10 3 EHS 2 2.71×10 -13 2.21×10 -5 6.85×10 -5 4.32×10 2 7.77×10 -16 1.26×10 -5 5.38×10 -5 5.17×10 2 3.54E-15 1.25×10 -7 3.96×10 -7 1.24×10 3 算法 F 4 F 5 F 6 Best Mean Std Runtime Best Mean Std Runtime Best Mean Std Runtime HS -2.08×10 2 -2.01×10 2 4.92×10 0 6.48×10 2 1.10×10 2 1.26×10 2 1.07×10 1 3.21×10 2 4.57×10 1 4.95×10 1 2.42×10 0 2.98×10 2 HS 2 -4.28×10 2 -4.26×10 2 2.03×10 0 5.25×10 2 1.13×10 -2 1.28×10 -2 8.39×10 -4 2.03×10 2 6.99×10 -2 8.04×10 -2 6.73×10 -3 2.15×10 2 GHS -2.26×10 2 -2.22×10 2 2.90×10 0 5.22×10 2 1.61×10 3 1.90×10 3 1.19×10 2 3.50×10 2 3.35×10 4 3.81×10 4 2.16×10 3 3.47×10 2 GHS 2 -2.65×10 2 -2.62×10 2 1.55×10 0 4.98×10 2 8.81×10 -4 1.10×10 -1 1.69×10 -1 3.14×10 2 1.54×10 -2 1.26×10 0 1.51×10 0 3.23×10 2 IHS -4.55×10 2 -4.53×10 2 2.43×10 0 6.36×10 2 1.02×10 2 1.17×10 2 5.45×10 0 4.99×10 2 6.66×10 0 4.63×10 1 3.27×10 1 4.56×10 2 IHS 2 -4.98×10 2 -4.97×10 2 1.33×10 -1 5.83×10 2 1.71×10 -2 1.20×10 -1 1.05×10 -1 4.16×10 2 1.37×10 -9 1.47×10 -9 6.97×10 -11 3.83×10 2 ITHS -4.51×10 2 -4.42×10 2 3.69×10 0 5.96×10 2 4.35×10 -3 5.94×10 -2 5.25×10 -2 4.38×10 2 6.79×10 2 1.39×10 3 5.00×10 2 5.66×10 2 ITHS 2 -4.98×10 2 -4.98×10 2 3.11×10 -1 4.89×10 2 1.18×10 -11 4.27×10 -11 3.71×10 -11 2.97×10 2 1.39×10 -9 2.85×10 -10 3.98×10 2 EHS -1.63×10 2 -1.58×10 2 1.99×10 0 8.64×10 2 4.43×10 3 4.52×10 3 4.70×10 1 6.68×10 2 1.27×10 5 1.32×10 5 1.78×10 3 6.48×10 2 EHS 2 -4.43×10 2 -4.41×10 2 1.38×10 0 8.10×10 2 3.84×10 2 4.52×10 2 2.89×10 1 5.90×10 2 2.36×10 4 2.61×10 4 1.33×10 3 5.38×10 2

3.3 算法更新成功率分析

 图 4 函数Rastrigin在 D =1 000时，改进前与改进后的算法成功率比较 Fig. 4 Successrate comparison between ITHS and improved ITHS on D =1 000

3.4 算法种群多样性分析

 图 5 函数Schwefel 2.26的多样性曲线( D =1 000) Fig. 5 diversity curve of function Schwefel2.26 ( D =1 000)

4 结束语

DOI: 10.3969/j.issn.1673-4785.201402019

0

#### 文章信息

TUO Shouheng, YONG Longquan, DENG Fang'an

Dynamic adjustment strategy for improving the harmony search algorithm

CAAI Transactions on Intelligent Systems, 2015, 10(02): 307-315.
DOI: 10.3969/j.issn.1673-4785.201402019