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

• 工程与应用 • 上一篇    下一篇

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

宋晓萍1,胡常安2   

  1. 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. 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

摘要: 为解决粒子群优化算法在求解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