Population Based Equilibrium in Hybrid SA/PSO for Combinatorial Optimization: Hybrid SA/PSO for Combinatorial Optimization

Population Based Equilibrium in Hybrid SA/PSO for Combinatorial Optimization: Hybrid SA/PSO for Combinatorial Optimization

Kenneth Brezinski (University of Manitoba, Winnipeg, Canada), Michael Guevarra (University of Manitoba, Winnipeg, Canada) and Ken Ferens (Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, Canada)
DOI: 10.4018/IJSSCI.2020040105

Abstract

This article introduces a hybrid algorithm combining simulated annealing (SA) and particle swarm optimization (PSO) to improve the convergence time of a series of combinatorial optimization problems. The implementation carried out a dynamic determination of the equilibrium loops in SA through a simple, yet effective determination based on the recent performance of the swarm members. In particular, the authors demonstrated that strong improvements in convergence time followed from a marginal decrease in global search efficiency compared to that of SA alone, for several benchmark instances of the traveling salesperson problem (TSP). Following testing on 4 additional city list TSP problems, a 30% decrease in convergence time was achieved. All in all, the hybrid implementation minimized the reliance on parameter tuning of SA, leading to significant improvements to convergence time compared to those obtained with SA alone for the 15 benchmark problems tested.
Article Preview
Top

2. Background

Metaheuristics have been developed over the years as a means in which to tackle computationally difficult problems. One of the most well studied metaheuristics is SA, which was originally applied for solving the TSP in the work of (Černý, 1985). One of the core properties that makes SA so appealing as a metaheuristic is the ability for it to accept worse solutions that would have otherwise been discarded as they lead to poorer short-term solutions (Franzin & Stützle, 2019). Alternatively, SA is regarded as relying too heavily on initial parameters (Trelea, 2003; van den Bergh & Engelbrecht, 2006); thereby requiring significant domain-level and application-level knowledge of the problem before initializing. Researchers have stayed on top of this problem by introducing hybrid strategies that complement the shortcomings of SA alone. These strategies will be discussed in the following section.

Complete Article List

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