Improving Heuristic Search by Machine Learning

点击翻译按钮获取中文摘要

Exploration and exploitation are two fundamental concepts in (meta)heuristic optimization. Surprisingly the lack of a formal definition has hindered the ability to measure and analyze them quantitatively. My most recent research has provided formal definitions for these concepts. Based on these definitions it has been possible to show the negative consequences of concurrent exploration and exploitation. We have also evidenced how selection in metaheuristic biases exploration, promoting failed exploration. These discoveries have been the base of a series of successful algorithms and diversifications techniques that we have developed during the past years (Leaders and Followers, Thresheld Convergence and Minimum Population Search). It has also motivated a new approach to optimization based on the idea of separating as much as possible both processes. The ultimate goal of this approach is the design of an exploration-only exploitation-only hybrid (EEH). The key challenge in such hybrid is the design of the exploration-only method. One of the limitations resides in the difficulty of measuring the effectiveness of exploration. Our definitions formalize these concepts, but there are few functions that allow measuring exploration in a practical way. Therefore the design of an "exploration benchmark" constitutes a fundamental intermediate goal to be achieved. The exploration benchmark and the EEH approach present exciting opportunities for the improvement of metaheuristics through machine learning. The ability to measure exploration on a broad number of functions will allow training deep learning models to estimate how promising an exploratory solution is, and thus avoid failed exploration. Selecting the best exploration strategy for a given function and predicting the optimum transition point from exploration to exploitation are also potential applications of machine learning into this new approach. The development of improved metaheuristics and the associated machine learning models provide a myriad of application opportunities; especially since this research is specifically focused on large scale domains. I will extend my previous experience in molecular docking with the aim of including a machine learning based optimizer, specifically designed for this problem, into the Autodock tool. In collaboration with the Quantum Computing research group at UPEI and Somru BioScience Inc. I will also apply these algorithms to a diversity of optimization and prediction problems in the fields of computational biology and chemistry.