生物地理学优化算法的改进及在聚类优化问题上的应用

发布时间：2020-07-07 15:17

【摘要】：优化问题无处不在,与人们的生活息息相关。为了高效地处理优化问题,群智能优化算法应运而生。生物地理学优化(Biogeography-Based Optimization,BBO)算法是群智能优化算法之一,其模拟了物种在不同栖息地之间的迁移行为和生态环境的变异现象。BBO算法结构简单易实现,吸引了大量学者关注,并在数据挖掘、图像处理、机械设计等诸多领域得到应用。然而,随着社会的发展和科技的进步,科学和工程领域中所面临的优化问题越来越复杂,对算法性能的要求也越来越高。目前,BBO算法的性能依然有着较大的提升空间。聚类优化是数据挖掘领域的一个重要分支,K-means算法是一种经典的聚类算法,其原理简单,具有较好的可伸缩性和高效性,但也存在K的个数无法确定,对初始点敏感等问题。为此,一些学者尝试用群智能算法解决K-means算法存在的问题。BBO算法性能良好,应用广泛,有潜力更好地处理聚类优化问题,但目前相关研究甚少,因此,BBO算法在K-means聚类优化上的应用有着较大的研究价值。本文介绍了BBO算法和聚类优化的研究背景及意义,描述了BBO算法的步骤,分析了BBO算法存在的主要缺陷,对BBO算法的国内外研究现状进行了简单综述。为了进一步提升BBO算法的性能并拓展其应用,本文针对BBO算法在处理高维和实际复杂问题时性能不强,效率不高和普适性不好的问题,提出了三种BBO改进算法,并应用改进算法处理K-means聚类优化问题。本文主要研究工作如下:(1)为了增强BBO算法的优化性能,提出了一种差分迁移和趋优变异的生物地理学优化算法(DGBBO)。对BBO算法的迁出栖息地选择方法,迁移算子和变异算子分别进行改进,克服了轮赌选择法可能选出较差的栖息地并将其信息分享给较优的栖息地,迁移算子在解空间中可搜索到的位置局限和变异算子可能破坏优质解的缺陷,又从多个角度降低计算复杂度,最终得到改进算法DGBBO。对DGBBO算法进行了计算复杂度分析,并在16个基准函数上进行了仿真实验,对比了其它state-of-the-art算法,实验结果表明,DGBBO算法具有较好的优化性能。(2)为了提升BBO算法的优化效率,提出了一种高效融合的生物地理学优化算法(EMBBO)。首先去掉BBO算法的变异算子,大幅度降低计算复杂度,又对BBO算法的迁移算子进行改进,弥补变异算子的缺失并增强局部搜索能力,然后在改进的迁移算子中融入单维全维交叉更新策略,平衡了探索和开采并进一步降低计算复杂度,接着在算法中融入反向学习机制,一定程度上避免算法陷入局部最优,最终得到高效算法EMBBO。对EMBBO算法进行了稳定性分析,并在21个基准函数和CEC2017测试集上进行了仿真实验,对比了其它state-of-the-art算法,实验结果表明,EMBBO算法具有较高的优化效率。(3)为了更好地处理K-means聚类优化问题,提出了一种生物地理学优化和灰狼优化(GWO)的混合算法(HBBOG)。将BBO算法和GWO算法分别进行改进,增强它们的性能,然后将两种改进算法采用单维全维交叉更新策略进行混合,使它们优势互补,整体上平衡探索和开采,最终得到混合算法HBBOG。对HBBOG算法进行了全局收敛性分析,并在30个基准函数和9个聚类数据集上进行了仿真实验,对比了其它有竞争力的算法,实验结果验证了HBBOG算法的普适性,表明HBBOG算法在处理K-means聚类优化问题上整体表现最佳。3项研究在算法设计方面:第一项研究是在BBO算法的基础上提出的创新性改进,重点强调算法性能的提升;第二项研究是在第一项研究的基础上,借鉴了部分创新性改进,又提出了新的改进,不仅强调算法性能的提升,还强调了计算复杂度的大幅度降低,从而达到算法优化效率高,可操作性强的目的;第三项研究是在第二项研究的基础上,借鉴了部分创新性改进,又提出了新的改进,除了强调算法性能的提升外,还要求算法能处理更多类型的优化问题,最终达到普适性强的目的。3项研究在实验设计方面:第一项研究在一组常用的基准函数上进行了实验;第二项研究在更多基准函数上进行了实验;第三项研究不仅在基准函数上进行了实验,还测试了聚类数据集。整体上,3项研究遵从由算法的简单改进到复杂改进,由单一改进研究到改进和应用综合研究的逻辑关系,后者较前者的改进更加完善,算法性能更加优秀,实验内容也更加丰富,这也对应了本文研究由浅入深的过程。
【学位授予单位】：河南师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18
【图文】：

DGBBO算法与其不完整变体的收敛曲线

概率,交叉策略,栖息地,榜样学习

图 4-2 共享操作优概率 ps的计算如下所示。/= t MaxDT策略源自遗传算法，被广泛应用于优化领域[54-55]。受交叉策略交叉策略，其表示如下。( ) ( ) ( 0.5 ) *( ( ) ( ))j SI j SI j i jSIV ← H SIV + rand H SIV H SIVSI是通过榜样学习法选出的栖息地。(4-2)可知，(0.5-rand)可以得到一个-0.5 和 0.5 之间的权重，(H一个交叉值。权重乘以交叉值再加 HSI(SIVj)，实现了在解空间中心的小范围内扰动，其实质是在 HSI(SIVj)附近区域进行局部样栖息地，拥有更优的 HSI，故这种局部搜索更可能搜索到

迁移算子

代策略和趋优引导策略主要用于局部搜索，相对来说，趋优引选取的，具有更高的种群多样性。由式(4-1)可知，t 的值增加，前期，ps的值较小，执行趋优引导策略的概率更大，在迭代接取代策略的概率更大。这样的设置符合算法前期对种群多避免多样性破坏优质候选解。使 Hi(SIVj)有机会通过三种不同的策略进行更新，可以在局克服原迁移操作可搜索位置局限的缺陷，大幅度增强了局部的迁移算子 BBO 算法变异算子中的缺陷，直接去掉了该算子。为了弥算子中融入了基于平均选择概率的两种差分扰动操作，其详改进的迁移算子流程如下所示。

【相似文献】