二次多背包问题(Quadratic Multiple Knapsack Problem, QMKP)是经典0-1背包问题的一类复杂变体,也是典型的NP-hard问题,对于人力资源调度、生产排程计划、设施选址规划等现实问题的求解具有重要理论和应用价值。它结合了二次背包问题和多背包问题的特性,将各物品间的联合价值与多个背包相融合,增加了问题的耦合度,也使得可行解数量猛增,导致求解难度大幅上升,对求解算法提出了很高的要求。
仿生算法是仿生学在优化算法领域的应用成果,在求解复杂优化问题方面表现出了显著的优越性。通过模拟自然界的生态平衡机制,提出了一种新型仿生算法——牵制平衡算法。为验证牵制平衡算法在求解资源配置类问题方面的优越性与求解二次多背包问题及其现实扩展问题的有效性和竞争力,本文使用牵制平衡算法对工程设计问题、基准测试函数和0-1背包问题标杆算例进行仿真测试并将所得结果与文献记录的优化算法进行对比分析;针对二次多背包问题特征与难点,提出了牵制平衡与差分进化混合算法,并对大量标杆算例进行了仿真测试和横向纵向对比分析;在案例研究中,针对二次多背包问题的现实应用——多回收中心逆向物流路径规划问题,提出了牵制平衡与差分进化嵌套混合算法,并设计了与其他优化算法的对比试验。
本文研究内容与成果如下:
(1)受到自然界生态平衡机制的启发,提出了一种新型仿生算法——牵制平衡算法,算法以种群个数对应设计变量的维度,以种群规模对应设计变量的值,以物种间的牵制关系为优化驱动力,以系统达到稳态平衡为优化目标,构造了自成长函数、牵制函数和迭代机制。通过对其进行实验角度的收敛性测试和算法机制测试以及数学角度的收敛性分析和复杂度分析,验证了算法的可行性。
(2)为验证牵制平衡算法对于连续型和离散型资源配置问题的求解性能,使用本算法对工程设计问题、基准测试函数、0-1背包问题标杆算例进行仿真实验,并将所得结果与国内外文献所记录其他优化算法进行对比分析,表明牵制平衡算法在求解资源配置类问题的优越性。
(3)为扩展牵制平衡算法的应用范围、扩充二次多背包问题的求解方法,提出了牵制平衡与差分进化混合算法用于复杂资源配置问题——二次多背包问题的求解,以HJ标杆数据集的180个算例为测试对象,通过横向对比验证了混合算法较于基础算法性能的显著提升,通过纵向对比分析验证了混合算法相较于文献中其他优化算法的竞争力和有效性。
(4)在案例研究中,研究多回收中心逆向物流路径规划问题与二次多背包问题的映射关系,将该问题作为二次多背包问题在物流领域的现实应用,对问题特征和求解难点进行深入分析,构建了相应数学模型,并提出了牵制平衡与差分进化嵌套混合算法对其进行求解,结果显示了所提方法求解复杂现实优化问题的实用性和优越性,扩展了牵制平衡算法与其他优化算法的结合形式,也为多回收中心逆向物流路径规划问题的求解提供了新思路。