Improving Heuristic Search by Machine Learning

探索和开发是(元)启发式优化中的两个基本概念。令人惊讶的是，缺乏正式的定义阻碍了对它们进行量化衡量和分析的能力。我最近的研究为这些概念提供了正式的定义。根据这些定义，可以显示同时勘探和开采的负面后果。我们还证明了元启发式中的选择如何偏向探索，从而促进失败的探索。这些发现是我们在过去几年中开发的一系列成功算法和多样化技术(领导者和追随者、阈值收敛和最小种群搜索)的基础。它还激励了一种新的优化方法，该方法基于尽可能将两个过程分开的想法。这种方法的最终目标是设计一种仅限于勘探、仅限于开采的混合体(EEH)。这种混合方法的关键挑战是设计仅用于勘探的方法。限制之一在于难以衡量探索的有效性。我们的定义将这些概念形式化，但几乎没有允许以实际方式测量勘探的函数。因此，设计一个“勘探基准”是要实现的一个基本中间目标。探索基准和EEH方法为通过机器学习改进元启发式方法提供了令人兴奋的机会。测量大量功能上的探索的能力将使训练深度学习模型能够估计探索性解决方案的前景，从而避免失败的探索。对于给定的函数，选择最佳的探索策略，预测从探索到开发的最佳转换点，也是机器学习在这一新方法中的潜在应用。改进的元启发式算法和相关的机器学习模型的发展提供了无数的应用机会；特别是因为这项研究专门专注于大规模领域。我将扩展我以前在分子对接方面的经验，目标是将一个专门为这个问题设计的基于机器学习的优化器加入Autodock工具。在与UPEI和Somru BioScience Inc.的量子计算研究小组的合作下，我还将把这些算法应用于计算生物学和化学领域的各种优化和预测问题。

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.