应用邻域搜索的多策略进化算法研究

发布时间：2020-08-29 09:00

　　在科学研究和工程项目中,很多实际问题都可转化为对应的优化问题来求解。作为一类有效的最优化方法,进化算法通过模拟自然界中生物进化现象来搜索问题的最优解,具有算法结构简单,性能优良等特点。相对于一些经典的最优化方法,特别是基于梯度信息的方法,进化算法对问题的数学性质要求不高,甚至可直接用于黑盒优化。然而,随着社会经济发展,优化问题也日趋复杂,求解难度大大增加,使得进化算法的性能受到了极大挑战,容易出现早熟或陷入局部最优等不足。事实上,就算法性能而言,影响进化算法性能的两个重要因素是:全局勘探能力和局部开采能力,如何平衡好这两种能力是提高算法性能的关键。为此,本文以平衡算法的全局勘探和局部开采能力为目标,着重研究了如何设计多策略机制用于提高进化算法的性能,避免单一策略带来的搜索局限性;同时,为充分利用种群中优秀个体的精英信息,还研究了如何应用邻域搜索机制来改善算法性能。本文的主要工作及创新点如下:(1)在人工蜂群算法中,解搜索方程用于生成新的候选解,是影响算法性能的主要因素。然而,已有相关研究指出,该方程存在勘探能力强而开采能力弱的问题。为此,我们提出了一种基于随机优秀个体的新解搜索方程,试图通过融合优秀个体的精英信息来增强方程的开采能力。并且,为保持算法在勘探和开采能力上的平衡,我们设计了一种简洁的多策略机制用于同时应用新旧方程,采用了IF-ELSE结构的方式来控制两种方程的使用频率。在22个典型的测试函数上开展数值实验,与3种知名的改进人工蜂群算法进行对比,实验结果表明该多策略机制能够有效提高算法性能。(2)在差分进化算法中,变异策略是影响算法性能的重要因素,不同类型的变异策略适合求解的问题类型一般也不同。然而,经典差分进化算法仅采用单一的变异策略用于生成新的候选解,导致算法性能受到了极大限制。为此,我们提出了一种基于多子种群技术的多策略机制用于增强算法性能。在该机制中,根据个体的适应度值将种群分为三个子种群,每个子种群分别采用不同的变异策略,使得各子种群具备不同的搜索能力,力图平衡整个种群的勘探和开采能力。在34个典型的测试函数上进行实验,与包含7种差分进化算法在内的12种进化算法进行对比,实验结果表明基于该多策略机制的差分进化算法能在大多数测试函数上取得更好结果。(3)在进化算法中,种群中的优秀个体通常包含了可用于指导算法搜索的精英信息,合理有效地利用这些信息可推动整个种群朝着更好的方向进化。然而,如何利用这些信息是设计相关学习机制的难点。为此,我们引入了基于环形拓扑结构的邻域搜索机制用于增强算法的性能。在该机制中,按个体下标索引的方式把种群中所有个体组织成环形结构,对每个个体定义了半径为K的邻域空间,在该邻域空间内开展细粒度搜索,以期找到更好个体,充分发挥优秀个体的引领作用。我们将该邻域搜索机制分别应用于人工蜂群算法和差分进化算法,实验结果表明该机制可有效地改善相应算法的性能,具有良好的普适性。(4)为进一步验证本文提出的改进算法的性能,我们引入了3个实际优化问题:无线传感器网络的覆盖控制问题、调频声波的参数估计问题、以及扩频雷达的波利相位编码设计问题。对于无线传感器网络的覆盖控制问题,我们采用本文提出的改进人工蜂群算法来解决,与经典人工蜂群算法相比,本文算法在覆盖率上能提高2.12%。对于调频声波的参数估计问题和扩频雷达的波利相位编码设计问题,我们采用本文提出的改进差分进化算法来解决,与经典差分进化算法相比,本文算法在这两个问题上的结果精度能分别提高92.22%和47.12%。
【学位单位】：江西师范大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP18
【部分图文】：

应用邻域搜索的多策略进化算法研究

邻域搜索操作示意图

【参考文献】