计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (9): 54-56.

• 理论研究、研发设计 • 上一篇    下一篇

改进型遗传蚁群混合算法求解0/1背包问题

王  娜,向凤红,毛剑琳   

  1. 昆明理工大学 信息与自动化学院,昆明 650000
  • 出版日期:2013-05-01 发布日期:2016-03-28

Modified genetic ant colony hybrid algorithms for solving 0/1 knapsack problems

WANG Na, XIANG Fenghong, MAO Jianlin   

  1. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650000, China
  • Online:2013-05-01 Published:2016-03-28

摘要: 针对原有的遗传蚁群混合算法收敛速度慢、运行时间长等缺陷,提出了一种新混合算法,该算法从蚁群中选取部分优良个体采用遗传算法寻优,所选个体数目随迭代次数自适应变化,同时,对算法中的交叉、变异操作以及赋值等方面进行了一些改进。仿真结果表明,该算法在搜索能力、收敛速度以及程序运行时间方面都有明显的提高,由此证明了该算法的有效性。

关键词: 0/1背包问题, 遗传算法, 蚁群算法, 混合方式, 算法策略

Abstract: To overcome the problems of searching speed and running time of traditional genetic and ant colony hybrid algorithm, an improved algorithm is proposed. In this algorithm, the better part of ants, whose number is adaptively changed with iterative generation, is selected to optimization by the genetic algorithm, meanwhile, some improvements at crossover operation, mutation operation and evaluation of traditional algorithm are proposed. The simulation results show that this algorithm is improved at searching capability, convergence speed and program running time.

Key words: 0/1 knapsack problem, genetic algorithm, ant colony algorithm, hybrid mode, algorithm strategy