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

  • 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
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.

Published
2021-05-31
How to Cite
Almufti, S. M., Marqas, R. B., Othman, P. S., & Sallow, A. B. (2021). Single-based and Population-based Metaheuristics for Solving NP-hard Problems. Iraqi Journal of Science, 62(5). https://doi.org/10.24996/10.24996/ijs.2021.62.5.34
Section
Computer Science