一种求解0-1背包问题的二进制修正和声搜索算法  

A binary modified harmony search algorithm for 0-1 knapsack problem

作　　者：欧阳海滨[1] 高立群[1] 孔祥勇[1] 刘宏志[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004

出　　处：《控制与决策》2014年第7期1174-1180,共7页Control and Decision

基　　金：国家自然科学基金项目(60674021)

摘　　要：针对0-1背包问题,提出一种二进制修正和声搜索算法.该算法修正了即兴创作过程,对参数PAR进行动态调整,同时提出一种随机修复机制,有效修复不可行的和声,增强算法的局部搜索.采用一种可行和声初始化方式,保证初始和声都是可行的,整个搜索过程完全采用0-1二进制模式,对14个0-1背包问题进行测试.将所提出算法与其他算法进行比较,结果验证了所提出算法的有效性.A binary modified harmony search algorithm is proposed to solve the 0-1 knapsack problem（KP）. In the algorithm, the improvisation process is modified and the parameter PAR is adjusted dynamically, as well as a stochastic repair operator is developed to effectively repair infeasible harmony and enhance local search. Besides, a feasible harmony initialization method is used to guarantee initial harmony feasible. The 0-1 binary model is completely used in the whole search process. Fourteen 0-1 knapsack problems are tested. The proposed algorithm is compared with other algorithms, and the statistical results demonstrate the effectiveness of the proposed algorithm.

关 键 词：0-1背包问题 二进制修正和声搜索算法 局部搜索 随机修复机制 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]