-
题名面向异构多背包问题的多级二进制帝国竞争算法
被引量：1
- 1
-
-
作者
李斌
唐志斌
-
机构
福建理工大学机械与汽车工程学院
福建省大数据挖掘与应用技术重点实验室(福建理工大学)
福建理工大学交通运输学院
-
出处
《计算机应用》
CSCD
北大核心
2023年第9期2855-2867,共13页
-
基金
教育部人文社会科学研究规划基金资助项目(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在超大规模组合优化问题中的求解提出了可行的算法设计方案。
-
关键词
0-1背包问题
异构多背包问题
帝国竞争算法
局部搜索策略
跳出局部最优机制
多级计算架构
-
Keywords
0-1 knapsack problem
Heterogeneous Multiple Knapsack Problem(HMKP)
Imperialist Competitive algorithm(ICA)
local search strategy
jump out of local optimum algorithm(jloa)
multiple level computing architecture
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
