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 87
- Downloads 0
Evaluating the Role of Information and Communication Technology (ICT) Support towards Processes of Management in Institutions of Higher Learning
The role of Information and Communication Technology in achieving organization’s strategic development goals has been an area of constant debate, and as well perceived in different management dimensions. Most unive...
Towards a Fraud Prevention E-Voting System
Election falsification is one of the biggest problems facing third world countries as well as developed countries with respect to cost and time. In this paper, the guidelines for building a legally binding fraud-proof El...
Preference in using Agile Development with Larger Team Size
Agile software development includes a group of software development methodologies based on iterative development, where requirements and solutions evolve through collaboration between cross-functional self-organizing tea...
EICT BASED DIAGNOSTIC TOOL AND MONITORING SYSTEM FOR EMF RADIATION TO SUSTAIN ENVIRONMENTAL SAFETY
The adverse effects of electromagnetic radiation from mobile phones and communication towers on health issues are being well documented today. However, exact correlation between radiation of communication towers and thei...
Using Digital Image Processing to Make an Intelligent Gate
This paper presents an automatic system for controlling and dominating building gate based on digital image processing. The system begins with a digital camera, which captures a picture for that vehicle which intends to...