Application of on-line machine learning in optimization algorithms: A case study for local search

The study on machine learning has been flourishing for several years, and machine learning algorithms are being applied to various fields with great achievements. In this paper, combining the on-line machine learning method into optimization algorithms is to be studied. In many heuristic optimization algorithms, one common way to reduce execution time and improve solution optimality is, first estimating the quality of a set of candidate solutions, and solving only promising candidates in detail. Currently most estimations are performed by empirical equations, whose accuracy greatly relies on the how well the equation is designed. In this paper, we propose an on-line learning based estimator to perform the solution estimation in heuristic algorithms to improve estimation accuracy. Then a simple case study is discussed, where a local search based heuristic with random start is used, and an on-line estimator considering the properties of local search is proposed. The experiments show that the accuracy of on-line estimator is much higher than the static estimator, and is also higher than a general off-line pre-Trained learner. Even though the on-line estimator introduced special time for its training, the heuristic algorithm still speeds up by 3.7X without optimality sacrifice.