Adaptive Acceptance Criterion (AAC) Algorithm for Optimization Problems

Abstract

Optimization methods commonly are designed for solving the optimization problems. Local search algorithms are optimization method, which are good candidate in exploiting the search space. However, most of them need parameter tuning and incapable of escaping from local optima. This work proposes non-parametric Acceptance Criterion (AC) that not relies on user-defined, which motivate to propose an Adaptive Acceptance Criterion (AAC). AC accepts a little worse solution based on comparing the candidate and best solutions found values to a stored value. The value is stored based on the lowest value of comparing the candidate and best solution found, when a new best solution found. AAC adaptively escape from local optima by employing a similar diversification idea of a previous proposed (ARDA) algorithm. In AAC, an estimated value added to the threshold (when the search is idle) to increase the search exploration. The estimated value is generated based on the frequency of the solutions quality differences, which are stored in an array. The progress of the search diversity is governed by the stored value. Six medical benchmark datasets for clustering problem (which are available in UCI Machine Learning Repository) and eleven benchmark datasets for university course timetabling problems (Socha benchmark datasets) are used as test domains. In order to evaluate the effectiveness of the propose AAC, comparison made between AC, AAC and other approaches drawn from the scientific literature. Results indicate that, AAC algorithm is able to produce good quality solutions which are comparable to other approaches in the literature.