A Hybrid Genetic Algorithm with Tabu Search for Optimization of the Traveling Thief Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2018, Vol 9, Issue 11
Abstract
Until now, several approaches such as evolutionary computing and heuristic methods have been presented to optimize the traveling thief problem (TTP). However, most of these approaches consider the TTP components independently, usually considering the traveling salesman problem (TSP) and then tackling the knapsack problem (KP), despite their interdependent nature. In this paper, we investigate the use of a hybrid genetic algorithm (GA) and tabu search (TS) for the TTP. Therefore, a novel hybrid genetic approach called GATS is proposed and compared with the state-of-the-art approaches. The key aspect of GATS is that TTP solutions are considered by firmly taking into account the interdependent nature of the TTP subcomponents, where all its operators are simultaneously implemented on TSP and KP solutions. A comprehensive set of TTP benchmark datasets was adopted to investigate the effectiveness of GATS. We selected 540 instances for our investigation, which comprised five different groups of cities (51, 52, 76, 100 and 150 cities) and different groupings of items, from 50 to 745 items. All types of knapsack (uncorrelated, uncorrelated with similar weights and bonded strongly correlated) with all different knapsack capacities were also taken into consideration. Different initialization methods were empirically investigated as well. The results of the computational experiments demonstrated that GATS is capable of surpassing the state-of-the-art results for various instances.
Authors and Affiliations
Saad T Alharbi
Keywords
Related Articles
- EP ID EP417655
- DOI 10.14569/IJACSA.2018.091138
- Views 71
- Downloads 0
Successful Transmission Rate of Mobile Terminals with Agents in Segmented Ad Hoc Network
Mobile Wireless Ad-Hoc Network (MANET) is a special kind of network, where all of the nodes move in time. Random movement is the commonly used to model the mobility in this network. Beside as a host, each node is intend...
An M-Learning Framework in the Podcast Form (MPF) using Context-Aware Technology
Mobile computing is rapidly transforming the world in which we live, with the advent of iPhones, iPads, tablet computers, and Android smartphones. M-learning in the podcast form (MPF) is a recent development forconveying...
A Bottom-up Approach for Visual Object Recognition on FPGA based Embedded Multiprocessor Architecture
This paper presents an object recognition approach of outdoor autonomous systems identifying the nature of the interested object when observing an image. Therefore, seeking for effective and robust recognition method, th...
Smart Smoking Area based on Fuzzy Decision Tree Algorithm
Cigarette smoke is very dangerous for both active and passive smokers who smoke inside a room because nicotine from cigarette smoke can stick on the wall or in the furniture and produce carcinogenic substances when react...
Impact of Anaphora Resolution on Opinion Target Identification
Opinion mining is an interesting area of research because of its wide applications in the decision-making process. Opinion mining aims to extract user’s perception from the text and to create a fast and accurate summary...