摘要
给出了背包问题的数学模型,分析了解决该问题的二重结构编码的混合遗传算法,在此基础上通过引入价值密度的概念并与局部搜索算法相结合对算法进行了改进,并通过大量的数值试验充分证明了改进后的二重结构编码算法的有效性有了一定的提高。
The knapsack problem is a typical NP complete problem. Its correspondent mathematical model is proposed. The genetic algorithm with the dual-structure codes is analyzed. The concept of the value density and the partial searching algorithm are combined to improve the algorithm. The experiment result shows that the improved one is more efficient.
出处
《成都信息工程学院学报》
2007年第3期301-305,共5页
Journal of Chengdu University of Information Technology
关键词
遗传算法
价值密度
背包问题
二重结构编码
genetic algorithm
value density
knapsack problem
dual-structure encode