A genetic algorithm for the unbounded knapsack problem

Author

Li, Ken-Li ; Dai, Guang-ming ; Li, Qing-hua

Author_Institution

Sch. of Comput., Huazhong Univ. of Sci. & Technol., Wuhan, China

Volume

3

fYear

2003

fDate

2-5 Nov. 2003

Firstpage

1586

Abstract

In this paper a new evolutionary algorithm is presented for the unbounded knapsack problem, which is a famous NP-complete combinatorial optimization problem. The proposed genetic algorithm is based on two techniques. One is a heuristic operator, which utilizes problem-specific knowledge, and the other is a preprocessing technique. Computational results show that the proposed algorithm is capable of obtaining high-quality solutions for problems of standard randomly generated knapsack instances, while requiring only a modest amount of computational effort.

Keywords

combinatorial mathematics; computational complexity; genetic algorithms; knapsack problems; NP-complete problem; combinatorial optimization problem; evolutionary algorithm; genetic algorithm; heuristic operator; preprocessing technique; problem-specific knowledge; unbounded knapsack problem; Biological cells; Biological systems; Dynamic programming; Evolutionary computation; Genetic algorithms; Genetic mutations; Heuristic algorithms; Large-scale systems; Processor scheduling; Routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Machine Learning and Cybernetics, 2003 International Conference on

Print_ISBN

0-7803-8131-9

Type

conf

DOI

10.1109/ICMLC.2003.1259749

Filename

1259749