Solving Travelling Salesman Problem Using Heart Algorithm

Solving Travelling Salesman Problem Using Heart Algorithm

Abdolreza Hatamlou (Department of Computer Science, Khoy Branch, Islamic Azad University, Khoy, Iran)
Copyright: © 2017 |Pages: 11
DOI: 10.4018/IJAEC.2017100103

Abstract

Solving hard problems like the Travelling Salesman Problem (TSP) is a major challenge faced by analysts even though many techniques are available. The main goal of TSP is that a number of cities should be visited by a salesman and return to the starting city along a number of possible shortest paths. TSP is although looking a simple problem, but it is an important problem of the classical optimization problems that are difficult to solve conventionally. It has been proved that solving TSP by the conventional approaches in a reasonable time is not possible. So, the only feasible option left is to use heuristic algorithms. In this article, we apply and investigate a new heuristic approach called Heart algorithm to solve Travelling Salesman Problem. It simulates the heart action and circulatory system procedure in the human beings for searching the problem space. The Heart algorithm has the advantages of strong robustness, fast convergence, fewer setting parameters and simplicity. The results of the Heart algorithm on several standard TSP instances is compared with the results of the PSO and ACO algorithms and show that the Heart algorithm performs well in finding the shortest distance within the minimum span of time.
Article Preview

1. Introduction

Nature has been a great source of inspiration for solving difficult and complex problems for decades. It has inspired many heuristic algorithms to solve hard problems in a reasonable time (Yang, 2008). Some of the famous and well-known Nature-inspired Algorithms are: Genetic Algorithms (Leardi, 2009; Bouyer, 2010), Particle Swarm Optimization (PSO) (Kennedy, 1995; Hatamlou 2013, 2017), Ant Colony Optimization (ACO) (Dorigo, 2005), Artificial Bee Colony (ABC) (Karaboga, 2007; Mohrechi, 2015), Gravitational Search Algorithm (GSA) (Rashedi, 2009; Hatamlou, 2011, 2012, 2013), Big Bang-Big Crunch Algorithm (BB-BC) (Hatamlou, 2011, 2013), Gray Wolf Optimizer (GWO) (Mirjalili, 2014), Black Hole Algorithm (BH) (Hatamlou, 2013, 2017; Farahmandian, 2015), and Heart Algorithm (Hatamlou, 2014, 2016). Nature-inspired algorithm has been applied to a broad range of applications and problems, like Timetabling, Clustering, Routing, Travelling Salesman Problem (TSP), Knapsack Problem, Graph Coloring, Vehicle Routing etc.

Nature-inspired algorithms usually start with an initial population of candidate solutions for the optimization problem and then cooperate with each other to find the optimal solution for that problem. In these algorithms the candidate solutions move in the problem space via some mechanism and search for optimal solutions by visiting different areas. Most of Nature-inspired algorithms try to make balance between intensification and diversification mechanism. The diversification means searching whole problem space as much as possible, while intensification ensures the algorithm to search promising areas by restricting the search space around the current best solutions.

Heart algorithm is one of the most recent Nature-inspired algorithms. It mimics the heart action and circulatory system procedure in the human beings for searching the problem space. Heart algorithm is a robust and reliable approach which has a simple structure.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing