基于混合蛙跳算法的背包问题求解  

A Shuffled Frog Leaping Algorithm for Solving Knapsack Problem

作　　者：轩宗怡[1] 张翠军[1] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031

出　　处：《科学技术与工程》2009年第15期4363-4365,共3页Science Technology and Engineering

基　　金：国家自然科学基金(60673015);河北省科学技术研究与发展项目(07213507D);石家庄经济学院重点项目(Y200606)资助

摘　　要：混合蛙跳算法(SFLA)是一种全新的后启发式群体进化算法,具有高效的计算性能和优良的全局搜索能力。背包问题是一个典型的NP完全问题。首先建立了背包问题基于0/1规划的数学模型,阐述了混合蛙跳算法的基本理论。针对离散搜索空间,提出了SFLA的改进算法,应用该算法解决了背包问题。在实例上的运行结果表明本文方法的可行性和有效性。Shuffled Frog Leaping Algorithm （SFLA） is a new meta-heuristic population evolutionary algorithm. It has fast calculation speed and excellent global search capability. Knapsack problem is a typical NP-eomplete problem. The 0-1 Knapsack problem mathematical model is established first, then the basic principle of SFLA is introduced. Aim at searching in discrete search space, an improved SFLA algorithm is given. And then, it is used to solve Knapsack problem. The results got on some typical instances show that the proposed method is feasible and effective.

关 键 词：进化算法 混合蛙跳算法 背包问题 

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