GA implementation of the multi dimensional knapsack problem using compressed binary tries

During the last two decades solving combinatorial optimization problems, using genetic algorithms(GA), has attracted the attention of many researchers. The genetic algorithm on which this work is based onuses a special repair operator to prevent the generation of infeasible solutions and to transform eachfeasible solution into a locally optimal solution. In longer runs it is likely that this algorithm producescandidate solutions that have already been generated and evaluated before. This effect can significantlyreduce the algorithm's overall performance. To prevent the reconsideration of already evaluated solutions, asolution based on a Trie is studied. This paper presents the algorithms and data structures for compressingthe Binary Trie and incorporates this in the GA implementation of the Multi Dimensional Knapsack Problem.