Improving Heuristic Search by Machine Learning

通过机器学习改进启发式搜索

• 批准号: RGPIN-2021-03205
• 负责人: BolufeRohler, Antonio
• 金额: $ 1.75万
• 依托单位: University of Prince Edward Island
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742433
• 关键词: Improving; Heuristic; Search; 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.

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