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

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

改进型遗传蚁群混合算法求解0/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

School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650000, China

Online:2013-05-01 Published:2016-03-28

摘要/Abstract

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

关键词: 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

王娜，向凤红，毛剑琳. 改进型遗传蚁群混合算法求解0/1背包问题[J]. 计算机工程与应用, 2013, 49(9): 54-56.

WANG Na, XIANG Fenghong, MAO Jianlin. Modified genetic ant colony hybrid algorithms for solving 0/1 knapsack problems[J]. Computer Engineering and Applications, 2013, 49(9): 54-56.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[4]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[5]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[6]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[7]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[8]	李壮阔，常凯旋. 合作博弈的连续蚁群算法求解[J]. 计算机工程与应用, 2021, 57(24): 198-204.
[9]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[10]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[11]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[12]	王晓光，杨培蓓. 航运物流企业数字化转型设计与效果分析[J]. 计算机工程与应用, 2021, 57(21): 241-247.
[13]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[14]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[15]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.