-
题名面向异构多背包问题的多级二进制帝国竞争算法
- 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
[自动化与计算机技术—计算机系统结构]
-
-
题名基于计算物流和群集智能的多集装箱码头泊位分配
被引量:1
- 2
-
-
作者
李斌
唐志斌
-
机构
福建理工大学机械与汽车工程学院
福建理工大学、福建省大数据挖掘与应用重点实验室
福建理工大学交通运输学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2023年第16期262-284,共23页
-
基金
教育部人文社会科学研究规划基金(19YJA630031)。
-
文摘
以港口运营方统一整合多集装箱码头作业空间资源为背景,探讨了考虑泊位水深约束和出口集装箱可转港作业的多码头动态连续泊位分配问题(multi-terminal dynamic and continuous berth allocation problem,MDC-BAP)。基于计算物流将MDC-BAP抽象为异构多背包问题进行运筹建模,建立了同时考虑港航双方作业总成本最小化的混合整数规划模型,进而设计了一类融合计算物流和群集智能的二阶段改进帝国竞争算法(two-stage improved imperialist competitive algorithm,TSI-ICA)对模型进行求解。采用三种计划周期12个大规模MDC-BAP算例执行数值实验,比较了多种改进帝国竞争算法和多种启发式规则在MDC-BAP模型上的综合求解性能,TSI-ICA设计的“元启发式算法+启发式规则”框架在大规模算例上的表现明显优于“启发式规则+启发式规则”的资源分配模式,并从运作成本和运营韧性两方面阐明了多码头协同生产优于单码头独立作业模式,从而为多集装箱码头泊位协同分配提供了较好的智能决策支持解决方案。
-
关键词
多集装箱码头
泊位分配问题
联合生产运营
异构多背包问题
计算物流
帝国竞争算法
排队论
-
Keywords
multiple container terminal
berth allocation problem
joint production and operation
heterogeneous multiple knapsack problem
computational logistics
imperialist competitive algorithm
queuing theory
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-