A Hybrid Hierarchical Heuristic-ACO With Local Search Applied to Travelling Salesman Problem, AS-FA-Ls

A Hybrid Hierarchical Heuristic-ACO With Local Search Applied to Travelling Salesman Problem, AS-FA-Ls

Nizar Rokbani (High Institute of Applied Science and Technology of Sousse, University of Sousse, Tunisia & REGIM-Lab, University of Sfax, Tunisia & National Engineering School of Sfax, Tunisia), Pavel Kromer (Department of Computer Science, FEECS, VSB - Technical University of Ostrava, Czech Republic), Ikram Twir (High Institute of Applied Science and Technology of Sousse, University of Sousse, Tunisia) and Adel M. Alimi (REGIM-Lab, University of Sfax, Tunisia & National Engineering School of Sfax, Tunisia)
Copyright: © 2020 |Pages: 16
DOI: 10.4018/IJSDA.2020070104

Abstract

The combinatorial optimization problem is attracting research because they have a wide variety of applications ranging from route planning and supply chain optimization to industrial scheduling and the IoT. Solving such problems using heuristics and bio-inspired techniques is an alternative to exact solutions offering acceptable solutions at fair computational costs. In this article, a new hierarchical hybrid method is proposed as a hybridization of Ant Colony Optimization (ACO), Firefly Algorithm (FA), and local search (AS-FA-Ls). The proposed methods are compared to similar techniques on the traveling salesman problem, (TSP). ACO is used in a hierarchical collaboration schema together with FA which is used to adapt ACO parameters. A local search strategy is used which is the 2 option method to avoid suboptimal solutions. A comparative review and experimental investigations are conducted using the TSP benchmarks. The results showed that AS-FA-Ls returned better results than the listed works in the following cases: berlin52, st70, eil76, rat99, kroA100, and kroA200. Computational investigations allowed determining a set of recommended parameters to be used with ACO for the TSP instances of the study.
Article Preview
Top

Introduction

The advent of self-driving cars, intelligent transportation systems, and internet of things devices routing challenges, recalled the interest in combinatorial optimization problems, COP. Among them, the traveling salesman problem is still attracting interest since it can stand for many industrial applications such as internet of things networks routing, components placements on board for electronics manufacturing, transportation systems (Bajracharya,2016), containers management & logistic optimization chains, robotics (Rajasekaran et al., 2014), etc. Bio-inspired techniques such as Flower Pollination algorithm by (Yang, 2009), Particle Swarm Optimization by (Kennedy & Eberhart, 1995), Ant Colony Optimization by (Dorigo & Birattari, 2007), Firefly Algorithm by (Yan, 2010) and Article Bee Colony algorithm by (Karaboga, 2005) showed their capacities to solve such problems.

Hybrid heuristics are in general built by combining several heuristics algorithms in order to tackle the weaknesses of each one and to improve the quality of the solutions essentially in engineering design problems (Moussa et al., 2015; Pradhan, 2017). Hybridization is already based on a collaboration schema between heuristics. Hierarchical heuristics can be seen as: low level hybrids and high-level hybrids. In low-level hybridization, an internal function, or sub-processing, of a heuristic is replaced by another heuristic. In high level hybridization, two heuristics are hybridized without affecting their respective internal functionality. The hierarchical mechanism is involved when heuristics are executed sequentially; the output of the first heuristic is used by the second one, while the co-evolutionary mechanism leads to an evolution in which agents from different heuristics cooperate to explore the space of solutions in parallel (Rokbani et al., 2013), and where authors proposed an early hybridization of ACO and PSO, to overcome the sensibility of ACO to parameters.

In (Wahid et al., 2018), the authors proposed a combination between the FA, the genetic algorithm, GA, and the Pattern Search, PS, with application to standard mathematical functions. In this approach GA was used to generate a set of solutions that were later evolved for a fixed number of iterations by the firefly algorithm. The evolved solutions were evaluated and if an optimum solution was not found, the GA was recalled to modify the population on the basis of its classical operators, crossover, and mutation. The pattern search was introduced to moderate the solution obtained by the FA. The proposed hybridization was tested using the standard test functions such as the Ackley, Rosenbrock, and the Sphere functions.

A hybridization schema based on the Ant Colony System, ACS, and the Firefly algorithm, FA, was proposed in (Goel & Maini, 2017) with application to Vehicle Routing Problem, VRP. A Hybrid Ant Firefly Algorithm, HAFA, consisting in using ACS to generate the initial problem solutions’ representing the pool for FA was used to improve the search space exploration ability. The best solution found by the FA was used to update the pheromone trail. Here, the authors proposed a discrete version of FA to adapt it to the discrete problem. A combination of ACO and FA has been proposed in (Olief et al., 2016) in which ACO looked for the global solution and the FA focused on local optima using its neighborhood mechanism for TSP. The FA was the first method to search for local best tours and then the ACO was involved to search for the best tour on top of the FA results. In (Ariyantne et al., 2016), the authors used the firefly algorithm to optimize ACO settings. They aimed to find the global best path by optimizing α, β, and ρ; while not using any local search mechanism. In (Kumbharana & Pandey, 2013) the authors proposed the use of FA to solve the TSP. The fireflies were in this approach encoded in a discrete finite space representation, as vectors of (n) positions. When a firefly was supposed to move based on the distance to its neighbor, the Hamming distance was used to look after the best configuration among a given set of cities. The mechanism efficiently allowed avoiding minima. The method was applied to several TSP problems limited to 51 cities, including the city10, 16, 23, 30, and Eli51 TSP instances.

Complete Article List

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