文章基本信息

标题：An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem
本地全文：下载
作者：Gupta, Sunanda ; Garg, M. L.
期刊名称：Journal of Computer Science
印刷版ISSN：1549-3636
出版年度：2009
卷号：5
期号：8
页码：544-547
DOI：10.3844/jcssp.2009.544.547
出版社：Science Publications
摘要：Problem statement: Knapsack problem is a typical NP complete problem. During last few decades, Knapsack problem has been studied through different approaches, according to the theoretical development of combinatorial optimization. Approach: In this study, modified evolutionary algorithm was presented for 0/1 knapsack problem. Results: A new objective_func_evaluation operator was proposed which employed adaptive repair function named as repair and elitism operator to achieve optimal results in place of problem specific knowledge or domain specific operator like penalty operator (which are still being used). Additional features had also been incorporated which allowed the algorithm to perform more consistently on a larger set of problem instances. Conclusion/Recommendations: This study also focused on the change in behavior of outputs generated on varying the crossover and mutation rates. New algorithm exhibited a significant reduction in number of function evaluations required for problems investigated.
关键词：Knapsack problem; genetic algorithm; adaptive repair operator