差分进化算法的改进与应用

作     者：左汶鹭 

作者单位：北方民族大学 

学位级别：硕士

导师姓名：高岳林

授予年度：2024年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：差分进化算法 反向学习 双种群 勘探与开发 车辆路径问题 

摘      要：差分进化(Differential Evolution,DE)算法是一种经典的优化技术,该算法依靠变异、交叉和选择操作实现种群进化,能够高效地搜索解空间。但其仍存在易陷入局部最优,进化后期收敛速度较慢,算法延展性不高等缺点。基于此,本文针对DE算法进行改进与应用研究,讨论其相关改进工作,分析其进化机制并有针对性地提出改进策略,得到两种新的DE变体。通过一系列数值实验验证其有效性、延展性和先进性,并扩展以使其适用于求解容量受限的车辆路径问题。本文主要贡献如下:1.针对差分进化算法的变异算子不能很好地适应种群进化状态,以及该算法在进化后期易陷入局部最优的缺点,提出基于随机邻域变异和趋优反向学习的差分进化算法。首先,为个体设置动态邻域。其次,用全局最优个体引导邻域最优个体形成复合基向量,并设置自适应缩放因子调节全局最优个体的引导程度,以提高变异向量符合进化状态的概率。最后,将反向个体与全局最优个体凸组合得到趋优反向学习策略,帮助种群跳出局部最优,提高收敛精度。基于21个Benchmark函数的数值实验结果表明该算法具有较强的竞争力,能够有效求解不同维度的优化问题。2.针对差分进化算法在进化中不能充分平衡勘探与开发的缺点,提出基于个体潜力值的动态双种群差分进化算法。首先,定义个体潜力值并据此将种群动态划分为潜力子群和普通子群,提高子种群的多样性。其次,改进DE/current/1用于潜力子群执行变异,设计带有权重因子的两阶段变异算子用于普通子群执行变异。同时,基于预定义的正弦公式和成功历史记忆分别为两个子群设置自适应参数,进一步平衡勘探与开发。基于CEC2013、CEC2017和CEC2020测试套件验证了改进算法的先进性和有效性。3.针对容量受限的车辆路径问题,将改进的差分进化算法进行离散化处理,使其能够适用于求解车辆路径问题。首先,介绍了个体编码与解码方式以及适应度评价函数。其次,离散化两种改进算法的变异算子,并提出离散形式的交叉算子。最后,采用局部搜索算子来提高个体质量,并结合贪婪选择策略得到两种改进的离散差分进化算法。在Augerat A数据集上验证了改进算法的有效性和实用性。