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



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.


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


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


Cited by

Year 2015 : 3 citations

 Jinwei Niu, Weimin Zhong,Yi Liang, Na Luo, Feng Qian, "Fruit fly optimization algorithm based on differential evolution and its application on gasification process operation optimization," volume 88, November 2015, pages 253–263, November 2015.

 Jayanthi Manicassamy, S. Sampath Kumar, Mohana Rangan, V. Ananth, T. Vengattaraman, P. Dhavachelvan, "Gene Suppressor: An added phase toward solving large scale optimization problems in genetic algorithm," Applied Soft Computing, volume 35, pages 214–226, October 2015.

 Shih-Huan Hsu and Tian-Li Yu, "Handling Overlap by Pairwise Linkage Detection, Incremental
Linkage Set, and Restricted / Back Mixing: DSMGA-II," TEIL Technical Report No. 2015002, February 2015.