A Comparison of Algorithms for Solving Multicomponent Optimization Problems

Autor:	Daniel K. S. Vieira, Marcus Henrique Soares Mendes
Rok vydání:	2017
Předmět:	Mathematical optimization Optimization problem General Computer Science Computer science Knapsack problem Genetic algorithm Benchmark (computing) Electrical and Electronic Engineering Travelling thief problem Travelling salesman problem Algorithm
Zdroj:	IEEE Latin America Transactions. 15:1474-1479
ISSN:	1548-0992
DOI:	10.1109/tla.2017.7994795
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::27678a654965481ec9a57fab8b1037ed https://doi.org/10.1109/tla.2017.7994795 Zobrazit plný text záznamu