Uma Comparação de Algoritmos para Resolver Problemas de Otimização Multicomponente (A Comparison of Algorithms for Solving Multicomponent Optimization Problems)

Daniel Kneipp de Sá Vieira (danielv@dcc.ufmg.br)1, Marcus Henrique Soares Mendes (marcus.mendes@ufv.br)2


1Universidade Federal de Minas Gerais
2Universidade Federal de Viçosa

This paper appears in: Revista IEEE América Latina

Publication Date: Aug. 2017
Volume: 15,   Issue: 8 
ISSN: 1548-0992


Abstract:
Real-world problems are often composed of multiple interdependent components. In this case, benchmark problems that do not represent that interdependency are not a good choice to assess algorithm performance. In recently literature, a benchmark problem called Travelling Thief Problem (TTP) was proposed to better represent real-world multi-component problems. TTP is a combination of two well-known problems: 0-1 Knapsack Problem and the Travelling Salesman Problem. This paper presents a genetic algorithm-based optimization approach for solving TTP. It aims to solve the overall problem instead of each sub-component separately. The proposed algorithm was tested on 60 representative instances of TTP available in the literature. The comparisons show that the genetic algorithm obtains competitive solutions for small TTP instances.

Index Terms:
Travelling Thief Problem, Genetic Algorithm, Optimization, Combinatorial Problem.   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (312)]