求解多维0-1背包问题的一种改进的遗传算法  

An Improved Genetic Algorithm for the Multidimensional 0-1 Knapsack Problem

作　　者：曾智[1] 杨小帆[1] 陈静[1] 陈文斌[1] 唐荣旺[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机科学》2006年第7期220-223,共4页Computer Science

基　　金：重庆市自然科学基金资助课题(编号:CSTC;2005BB2191)

摘　　要：针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子———中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他最新的遗传算法进行比较,经过对求得近似解的精度及计算所需时间两方面的对比,验证了其有效性。This paper proposes a new crossover operator which is called median crossover. It is designed by using the ideas of the greedy algorithm and the 2- division search algorithm, and aims at the multidimensional 0-1 knapsack problem. Based on this median crossover operator, the paper also presents an improved genetic algorithm for solving the multidimensional 0-1 knapsack problem. Furthermore, the efficiency of the presented method is investigated by comparing it with the traditional simple genetic algorithm and other latest methods, in respect of the accuracy of an approximate solution and the processing time through series of numerical experiments.

关 键 词：多维0-1背包问题 遗传算法 中值杂交算子 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]