A Genetic Algorithm for Multi-component Optimization Problems: The Case of the Travelling Thief Problem
| Autor: | Marcus Henrique Soares Mendes, Gustavo Luís Soares, Daniel K. S. Vieira, João A. Vasconcelos |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
Optimization problem Heuristic (computer science) Computer science Crossover 0102 computer and information sciences 02 engineering and technology 01 natural sciences Travelling salesman problem 010201 computation theory & mathematics Knapsack problem Genetic algorithm 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing Algorithm Selection (genetic algorithm) |
| Zdroj: | Evolutionary Computation in Combinatorial Optimization ISBN: 9783319554525 EvoCOP |
| DOI: | 10.1007/978-3-319-55453-2_2 |
| Popis: | Real-world problems are often composed of multiple interdependent components. In this case, benchmark problems that do not represent that interdependence are not a good choice to assess algorithm performance. In recent 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 (KP) and the Travelling Salesman Problem (TSP). This paper presents a genetic algorithm-based optimization approach called Multi-Component Genetic Algorithm (MCGA) for solving TTP. It aims to solve the overall problem instead of each sub-component separately. Starting from a solution for the TSP component, obtained by the Chained Lin-Kernighan heuristic, the MCGA applies the evolutionary process (evaluation, selection, crossover, and mutation) iteratively using different basic operators for KP and TSP components. The MCGA was tested on some representative instances of TTP available in the literature. The comparisons show that MCGA obtains competitive solutions in 20 of the 24 TTP instances with 195 and 783 cities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|