离散杂草优化算法在0/1背包问题中的应用

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (30): 239-242.

离散杂草优化算法在0/1背包问题中的应用

宋晓萍1，胡常安2

1.烟台南山学院管理科学与工程学院，山东烟台 265713
2.兰州理工大学机电工程学院，兰州 730050

出版日期:2012-10-21 发布日期:2012-10-22

Discrete invasive weed optimization algorithm for 0/1 knapsack problem

SONG Xiaoping1, HU Chang’an2

1.College of Management Science and Engineering, Yantai Nanshan University, Yantai, Shandong 265713, China
2.College of Mechanical-Electronical Engineering, Lanzhou University of Technology, Lanzhou 730050, China

Online:2012-10-21 Published:2012-10-22

摘要/Abstract

摘要： 为解决粒子群优化算法在求解0/1背包问题中的早熟收敛问题，将杂草优化算法应用到离散问题，提出了一种离散杂草优化算法（DIWO）。根据组合优化问题的特点，对原算法中正态分布于父代周围的子代进行离散化分析，引入遗传操作中的一种改进的变异机制，保证了新算法的有效性，使其具有局部的随机搜索能力。通过三个仿真实例验证，对比粒子群算法，新算法在种群数量较小、迭代次数较少的情况下能取得更好的结果。

关键词: 杂草优化算法, 0/1背包问题, 组合优化

Abstract: To address the issue of restraining premature stagnation problem of particle swarm optimization algorithm for solving 0/1 knapsack problem, a Discrete Invasive Weed Optimization algorithm（DIWO） is designed. Based on the characteristics of combinatorial optimization problem, this paper disperses the distribution of the offspring, an improved mutation operator of the genetic algorithm is applied to the new algorithm, to ensure its effectiveness and the local random search capability. The experimental results show that the algorithm, with the smaller populations and the fewer number of iterations, can produce better results, compared with the particle swarm optimization algorithm for knapsack problem.

Key words: invasive weed optimization, 0/1 knapsack problem, combinatorial optimization

宋晓萍1，胡常安2. 离散杂草优化算法在0/1背包问题中的应用[J]. 计算机工程与应用, 2012, 48(30): 239-242.

SONG Xiaoping1, HU Chang’an2. Discrete invasive weed optimization algorithm for 0/1 knapsack problem[J]. Computer Engineering and Applications, 2012, 48(30): 239-242.

[1]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[2]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[3]	李袁，高尚，李肇基，王万耀. 新型差分进化模型的多等级子群杂草优化算法[J]. 计算机工程与应用, 2018, 54(21): 107-114.
[4]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[5]	杨小东，康雁，柳青，孙金文. 求解作业车间调度问题的禁忌分布估计算法[J]. 计算机工程与应用, 2017, 53(7): 147-153.
[6]	黄务兰1，2，张涛1，3. 基于改进全局人工鱼群算法的VRPSPDTW研究[J]. 计算机工程与应用, 2016, 52(21): 21-29.
[7]	林若男，李强. 云计算环境下基于模板的任务调度策略与算法[J]. 计算机工程与应用, 2016, 52(19): 48-52.
[8]	戎容，吴萍. 基于遗传算法的股票市场选择模型[J]. 计算机工程与应用, 2016, 52(18): 167-172.
[9]	李迎1，张璟1，2，虎群1，李军怀1，2. 人工鱼群算法在虚拟机分配中的应用[J]. 计算机工程与应用, 2015, 51(4): 22-28.
[10]	李果1，洪旭东2，许建1，黄翰2. 求解护士分配问题的矩阵编码进化算法[J]. 计算机工程与应用, 2015, 51(4): 244-248.
[11]	林耿. 最小赋权支配集的迭代禁忌搜索算法[J]. 计算机工程与应用, 2015, 51(23): 78-81.
[12]	蒋国清1，潘勇2，胡飞跃1. 两阶段式的物流配送路径优化方法[J]. 计算机工程与应用, 2015, 51(2): 255-258.
[13]	陈志泊，张蕾蕾，李巨虎，孙国栋. 基于入侵杂草优化算法的无线传感网节点定位[J]. 计算机工程与应用, 2014, 50(9): 77-82.
[14]	吴家皋1，张曦1，庄嵩杰1，邹志强1，胡斌2. 面向多图层的空间矢量数据缓存更新策略研究[J]. 计算机工程与应用, 2014, 50(7): 89-93.
[15]	于蕾1，周忠良1，郑丽颖2. 基于入侵性杂草优化算法的图像识别的研究[J]. 计算机工程与应用, 2014, 50(16): 188-191.