Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (21): 43-46.
• 研究、探讨 • Previous Articles Next Articles
SHE Xiangyang,ZHU Minghao,ZHAO Yamin
Received:
Revised:
Online:
Published:
厍向阳,朱命昊,赵亚敏
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
摘要: 分析了人工鱼群算法求解组合优化问题的不足,提出一种改进人工鱼群算法。该算法针对背包问题的特点,采用随机键方法对待装载物品进行编码,利用物品的单位价值(价值-质量比)启发式信息进行解码,直接在编码空间上模拟人工鱼行为。使用优质解随机游走寻优、优质解保留劣质解被替换和劣质解随机游走寻优三个更新算子来改善人工鱼群的全局搜索能力。通过实例进行了算法测试和比较。算法测试表明:改进后的人工鱼群算法提高了收敛速度,增强了全局搜索能力。
关键词: 人工鱼群算法, 背包问题, 组合优化, 启发式信息
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.
厍向阳,朱命昊,赵亚敏. 求解0/1背包问题的改进人工鱼群算法研究[J]. 计算机工程与应用, 2011, 47(21): 43-46.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/
http://cea.ceaj.org/EN/Y2011/V47/I21/43