求解0—1背包问题人工蜂群算法

《求解0—1背包问题人工蜂群算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、求解0-1背包问题人工蜂群算法摘要：提出了一种用于求解0-1背包问题的人工蜂群算法，详细阐述了该算法求解背包问题的具体操作过程。算法主要使用了两个思想策略：启发式贪婪算法和人工蜂群算法。通过对其它文献中仿真实例的计算和结果对比，表明该算法对求解0-1背包问题的有效性，这对人工蜂群算法解决其它离散问题会有很大帮助。Abstract:ArtificialBeeColonyAlgorithmwasproposedtosolvethe0-1knapsackproblem,andthespecificoperationprocesswaselaborated.Thealgor

2、ithmmainlyusestwoideologicalstrategy:heuristicgreedyalgorithmandartificialbeecolonyalgorithm・Throughthecalculationandresultcomparisonofsimulationinstanceinotherliterature,itshowsthealgorithmhasvalidityorsolving0-1knapsackproblem,whichwillbeagreathelptosolveotherdiscreteissuesbyArtifici

3、alBeeColonyAlgorithm・关键词：人工蜂群算法；背包问题；群体智能Keywords:ArtificialBeeColonyAlgorithm；knapsackproblem；swarmintelligence中图分类号:TP39文献标识码：A文章编号:1006-4311(2013)01-0176-020引言0-1背包问题是一个典型的组合优化难题，有着广泛的实际应用背景，许多优化问题都可以通过一系列背包问题子问题来解决。随着问题规模的增长，求解背包问题的时间复杂性增长非常快，从计算复杂性理论来看，背包问题是个NP完全问题，在最坏的情况下的时间复杂性为0

4、(2n)o贪婪算法、遗传算法［1］、蚂蚁算法［2,3］等，是该问题的求解方法所采用的主要启发式算法，因此设计新的高效算法来求解背包问题具有重要的实际意义。人工蜂群算法［4］是一种基于群体智能的随机优化算法,它是Karaboga于2005年提出的。蜜蜂根据各自的分工进行不同的活动，人工蜂群算法比遗传算法、粒子群算法具有更好的优化性能。实现蜂群信息的共享和交流，从而找到问题的最优解。由于人工蜂群算法目前未能有效解决离散及组合优化问题，所以只能用于求解连续空间的优化问题，这已成为限制其发展的瓶颈问题。针对0-1背包问题的特点,对人工蜂群算法的运算规则进行重新定义，利用启发

5、式信息，使算法既具有人工蜂群算法的整体优化特性，同时在算法中加入贪婪算法这个很有效的局部搜索方法，又加快了算法的收敛速度。通过对0-1背包问题测试算例的仿真实验和与其它算法的比较，表明了本文算法在迭代相同次数的情况下更容易找到最优解，体现了算法的可行性和髙效性。为我们将人工蜂群算法应用到离散问题，特别是组合优化问题具有一定的启发性，也为进一步深入研究奠定了基础。10-1背包问题的描述0-1背包问题的一般提法为：已知n个重量和价值分别为wj>0和cj>0(j=l,2-n)的物品，背包的容量假设为00,如何选择哪些物品装入背包可使在背包的容量限制之内所装物品的价值最大。

6、引入变量xj,当物品j被选择装入时，xj=l,否则，xj=0o则该问题的数学模型为：