摘要：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 on uses a special repair operator to prevent the generation of infeasible solutions and to transform each feasible solution into a locally optimal solution. In longer runs it is likely that this algorithm produces candidate solutions that have already been generated and evaluated before. This effect can significantly reduce the algorithm's overall performance. To prevent the reconsideration of already evaluated solutions, a solution based on a Trie is studied. This paper presents the algorithms and data structures for compressing the Binary Trie and incorporates this in the GA implementation of the Multi Dimensional Knapsack Problem.
Loading...
