多背包问题的遗传算法求解  

Genetic Algorithm for Multi Knapsack Problem

作　　者：虞安波[1] 杨家本[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《计算技术与自动化》2002年第2期59-63,共5页Computing Technology and Automation

摘　　要：本文提出了一种新的组合优化问题—多背包问题,并给出了它的基于0/1规划的数学模型;提出了解决多背包问题的遗传算法。该算法以目标函数加约束惩罚函数作为适应值函数,交叉算子选用了一致交叉的方法,仿真的结果表明该遗传算法在求解多背包问题上的表现是良好的。In this paper,a new kind of combinational optimization problem - multi - knapsack problem and its correspondent mathematical model is proposed. A genetic algorithms is applied to solute such a complex problem. In this algorithms , the fitness function is the sum of the object function and the all constraint punishment functions. And Uniform Crossover is used as the crossover operator. The simulation result indicate that the performance of GA on multi - knapsack problem is sound and robust.

关 键 词：多背包问题 遗传算法 组合优化问题 数学模型 

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