© 2021 The AuthorMetaheuristic algorithms are solution approaches to solve optimization problems by repeating some algorithmic steps while searching the solution space. The strategy of the metaheuristic includes two basic tactics; exploration for escaping the local optimum and exploitation for the global optimum. The number of solutions while exploring the solution space can be used to classify metaheuristics. If the metaheuristic uses only one solution to generate a new solution, we call it the single-solution-based metaheuristic. Simulated annealing, iterated local search, adaptive large neighborhood search, iterated greedy, local search, and tabu search are examples of single-solution-based metaheuristics. Most of these metaheuristics use an acceptance criterion to whether accept the newly generated solution instead of the incumbent solution to escape from the local optimal. The most used acceptance criterion in the literature is the Metropolis criterion or simulated annealing-like acceptance criterion that decides whether accept the new solution by calculating its acceptance probability. In this study, we propose a fuzzy rule-based acceptance criterion that fuzzies the inputs of the metaheuristic within a fuzzy inference system to create the decision output about the acceptance. The proposed new acceptance criterion is compared with the well-known probabilistic approach in the experimental study with traveling salesman problem, multidimensional knapsack problem, single machine weighted earliness/tardiness problem, linear regression problem, and two continuous optimization problems. The statistical analyses reveal that the number of acceptance solutions while using the proposed acceptance criterion is less than the probabilistic one has but the metaheuristic performance increases with the proposed criterion. Additional analyses are made to explain why the fuzzy criterion convergences better to the global optimum than the probabilistic criterion.