Crystal Structure Prediction via Oblivious Local Search

Antypov, Dmytro ORCID: 0000-0003-1893-7785, Deligkas, Argyrios, Gusev, Vladimir ORCID: 0000-0002-2815-607X, Rosseinsky, Matthew J ORCID: 0000-0002-1910-2483, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail (2020) Crystal Structure Prediction via Oblivious Local Search 18th Symposium on Experimental Algorithms (SEA 2020), 160. 21:1-21:14. ISSN 1868-8969

Text 2003.12442v1.pdf - Published version Download (1MB) | Preview

Abstract

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.

Item Type:	Article
Additional Information:	To be published in the 18th Symposium on Experimental Algorithms (SEA 2020)
Uncontrolled Keywords:	crystal structure prediction, local search, combinatorial neighborhood
Depositing User:	Symplectic Admin
Date Deposited:	01 May 2020 09:46
Last Modified:	21 Apr 2026 20:40
DOI:	10.4230/LIPIcs.SEA.2020.21
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3085408
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.