合金团簇结构优化问题的高效求解算法

This project concerns a problem related to the structure of matters, which originates from the study of the molecular physics of clusters and is realized in the global optimization problem in mathematics and computer science. The mathematical model of the problem is: Given N points in three-dimensional space, each point having a property of A or B, wherein any one point with a potential energy,the potential energy of the system is a function of the distance between each point and the remaining N-1 points. Thus, the total potential energy U of the system formed by N points is the sum of the potential energy of each point. The aim is to layout the N points in the space in order to minimize the total potential energy U. This problem involves both continuous optimization and discrete optimization and it has proven to be NP-hard. Therefore, it is of theoretically significance to solve this problem effectively and this algorithm has also important practical applications in physical chemistry as well as deepening the understandings of the structure of matters, and guiding people to create new types of material to meet real world demand. This project will focus on the alloy clusters with Gupta potential energy. The research work includes: Building a precise dynamic lattice point, as a foundation for designing efficient continuous optimization solution strategy; Designing adaptive tabu search strategy to achieve combinatorial optimization and to design targeted disturbance operator (i.e. exchanging the position of atoms), in order to improve the search capability of tabu search; Reasonably combining continuous optimization and combinatorial optimization strategies so as to design efficient algorithms for alloy clusters.

本项研究是一个有关物质结构的问题,它起源于分子物理学中的团簇研究,而落实于数学与计算机科学中的全局优化问题。其数学模型为：已知三维空间中的N个质点，每个质点具有性质A或B，其中任一质点所具有的势能为该质点与其余N-1个质点之间距离的已知函数，N个质点所形成的体系其总势能U为各质点势能之和，问这 N个质点在空间中如何布局才能使总势能U最小。本问题涉及连续优化和组合优化,具有NP难度，对其求解能深化人类对物质结构的认识，引导人们制造出满足实际需求的新型物质。本项目以Gupta 势能描述的合金原子团簇为研究重点，研究工作包括：构建精确的动态格点，以此为基础设计高效的连续优化求解策略；采用自适应的禁忌搜索策略实现组合优化，设计有针对性的扰动算子（即交换原子位置的策略）以提高禁忌搜索的搜索能力；将连续优化策略与组合优化策略合理地结合起来，设计合金团簇优化的无偏见高效求解算法.

本项研究源于分子物理学中的基础性问题——团簇结构预测。团簇的最低能量结构称为团簇基态结构，它的理论确定被证明是NP难度的。.团簇的大部分物理与化学性质由其几何结构决定，合金原子团簇具有很多块状材料所不具备的优良特性，其微观几何结构是人工合成新型材料的关键。虽然实验的方法可以得到一些团簇结构的信息，但是现有的技术手段仍很难确定团簇的基态结构。为弥补现有实验方法的不足，人们希望通过理论计算的方法借助计算机来预测原子团簇的基态结构。.团簇基态结构的确定尚无多项式时间的精确求解算法。为其设计高效的求解算法，不仅能给实验方法以有益的补充，也可为其他NP难度问题的求解提供有价值的借鉴。本项研究围绕合金团簇基态结构预测问题展开工作，为此问题提供高效的求解算法。.在本项目的研究工作过程中，我们主要做了两方面的工作，如何在算法的执行到达目标函数的极小值点时，尽快地解脱这种“卡壳”的困境；如何将连续的搜索空间转化为离散的搜索空间，缩小寻优搜索的范围。.主要研究内容如下：.1 用更精确的方法计算格点的势能，避免了由于格子构建不精确而忽略目标函数全局最优点的搜索。在动态格子搜索过程中，采用具有继承性的公式计算团簇的势能，节省了计算时间。.2 用基于距离和基于能量的两种表面操作和内部操作，较大幅度地改变处于“卡壳”状态的团簇构型，使算法的执行尽快从目标函数局部极小值“陷阱”中解脱出来。.3 用两阶段的内部优化策略，执行动态格子操作和表面优化操作之后，对团簇再执行一次适应性的扰动，使得对团簇的扰动从剧烈到精细，既快速地降低团簇的势能，又避免了较大扰动导致搜索从最优解附近越过，以致忽略了最优解。.4 将在单原子团簇结构优化求解中所得的经验用于双原子团簇结构优化。.5 构建动态格子时生成A、B两类格点，使得格子搜索更精确。.6 用两阶段方式互换团簇中A、B高能原子的位置，让算法的执行尽快从目标函数局部极小值“陷阱”中解脱出来。