萤火虫算法的改进及其在物流中心选址中的应用

发布时间：2020-07-24 04:29

【摘要】：随着工程技术领域和科学计算规模的日益增长,传统优化计算方法无法在合理时间内找到所需解,从求解效率来讲,对于这类问题的求解基本无效。近年来,基于仿生学的启发式智能优化算法不断发展和研究,因其操作简单、求解高效等特点得到众多学者的青睐,并广泛应用到许多领域中。2008年剑桥大学学者Xin-She Yang受萤火虫自身发光来传递信息这一特征,提出了萤火虫算法(Firefly Algorithm,FA),该算法作为一种较为新颖的启发式算法,因其模式简单清晰、需设置的参数较少、收敛速度和求解精度较高的优点,引起了诸多学者的关注,被应用于聚类、经济调度、发电系统、复杂网络、图像标注等多个领域。虽然萤火虫算法优点明显广受青睐,但同其它启发式算法一样,其本身也存在一些不足,如在高维条件下,由于吸引度减弱易导致算法陷入局部极小值、求解性能降低等问题。针对萤火虫算法存在的不足之处,本文在查阅大量相关文献和多次实验测试后,分析此现象产生的缘由,对萤火虫算法所涉及到的参数、自身搜索机制等进行优化改进,提升算法的寻优性能。并将改进后的算法应用于多配送中心选址问题中,求解到了较优的求解方案。本文的主要工作如下:(1)为了提高萤火虫算法在高维条件下的求解精度,提出了一种具有振荡、约束和自然选择机制的萤火虫算法(OCSFA)。首先,引入二阶振荡因子,平衡上一代个体对当前代个体的影响,防止萤火虫个体陷入局部极值;然后,加入基于sigmoid函数的约束因子,动态调整个体移动距离,在算法后期避免萤火虫个体在理论最优值附近过度扰震导致精度降低的情况;最后,采用基于高斯积分倒数递减趋势的自然选择,维持个体多样性的同时加快算法的收敛速度。通过理论分析证明了改进算法的收敛性和时间复杂度,通过对12个不同特征标准测试函数多个维度的函数优化仿真实验,测试结果表明改进算法的寻优精度和收敛速度均有明显提升。尤其是在高维情况下,几乎对所有函数仍能找到理论最优解,较好解决了萤火虫算法不适合于高维求解的问题。(2)针对基本萤火虫算法求解多配送中心选址问题时存在易陷入局部极值、寻优精度较低的不足,提出一种具有全局导向移动机制和动态调整步长因子与吸引度的萤火虫算法(GDAFA)。首先,通过寻优距离偏差度自适应策略结合高斯分布,对固定取值的步长因子进行改进,更好地均衡算法的探测与挖掘能力,提高萤火虫种群的多样性;然后,引入最小吸引度,并随迭代次数自适应地改变,避免萤火虫之间缺失牵引力而引起随机游动;最后,根据当前最优萤火虫位置改进移动机制,不仅使萤火虫的移动具有一些全局导向性,而且扩大了个体间的信息共享,提升了算法的进化寻优能力。理论分析证明了GDAFA算法的收敛性和时间复杂度,测试结果则显示,改进后的算法具有较好的求解性能,且算法的收敛速度与求解精度均有显著提升。(3)将GDAFA算法运用于求解多配送中心选址问题。定义了适合求解问题的编码方式,并用边界缓冲域处理越界萤火虫,增加方案的多样性;用替换原则处理萤火虫个体中序号相同的备选点,提高备选方案的有效性;对模型中约束条件进行优化,将定值惩罚距离改进为自适应取值,增加模型的适应能力。实验结果表明,本文算法无论在最优解、最差解还是平均解均优于其他四种对比算法,因此改进算法GDAFA求解多配送中心选址问题是一种有效、可行的方法。
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;F252
【图文】：

萤火虫,算法流程图

萤火虫算法流程图

【参考文献】