计算机应用

作者：李斌, 唐志斌

单位：1.福建理工大学 机械与汽车工程学院, 福州 350118；2.福建省大数据挖掘与应用技术重点实验室(福建理工大学), 福州 350118；3.福建理工大学 交通运输学院, 福州 350118

关键词：0-1背包问题,异构多背包问题,帝国竞争算法,局部搜索策略,跳出局部最优机制,多级计算架构

基金：教育部人文社会科学研究规划基金资助项目(19YJA630031)

在传统多背包问题的基础上，从典型物流服务场景中共性抽象出异构多背包问题（HMKP），并设计和定制了一种帝国竞争算法（ICA）对HMKP进行求解和评估。针对原始ICA易陷入局部最优以及0-1背包问题最优解往往在约束边界周围的特点，设计了双点自变异策略（TPAS）和跳出局部最优算法（JLOA）对ICA进行改进，提出面向0-1背包问题的二进制帝国竞争算法（BICA）。BICA在求解35个0-1背包问题算例时展现出了全面、高效的寻优能力，基于最佳匹配值法（BMV）的BICA在第一组测试集的20个算例上能对19个算例100%找到理想最优值，在第二组测试集的15个算例上能对12个算例100%找到理想最优值，在所有对比算法中表现最优。数值结果分析表明，BICA在寻优演化中维持多极发展策略，并依托独特的种群进化方式在解空间中高效搜索理想解。在此基础上，针对HMKP强约束性和高复杂度的特性，基于BICA设计了求解HMKP的多级二进制帝国竞争算法（MLB-ICA）。分别在多个典型0-1背包问题算例组合构建的HMKP高维测试集上进行了MLB-ICA的数值实验和性能评估，结果表明虽然MLB-ICA的求解时间比Gurobi长，但求解精度提高了28%。可见，MLB-ICA能以较低的计算代价在可接受的时间范围内高效求解高维复杂的HMKP，为ICA在超大规模组合优化问题中的求解提出了可行的算法设计方案。

来源：2023年第9期

《计算机应用》期刊编辑部

查看计算机应用杂志2023年第9期