基于随机局部搜索的改进布谷鸟搜索算法

基于随机局部搜索的改进布谷鸟搜索算法

0算法整体框架在设计应用中，许多优化问题，如容器设计、波纹管设计、拉压弹簧结构优化设计等，可以转变为非线性约束优化设计。不失一般性,一个非线性约束优化问题(最小化问题)可描述为其中:f(x)是目标函数,gj(x)和hj(x)分别为不等式约束和等式约束,li和ui分别为变量xi的上下界。等式约束hj(x)=0通常可以转换为hj(x)-δ≤0和-hj(x)-δ≤0两个不等式约束来处理,δ是一个很小的正数。与传统的优化方法相比,以遗传算法等为代表的智能优化算法是一类基于种群迭代的全局优化方法,它不需要问题的梯度信息,容易实现,能以较大的概率收敛到问题的全局最优解,在函数优化、机器学习、神经网络训练、参数优化等领域中得到广泛应用［1］。然而,智能优化算法是基于无约束的优化技术,在求解约束优化问题式(1)时一定要结合一种合适的约束处理技术。Michalewicz等人［2］将现有的基于进化算法的约束处理技术分成四类,即惩罚函数法、多目标法、可行解优于不可行解法和其他混合方法。利用进化算法求解约束优化问题已成为进化计算领域的研究热点之一,并涌现出大量的约束优化进化算法［3］。布谷鸟搜索(cuckoosearch,CS)算法是Yang等人［4］于2009年提出的一种模拟布谷鸟寻窝产卵行为的全局搜索方法。CS算法是一种新的基于种群迭代的搜索算法,具有容易实现、参数设置少等优点,在无约束优化等领域有着广泛的应用［5，6］。CS算法已被证明在收敛速度和稳定性方面都超过了遗传算法和粒子群优化算法［4］,然而与其他基于种群迭代的智能优化算法一样,CS算法同样存在后期收敛速度慢、局部搜索能力弱和易早熟收敛等缺点。针对CS算法存在局部搜索能力弱的缺点,本文提出了一种改进的CS算法。为了平衡算法的勘探和开采能力,引入惯性权重对Lévy飞行更新公式进行修改;利用随机局部搜索算法对当前最优解进行局部搜索,以加快算法的收敛速度;结合改进的可行性规则处理约束条件,对三个工程结构优化设计问题进行求解,数值实验结果表明了改进算法的有效性。1布谷鸟窝的寻窝CS算法模拟了布谷鸟为寻找适合产卵的鸟窝而随机游走的寻窝过程。为了模拟布谷鸟寻窝的行为,需设定以下三个理想的状态［4］:a)布谷鸟一次只产一个卵,并随机选择鸟窝位置来孵化它;b)在随机选择的一组鸟窝中,最好位置的鸟窝将会保留到下一代;c)可利用的鸟窝数量N是固定的,一个鸟窝主人能发现一个外来鸟蛋的概率为Pa。在CS算法中,一个鸟巢的卵表示一个候选解,一个布谷鸟的卵表示一个新的解。在上述三个理想状态的基础上,布谷鸟寻窝的路径和位置更新公式如下:其中:xti表示第i个鸟窝在第t代的鸟窝位置;α为步长控制量;⊕为点积;L(λ)为随机步长路径,其服从Lévy分布:通过位置更新后,用随机数r∈[0,1]与鸟窝的主人发现外来鸟的概率Pa对比,若r>Pa,则对xti进行随机改变,否则不变。CS算法的伪代码如下所示。与粒子群优化算法一样,布谷鸟搜索算法也是基于种群迭代的全局随机搜索算法,将鸟窝位置看做是问题的候选解(最优鸟窝位置即对应为问题的最优解),通过位置更新公式进行迭代,从而逼近最优解。然而,PSO算法主要以个体自身的最优位置和群体中全局最优位置为引导进行位置更新,从而引导粒子群逐步向最优粒子靠拢,具有较强的局部搜索能力,引入惯性权重以平衡算法的全局与局部搜索能力。CS算法则通过产生随机步长来更新鸟窝位置,其步长服从Lévy分布,最后以一定概率对当前鸟窝位置进行判断是否进行改变。2改进的布谷鸟搜索方法2.1基于佳点集方法的计算效率在求解具体问题前,对其全局最优解处在什么位置还一无所知,如果随机初始化种群个体,不利于搜索到全局最优解,可能导致要增加迭代次数或种群大小,这势必会增加算法的计算量。另外,Huapt等人［7］指出,在基于种群迭代搜索的全局优化算法中,多样性较好的初始种群对寻找全局最优解很有帮助。佳点集方法是一种有效的、可以减少实验次数的实验方法。在相同取点个数的条件下,佳点序列要比其他方法选取的点序列更均匀［8］。因此,本文采用佳点集方法生成初始种群,从而保证了初始种群的多样性。图1是采用佳点集方法产生的规模为80的二维初始种群分布。从图1可以看出,与随机方法相比,利用佳点集方法产生的初始种群个体分布均匀,具有较好的多样性。2.2改进惯性权重在基本CS算法中,布谷鸟寻窝的路径和位置是随机的,以父代位置信息为参考进行更新。为了提高CS算法的性能,本文在布谷鸟寻窝的路径和位置更新式(2)中引入惯性权重:惯性权重的引入可使CS算法有扩展搜索空间的趋势,有能力搜索新的区域。一般来说,在全局优化算法中,总希望前期有较强的全局搜索能力、后期有较高的开发能力,以加快收敛速度。实验表明,较大的惯性权重w有利于跳出局部最优,进行全局寻优;较小的w值有利于局部寻优,加速算法收敛。为了平衡算法的全局和局部搜索能力,惯性权重w的值应随着迭代次数的增加而递减。然而,CS算法在实际搜索过程中是非线性的,惯性权重线性递减策略不能反映实际的优化搜索过程。因此本文引入一种惯性权重非线性递减策略［9］:其中:iter为当前迭代次数。2.3最优值生成随机局部搜索算法是Luus等人［10］提出的一种具有较强局部搜索能力的方法。2007年,Selvakumar等人［11］对其进行了改进,具体实现步骤如下:设初始搜索点为X0,其对应的目标函数值为F0best。其中:Xmin和Xmax为局部搜索域的边界;β为局部搜索的参数;DGmin和DGmax是决策变量可行域的边界值;R0为本地搜索的初始范围;X0best(随机局部搜索的初始最好搜索点)和Xopt(最优搜索点)等于X0。b)生成NL个本地搜索点。其中:r(D,1)为D个[-1,1]间的随机数矢量。c)计算每个局部搜索点的目标函数值,所有搜索点的最小目标函数值记为Fbmest,相应的决策变量X记为Xbmest,最优值更新如下:d)缩小搜索范围。其中:γ为收缩因子。e)判断是否达到终止条件,若满足,则输出最优结果Fopt和Xopt;否则,返回步骤b)。2.4基于三个可行性规则的热价CS算法是基于无约束的全局优化方法,因此在求解约束优化问题时一定要结合一种合适的约束处理技术。惩罚函数法是最常用的约束处理技术之一,但其惩罚因子难以确定。Deb［12］提出了一种不需要任何参数的联赛选择算子,并采用三个可行性规则来比较成对个体的优劣:a)若比较的两个个体均为可行个体,则目标函数值小的个体存活到下一代。b)若比较的两个个体一个为可行个体,另一个为不可行个体,则可行个体存活到下一代。c)若比较的两个个体均为不可行个体,则约束违反度小的个体存活到下一代。约束违反度计算公式为这种约束处理技术简单,容易实现,本文采用基于可行性规则的联赛选择算子来处理约束条件。2.5随机改变发现条件ca)设置算法参数,利用佳点集方法产生初始种群,令iter=1。b)根据2.3节的方法计算并找出当前最优鸟窝位置和其对应的最优适应度值。c)判断算法是否满足终止条件,若满足,则算法结束,输出最优值;否则,转步骤d)。d)按式(2)(4)和(5)更新鸟窝的位置,得到新的鸟窝位置。e)随机产生一个均匀分布的数r∈[0,1],如果r>Pa,则随机改变发现概率较大的鸟窝位置,找出并保留最优鸟窝位置及对应值。f)利用随机局部搜索算法对当前最优鸟窝位置进行局部寻优,令iter=iter+1,返回步骤b)。3求解优化问题为了测试本文算法(记为MCS)的性能,从文献中选取了两个工程结构设计优化问题进行求解。MCS算法的参数设置为:种群规模N=50,α=1,Pa=0.25,最大迭代次数itermax=1000。3.1mcs算法与ga4、cpso算法的比较焊接梁的结构如图2所示。焊接梁结构设计优化的目标是在一定约束条件下使其总成本最小。它有四个设计变量,即x1(h)、x2(l)、x3(t)和x4(b),其目标函数和约束条件如下:其中:。变量的取值范围为0.1≤x1,x4≤2,0.1≤x2,x3≤10。焊接梁结构设计优化问题通常作为标准测试问题用来测试优化方法的有效性。利用本文提出的MCS算法对焊接梁结构设计优化问题进行求解,并与MBA(mineblastalgorithm)［3］、GADTS(geneticalgorithmswithdominancetournamentselec-tion)［13］、CPSO(co-evolutionaryparticleswarmopti-mization)［14］和CAEP(culturalalgorithmwithevolutionaryprogramming)［15］进行比较,寻优结果如表1和2所示(其他方法的结果直接来源于文献)。从表1和2可知,MCS算法得到的结果要优于GA4和CP-SO算法;与CAEP算法相比,MCS算法得到相似的最优结果和较好的平均结果、最差结果和标准差;与MBA算法相比,MCS算法得到了稍好的最优结果,但MBA算法得到了较好的平均结果、最差结果和标准差。图4给出了MCS算法对焊接梁结构设计问题的寻优曲线。为了进一步说明MCS算法的有效性,本文将其与当前几种性能较好的粒子群优化算法进行比较,它们是NMPSO(hy-bridNelder-Meadsimplexparticleswarmoptimization)［16］、HPSO(hybridparticleswarmoptimization)［17］、PSO-DE(hybridparticleswarmoptimizationanddifferentialevolution)［18］和CVI-PSO(con-straintviolationintervalparticleswarmoptimization)［19］。比较结果如表3所示。从表3可以看出,MCS算法得到的平均结果、最差结果与标准差要优于NM-PSO算法;与HPSO算法和CVI-PSO算法相比,MCS算法获得了相似的最优结果和较好的平均结果、最差结果及标准差;与PSO-DE算法相比,MCS算法得到了相似的结果。3.2mcs算法与其他算法的比较压力容器的结构如图4所示。它的优化目标是总造价最小。它有四个设计变量,即两端帽的厚度Th(x1)、壳的厚度Ts(x2)、内径R(x3)和容器中间部分圆柱的长度L(x4)。其目标函数和约束条件如下:其中:变量的取值范围为1≤x1≤99,1≤x2≤99,10≤x3≤200和10≤x4≤200。利用MCS算法对压力容器结构设计问题进行求解,并与GADTS、CPSO、MBA和NMPSO算法进行比较,结果如表4和5所示。从表4、5中结果可以看出,与其他几种算法相比,MCS算法得到了最好的结果。与GA4和MBA算法相比,MCS算法得到了较好的结果;与NMPSO算法相比,MCS算法得到了较好的最优结果,而NMPSO获得了较好的平均结果、最差结果和标准差;与CPSO算法相比,MCS算法取得了较好的最优、平均和最差结果,而CPSO算法获得了较好的标准差。图5给出了MCS算法对压力容器结构设计问题的寻优曲线。为了进一步验证MCS算法的性能,本文将其与NM-PSO、HPSO、PSO-DE和CVI-PSO算法进行比较,比较结果如表6所示。从表6可知,与NM-PSO和PSO-DE算法相比,MCS算法获得了较好的最优结果和较差的平均结果、