求解0-1背包问题的改进离散和声搜索算法  

Discrete global harmony search algorithm for 0-1 knapsack problems

作　　者：欧阳海滨 夏红刚[2] 王清[1] 马鸽 OU YANG Hai-bin;XIA Hong-gang;WANG Qing;MA Ce(School of Mechanical and Electric Engineering,Guanghzou University,Guangzhou 510006,China;School of Information Engineering,Shenyang University,Shenyang 110044,China)

机构地区：[1]广州大学机械与电气工程学院,广东广州510006 [2]沈阳大学信息工程学院,辽宁沈阳110044

出　　处：《广州大学学报（自然科学版）》2018年第1期64-70,共7页Journal of Guangzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目(61273155;51478132)

摘　　要：提出一种求解0-1背包问题的改进离散和声搜索算法(IDHS).该算法应用分布估计算法的概率思想,设计自适应调整策略,提高算法的搜索能力.引入精英培养机制,加强精英和声的开发,提高算法逃离局部最优的概率.通过随机修复方法和置换策略来改善和声的可行性,增加解的多样性.对背包问题进行测试,结果验证了IDHS算法的有效性.An improved discrete harmony search algorithm is proposed to solve 0-1 knapsack problem(KP).An adaptive adjusting strategy is designed based on the probabilistic model of estiamtion of distribution algorithm,which aims to improve the algorithm capability.An elite training mechanism is introduced to enhance the exploitation of the elite harmony for escaping the local optimum.Random repair method and replacement strategy are used to improve the feasiblity of harmony and increase the diversity of solution.Several knapsack problems are tested to demonstrate the effectiveness of the proposed algorithm.

关 键 词：背包问题 概率模型 精英培养机制 随机修复 

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