Improvement of genetic algorithms with decomposition procedures for large-scale multiobjective multidimensional 0-1 knapsack problems incorporating fuzzy goals

For a 0-1 knapsack problem, if it is small in size, a strict optimal soluti on can be obtained by the branch-and-bound method or dynamic programming. A s the size of the problem grows larger, however, it rapidly becomes harder to find a strict optimal solution to it based on these methods because of t he exponential increase of computational load. As a result, various approxi mate algorithms have been proposed to obtain approximate optimal solutions. For a large-scale 0-1 knapsack problem, the authors have proposed a geneti c algorithm using triple string representation and decomposition procedures to make use of the special structure of the problem. However, in this gene tic algorithm, in decoding procedures in which an individual S in the indiv idual space is mapped to a solution x in the solution space, since only con straints are considered, improvements of search efficiency are being sought by taking consideration of objective functions. Therefore, in this paper w e propose a new genetic algorithm with decomposition procedures using indiv idual representation on the basis of an optimal solution to the correspondi ng continuous relaxation problem. (C) 2000 Scripta Technica.