Benchmarking Randomized Optimization Algorithms on Binary, Permutation, and Combinatorial Problem Landscapes
This study provides practical guidance for selecting optimization algorithms based on problem type and constraints, but it is incremental as it benchmarks existing methods without introducing new ones.
The paper evaluated four randomized optimization algorithms (RHC, SA, GA, MIMIC) on binary, permutation, and combinatorial problems, finding that MIMIC and GA produce high-quality solutions for binary and combinatorial problems but with varying computational costs, while RHC and SA are less expensive but perform poorly in complex landscapes.
In this paper, we evaluate the performance of four randomized optimization algorithms: Randomized Hill Climbing (RHC), Simulated Annealing (SA), Genetic Algorithms (GA), and MIMIC (Mutual Information Maximizing Input Clustering), across three distinct types of problems: binary, permutation, and combinatorial. We systematically compare these algorithms using a set of benchmark fitness functions that highlight the specific challenges and requirements of each problem category. Our study analyzes each algorithm's effectiveness based on key performance metrics, including solution quality, convergence speed, computational cost, and robustness. Results show that while MIMIC and GA excel in producing high-quality solutions for binary and combinatorial problems, their computational demands vary significantly. RHC and SA, while computationally less expensive, demonstrate limited performance in complex problem landscapes. The findings offer valuable insights into the trade-offs between different optimization strategies and provide practical guidance for selecting the appropriate algorithm based on the type of problems, accuracy requirements, and computational constraints.