基于有导向变异算子求解多维背包问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (15): 36-38.

基于有导向变异算子求解多维背包问题

陆建波，闭应洲，龙珑，元昌安

广西师范学院计算机与信息工程学院，南宁 530001

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-21 发布日期:2011-05-21

Solving multi-knapsack problems based on guided mutation

LU Jianbo，BI Yingzhou，LONG Long，YUAN Chang’an

College of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530001，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

摘要/Abstract

摘要： 多维背包问题（MKP）是经典的NP难的组合优化问题。引入有导向变异算子的进化算法GM-EA（Guided Mutation EA）来求解该问题，通过结合粒子群优化的方法改进郭涛算法，更好地利用种群中的全局信息，取得较好的效果。实验结果表明GM-EA是求解MKP有效的算法。

关键词: 多维背包问题, 有导向的变异, 局部搜索, GAlib

Abstract: Multidimensional Knapsack Problem（MKP） is a kind of classical combinatorial optimization problems.A “Guided” Mutation Evolutionary Algorithm（GM-EA） is introduced to solve this problem，which combines Guotao’s algorithm with the idea from particle swarm optimization，utilizes the global information in population.The experimental results show that GM-EA algorithm is competitive to solve MKP.

Key words: Multidimensional Knapsack Problem（MKP）, guided mutation, local search, GAlib

陆建波，闭应洲，龙珑，元昌安. 基于有导向变异算子求解多维背包问题[J]. 计算机工程与应用, 2011, 47(15): 36-38.

LU Jianbo，BI Yingzhou，LONG Long，YUAN Chang’an. Solving multi-knapsack problems based on guided mutation[J]. Computer Engineering and Applications, 2011, 47(15): 36-38.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[4]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[5]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[6]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[7]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[8]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[9]	洪剑珂1，张峥华2，许贵平2. 基于加强概率控制策略的SAT局部搜索算法[J]. 计算机工程与应用, 2017, 53(14): 56-60.
[10]	王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.
[11]	伍艳莲1，2，姜海燕1，2，庄嘉祥1，郭小清1，许一骅1. 精英策略个体优势遗传算法研究[J]. 计算机工程与应用, 2016, 52(7): 143-149.
[12]	林耿1，徐梅琴2. 图的最大二等分问题的一种离散填充函数算法[J]. 计算机工程与应用, 2016, 52(5): 27-32.
[13]	鲁宇明1，4，王彦超2，刘嘉瑞3，Wu Liu4. 一种改进的生物地理学优化算法[J]. 计算机工程与应用, 2016, 52(17): 146-151.
[14]	胡博. 基于均匀设计的免疫克隆多峰函数优化[J]. 计算机工程与应用, 2015, 51(2): 57-59.
[15]	胡敏1，胡博1，黄红梅2. 基于免疫Memetic算法的网络组播路由优化[J]. 计算机工程与应用, 2013, 49(2): 105-108.