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 59
- Downloads 0
Hybrid PSO-MOBA for Profit Maximization in Cloud Computing
Cloud service provider, infrastructure vendor and clients/Cloud user’s are main actors in any cloud enterprise like Amazon web service’s cloud or Google’s cloud. Now these enterprises take care in infrastructure deployme...
Embedded Object Detection with Radar Echo Data by Means of Wavelet Analysis of MRA: Multi-Resolution Analysis
A method for embedded object detection with radar echo data by means of wavelet analysis of MRA: Multi-Resolution Analysis, in particular, three dimensional wavelet transformations is proposed. In order to improve embedd...
Evaluation of Fault Tolerance in Cloud Computing using Colored Petri Nets
Nowadays, the necessity of rendering reliable services to the customers in business markets is assumed as a crucial matter for the service providers, and the importance of this subject in many fields is undeniable. Desig...
Integrating Service Design and Eye Tracking Insight for Designing Smart TV User Interfaces
This research proposes a process that integrate service design method and eye tracking insight for designing a Smart TV user interface. The Service Design method, which is utilized for leading the combination of the qual...
Blind Image Quality Evaluation of Stitched Image using Novel Hybrid Warping Technique
Image stitching is collection of sequential images captured at fixed camera center having considerable amount of overlap and produces aesthetically pleasing seamless panoramic view. But, practically it is very difficult...