摘要
针对典型的一类NP完全问题——背包问题,提出一种混合编码的差异演化求解方法。该方法基于差异演化算法框架,采用混合编码机制,每个决策变量均由一个实数和一个二进制数的组合表示。利用新定义的映射算子,构建混合编码的种群;增加边界约束处理算子,确保变异算子计算结果满足边界约束条件;利用新定义的丢弃算子对于不可行的装包策略进行修正。通过数值仿真实验,将该方法与遗传算法、二进制差异算法的计算结果比较分析,表明该算法求解背包问题的有效性与适用性。
This paper proposed mixed-coding-based differential evolution algorithm for 0-1 knapsack problem which was NP complete. This algorithm was based on the original differential evolution using mix-coding mechanism in which each decision variable was represented by the combination of one float number and a binary number. Firstly, proposed a new mapping operator to construct mixed-coding population, and then defined a new operator which dealt with the boundary constraint. Lastly used a discarding operator to adapt the infeasible solution. Simulation numerical results compared with that of genetic algorithm and binary differential evolution show that this algorithm is efficient and practical for 0-1 knapsack problem.
出处
《计算机应用研究》
CSCD
北大核心
2010年第6期2031-2033,共3页
Application Research of Computers
基金
国家自然科学基金资助项目(70771037)
江西省教育厅科技资助项目(GJJ09347)