Crystal 结构预测 (Crystal Structure Prediction via Oblivious Local Search)

We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand, usually easy to implement, but they can be slow in practice. On the other hand, the more sophisticated approaches perform well in general, however almost all of them have a large number of parameters that require fine tuning and, in the majority of the cases, chemical expertise is needed in order to properly set them up. In addition, due to the chemical expertise involved in the parameter-tuning, these approaches can be {\em biased} towards previously-known crystal structures. Our contribution is twofold. Firstly, we formalize the Crystal Structure Prediction problem, alongside several other intermediate problems, from a theoretical computer science perspective. Secondly, we propose an oblivious algorithm for Crystal Structure Prediction that is based on local search. Oblivious means that our algorithm requires minimal knowledge about the composition we are trying to compute a crystal structure for. In addition, our algorithm can be used as an intermediate step by {\em any} method. Our experiments show that our algorithms outperform the standard basin hopping, a well studied algorithm for the problem.

翻译：我们研究水晶结构预测,这是计算化学方面的主要问题之一。这基本上是一个连续的优化问题,它涉及许多不同、简单和尖端的方法。简单搜索技术容易理解,通常容易实施,但实际上却很慢。另一方面,较复杂的方法一般地表现良好,但几乎所有方法都有许多需要微调的参数,在多数情况下,需要化学专门知识才能正确设置这些参数。此外,由于参数调控涉及的化学专门知识,这些方法可能偏向于以前已知的晶体结构。我们的贡献是双重的。首先,我们从理论计算机科学的角度将水晶结构预测问题与其他几个中间问题一起正式化。第二,我们建议根据本地搜索对水晶结构预测进行隐蔽的算法。显然,我们的算法要求我们对正试图对水晶结构的构成知之甚少。此外,我们的算法可以用作中间步骤,通过任何方法来使用。我们的贡献是双重的。首先,我们将水晶结构预测问题与其他中间问题一起正式化,从理论的计算机科学角度来研究。第二,我们提出的水晶结构预测法的算法显示我们的标准比标准的问题。