基于二重结构编码遗传算法求解背包问题的研究  

Study of Solving Knapsack Problem Based on Binary Codes Genetic Algorithm

作　　者：刘正龙[1] 杨艳梅[2] 罗玉军[1] 

机构地区：[1]川北医学院计算机与数学教研室,四川南充637000 [2]西华师范大学数学与信息学院,四川南充637007

出　　处：《计算机技术与发展》2013年第7期112-115,共4页Computer Technology and Development

基　　金：四川省教育自然科学基金(12ZB040);四川省教育发展研究中心基金(CJF10019)

摘　　要：针对背包问题传统的解决方法有动态规划法、分支界限法、回溯法。传统的方法不能有效地解决背包问题。文中提出二重结构编码的遗传算法解决背包问题,是一种适合于在大量的可行解中搜索最优解的有效算法,在约束条件的处理上结合贪婪算法,既加快了算法的收敛速度,又克服了传统方法容易陷入局部最优的特点,提高了搜索效率。通过计算机仿真试验结果表明,二重结构编码的遗传算法比基本遗传编码有更好的近似解,充分证明了使用二重结构编码的混合遗传算法来求解背包问题的有效性和实用性。For knapsack problem solutions the traditional methods are the branch and bound method, dynamic programming and backtracking. Traditional methods cannot effectively solve knapsack problem. Propose dual-structure coding genetic algorithm to solve knapsack problem,is an effective algorithm is suitable for a large number of viable solutions for finding optimal solutions, combining with the greedy algorithm on the processing of constraints, not only accelerates the speed of convergence of the algorithm, but also overcomes the traditional methods vulnerable to local optimization features to improve search efficiency. Through the computer simulation results show that dual-structure coding genetic algorithm for approximate solution is better than basic genetic coding, demonstrate using hybrid genetic algorithm for dual-structure codes to solving knapsack problem is effective and practical.

关 键 词：遗传算法 背包问题 计算机仿真 二重结构编码 二重结构解码 

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