求解0/1背包问题的改进人工鱼群算法研究

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (21): 43-46.

求解0/1背包问题的改进人工鱼群算法研究

厍向阳，朱命昊，赵亚敏

西安科技大学计算机科学与技术学院，西安 710054

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

Improved artificial fish school algorithm to solve knapsack problem

SHE Xiangyang，ZHU Minghao，ZHAO Yamin

Computer Science and Technology College，Xi’an University of Science and Technology，Xi’an 710054，China

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

摘要/Abstract

摘要： 分析了人工鱼群算法求解组合优化问题的不足，提出一种改进人工鱼群算法。该算法针对背包问题的特点，采用随机键方法对待装载物品进行编码，利用物品的单位价值（价值-质量比）启发式信息进行解码，直接在编码空间上模拟人工鱼行为。使用优质解随机游走寻优、优质解保留劣质解被替换和劣质解随机游走寻优三个更新算子来改善人工鱼群的全局搜索能力。通过实例进行了算法测试和比较。算法测试表明：改进后的人工鱼群算法提高了收敛速度，增强了全局搜索能力。

关键词: 人工鱼群算法, 背包问题, 组合优化, 启发式信息

Abstract: After analyzing the disadvantages of artificial fish school algorithm solving combinational optimization problems，an improved artificial fish school algorithm is put forward.Facing the characteristic of KP，this algorithm directly simulates artificial fishs behaviors in the coding space，encoding by the rand key and decoding by the heuristic information，such as the value of unit quality goods（value-quality ratio）.The globe searching capability of artificial fish school algorithm is improved by three updating operators，which include good solutions swimming in the coding space at random to search better solutions than themselves，preserving good solutions and substituting good solutions for bad solutions，bad solutions swimming in the coding space at random to search better solutions than themselves.Comparison and analysis are carried out with examples.Algorithm tests show that this algorithm can improve the speed of convergence efficiently and is good at global searching in solution space.

Key words: Artificial Fish School Algorithm（AFSA）, Knapsack Problem（KP）, combinational optimization, heuristic information

厍向阳，朱命昊，赵亚敏. 求解0/1背包问题的改进人工鱼群算法研究[J]. 计算机工程与应用, 2011, 47(21): 43-46.

SHE Xiangyang，ZHU Minghao，ZHAO Yamin. Improved artificial fish school algorithm to solve knapsack problem[J]. Computer Engineering and Applications, 2011, 47(21): 43-46.

[1]	高一锴，彭力，徐龙壮. 改进AFSA算法优化TWSVM的火焰识别方法[J]. 计算机工程与应用, 2021, 57(8): 204-213.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[4]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[5]	吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
[6]	杨宇，曾国辉，黄勃. 基于双树复小波包和改进SVM的轴承故障诊断[J]. 计算机工程与应用, 2020, 56(17): 231-235.
[7]	邹德龙，王宝华. 一种混合优化算法面向高维函数优化的研究[J]. 计算机工程与应用, 2019, 55(20): 122-127.
[8]	陈长倩，慕晓冬，牛犇，王立志. 结合高斯分布的改进二进制灰狼优化算法[J]. 计算机工程与应用, 2019, 55(13): 145-150.
[9]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[10]	孙晶，李硕，赵会群. 基本路径测试用例自动生成的方法研究[J]. 计算机工程与应用, 2018, 54(20): 48-53.
[11]	张健，郭星，李炜. 改进果蝇优化算法在多目标搜索的应用[J]. 计算机工程与应用, 2018, 54(2): 131-136.
[12]	刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.
[13]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
[14]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[15]	姚凌波，戴月明，王艳. 反向自适应高斯变异的人工鱼群算法[J]. 计算机工程与应用, 2018, 54(1): 179-185.