DO I :10.16355/j .cnki .issn1007 -9432tyut .2011.02.019 第 42 卷　第 2 期 2011 年 3 月　　 　 太 原 理 工 大 学 学 报 JO U RN A L O F T AI YU A N U N IV ERSI T Y O F T ECH N O LOG Y 　 V ol.42 N o.2 　 M ar.2011 ＊ 　　文章编号:1007-9432(2011)02-0141-04 混沌的自适应和声搜索算法 陈莹珍 , 高岳林 (北方民族大学 信息与系统科 学研究所, 宁夏 银川 750021) 摘　要 :和声搜索算法是一种启发式优化算法 , 针对现有改进的和声搜索算法(IHS)的不足, 提出了一种混沌自适应和声搜索算法(CA HS)。 在该算法中, 首先采用混沌策略初始化种群, 然后 采用自适应的和声保留概率、音调调节概率和音调调节步长产生新解 , 每次迭代产生多个新解 , 充 分利用和声记忆库的信息 。 如果算法停滞, 则采用混沌变异机制。 本文用 5 个标准的测试函数对 该算法进行测试 , 结果表明该算法(CA HS)比 IHS 和 A H SPSO 算法有较强的寻优能力和跳出局 部最优解的能力 。 关键词 :和声搜索算法;自适应搜索 ;混沌 中图分类号 :T P18 　　　文献标识码:A 1 　研究现状 [ 2] 2001 年 G eem Z W 等人提出了一种新 的启发 式算法———和 声搜索[ 1] (Harm ony Search , H S)算 法.类似于粒子群算法的思想来源于鸟群捕食 , 和声 搜索(H S)的基本思想来源于音乐创作。 在音乐创 作中 , 乐师们反复调整乐队中各乐器的音调, 最终得 到一个优美的和声。 研究者已经提出了各种和声搜 索的改进方法, 例如, 2007 年 M ahdavi M 等提出了 算法。 在基本 的和声搜索算法中, 音 调调节 IHS 概率(PA R , 在表达式中记为 R PA )和调节步长(bw , 公式中记作 w b)都是采用一个固定的值, 但是在实 际中 , 在优化的前期 , 希望有较小的 P A R 和较大的 bw ;随着迭代次数的增加 , 则希望有较大的 PA R 和 较小的 bw , 因此 , M ahdavi M 等提出 了基 于动 态 PA R 和 bw 的 IHS 算法, 文中采用的动态的 R P A 和 w b 的表达式如下: R PA(ng)= R PA , m in + (R P A , max -R P A , m in)×ng/ N I , w b(n g)= w b , max exp L nw b, m in/(w b, m ax ×N I))×n g . (1) 式中 :R P A (ng)为 每一代的 音调调节 概率;R PA , max , R PA , min分别是音符调节概率的最大值和最小值;N I 为最大迭代次数 ;ng 为当前迭代次数;wb(n g)为每 一代的音调调节步长 , w b , m ax , w b , min 为音调调节步长 的最大值和最小值 。 2010 年 , 高立群等提出了自适应和声粒子群搜 [ 3] 索(A HSPSO)算法 , 将和声搜索算法与粒子群搜索 算法结合, 首先用粒子群优化和声记忆库中的变量, 再利用动态的 R PA 和 wb 产生新解, 更新记忆库。文 中采用的自适应的音调调节概率和调节步长如下: R PA , i = 1 , Ei/ E i-1 ≥1 , Ei-1 = 0 ; Ei/ E i-1 , Ei/ E i-1 <1 . (2) 式中:Ei 为第 i 代和声记忆库中解变量的目标函数 值的最大值与最小值之差, E 0 =1 . w b(i)=d 1(Hi , max)- upper , x i upper -xi lower)/ n g . Hi , m in +d2(xi (3) 式中:n g 是当前迭代次数 , xi lower是变量 xi 的上 界和下界;Hi , m ax , H i , min是 记忆库中 xi 的最大值和 最小值;d 1 , d2 是两个常数。 迭代次数较大时 , 左部 分可以起一定的调节作用, 当算法陷入局部最优时, 右部分可以起调节作用 。 此外, 和 声 搜 索 已 经 广 泛 应 用 于 工 程 实 际 中[ 4-7] 。例如, 2006 年李亮等提出了改 进和声搜索 算法及其在土坡稳定分析中的应用[ 4] 。 利用改进的 和声搜索算法寻求复杂土坡的临界滑动面及其对应 ＊收稿日期 :2010-10-23 　　　基金项目 :国家自然科学基金资助项目(60962006) 　　　作者简介 :陈莹珍(1987-), 女 , 湖北襄樊人 , 主要从事最优化理论及应用 , 智能计算与智能信息处理 , 金融数学与金融工程研究 , (E-mail)ch enyingz hen 1987@yahoo .com .cn 　　　通讯联系人 :高岳林(1963-), 男 , 教授 , 博士 , 研究生导师 ,(E-mail)gaoy ueli n@263.net 中国煤炭期刊网 www.chinacaj.net

142 太 原 理 工 大 学 学 报　　　　　　　　　　　　　　　　　　第 42 卷　 的安全系数, 改进的和声搜索算法在每次迭代中产 生多个新解, 而基本的和声搜索算法中每次迭代只 产生一个新解。 对改进的和声算法与基本的和声搜 索算法的结果进行了比较, 发现改进和声搜索算法 比基本和声搜索算法能搜索到更危险的滑动面。 2007 年 , 金永强等提出了基于和声搜索的边坡 [ 5] 。传统的和声搜索算法 稳定性投影寻踪聚类分析 采用了固定的和声保留概率 P A R , 不能同时兼顾局 部最优解和全局最 优解的寻求 。 笔者采用动 态的 H MC R(表达式中记为 R H MC)和 PA R 对基本的和声 搜索算法进行了改进, 针对边坡稳定问题的高维非 线性 、非正态的特点 , 提出了一种基于和声搜索和投 影寻踪理论的边坡稳定性评价方法 , 利用投影寻踪 理论将边坡稳定性评价多指标问题转换为单一投影 指标, 采用改进的和声搜索算法优化投影方向 。 文 中, R HM C 和 R PA 的表达式如下 : n g N I R HM C(ng)=R HM C, m in ×exp R HM C, m in R H MC , max ln , R PA(n g)= n g N I (R PA , min -R P A , m ax)+R PA , min . 式中 :N I 为 最 大迭 代 次数 ;ng 为 当前 迭 代 次数 ; R H MC , min , R HMC , m ax , R PA , m in , R PA , m ax 分 别 为 迭 代 起 始 时、迭代终止时第 ng 次迭代时的 R H MC 和 R PA值 。 笔者结合了以上的改进方法, 并对其中部分参 数做了改进 , 对和声保留概率(R HMC)、音调调节概 率(R PA)都采用线性变换, 对文献[ 3] 中提出的音调 调节步长中参数 d 1 , d 2 也采用了线性变化, 音调调 节时增加或减少不再是随机的 , 而是由记忆库中的 变量的平均值决定的 ;同时, 本文将混沌机制作用在 种群的初始化和算法停滞时的变异中。 2 　基本和声搜索算法 和声搜索(H S)是基于音乐演奏过程提出来的 。 在音乐演奏中, 每个演奏者发出一个音调, 构成一个 和声向量 , 如果这个和声比较好, 就把它记录下来 , 以便下次产生更好的和声 。乐器的音调类比于优化 i(i =1 , 2 , …, n), 将各乐器声调 问题中的决策变量 xj 的和声类比于解向量 X j =(x j n), 美学评 价类比于目标函数 f (X j), 音乐家要找到由美学评 价定义的优美的和声, 研究人员要找到由目标函数 定义的全局最优解。 和声搜索算法包括一系列的优 化因素, 例如和声记忆库(H M), 和声记忆库的大小 (H MS), 和声 保 留概 率(H MC R), 音 调 调节 概 率 (PA R)等。 在和声搜索算法中 , 和声记忆库储存可 行解向量 , 和声记忆库的大小决定着可行解的数量 , 2 , …, x j 1 , x j 和声保留概率就是从记忆库中选择新产生的解的概 率 , 音调调节概率是对产生的新解进行扰动的概率。 基本和声搜索的步骤如下。 St ep1 　设定和声搜索的基本参数 : a.变量的个数 N V A R ; b.各变量的取值范围 ; c.和声记忆库可保存和声的个数 H M S ; d.和声记忆保留概率 H MC R; e.音调调节概率 PA R; f.最大迭代次数 。 St ep2 　初始化和声记忆库。 St ep3 　产生新解 。每次可以通过三种机理产 生一个新解 。 a.保留和声记忆库中的分量 ; b.随机选择产生; c.对 a.b.中某些分量进行微调扰动产生 。 St ep4 　更新记忆库 。若新解优于记忆库中最 差解, 则用新解替换最差解 , 得到新的记忆库。 St ep5 　判断是否满足终止条件, 若满足, 停止 迭代, 输出最优解 ;否则 , 重复 Sep3 , St ep4 。 3 　混沌自适应和声搜索算法 3.1 　混沌机制 混沌是 自然 界 存 在 的一 种 广 泛 的 非 线性 现 , 其行为复杂且类似随机 , 但看似一片混乱的混 象[ 8] 沌变化过程并不完全混乱 , 而是存在着精细的内在 规律性 。混沌优化方法是一种新颖的优化算法, 它 利用混沌系统特有的遍历性来实现全局寻优 , 其基 本思想是首先产生一组混沌变量 : Y 0 =(y0 , 1 , y 0 , 2 , … , y 0 , D), y0 , i ∈ (0 , 1) 且以此向量为初始点, 根据 lo gistic 方程 y n, i =4yn -1 , i(1 -yn-1 , i) (5) 产生混沌序列 {Y n =(y n , 1 , yn , 2 , … , y n , D), n =1 , 2 , …, M}, 然后把每维上的混沌变量以载波的方式变换到变量 的取值空间[ 9] , 根据下式 i +r in g(2y n , i -1), 1 n , i = x ＊ y′ r i(t)= r0 , i 1 - 1 +ex p(-0.02ng +4) (6) 得到对应的优化变量 ′ n =(y′n , 1 , y Y ′ n , 2 , … , y ′ n , D), 这样就把当前的解变换到以 x ＊ i 为中心 , 以 R(ng)=(r 1(n g)), r2(ng), …, r D(ng)) 为半径的区域上。 中国煤炭期刊网 www.chinacaj.net

　第 2 期　　　　　　　　　　　　　　　　陈莹珍等:混沌的自适应和声搜索算法 143 本文中使用了两次混沌技术。 第一使用随机混 沌运动初始化种群;第二如果算法停滞, 就选取 M/ 2 个个体进行混沌变异, 具体的变异方法就采用上 述的计算公式。 3 .2 　和声保留概率 和声保留概率的变化是由小到大的 , 在优化的 前期阶段 , 较大的值有利于找到局部最优解, 后期较 小的值可以增加解的多样性[ 5] 。根据文献[ 5] 的思 想, 笔者提出了新的和 声保留概率的 表达式, 定义 H MC R 的变化如下: R H MC =R H MC , m ax - (R HM C, m ax -R H MC , min)＊ng/ N I . (5) 式中 :R H MC , max , R HM C, m in分别为和声保留概率的的最 大值和最小值。 3 .3 　音调调节概率 一般情况下 , 音调调节概率 R PA 的变化 是由小 到大的, 在优化的前期阶段, 较小的值有利于找到局 部最优解, 后期较大的值可以增加解的多样性 。 根 据文献[ 2] 的思想, 笔者提出了音调调节概率的表达 式, R PA 的变化定义如下 : R P A =(0.382ng +0.618n g)/ N I . (6) 3 .4 　音调调节的步长 在最初的和声搜索中 , 每个变量的调节步长 w b 是一样的 , 但是这个步长并不适合所有的变量 , 根据 文献[ 3] 中音调调节步长的变化, 对于 d 1 , d 2 两个参 数, 做了如下的改进 : wb(i)=d 1 ×H i , max - H i , min +d 2 ×(xi upper -xi low er)/ n g , d 1 =(d 1 , m ax -d1 , m in))＊ng/ N I +d 1 , min ; d 2 =(d 2 , m in -d 2 , max)＊ng/ N I +d 2 , max . (7) 　　实验表明 , 当 d 1 是线性 递增, d 2 是线性递 减 时, 算法的性能更好 。 3 .5 　调节的方向 如果产生的新解需要进行微调, 在原来的算法 中都是随机的, 本文中计算出记忆库中解的平均值 , i , new =xi , new +w b 如果产生的新解小于平均 值, 则 x′ ′ (i);若产生的新解大于平均值, 则 x i, new =xi , new -w b ′ (i), 其中 x i, new , x i , new 分别为调节前后解 xi 的值 , av- erage(xi)是和声记忆库中变量 x i 的平均值。 i , new = xi , new +w b(i), if xi , new ≤average(x i), x′ (8) xi , new -w b(i), o thers . 3 .6 　每代和声产生数目 在本文的迭代过程中 , 采用了文献[ 4] 的思想 , 基本的和声搜索算法在每次迭代中仅产生一个新的 解 , 没有尽可能大的利用和声记忆库的累积信息 , 文 献[ 4] 中 , 每次迭代的过程中都产生 N 个新解, 与和 声记忆库中 H M S 个解放在一 起, 找出 H M S 个最 优解作为新的和声记忆库。 3.7 　停滞判断 如果和声记忆库中解的函数值的最大值和最小 值之差小于等于ε, 那么就认为算法停滞, 需要进行 混沌变异。 3 .8 　改进的和声搜索算法的步骤 St ep1 　设定和声搜索的基本参数 : 变量的个数 N V A R ;各变量的取值范 围;和声 记忆库可保存 和声的个数 H MS ;每次 迭代产生新 解的个数 N ;最大迭代次数;和声记忆保留概率的 上下界 ;d 1 , min , d1 , m ax , d 2 , m in , d 2 , max . St ep2 初始化和声记忆库。 St ep3 产生新解。 通过公式(5),(6),(7), (8) 产生新解, 每次迭代得到 N 个新解 。 St ep4 计算新解的目标函数值 , 从新产生的 N 个解和记忆库中选出 HM S 个好的解, 作为新的和 声记忆库。 St ep5 判断是否满足终止条件 , 如 不满足则返 回 step3 ;否则算法结束。 4 　实验及结果分析 为了检验算法的有效性, 下面用了 5 个经常用 到的测试函数对该算法进行测试(见表 1)。 这些函 数模拟了在工程实际中经常碰到的各种特征问题, 因此可以比较准确地衡量算法的优化性能 。 1)Sphere 函数: f 1(x)= ∑n i =1 　　2)Ronsenbrock 函数 : i ; x2 (100(xi+1 -x2 i )2 +(xi -1)2); f 2(x)= ∑n-1 i=1 　　3)Schaff er 函数: f 3(x)=0.5 +(sin 1 +x2 x2 (1 +0.001(x2 2)2 -0.5 1 +x2 2))2 ; 　　4)A ckley 函数 : f 4(x)=-20ex p(-0.2 (∑n i =1 i )/ n)- x2 ex p((∑n i =1 cos(2πx i))/ n)+20 +e; 　　5)G riew ank 函数 : 中国煤炭期刊网 www.chinacaj.net

144 太 原 理 工 大 学 学 报　　　　　　　　　　　　　　　　　　第 42 卷　 f 5(x)= 1 4 000 ∑n i =1 函数 函数名 f 1 f 2 f 3 f 4 f 5 Sphere Ronsenbrock S chaff er A ckley G riew ank x2 cos i - ∏n i =1 表 1　测试函数 阈值 最优值 维数 0.1 100 10 -5 0.1 0.1 10 10 0 0 0 0 0 2 10 10 x i i +1 . 搜索范围 [ -1000, 1000] [ -30, 30] [ -5.12, 5.12] [ -30, 30] [ -600, 600] 为了分析每个算法的性能 , 每种算法单独运行 100 次, 最大迭代次数为 8 000 次 。 M =20 , N =20 , R H MC , min =0.5 , R H MC , m ax =1 .m 为 100 次迭代得到的 最优值的子样均值, b 为最优值 , w 为最劣值 , v 为子 样方差, s 为成功率 。比较结果如表 2 ～ 表 6 所示。 表 2　对 Sphere 的优化结果 方法 IH S AH SP SO CA HS m 43 .020 8 0.061 0.002 2 b 1.48 ×10 -4 0.038 1 5 .9650×10-4 w 326 .695 1 0.094 7 0.005 1 v 1 .68×106 2.882 2 5 .9948×10-7 表 3 　对 Ro nsenbr ock 的优化结果 方法 IH S AH SP SO CA HS m 127.091 0 28.946 8 2 .005 2 b 7 .463 7 6 .953 7 0 .004 7 w 661 .854 440 .727 8 .953 2 v 1.36 ×10 7 7.16 ×10 5 2.929 6 表 4 　对 Schaffer 的优化结果 方法 IH S AH SP SO CA HS m b 0.004 4 8 .78×10 -4 3.9587 ×10-5 1.25 ×10 9 1 .57×1011 0 w 0.004 9 0.004 9 0.002 1 v 0.014 1 6.13 ×10 -4 7 .778 4×10-8 s 8 100 100 s 58 92 100 s 10 42 98 表 5 　对 A ckley 的 优化结果 方法 IH S AH SP SO CA HS m 0.825 1 0.030 2 0.0018 b 0.001 12 0.014 6 9 .1710×10-4 w 2.510 4 0.061 9 0.0025 v 500.249 7 0.690 9 9 .7636×10-8 s 18 100 100 方法 IHS A HS PSO CA HS m 0.151 0 0.095 6 0.083 4 b 0.307 1 0.008 4 0.002 2 w 0.342 0 0.225 1 0.199 6 v 17.363 2 7.059 6 0.001 1 s 26 58 75 Sphere 是个简单的单峰函数。 Ronsenbrock 是 多峰函数, 其全局最优点位于一个狭长的抛物线形 山谷内 , 一般优化方法很容易陷入局部最优 ;Schaf- fe r 函数是正弦波包络函数 , 峰值多而且都是急剧变 化的, 由于它具有强烈的振荡性以及全局最优点被 无数个局部最优点包围的特性, 一般算法很难找到 它的全局最优点;A ckley 函数是函数叠加上适度放 大的余弦函数再经调制而得到的连续型实验函数, 其最小值求解十分困难 ;G riew ank 函数的变量之间 具有乘积项产生的强烈的相互影响, 是激烈的多峰 函数。 平均最优值反映的是算法的收敛精度 , 方差 反映算法的稳定性, 成功率反映了算法的全局最优 能力。 从表 2 到表 6 可以看出, 对于以上 5 个测试函 数来说 , 本文提出的混沌适应和声搜索算法找到的 最优值 、平均值、方差均比前面两个算法要好 , 成功 率比前两个算法高 。尽管对于复杂的多峰函数, 本 算法仍能有效地跳出局部最优解 , 找到全局最优解。 实验表明本算法有很好的跳出局部最优的能力, 从 整体上看, CA H S 算法优于另外的两种改进算法 。 5 　结论 本文针对和声搜索算法的不足, 提出了混沌自适 应和声搜索(CA HS)算法, 该算法结合了各种改进的和 声搜索算法的优点, 加入了混沌搜索机制并对其中的 参数进行调整。与其它两种算法比较表明该算法有较 强的跳出局部最优解的能力, 稳定性较好。但是该算 法仍存在不足, 在以后的工作中会逐步改进, 并用来解 决实际问题。 表 6 　对 G riew ank 的优化结 果 参考文献: [ 1] 　Geem Z W, Kim J H , Loganathan G V .A new heu ristic optimization algorithm :Harmony search[ J] .Simulation, 2001, 76(2):60-80. [ 2] 　M ahdavi M , Fesanghary M , Daman gi r E .A n improved harmony search algorit hm fors ol vi ng opt imizat ion p rob lem[ J] .A pplied M at hematics and Compu tati on, 2007, 188(2):1567-1597. [ 3] 　高立群 , 葛延峰 , 孔芝 , 等 .自适应和声粒子群搜索算法[ J] .控制与决策 , 2010, 25(7):1101-1104. [ 4] 　李亮 , 迟世春 , 林皋 .改进和声搜索算法及其在土坡稳定分析中的应用[ J] .土木工程学报 , 2006, 39(5):107-111. [ 5] 　金永强 , 苏怀智 , 李子阳 .基于和声搜索的边坡稳定性投影寻踪聚类分析[ J] .水利学报 , 2007,(S1):682-686. [ 6] 　K an g S L, Geem Z W.A new st ruct u ral op timiz at ion m et hod based on t he harmony search alg ori th m[ J] .Comput S t ru ct , 2004, 82(9/ 10):781-798. [ 7] 　G eem Z W .O ptim al cost design of w at er di st ribut ion net w orks u sing harmony search[ J] .Eng O pt imiz, 2006, 38(3):259-280. (下转第 154 页) 中国煤炭期刊网 www.chinacaj.net

154 太 原 理 工 大 学 学 报　　　　　　　　　　　　　　　　　　第 42 卷　 The Way to Implement Remote Monitoring in DCS Experiment Teaching System by OPC Technique XIE Peng-hua , NIU Yu-guang (College o f I n f ormation Engineering of TU T , Taiy uan 030024, China) Abstract:A desi gn met hod o f ex perimental teaching sy st em by using O PC technique to moni- to r t he remo te real-time data i n the sy stem o f S U PCO N DCS w as presented , so as to t ransmit re- m ot e real-t ime data o f DCS system and to display t he data dynami cally by Web .It w as illustrat ed to pro gram O PC client and A ctiveX cont rols to access OP C server , and t o em bed A cti veX co nt rol s i n Web pages to implement the comm unicat ion w i th t he O PC server .Wi th t he examples of exper- iment al teachi ng system , a g roup of real-time dat a o btained by accessing O PC server t o moni to r the o n-sit e equipment by Web w as given .T he ex periment proved that a new w ay w as provided t o im plement remo te m oni to ring in DCS ex perimental teaching system . Key words:D CS remo te real-time moni to ri ng ;O PC technolo gy ;A ctiveX contro l (编辑 :庞富祥) (上接第 144 页) An Improved Adaptive Harmony Search Algorithm CHEN Ying-zhen, GAO Yue-lin (Institute o f I n f ormation and S ystem Science , Bei f ang University of N ationalities , Y inchuan 750021 , China) Abstract:H armony Search (H S)i s a heuristic optimization met hod .Fo r t he purpose of av oi- ding t he disadv ant ag e of i mproved harm ony search (IH S)alg orit hm , a new adaptive harm ony search algo ri thm is presented .T he algo rithm ut ilizes chao s technique initializing populat ion , a- dapt ive harmony pro babi li ty , and pitch adjusti ng f requency and bandwidt h to pro duce new solu- tions .In each ite rat ion , several so lutions are gene rat ed so as t o makes f ull use of info rmatio n of harm ony mem ory .If t he algo ri thm arriv es at stag nating state , chao s m utati on i s ado pt ed in o rder to increase t he di versity solutio ns .Finally , the proposed algo ri thm i s test ed by five benchmark functi on and compared w ith H IS , A H SPSO .T he t est result s show the favo rable abilities of accu- racy and escaping lo cal mi nimum s . Key words:harm ony search algo ri thm ;adaptive search ;chaos (编辑 :贾丽红) 中国煤炭期刊网 www.chinacaj.net