Published in

Elsevier, Neurocomputing, (146), p. 17-29, 2014

DOI: 10.1016/j.neucom.2014.04.069

Links

Tools

Export citation

Search in Google Scholar

On the performance of Linkage-tree Genetic Algorithms for the multidimensional knapsack problem

Journal article published in 2014 by Jean P. Martins, Carlos M. Fonseca ORCID, Alexandre C. B. Delbem ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Model-based Genetic Algorithms (GAs), as the Linkage-tree GA (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 (MKP) 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 reasons linkage-learning did not provide useful information to solve MKP in the settings used for the experiments.