烟花算法译文.doc

烟花算法（最优化）摘要：通过观察烟花爆炸得到启示，一种新颖的（novel）蚁群智能算法（称作烟花算法），被提出以解决全局复合函数最优化问题。在烟花算法的提出中，使用了两种爆炸（搜索）进程，同时也设计了保持粒子多样性的机械设置。为了验证FA的性能（validation），用了9个标准测试函数做了大量的实验来比较FA和两个粒子群最优化（PSO）算法的变型，即标准PSO和克隆PSO。实验结果证明了假设的FA无疑胜过那两种PSO变型，不管在集中速度还是解决全局准确度方面。关键词：自然运算，群智能，烟花算法，粒子群最优化，函数最优化。1.介绍：最近几年，群智能（SI）已经在全世界致力于算法问题工作的研究者中变得流行起来。SI算法，例如粒子群最优化（PSO），蚁群系统，克隆选择算法和群体机器人等，在解决许多算法问题上都有许多优点。在所有的SI算法中，PSO在研究多维空间的优化选址问题中是一个最流行的算法。在1995年，K和E提出了PSO作为一个能力全局优化算法，由于鸟群的行为使他们受启发。从此以后，PSO就吸引了全世界研究者们的关注，大量的PSO正确性检测也不断提出。就像PSO，大多数群智能算法是由于自然界一些智能克隆行为的启发。在这篇论文中，由于烟花出现的群体行为的启发，一个新颖的称作烟花算法（FA）的群智能算法被提出用于函数最优化。FA是通过刺激烟花的爆炸进程来呈现和实行的。在FA中，使用了2个爆炸（搜索）进程，同时也精心设计了保持粒子多样性的机械设置。为了验证（validate）假设的FA执行的正确性，用FA、标准PSO（SPSO）和克隆PSO（CPSO）的9个标准测试函数做了比较实验。结果显示FA不管在最优化准确度还是收敛速度方面都明显胜过SPSO和CPSO。该论文的余下部分是这样组织的。第二章节描述了FA的框架，介绍两种搜索进程和保持多样性的机械设置。第三章节显示实验结果以验证FA的执行正确性。第四章节总结论文。2烟花算法2.1 FA框架当烟花爆炸后，火花的散落将充满烟花周围的局部空间。我们认为，烟花的爆炸进程可以看作是一个在局部空间内对固定点的搜索，这个空间范围是烟花爆炸后在爆炸中产生的火花。当我们要找到一个定义为f(x)=y的点x，我们可以在潜在区域里不断的引爆烟花，直到一个火花命中了点x或者相当靠近点x。在图1显示了FA的大致框架来模仿引爆烟花的进程。在FA中，为了每个爆炸的产生，我们首先选择n个位置，在这n个位置中分别引爆了n个烟花。在爆炸之后，我们可以得到和估计粒子的位置。当找到最优位置，算法结束。否则，在从附近的火花选择n个其他的位置和烟花进行下一轮的爆炸。从图1中可以看到在一个好的爆炸进程设计下的FA的成功执行，及选择位置的适当方法，将分别在2.2和2.3小节进行详尽说明。2.2烟花爆炸的设计通过观察烟花表演，我们可以发现烟花爆炸两个特有的行为。当烟花制造得很好，将会产生大量的火花，火花集中于爆炸的中心点。在这种情况下，我们可以欣赏到烟花的壮观表演。然而对于坏的烟花爆炸而言，只会产生相当少的火花，这些火花零星散落（scatter）在空间中。图2中显示了两种情况。从搜索算法的角度看，一个好的烟花意味着烟花要定位在距离最优位置很近的可能区域范围。这样它就适合利用更多的火花来搜索烟花的局部区域。相反，一个坏的烟花意味着最优位置可能离烟花定位较远。然后搜索距离就会变大。在FA中，相比于坏的烟花，好的烟花应产生更多的火花，且充分（amplitude）的爆炸更小。火花数。假设FA设计于解决一般的最优化问题：Min f(x) R, xmin x xmax ，(1) 其中x=x1,x2,.xd表示潜在空间一个定位，f(x)是一个目标函数，xmin和xmax表示潜在空间的范围。然后由每个烟花xi产生的火花的数目定义如下：m是一个控制n个烟花产生火花总数的参数，是n个烟花中的目标函数的最大值（最坏的），表示计算机常量的最小值，用来避免除0错误。为了避免华丽的烟花造成重大后果，定义范围为si，在等式3表示。其中a与b是固定常量参数。爆炸的位移幅度。相比于火花数目的设计，一个好的烟花的爆炸的位移幅度比一个坏的更小。每个烟花的爆炸振幅定义如下：其中表示最大爆炸振幅，ymin =min(f(xi) (i =1, 2,.,n)是n个烟花当中的目标函数最小值（最好的）。产生火花。在爆炸过程中，火花可能从任意z的方向（维数）受爆炸的影响。在FA中，我们获得了受影响的任意方向的数目，如下：其中d是位置x的维数，rand(0, 1)是区间0,1上的一个均匀分布。我们可以用算法1获得烟花xi的火花的位置。模仿爆炸过程，首先产生一个火花的位置。然后如果发现获得的位置超出了潜在空间，根据算法把它画到潜在空间中去。算法1.获取火花位置初始化火花位置；随机选择z维；计算位移（displacement）：；对每一维（已选择的z维）令；若则画到潜在空间：；结束if结束for为了保持火花多样性，我们设计了另一种方式来产生火花高斯爆炸，在算法2中表示。一个高斯函数（1，1），表示1和标准偏差（deviation）1的高斯分布，是用来确定爆炸系数，在我们的实验中，个这种类型的火花是在每一个爆炸代中产生的。算法2.获取一个特定火花位置初始化火花位置：；随机选择z维；计算高斯爆炸的系数；2.3位置的选择在每个爆炸产生过程的开始，应该选择n个位置来用作烟花爆炸。在FA中，目前最好的位置x*，（目标函数f(x*)根据它为目前的最佳位置），为下一个爆炸产生始终保留着。此后，n-1个位置的选择是基于与其他地点的距离，以保持火花的多样性。一般把位置xi与其他位置的距离定义如下：其中K是所有烟花和火花的当前位置集合。一个位置xi的选择概率定义如下：计算距离时，任何距离的测量措施（measure）都可以使用，包括曼哈顿距离，欧式距离，角度为基础的距离等。其中d(xi, xj)定义为| f(xi) f(xj) |，它的概率等于在Ref中基于概率的免除密度的定义。2.4总结算法3总结了FA的框架。在每一个爆炸产生中，根据算法1和算法2分别产生了两种火花。根据第一种，火花数目和爆炸振幅取决于对应的（corresponding）烟花(f(xi)的质量。相比之下，另一种产生于使用高斯爆炸进程，在一个烟花周围的局部高斯空间进行搜索。获取两种火花位置以后，再为下一个爆炸产生选择n个位置。在FA中，每代产生中大约有个函数估计值。假设一个函数的优化可以在第T代产生中找到，我们就可以推出FA的复杂度是。算法3.FA的构造随机选择烟花的n个位置；while停止准则=false分别在n个位置引爆n个烟花：for 每个烟花xi根据等式3计算那些烟花产生的火花数目：；用算法1获取烟花xi的个火花的位置； end for for k=1: 随机选择一个烟花xj； 使用算法2来产生那个烟花的一个特定火花； end for选择最佳位置并保留到下一代爆炸产生；根据等式7已给的概率，从两种火花和当前烟花中随机选择n-1个位置。end while3 实验3.1基准函数为了调查假设的FA的性能，我们用9个基准功能进行实验。对所有功能的可行范围被设置为100, 100D。这个函数表达式，初始化间隔和维度在表1列出。表1. 我们的实验中使用的9个基准函数3.2 FA，CPSO和SPSO的对比实验在这一节，我们在收敛速度和优化精度方面把FA与CPSO和SPSO的执行作比较。表2. FA,CPSO和SPSO的解决方案的统计工具和标准偏离（deviation）在9个标准测试函数20个独立运行CPSO和SPSO的参数都是Ref里的集合。对于FA来说，通过一些初步实验选择参数。我们发现FA在这样的设定下运行得十分好：n =5, m = 50, a =0.04, b =0.8, A = 40, and m = 5,应用于所有比较实验。表2描述了在9个基准函数的3个算法的优化精度，平均超过20个独立运行。可以看到假设的FA在所有函数上清楚地胜过了CPSO和SPSO。另外，FA在大多数基准函数可以发现最优化的解决方案比10000函数赋值少，正如表3所示。然而，CPSO和SPSO的优化精度在10000函数赋值里是不能接受的。除了优化精度，收敛速度在优化中也是十分必不可少的。为了验证FA的收敛速度，我们做了更多的细致深入的实验。图3描述了FA、 CPSO和SPSO在8个基准函数平均超过20个独立运行的收敛曲线。从这些结果我们可以得到一个结论，假设的FA比CPSO和SPSO有更快的速度。从表3我们可以发现FA只要10000次函数赋值就可以找到优秀的解决方案。这也反映了假设的FA较快的收敛速度。图3.FA,CPSO,SPSO在8个基准函数的收敛曲线。The function tness are averaged over 20 independent runs.表3. FA,CPSO,SPSO在10000个函数赋值的20次独立运行的9个基准函数的解决方案的统计工具和标准偏离3.3 讨论正如实验中所看到的，相比于PSO，FA具有更快的收敛速度和更好的优化精度。我们认为，FA的成功主要表现在以下两个方面。在FA中，火花从z维遭受的爆炸威力的同时，每个火花随机选择了z维。因此，有概率在烟花和目标位置之间出现了不同正好位于这些z维。= =。在这个方案中，烟花的火花可以从z个方向向目标位置移动，同时这z个方向使FA有较快的收敛速度。产生两种类型的火花来保持火花多样性，位置的特定选择过程是一个为了保持多样性机械设置。因此，FA有能力避免过早的收敛。4 结论通过模拟烟花的爆炸过程，所谓的FA是假设并实施的功能优化。FA,CPSO,SPSO之间的实验显示了假设的FA有一个不错的表现= =。在9个基准函数上，它在优化精度和收敛速度方面