具有邻域搜索机制的爆炸搜索算法

第３７卷　第１８期　、，０１．３７　・计算机工程　２０１１年９月　Ｓｅｐｔｅｍｂｅｒ　２０１　１　Ｎｏ．１８　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　人工智能及识别技术・　文章编号；１ｏ０ｏ．３４２８（２０１１）１８—－ｏ１８，一ｌ２　文献标识码ｔ　Ａ　中圈分类号：ＴＰ１８　具有邻域搜索机制的爆炸搜索算法　曹炬，侯学卿　（华中科技大学数学与统计学院，武汉４３００７４）　摘要：受烟花（炸弹）爆炸的启发，提出一种新型的智能优化算法一爆炸搜索算法（ＥＳＡ）。该算法引入邻域搜索的思想，包含３个重要算　子：爆炸搜索算子，迁移算子，变异算子，具有较大的局部一全局搜索能力，且收敛速度快、稳定性好。对ｂｅｎｃｈｍａｒｋ函数集进行仿真并与　ＣＰＳＯ等算法进行比较，实验结果证实了ＥＳＡ的高效性。　关奠词：智能优化算法；爆炸搜索算法；邻域搜索；爆炸搜索算子；迁移算子；变异算子　Ｅｘｐｌｏｓｉｏｎ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　Ｎｅｉｇｈｂ０ｒｈ００ｄ　Ｓｅａｒｃｈ　Ｍｅｃｈａｎｉｓｍ　ＣＡＯ　Ｊｕ．ＨｏＵ　Ｘｕｅ－ｑｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｓｔａｔｉｓｔｉｃｓ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ）　［Ａｈｓｔｒａｃｔｌ　Ｉｎｓｐｉｒｅｄ　ｂｙ　ｅｘｐｌｏｓｉｏｎ　ｏｆ　ｆｉｒｅｗｏｒｋｓ（ｂｏｍｂ），ａ　ｎｅｗ　ｉｎｔｅｌｌｉｇｅｎｃｅ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｉｓ　ｃａｌｌｅｄ　Ｅｘｐｌｏｓｉｏｎ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ（ＥＳＡ）．Ｏｎｅ　ｔｈｅｏｒｙ　ｄｅｆｉｎｅｄ　ａｓ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｓｅａｒｃｈ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ＥＳＡ　ａｎｄ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｎｃｌｕｄｅｓ　ｔｈｒｅｅ　ｉｍｐｏｒｔａｎｔ　ｏｐｅｒａｔｏｒ：ｅｘｐｌｏｓｉｏｎ　ｓｅａｒｃｈ　ｏｐｅｒａｔｏｒ，ｍｏｖｉｎｇ　ｏｐｅｒａｔｏｒ，ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ．Ｔｈｉｓ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｓｔｒｏｎｇｅｒ　ａｂｉｌｉｔｙ　ｏｆ　ｇｌｏｂａｌ　ｓｅａｒｃｈ　ａｓ　ｗｅｌｌ　ａｓ　ｌｏｃａｌ　ｓｅａｒｃｈ．Ａｎｄ　ｉｔ　ａｌｓｏ　ｈａｓ　ｆａｓｔ　ｃｏｎｖｅｒｇｅｎｃｅ　ａｎｄ　ｇｏｏｄ　ｓｔａｂｉｌｉｔｙ　ｆｅａｔｕｒｅｓ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔ　ｕｓｉｎｇ　ｓｔａｎｄａｒｄ　ｂｅｎｃｈｍａｒｋ　ｆｕｎｃｔｉｏｎｓ　ａｎｄ　ｃｏｍｐａｒｉｓｏｎ　ｗｉｔｂ　ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍｓ　ｐｒｏｖｅｓ　ｈｅ　ｔｅｆｉｃｉｆｅｎｃｙ　ｏｆｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ．　［Ｋｅｙ　ｗｏｒｄｓ］ｉｎｔｅｌｌｉｇｅｎｔ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；Ｅｘｐｌｏｓｉｏｎ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｈｍ（ｔＥＳＡ）；ｎｅｉｇｈｂｏｒｈｏｏｄ　ｓｅａｒｃｈ；ｅｘｐｌｏｓｉｏｎ　ｓｅａｒｃｈ　ｏｐｅｒａｔｏｒ；ｍｉｇｒａｔｉｏｎ　ｏｐｅｒａｔｏｒ；ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１１．１８．０６０　１概述　优化技术是一种以数学为基础，用于求解各种工程问题　化问题。在算法中称搜索点为炸点，，（　）为评测函数，值越　小表示炸点位置越好。在爆炸搜索算法中，主要包括３个算　子，即爆炸搜索算子、迁移算子、变异算子。算法流程如下，　其中，ｇｂｅｓｔ为历史最优点。　优化解的应用技术，作为一个重要的科学分支一直受到人们　的广泛重视，许多实际问题都可以转化为求解某一目标函数　的全局最小值，即ｍｉｎｆ∽：ｆ２ｃ　Ｒ（　∈　，ｒ０，ｉ＝１，２＇…，，ｚ）。　爆炸搜索算法流程：　Ｉｎｉｔｉａｌｉｚｅ：在搜索空间内初始化Ｍ个炸点，并计算各个炸点的　破坏程度（目标函数值），并存储目标函数值最小的点到ｇｂｅｓｔ；　Ｗｈｉｌｅ（终止条件不满足）　每个炸点执行爆炸搜索算子；　近年来，人们根据自然界的一些生命现象提出了许多智能优　化算法，如遗传算法　Ｊ、微粒群优化算法［３－４１等。然而，很　多实际中的目标函数比较复杂，可能有很多局部极小值，这　些算法不一定能找到全局最小值，因此，仍然需要对这些算　执行迁移算子；　执行变异算子；　更新ｇｂｅｓｔ　Ｅｎｄ　Ｗｈｉｌｅ　法进行研究。基于此，本文提出一种爆炸搜索算法（Ｅｘｐｌｏｓｉｏｎ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ，ＥＳＡ），该算法是受烟花（炸弹）爆炸现象的　启发提出的，算法提出了邻域搜索的思想，该算法能有效地　对炸点的邻域进行搜索，并引入其他策略使算法能有效地避　免早熟。　输出最好的个体。　２．２爆炸搜索算铑中各算子的实现　２．２．１爆炸搜索算子　爆炸搜索算子为ＥＳＡ的核心算子，主要实现邻域搜索，　２爆炸搜索算法　’　当炸弹爆炸时，它能够对周围的一个圆形邻域产生影　响，而且随着炸弹威力的不同影响的区域大小也不相同，如　果将该区域看成空间中的一个局部区域，炸出的弹片看成区　域中的点，一次爆炸就类似于对局部区域的一次探索。如果　完成炸点位置的更新，临域的大小能自适应地变化，使得算　子具有较强的全局搜索能力。定义Ｒｔ＝（Ｒｔ１，Ｒｔ２，…，尺　）为区　域的半径，即炸点Ｘ爆炸所影响的区域为【ｘ—Ｒｔ，Ｘ＋Ｒｔ］。　在一个搜索区域内点的数量是不可数的，在实际中需从这不　把一次爆炸看做对炸点位置周围的一次覆盖型探索，则这种　探索可看做空间中该点附近的一次局部搜索，受此启发提出　邻域搜索的思想，在算法的实现中加入自适应因子，使得探　索区域能自适应地增大，炸点可以移动较大的距离，实现了　全局的搜索，变异算子的引入使得算法不易陷入局部最优，　因此，ＥＳＡ对于多蜂的目标函数也具有较好的性能。　可数的点中选出部分进行评测，考虑到效率，这些点要尽量　少，而且能够尽可能包含区域内最好点。然后从这些点中选　择出最好的一个作为下一次爆炸的位置，从而完成炸点位置　的更新。　作者简介：曹炬（１９５５一），男，教授、博士，主研方向：智能计算，　运筹学；侯学卿，硕士研究生　收稿日期：２０１１—０３—１５　Ｅ－ｍａｉｌ：ｈｘｑｉｎｇ．ｈｕｓｔ＠ｇｍａｉｌ．ｃｏｒｎ　２．１爆炸搜索算法的漉程　本文设计的算法主要适用的问题可以表示为无约束的优　１８４　计算机工程　２０１１年９月２０日　＝Ｏ．ＯＩ（Ｘ　一Ｘ　），　对炸点Ｘ＝（　，Ｘ２，…，　）执行爆炸搜索算子，首先取　＝ｒａｎｄ（），从点集｛　±２ｘ（Ｏ，０，…，以，…，０），ｉ＝１，２，…，ｎ｝选　函数维数。取　＝１．５，Ｎｕｍ＝１６，　这４个参数是根据大量的实验结果选择的。　择最好的　（　≤２ｎ）个点，并记录炸点Ｘ到　个点的方向　向量＂Ｐｐ　，…，ｖ　，由此得到了Ｋ个方向，接下来将在Ｋ个　方向上选择点进行评测。令Ｎｕｍ表示在每个方向上选择的点　ＰＳＯ算法采用自适应惯性权策略（ＣＰＳＯ）　】，ＧＡ交叉变　异概率分别为０．８、０．叭，采用高斯扰动进行变异操作　Ｉ。　３．２仿真结果　表１给出ＥＳＡ的仿真结果，同时与ＣＰＳＯ算法和ＧＡ算　法进行了比较。通过仿真结果可以看出，ＥＳＡ取得了较好的　结果，能够有效地避免早熟，标准差也比较小，具有好的稳　定性。图１～图４给出上述函数在仿真时最优值的变化曲线，　的个数，Ｓｔｅｐ＝２Ｒｔ／Ｎｕｍ，然后从点集：　｛ｘ＋ｒａｎｄ（）￣ｍｘＳｔｅｐ０Ｖｉ　Ｉｉ＝１，２，…，Ｋ；ｍ＝１，２，…，Ｎｕｍ｝　中选择最好的点Ｘ—Ｔｅｍｐ，其中，＠表示两向量对应位置相　乘。如果Ｘ—Ｔｅｍｐ比炸点Ｘ好，则Ｘ＝Ｘ—Ｔｅｍｐ作为新的炸　点位置，否则，炸点ｘ不发生变化。　从曲线上可以看出ＥＳＡ算法的收敛速度也是比较快的。　表１　４个高堆函数的　试结果　为了保证算法不陷入局部最小，参数Ｒｆ是自适应的。定　义参数ｉｎｉｔ—Ｒｔ：　ｉｎｉｔ—Ｒｔ＝　ｆ一一ｔＸ（　ｆ　一Ｒｔｍｉ　）／Ｔ　其中，ｔ表示当前迭代代数；Ｔ表示最大迭代代数；Ｒ　、　Ｒ　表示ｉｎｉｔ—Ｒｔ的上限和下限。　如果ｘ—Ｔｅｍｐ优于炸点　，即炸点Ｘ位置发生更新，　Ｒｔ：ｉｎｉｔ—Ｒｔ，否则Ｒｔ：　ｆ，其中，　＞１为比例因子。这　样当炸点ｘ陷入局部最小时，随着ｍ的增大，有助于Ｘ跳　出局部最优。　爆炸搜索算子目的在于进行邻域搜索，临域的自适应变　化保证算子兼顾了局部与全局。　２．２．２　迁移算子　令　表示迁移比例，即最差的【　Ｍ】个炸点发生迁移。　本算子的执行流程为：选择最差的［ｉｔＭ］个炸点，使这些炸点　向历史最优点ｇｂｅｓｔ移动，更新公式如下：　Ｘ　＝Ｘ＋２ｘ　ｒａｎｄ（）￣（ｇｂｅｓｔ—Ｘ、　通过迁移算子可以使差的炸点向最好的位置移动，快速　跳出差的位置从而提高算法的效率，同时该算子也能在一定　程度上提高算法的收敛速度。　２．２．３变异算子　变异算子的引入主要是增加随机性，增加炸点的多样　性。本算子引入参数　表示变异概率，推荐　取０．０１～０．１。　炸点Ｘ＝（　，Ｘ２，…，　）发生变异，按照下面公式更新位置：　＝　（１＋Ｎ（０，ｏ９）　其中，Ｎ（０，　）表示一个０均值，标准差为　的正态分布随　机数，　＝（　，　，…，　）＝　ｘ　一Ｘ　。　），ｘ一，Ｘ　ｍ，　为搜索　空间的上下限，ｙ推荐取０．１。　３仿真实验及分析　本节将对ｂｅｎｃｈｍａｒｋ函数进行仿真，限于篇幅，选取部　分数据罗列，下面给出了这４个ｂｅｎｃｈｍａｒｋ函数，其中，Ｆ３　的最优值为一１２　５６９．５，其他３个均为０。　ｆｌ（ｘ）：∑当　≤１００　（　）：∑　ｌ　ｓｉｎ　ｔ…　ｌＸｉＩ≤５００　（　）＝∑　ｌ＃一１０ｃｏｓ（２ｘｘｉ）＋１０　　ｌＪ　ｌ≤５．１２　ｒ——————　———一　厂４（　）＝一２０ｅｘｐ｛一０．２…／￣３…０　２／３０　Ｊ—　ｅｘｐ（∑　ｃｏｓ（２般ｆ），３ｏ）＋２０＋ｅ　Ｉ　Ｉ≤３２　３．１参数设定　算法中涉及的参数有：炸点规模　，迭代次数　，变异　概率ＪＰＭ以及ｙ、　Ｋ、Ｒｔ、尺　、ａ、Ｎｕｍ。其中在仿真　中，迭代代数　２　０００，炸点规模Ｍ＝５０，根据经验选定ＰＭ＝　０．０５，　＝０．１，／１＝０．２，Ｋ＝ｍａｘ｛Ｄｉｍ／１０，１），其中，Ｄｉｍ为　８Ｏ　４００　８００　ｌ　２００　ｌ　６００　２　０００　迭代代数　图１　Ｆ１仿真量优值的变化情况　５　０００　７　０００　魍　阔一９　０００　监　血　ｌ１　０００　０　４００　８００　１　２００　ｌ　６００　２　０００　迭代代数　圈２　Ｆ２仿真最优值的变化情况　００　８０　ｊ罾６Ｏ　轻　闰　盖４ｏ　迭代代数　圈３　Ｆ３仿真曩优值的变化情况　（下转第１８７页）　第３７卷第ｌ８期　陈建东，王小明：ＬＳ—ＳＶＭ模型选择的秩准则及其比较　１８７　表５给出了相应的调谐参数值及其计算时间。　表４模式爿剐中的参数，值　在预测误差方面，从表６可以发现，所有方法都比较接　近，其中，ＦＢ方法最佳，ＯＩＣ次之。在预测效果的稳健性方　面，仍然是ＦＢ方法最佳，ＯＩＣ次之。　６结束语　本文对ＦＢ、ＡＩＣ、ＢＩＣ、ＧＣＶ和ＯＩＣ方法进行了计算效　率、预测效果以及稳健性三方面的比较。综合各方面情况来　看，ＯＩＣ准则可能是惩罚方法中最优的，与ＦＢ方法相比，　在计算时间方面具有巨大的优势，保持了较好的预测能力，　稳健性也比较接近于ＦＢ方法；而ＦＢ方法在稳健性方面表现　最佳，同时也具有一定的预测精度，但计算强度比较高，耗　时较多。因此，ＯＩＣ准则是一个比较好的方法，具有高效的　计算效率、较高的预测精度和较好的稳健性。　在模型的调谐参数方面，从表４可以发现，所有的惩罚　方法选出的调谐参数都比较接近，且都比ＦＢ方法大，其中　ＯＩＣ准则最接近ＦＢ方法。在这个例子中ＡＩＣ和ＧＣＶ准则并　没有出现较大的奇异值，认为很有可能所有的目标函数的尾　部比较陡峭。　参考文献　［１］Ｈａｓｔｉｅ　Ｌ　Ｔｉｂｓｈｉｒａｎｉ　Ｒ，Ｆｒｉｅｄｍａｎ　Ｊ．Ｔｈｅ　Ｅｌｅｍｅｎｔｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃａｌ　Ｌｅａｒｎｉｎｇ：Ｄａｔａ　Ｍｉｎｉｎｇ，Ｉｎｆｅｒｅｎｃｅ，ａｎｄ　Ｐｒｅｄｉｃｔｉｏｎ［Ｍ］．Ｎｅｗ　Ｙｏｒｋ，　ＵＳＡ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００１．　在计算时间方面，从表５可以发现，所有的惩罚方法都　［２］Ｅｆｒｏｎ　Ｂ，Ｔｉｂｓｈｉｒａｎｉ　Ｒ　Ｊ．Ａｎ　Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｔｈｅ　Ｂｏｏｔｓｔｒａｐ［Ｍ］．　［Ｓ．１．】：Ｃｈａｐｍａｎ＆Ｈａｌｌ，１９９３．　［３】Ｌｅｎｄａｓｅ　Ａ，Ｗｅｒｔｚ、‘Ｓｉｍｏｎ　Ｇ　Ｆａｓｔ　Ｂｏｏｔｓｔｒａｐ　Ａｐｐｌｉｅｄ　ｔｏ　ＬＳ—ＳＶＭ　比ＦＢ方法快数百倍，ＡＩＣ、ＢＩＣ和ＧＣＶ准则之问用时比较　接近。表６给出了相应的模型错判率的计算结果。　表６模式爿捌中的借爿率　（％）　ｆｏｒ　Ｌｏｎｇ　Ｔｅｒｍ　Ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　Ｔｉｍｅ　Ｓｅｒｉｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｉｎｔ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ．Ｂｕｄａｐｅｓｔ，Ｈｕｎｇａｒｙ：【ｓ．ｎ．］，　２００４：７０５—７１０．　［４］穆朝絮，梁瑞鑫，李训铭．非线性系统的ＬＳＳＶＭ联合逆控制　器［Ｊ１．计算机工程，２００９，３５（１２）：１８１—１８３．　编辑（上接第１８４页）　１６　索书志　（５）较低的时间复杂度。ＥＳＡ算法中各个算子的实现相　对比较简单，具有较低的时间复杂度。　ｌ２　４结束语　本文提出了一种新型智能优化算法——爆炸搜索算法　（ＥＳＡ），并通过测试验证了算法的高效性。在以后的工作里可　趔　籁　陋８　堰　皿　以对算法中各个算子做进一步优化，以降低复杂度和提高效　４　率，并将算法用于解决一些实际问题。　０　０　４００　８００　１　２００　１　６００　２　０００　参考文献　［１］Ｉｏａｎｎｉｓ　Ｇ　Ｔｓｏｕｌｏｓ．Ｍｏｄｉｉｆｃａｔｉｏｎｓ　ｏｆ　Ｒｅａｌ　Ｃｏｄｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　迭代代数　ｆｏｒ　Ｇｌｏｂａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｎｔａ—　ｔｉｏｎ，２００８，２０３（１）：５９８—６０７．　【２】　Ａｒｙａｎｅｚｈａｄ　Ｍ　Ｂ，Ｈｅｍａｔｉ　Ｍ．Ａ　Ｎｅｗ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｈｍ　ｆｏｒ　ｔ圈１　Ｆ４仿真最优值的变化情况　３．３结果分析　通过测试可以看出ＥＳＡ具有以下特点：　Ｓｏｌｖｉｎｇ　Ｎｏｎｃｏｎｖｅｘ　Ｎｏｎｌｉｎｅａｒ　Ｐｒｏｇｒａｍｍｉｎｇ　ｒｏｂｌＰｅｍｓ［Ｊ］．Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎ，２００８，１９９（１）：１８６—１９４．　［３］Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　Ｒ．Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［ＣＪ／／Ｐｒｏｃ．ｏｆ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕｒｌ　Ｎｅｔａｗｏｒｋｓ．【Ｓ．１．】：ＩＥＥＥ　Ｐｒｅｓｓ，１９９５：１９４２—１９４７．　（１）强大的全局搜索能力与局部搜索能力。无论单峰函数　还是多峰函数，ＥＳＡ都能计算出很好的结果，而且精度都比　较高。　（２）收敛速度快。ＥＳＡ能够在很小的代数内找到全局最优　点或者到达全局最优点附近。　【４】　蔡昭权，黄　翰．自适应变异综合学习粒子群优化算法【Ｊ】．　计算机工程，２００９，３５（７）：１７１—１７２．　（３）稳定性高。ＥＳＡ具有较小的方差，即每次测试结果的　波动不大。　【５】王凌，刘波．微粒群优化与调度算法【Ｍ】．北京：清华大学　（４）通用性好。在上述测试中ＥＳＡ的参数设置是一样的，　而且每个函数的结果都是优秀的。　出版社，２００１．　编辑索书志