袁德辉，杨圣云，傅胤荣，赖国明

（韩山师范学院数学与信息技术系，广东潮州 521041）

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

袁德辉，杨圣云，傅胤荣，赖国明

（韩山师范学院数学与信息技术系，广东潮州 521041）

提出了一种组合排序方案，并将这种排序方案应用于遗传算法．利用该排序下的遗传算法针对OR数据库中的多维度背包问题进行了求解，同时和其它类似算法进行了实验比较.

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

1 引论

众所周知，许多实际问题都可以归结为多维度背包问题（MKP），如资本预算问题[1]、分布式计算机系统中的处理器和数据库指派问题[2]、集装箱装载问题[3]、下料问题[4]等．因此关于求解多维度背包问题的研究经久不衰，特别是随着计算机技术的发展，这方面的研究变得更加活跃．所有背包问题在理论上属于NP-Hard问题，也就是说，有很大的可能性设计不出多项式时间解法[5]．目前背包问题解法大致上分为精确算法和近似算法两类．遗传算法及其改进方法[6-7]、蚂蚁优化算法[8]、属性论方法[9]等均属于近似算法范畴．多维度背包问题（MKP）的一般定义如下：

其中n表示变量的个数；m表示约束条件个数；pj表示第j个变量的受益量；bi表示第i个约束的预算；rij表示第j个变量占用第i个约束的量；xj表示0-1决策变量（当变量j被选择时xj=1，否则xj=0）．从以上模型可以看出，所有0-1整数线性规划问题都可以看成是一个背包问题，因此求解多维度背包问题就是……