| 求解广义背包问题的贪心DS_BPSO算法 |
| |
| 引用本文： | 贺毅朝,刘建芹,曲文龙,王彦祺.求解广义背包问题的贪心DS_BPSO算法[J].计算机应用与软件,2008,25(4):230-233. |
| |
| 作者姓名： | 贺毅朝 刘建芹 曲文龙 王彦祺 |
| |
| 作者单位： | 1. 石家庄经济学院信息工程系,河北,石家庄,050031
2. 石家庄信息工程职业学院,河北,石家庄,050035 |
| |
| 摘 要： | 首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.
|
| 关 键 词： | 广义背包问题 DS_BPSO算法 贪心变换 GDS_BPSO算法 |
| 修稿时间： | 2006年5月23日 |
A GREEDY DS_BPSO ALGORITHM FOR GENERAL KNAPSACK PROBLEM |
| |
| He Yichao,Liu Jianqin,Qu Wenlong,Wang Yanqi.A GREEDY DS_BPSO ALGORITHM FOR GENERAL KNAPSACK PROBLEM[J].Computer Applications and Software,2008,25(4):230-233. |
| |
| Authors: | He Yichao Liu Jianqin Qu Wenlong Wang Yanqi |
| |
| Affiliation: | He Yichao1 Liu Jianqin2 Qu Wenlong1 Wang Yanqi11(Department of Information Project,Shijiazhuang University of Economics,Shijiazhuang 050031,Hebei,China)2(Shijiazhuang Information Engineering Vocational College,Shijiazhuang 050035,China) |
| |
| Abstract: | Firstly,the concept of greedy transformation is defined according to the evolution algorithm for knapsack problem,and an effective algorithm is proposed to implement greedy transformation.Then,through the combination of this algorithm and binary particle swarm optimization with double-structure coding given in 5],solve general knapsack problem(GKP),a rapid DS_BPSO algorithm based on greedy transformation(GDS_BPSO)is advanced to solve general knapsack problem(GKP).GDS_BPSO is applied to solve the knapsack s... |
| |
| Keywords: | General knapsack problem DS_BPSO algorithm Greedy transformation GDS_BPSO algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
