Scholarlink

Metaheuristic algorithms play a key role in solving complex NP-hard optimization problems by offering scalable and efficient solutions. This study evaluates the performance of four popular metaheuristic algorithms: Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), and Ant Colony Optimization (ACO). These algorithms were tested on three NP-hard problems: Job Shop Scheduling Problem (JSSP), Vehicle Routing Problem (VRP), and Network Design Problem (NDP). Despite having different goals, these problems share common challenges such as resource allocation and conflict resolution. The algorithms were evaluated using profiling tools such as <chrono>, gperftools, and Valgrind’s Callgrind. Metrics like execution time, memory usage, cache performance, and instruction count were analyzed. SA achieved the fastest execution and lowest resource use for JSSP. ACO performed best for VRP with fewer cache misses and fast performance. GA provided the best results for NDP with efficient instruction handling. TS delivered balanced results across all problems. These findings help in selecting the most suitable algorithm for specific optimization tasks in scheduling, transportation, and network systems.</chrono>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Optimizing NP-Hard Problems: A Comparative Study of Metaheuristic Algorithms with Benchmark Performance Analysis

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Md. Maruf Hossain Munna,
  • Riazul Zannah,
  • Sajedul Islam,
  • Syeda Shakira Akter,
  • Md. Asif Sarker Emon,
  • Mustakim Ahmed,
  • Md. Faruk Abdullah Al Sohan

摘要

Metaheuristic algorithms play a key role in solving complex NP-hard optimization problems by offering scalable and efficient solutions. This study evaluates the performance of four popular metaheuristic algorithms: Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), and Ant Colony Optimization (ACO). These algorithms were tested on three NP-hard problems: Job Shop Scheduling Problem (JSSP), Vehicle Routing Problem (VRP), and Network Design Problem (NDP). Despite having different goals, these problems share common challenges such as resource allocation and conflict resolution. The algorithms were evaluated using profiling tools such as , gperftools, and Valgrind’s Callgrind. Metrics like execution time, memory usage, cache performance, and instruction count were analyzed. SA achieved the fastest execution and lowest resource use for JSSP. ACO performed best for VRP with fewer cache misses and fast performance. GA provided the best results for NDP with efficient instruction handling. TS delivered balanced results across all problems. These findings help in selecting the most suitable algorithm for specific optimization tasks in scheduling, transportation, and network systems.