Busca avançada
Ano de início
Entree


A Comparison of Linkage-learning-based Genetic Algorithms in Multidimensional knapsack Problems

Texto completo
Autor(es):
Martins, Jean P. ; Bringel Neto, Constancio ; Crocomo, Marcio K. ; Vittori, Karla ; Delbem, Alexandre C. B. ; IEEE
Número total de Autores: 6
Tipo de documento: Artigo Científico
Fonte: 2013 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2013-01-01.
Resumo

Linkage Learning (LL) was proposed as a methodology to enable Genetic Algorithms (GAs) to solve complex optimization problems more effectively. Its main idea relies on a reductionist assumption, considering optimization problems as being composed of substructures that could be exploited to improve the GA's search mechanism. In general, LL-GAs have been compared in a restricted set of well-known optimization problems, in which the reductionist assumption holds true, and only a few studies have concerned their performances in broader scenarios. To help to fill this gap, we have compared four different LL-GAs in the classic Multidimensional Knapsack Problem (MKP) using all the instances provided by Chu & Beasley (1998). Our objective was to verify if the relative performance of algorithms as: the Extended Compact Genetic Algorithm (eCGA), the Bayesian Optimization Algorithm (BOA) with decision graphs, the BOA with community detection, the Linkage Tree Genetic Algorithm (LTGA) and a simple GA; would remain the same in the MKP's instances, where the existence of substructures is unknown. However, the results have shown the opposite, and algorithms as BOA have only found similar solutions to those found by the eCGA and LTGA when using large population sizes. (AU)

Processo FAPESP: 11/07792-4 - Análise da Aprendizagem de Ligação e Desenvolvimento de Algoritmos Genéticos Multiobjetivo baseado em Modelos
Beneficiário:Jean Paulo Martins
Modalidade de apoio: Bolsas no Brasil - Doutorado