求解多维度背包问题的一种组合排序遗传算法  

A Genetic Algorithm Base on a New Order for Multidimensional Knapsack Problem

作　　者：袁德辉[1] 杨圣云[1] 傅胤荣[1] 赖国明[1] 

机构地区：[1]韩山师范学院数学与信息技术系,广东潮州521041

出　　处：《韩山师范学院学报》2011年第6期22-28,共7页Journal of Hanshan Normal University

基　　金：国家自然科学基金(30800244)资助项目;广东省自然科学基金(10152104101000004)资助项目;韩山师院团队科研(LT200801)资助项目

摘　　要：提出了一种组合排序方案,并将这种排序方案应用于遗传算法.利用该排序下的遗传算法针对OR数据库中的多维度背包问题进行了求解,同时和其它类似算法进行了实验比较.The paper presents a new order for the muhidimensional knapsack problem. Using this new order, we design an improved genetic algorithm. Computational results show that the new genetic algorithm is capable of obtaining high-quality solutions for MKP. Computational results also show that this algorithm gives superior quality solutions than Chu＇s.

关 键 词：多维度背包问题 组合排序 遗传算法 适应度函数 伪利用率 

分 类 号：O224[理学—运筹学与控制论]