On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem

Authors

Abstract

Model-based Genetic Algorithms (GAs), as the Linkage Tree Genetic Algorithm (LTGA) and most Estimation of Distribution Algorithms (EDAs), assume a reductionist perspective when solving optimization problems. They use machine-learning techniques to discover problem?s substructures that might be useful to generate new solutions. This idea was grounded on Simon?s near-decomposability principle and Holland?s Building Block (BB)-hypothesis, and have enabled the development of effective algorithms in some contexts. Although near-decomposability is commonly seen in nature, we cannot assume the same occurs for optimization problems. Therefore, the existence of problems where these algorithms are not effective is also focus of research. Recent studies have argued that Multidimensional Knapsack Problems (MKPs) are examples of such cases. This paper extends these studies with an extensive comparison of various LTGA variants for the MKP. Using a well-known GA as reference, we analyzed the difficulties faced by the LTGA and explained why its linkage-tree model is not of much help to solve the problem. The results have shown that the LTGA was not able to outperform the GA and performed very similarly to a LTGA using random linkage-models. Further analysis of the linkage-trees, grounded on the knapsack-core concept, enabled interesting conclusions about the reason that linkage-learning did not provide useful information to solve MKPs in the settings used for the experiments.

Keywords

Linkage-tree GA, Multidimensional knapsack problem, Linkage-learning usefulness

Journal

Neurocomputing, Vol. 146, pp. 17-29, December 2014

DOI