用遗传算法实现罚函数法解多选择背包问题  

Solution to multiple-choice knapsack problem using penalty function method implemented by genetic algorithm

作　　者：鲍江宏[1] 

机构地区：[1]华南理工大学数学科学学院,广东广州510641

出　　处：《计算机工程与设计》2008年第17期4518-4520,4524,共4页Computer Engineering and Design

摘　　要：多选择背包问题最为复杂,传统的整数规划算法难以适用。另僻蹊径,采用数学上的罚函数法来求解。对罚函数法进行改进,使得能对多选择背包问题的数学模型进行求解。重点研究了如何把3种约束条件转化成目标函数的惩罚项。再从遗传算法的角度,来研究如何实现这种新的罚函数法。最终使用VisualC++6编程实现,并与前人的算法进行比较,取得了较好的效果。Among its variations, multiple-choice knapsack problem （MCKP） is the most complicated, so that the traditional methods to solve integer programming are not competent for it. The mathematic penalty function method is originally used instead of the traditional ones. First, the method is improved so as to be suitable for the mathematic model of MCKP. It is focused on how to translate three kinds of constraints into penalty parameters of objective function. Then it is studied how to implement the new penalty function method using genetic algorithm （GA）. Finally, the algorithm is programmed in Visual C＋＋ 6. Comparing with the former ones, a better result is obtained.

关 键 词：多选择背包问题 遗传算法 罚函数法 基因表示 精英策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]