Single-based and Population-based Metaheuristics for Solving NP-hard Problems

Saman M.  Almufti; Ridwan B.  Marqas; Pawan Sh.  Othman; Amira Bibo  Sallow

doi:10.24996/10.24996/ijs.2021.62.5.34

Authors

Saman M. Almufti Department of Computer science, Nawroz University, Duhok, Iraq
Ridwan B. Marqas Department of Information Technology, Duhok Private Technical Institute, Duhok, Iraq
Pawan Sh. Othman Department of Computer System, Ararrat Private Technical Institute, Duhok, Iraq
Amira Bibo Sallow Department of Computer Sciences, Nawroz University, Duhok, Iraq

DOI:

https://doi.org/10.24996/10.24996/ijs.2021.62.5.34

Keywords:

Metaheuristics, Elephant Herding Optimization, Tabu Search, NP-Hard, Traveling Salesman Problem

Abstract

Metaheuristic is one of the most well-known fields of research used to find optimum solutions for non-deterministic polynomial hard (NP-hard) problems, for which it is difficult to find an optimal solution in a polynomial time. This paper introduces the metaheuristic-based algorithms and their classifications and non-deterministic polynomial hard problems. It also compares the performance of two metaheuristic-based algorithms (Elephant Herding Optimization algorithm and Tabu Search) to solve the Traveling Salesman Problem (TSP), which is one of the most known non-deterministic polynomial hard problems and widely used in the performance evaluations for different metaheuristics-based optimization algorithms. The experimental results of Elephant Herding Optimization algorithm and Tabu Search for solving ten different problems from the TSPLIB95 library are compared.