求解背包问题的病毒协同进化粒子群算法  

Virus-evolutionary particle swarm optimization algorithm for knapsack problem

作　　者：高芳[1] 崔刚[1] 吴智博[1] 刘宏伟[1] 杨孝宗[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《哈尔滨工业大学学报》2009年第6期103-107,共5页Journal of Harbin Institute of Technology

基　　金：中国高技术研究发展计划重大资助项目(2006AA01A103)

摘　　要：为提高粒子群算法的搜索性能,提出一种基于病毒进化理论的改进离散粒子群算法:病毒协同进化粒子群算法.在粒子群中引入生物病毒机制和宿主与病毒基于感染操作的思想,病毒采用与粒子等长的编码方式,执行反向代换、结合等操作,利用病毒的水平感染和垂直传播能力较好地维持个体的多样性和对解空间的局部搜索能力.通过解决背包问题对算法进行验证,仿真表明所提算法搜索性能优于遗传算法、模拟退火及标准粒子群等其他算法.该算法能有效求解背包问题等NP难题.To improve the search capability of particle swarm algorithm, an improved discrete particle swarm optimization algorithm based on virus evolution theory is proposed and named as virus-evolutionary discrete particle swarm optimization （VEPSO） algorithm. Biological virus mechanism and the infection-based operation between host and virus are introduced in the particle swarm. Virus individual is coded with the same length as particle, and it executes infection and incorporation operations. The horizontal infection and vertical propagation of virus are fully used to maintain the individual diversity and local search capability in solution space. This algorithm is verified by solving knapsack problem. Simulation results show that the search capability of VEPSO algorithm is better than that of genetic algorithm, simulated annealing and standard PSO algorithm. This algorithm is able to effectively solve knapsack and other NP-hard problems.

关 键 词：粒子群算法 病毒 背包问题 病毒感染 

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