基于贪婪策略整体分布优化算法的0-1背包问题求解  

Based on greedy strategy overall distribution optimization algorithm solving 0-1 knapsack problem

作　　者：薛翠平[1] 刘静宜[1] 肖冬[2] 

机构地区：[1]东北大学理学院,辽宁沈阳110004 [2]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北师大学报（自然科学版）》2015年第2期53-57,共5页Journal of Northeast Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61203214)

摘　　要：提出了一种思想简单且可用于0-1背包问题求解的基于贪婪策略整体分布优化算法.该算法首先随机产生一个初始种群,经贪婪策略将种群变成价值相对较高的可行解,保留本次最优解;然后以最优解为中心,用柯西分布产生新的种群,经贪婪策略将新种群变成相对价值较高的可行解,再保留本次最优解,重复以上过程,达到最大迭代次数,求出问题的全局最优解;最后,对不同规模的问题进行了实验.结果表明:该算法在求解0-1背包问题上是有效的,比遗传算法、贪婪算法具有更强的寻优能力.Overall distribution optimization algorithm based on greedy strategy with simple idea, which can be used to solve large-scale 0-1 knapsack problem is presented in the paper. Firstly, an initial population is brought out randomly in the method, and according to greedy strategy, it is developed into higher valuable feasible solution and the optimum solution is reserved. Then, a new population is produced around optimum solution according to Cauchy distribution, and again it＇s developed into higher valuable feasible solution after greedy strategy and it＇s reserved. Repeat the whole solution procedure above, reach the most iteration, and seek out the globally optimal solution to the problem. Lastly, different scale problems are tested. The result shows that the method is efficient in solving 0- 1 knapsack problem, and compared to genetic algorithm and greedy strategy, it＇s more powerful to seeking for optimum.

关 键 词：0-1背包问题 整体分布优化算法 贪婪策略 价值密度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]