英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
在世博会包装中的直接空间解：GRASP与HBB-BC算法的结合
大爆炸-大紧缩混合算法是一种全局优化算法和模拟退火算法的结合，前者的灵感来自于宇宙演化理论中的大爆炸和大紧缩理论。该工程已经在博览会中最新版本的程序中实现，并且应用于粉末衍射数据中得到的晶体结构解中。大爆炸-大紧缩混合算法的一些方面可以进一步优化，以达到在更短计算时间内获得更高质量解的目标。在本研究中，大爆炸-大紧缩混合算法已经与贪婪随机自适应搜索过程（GRASP）进行了结合，并且这一算法的某些步骤也得到了改进。这一应用于博览会包装中的新算法，已经在众多为人熟知的晶体结构上进行了成功的测试。
一、介绍
粉末衍射数据得到的晶体结构解是粉末衍射方法的最关键目标之一。它通常是以一个复杂的途径进行的，作为所有解决方案技术的前提，它需要确定好单元参数和空间组。随后，可以利用倒晶格空间（RS）的方法以及/或者直接空间（DS）法接近晶体结构。倒晶格空间（RS）的方法包括【直接的方法（贾柯瓦佐于2015年）；帕特森法（里乌斯等人于2007年，里乌斯和弗罗泰拉于2007年，里乌斯于2011年）；最大值-熵方法（吉尔摩等人于1999年）】。直接空间（DS）法包括【网格搜索（切尼舍夫和申克于1998年）；蒙特卡罗法（哈里斯等人于1994年；安德列夫等人于1997年；特雷梅恩等人于1997年）；模拟退火法（柯克帕特里克于1984年）；遗传算法（戈德伯格于1989年，卡里乌基等人于1997年，尚克兰等人于1997年）；并行回火法（法夫雷尼克林和塞尔尼于2004年）；粒子群优化法（索玛和大卫于1999年；冯等人于2009年）】。这两种方法具有不同的功能以及局限，本文主要研究DS法。
在直接空间中，模拟退火法（SA）作为一种直接求解结构的全局优化算法，得到了广泛而成功的应用。特别是在最近应用上的改进（卡波瓦、科尔、柯尔布、洛佩兹伊巴内兹等人于2017年；卡波瓦、科尔、柯尔布、威廉姆斯和尚克兰于2017年），以及在计算机程序DASH中实现（大卫等人于2006年），这些成果都在很大程度上提高了DS法的适用范围和成功率。因此，我们提出一种新的直接空间求解策略和计算工具。
有人认为（哈里斯等人，2011年）结构解决方案可以受益于混合方法的使用。一个例子是将RS法和DS法相结合，以此来激发出两者最佳的特质。【电荷翻转法（奥斯兹兰尼和苏托，2004年Oszlanyiamp;Suuml;toOszlanyiamp;Suuml;to）和SA与直接法的结合（奥托马尔等人，2003年，2008年）】
我们之前提出了一种创新的混合全局优化方法：混合大爆炸大紧缩法（HBB-BC）（奥托马尔，科列罗等人，2013年）。HBB-BC是基于宇宙演化理论中的一种，即大爆炸和大紧缩理论，并与传统的模拟退火法进行适当混杂，它已经在博览会中的程序（奥托马尔，科奇等人，2013年）得到实现，并成功地应用于粉末衍射数据得到的晶体结构解中。
大多数DS搜索方法的随机性意味着，为了确定是否已经找到真正的全局最小值，必须进行多次运行，这不可避免地需要大量的运行时间和计算时间。
尽管HBB-BC方法需要在不减少正确解数量的情况下，要在博览会软件中实现的传统SA算法相比，还能持续减少执行时间（奥托马尔，科列罗等人，2013年），但仍需要提高优化方法的速度。本研究对HBB-BC方法进行了优化。首先将其与元启发式贪婪随机自适应搜索过程（GRASP）相结合（费奥和雷森德，1995年），这是一种有效的重复抽样技术。然后对构成算法的两个步骤，也就是大爆炸和大紧缩阶段进行了修正。新算法（这里称为GHBB-BC）已经在程序博览会的高级版本中实现，目的是使解决过程更快、更成功。
为了方便读者，本文简要介绍了HBB-BC算法的基本概念以及新过程中一些保留的概念，并且会分析被修改的一些方面。文中还介绍了GRASP法在传统版本中以及在GHBB-BC中的修改和实现，详细说明了GHBB-BC算法，并介绍了其在博览会上应用的主要特点。GHBB-BC方法已经在我们的测试结构数据库中得到了成功的演示。
2、一般概念
HBB-BC法是传统模拟退火算法和大爆炸-大紧缩理论的结合。后者包括两个连续的阶段：大爆炸对应于一个能量耗散的过程，用于创建完全随机的初始总体；大紧缩对应一个收缩过程，用于收敛到全局最优点。该算法在博览会的程序中按照如下总结的步骤实现【详情见奥托马尔，科列罗等人（2013）】：
（1）、从一个预期的结构模型开始，随机创建一个候选解的初始总体（第一次大爆炸）。
（2）、Rwp可靠性参数代表计算轮廓与可观测数据的拟合，用来评估每个候选解。
（3）、紧接着大紧缩这一步的是选择，选择种群中最低Rwp值作为xc的中心。
（4）、又一次大爆炸，根据等式：
xinew=xc （2r-1）alpha;， (1)
由已知的xc可以得出新的解xinew，在式子中r是在区间[0，1]之间的随机数。alpha;限制搜索空间的大小，并且遵循以下表达式：
alpha;=alpha;max（ ）k/Niter， (2)
其中k是当前的大爆炸迭代步骤，Niter（通过考虑候选解中存在的结构碎片数和扭转角来确定）是该过程执行的最大可能迭代次数。alpha;min和alpha;max通常分别设置为0.0001和1.0 。
（5）、计算所有候选解的Rwp值。
（6）、为了改善模型在非对称单元中的位置，根据Rwp选择最差候选模型并提交给快速SA。
（7）、对研究中的候选解重新计算Rwp值。有两种情况：如果Rwplt;0.15(Rwp)（此平均值是根据总体中所有元素来计算的），过程返回到步骤（3）并进行新的迭代；如果Rwpge;0.15(Rwp)，根据Rwp值，第二个和第三个最差候选值依次提交给快速SA。
（8）、过程返回到步骤（3）,并在一个循环中重复，直到达到停止标准（详情见奥托马尔，科列罗等人，2013）。
当这个程序应用于各种晶体粉末样本，并且与传统SA算法相比较时，该程序清楚的显示了其在不减少正确解决方案数量的情况下节省计算时间的技巧（见见奥托马尔，科列罗等人，2013）。
然而，当多于一个总体元素被提交到SA全局优化算法【程序中的步骤（7）】，即使SA是快速的，也很难实现低Rwp值，并且通常需要更长的计算时间来完成该过程。
在我们的方法中引进GRASP，特别是在第一个大爆炸步骤中，支持候选模型的优化，从而可以在SA过程中节省计算时间（见第四节）。
对“标准程序”进行一些改进，目的是增强HBB-BC的潜力，特别是减少时间的消耗。主要的进展在于引进了使用有效抽样的元启发式GRASP程序，以改进第一个大爆炸步骤产生的总体，以及改进了HBB-BC方法的一些步骤。这两方面的细节如下。
3、贪婪随机自适应搜索过程
GRASP是一种元启发式算法，通常应用于非常困难且具有巨大解空间的组合优化问题（费奥和雷森德，1995；费斯塔和雷森德，2009a）。与其他元启发式方法相比，GRASP具有一些吸引人的优点，比如易于实现，并且在其基本版本中只需要调整一个参数（见下文）。这导致了GRASP的广泛发展，主要用于运筹学问题（比如路径、位置、图形优化、调度、逻辑、覆盖与划分、最小斯坦树，以及分配）和工业应用（比如制造、运输、电信、计算生物学、图形和地图绘制、电力系统和超大规模集成电路以及其他应用领域）（费斯塔和雷森德，2002，2009b）。GRASP还与其他元启法式方法相结合（费斯塔和雷森德，2009c，2013），其中我们利用Tabu搜索【用于解决多层设施布局问题（拉古娜和维拉德，1991）】，遗传算法【用于二次分配问题（阿莫尼等人，2000；阿胡加等人，2000）】和模拟退火【分别见德拉佩纳（2004）和索斯诺斯卡（2000）关于乡村投递员问题和简化车队分配问题】。
这促使我们将HBB-BC程序和GRASP方法结合，并将其第一次在文中作为重复采样技术而应用到粉末衍射数据中的晶体结构解中去。
下面对传统GRASP的基本组成部分进行简要描述，以及对应用于博览会程序中的改良GRASP版本的主要概念进行了说明。
3.1 传统GRASP
在下面的例子中，我们引用了一个由有限个候选解X={x1，x2，hellip;xn}以及一个目标函数最小化f：X→R所定义的一般优化问题。目的是在X中寻找一个最优解x*，使得f(x*)le;f(x)。
GRASP是一个迭代过程，每个迭代过程包含两个阶段：解的构成以及局部搜索。
3.1.1建设阶段。
这一阶段的目的是从X可行解的集（S）。从空集S开始，一次迭代建立一个元素，如下所示：
（1）每个候选解的目标函数值连同其在X中的最小值（fmin）和最大值（fmax）一起计算。
（2）由目标函数满足以下方程的所有可能候选元素构成的最佳候选列表称为受限候选列表（RCL）：
f(x)isin;[fmin,fmin beta;(fmax-fmin)]（3）
beta;是用于调整极限值[fmin beta;(fmax-fmin)]的参数，根据该值，元素被解读为RCL中的“可能”解或者被拒绝。注意beta;=0的情况对应一个非常特定的策略，而beta;=1则对应一个完全随机的情况。在GRASP过程中，beta;是唯一变化的参数。对于其变化调整，提出不同的策略，包括固定值，接近纯粹贪婪的选择（比如：beta;=0.2）（雷森德和里贝罗，2003，2010）；在[0，1]范围内的随机选择；以及从一组离散的可能值中进行选择，其概率取决于在前一次迭代中获得的解的质量（反应性GRASP）（普雷斯和里贝罗，1999，2000）。后一种选择意味着反应式GRASP在GRASP的无记忆构建阶段包含了一种学习机制。
（3）RCL中的一个可能的参量（x）是随机选择得出的，并且将其合并到正在构造的集合S中；然后从X中移除x，随后对其进行更新。
（4）重复步骤（1）~（3）直到X变为空集。
（5）最终集（S={x}）将被提交到本地搜索中。
3.1.2 本地搜索阶段
与许多确定性方法一样，GRASP生成的解不能保证是最优解。因此，最好应用本地搜索阶段，该阶段处于构造集合S，并且试图通过在其邻域中用一个更好的解替换每个解来反复的改进它。如果没有找到任何改进，则终止本地搜索。
构造阶段和本地搜索在用户定义的多次GRASP迭代中重复，在所有已定义的GRASP迭代中找到的最佳解决方案将作为最终结果保留。
3.2 GHBB-BC算法中的反应式GRASP
在反应式GRASP版本中的GRASP技术经过适当修改，并与HBB-BC程序结合，以用作重复采样技术。它能够改善初始种群，并加速获取良好的结构解决方案。
我们可以考虑使用GRASP对大爆炸产生的候选总体进行抽样，并节省计算时间，但这样的想法或将无法成功实施。事实上，如果我们把Rwp看作GRASP的目标函数，在3.1节中提到的构建阶段的操作（3）会以一个循环的方式结束，并且没有任何改进。从大爆炸初始总体X中删除一个候选解通常不会对X中计算的目标函数的最小值和/或最大值产生改变，并且还会使过程以失败告终。
我们决定在参数搜索空间中应用GRASP的抽样效率来改进第一大爆炸种群中每个候选解，以产生更好的结果并节省时间。
下面描述该算法的主要方面，以及图1中所示的GRASP构造阶段的示例图。
反应式GRASP从大爆炸总体的每个元素（x）开始，并迭代（对于Niter_G循环）执行以下步骤：
（1）产生NGRASP~1.5NDOF个元素，形成该程序中的有限候选解集X（见3.1节）。GRASP构造阶段能够建立元素的有效子集；GRASP局部搜索阶段只提供一个元素，且可能比x更好。NDOF表示模型中存在的内部和外部自由度（DOFs）总数。NGRASP元素是由x的自由度在数量和类型上随机变化而产生的。图1中就有这样一个示例，在具有（x，y，z）平移变量和（theta;，phi;，psi;）旋转变量的刚性片段的情况下，NDOF=6，NGRASP=7。这是非常简单的一种情况，NDOF通常会大于6。在我们的应用程序中NDOF的最大值是38（见第五节）。每个元素中不同的自由度类型由星号“*”表示。
（2）为每个生成的模型计算Rwp值。
图1 GRASP构造阶段示例
NGRASP与产生的元素数量相等，并且DOFs显示了模型中自由度的总数。（a）是GRASP候选解决方案
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236259]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
