求解背包问题的混合粒子群优化算法  

Hybrid particle swarm optimization algorithm for solving knapsack problem

作　　者：王晓华[1,2] 沐爱勤[2] 刘金波[2] 

机构地区：[1]中国矿业大学计算机学院,江苏徐州221008 [2]徐州空军学院基础部,江苏徐州221000

出　　处：《计算机工程与应用》2012年第1期44-46,56,共4页Computer Engineering and Applications

摘　　要：提出一种新的遗传思想:父代的基因决定子代继承某一基因的概率,而不是由单纯的交叉产生子代。根据此思想,提出两种利用遗传概率产生子代的方法,并将它们分别与粒子群优化算法相结合得到两种求解背包问题的混合粒子群优化算法。通过数值实验说明了同样的算法采用遗传策略要比交叉策略寻优性更强,分析了变异概率对算法的影响。A new genetic idea that offspring’s gene is decided by its parent’s, rather than produced by a simple cross is proposed. According to this idea, two methods of producing offspring with genetic probability are produced and they are combined with the particle swarm optimization respectively. The two hybrid particle swarm optimizations are applied to solving knapsack problem, and their performances are compared by normal numerical experiments. The validity of two hybrid algorithms is verified and the impacts of mutation probability on the algorithms are analyzed.

关 键 词：粒子群优化算法 背包问题 遗传概率 

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