搜索中学习的亚历杭德罗·阿贝莱斯·罗德里格斯在文件中的作用

在搜索过程Alejandro Arbelaez Rodriguez引用此版本：亚历杭德罗·阿贝莱斯·罗德里格斯在搜索中学习。其他[cs.OH]。巴黎第十一大学，2011年。英语NNT：2011 PA 112063。00600523HAL Id：tel-00600523https://theses.hal.science/tel-006005232011年6月15日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireTHE` SEDELpresente'e en vue deDOCTEURDELSpecialite'：INFORMATIQUEpar一个LEJANDRO阿尔贝拉斯·罗德里格斯L收入D 埃塞尔岛从2011年5月31日起，对委员会进行审查Susan L. 爱因斯坦，纽约市立大学亨特学院（特别报告员）Youssef HAMADI，微软研究院（Direct eur de the`se）阿卜杜勒·伊塞尔，LRI（审查员）Eric MONFROY，Université de Nantes/Universidad de Valparaiso（In vite'）Barry O科克大学（特别报告员）Fre 'de'ricSAUBION， 昂热大学（审查员）Thomas SChiex，INRA（审查员）我是SEBAG，CNRS /LRI（Directeur de the`se）微软研究院- INRIA联合中心28 rue Jean Rostand 91893 Orsay Cedex，法国HD THESIS通过一个LEJANDRO阿尔贝拉斯·罗德里格斯L收入D 埃塞尔岛微软研究院- INRIA联合中心28 rue Jean Rostand 91893 Orsay Cedex，法国v确认首先，我要感谢我的主管优素福·哈马迪和米奇·埃勒·塞巴格在此期间不断提供指导和建议我还要感谢Marc Schoenauer给我机会成为TAO研究小组的一员还要特别感谢CamiloRueda和NumbersCatan Numbers，他们支持我申请微软研究院- INRIA联合中心的博士学位我还要感谢苏珊·L。爱泼斯坦、阿卜杜勒·利塞、埃里克·蒙弗罗伊、巴里·我要感谢我的朋友们，他们使我在法国的逗留更加愉快，特别是在大学里：阿尔瓦罗·菲亚略、罗马里奇·戈德尔、雷蒙德·鲁斯、路易斯·达科斯塔、易卜拉欣·阿卜杜拉希、丹尼尔·里基茨和赛义德·贾布里勒。同样在研究实验室外的还有：卡洛斯·奥拉特、安德烈斯·阿里斯蒂扎巴尔、路易斯·皮诺、弗兰克·瓦尔托、埃莱·内·科拉多、西维·马尔伊斯·埃斯卡、塔蒂亚娜·埃尔南德斯和卡洛斯·阿库纳·纳。还有所有在法国和我一起打乒乓球的人：皮埃尔·蒙索、朱利安·克莱德拉、阿尔宾·安德里厄、西尔瓦因·梅鲁格、托马斯·特雷尔、塞巴斯蒂安·加代尔和塞巴斯蒂安·巴尔特·赫莱米，仅举几例。我不得不说，我将错过周六的法国比赛。我也想表达我的感激之情的成员AVISPA研究小组在加利福尼亚州哥伦比亚，以及，mannyy感谢阿尔贝托·德尔加多，朱利安·古铁雷斯，Jor gePe'rez，丹尼尔·里基茨，和卡洛斯·奥拉特校对本论文的一些章节。最后但并非最不重要的是，我要衷心感谢我的家人，我的父母Juan Bautista和Yolanda，我的兄弟Gilma和Juan Carlos，以及我的小侄子Stephan，感谢他们在我一生中在许多方面给予我的支持和鼓励。Alejandro Arbelaez Rodriguez，巴黎，2011年vii摘要自主搜索是约束编程中的一个新兴领域，其动机是将机器学习技术应用于算法选择问题的重要性，并且具有从规划和配置到调度的潜在应用。该领域旨在开发自动工具，以提高搜索算法的性能，以解决组合问题，例如，为约束求解器选择最佳参数设置以求解特定问题实例。在这篇文章中，我们研究了三种不同的观点来自动解决组合问题，特别是约束满足，约束优化和SAT问题。首先，我们提出了domFD，一个新的变量选择启发式，其目标是精确地计算一个简化形式的函数依赖称为弱依赖。然后，这些弱依赖性用于指导每个决策点的搜索。其次，我们从两个不同的角度研究了算法选择问题。一方面，我们回顾了传统的投资组合算法离线学习蛋白质结构预测问题的遗传模型。另一方面，我们提出了连续搜索范式，其目标是让任何用户最终得到他的约束求解器，以实现他们的问题上的最高性能Continuous Search有两种模式：功能模式使用当前的物流模型解决用户最后，最后一部分的SIS，认为增加一个知识共享层，目前的投资组合为基础的并行本地搜索求解SAT的问题。我们发现，通过定期共享并行组合中每个算法的最佳配置，并以特殊方式聚合这些信息，可以大大提高整体性能。ix内容1介绍11.1动机和背景11.2约束编程21.3本论文的贡献31.4论文大纲41.5出版物列表62形式主义92.1约束满足问题92.2完成搜索102.2.1变量和值排序152.3不完整的搜索162.4命题的可满足性问题192.4.1变量选择192.5约束优化问题222.6监督机器学习242.6.1支持向量机2.6.2决策树263相关工作293.1算法选择问题293.1.1SAT30端口x3.1.2QBF34的端口3.1.3CSP35端口3.2优化问题的解决方案373.3每班学习393.4自适应控制413.5其他工作434在基于树的搜索中利用弱相关性474.1一、导言. 474.2约束传播484.3在基于树的搜索中利用弱依赖关系504.3.1弱依赖性504.3.2示例504.3.3计算弱依赖关系524.3.4domFD动态变量排序534.3.5DomFD54的复杂性4.4实验554.4.1问题564.4.2搜索所有解或最优解584.4.3用经典的分支和修剪策略搜索解。584.4.4使用基于重启的分支修剪策略搜索解Egy594.4.5综合624.5以前的工作4.6摘要645构建蛋白质结构预测问题的Portfolio655.1一、导言. 655.2蛋白质结构预测问题665.3特征685.3.1问题特征68xi5.3.2CP features特点695.4算法组合70xii内容5.4.1算法子集选择725.5实验735.6摘要806约束编程中的连续搜索6.1导言. 836.2约束编程中的连续搜索6.3动态连续搜索866.3.1代表实例：特征定义876.3.1.1静态特征886.3.1.2动态特征886.3.2特征预处理896.3.3学习和使用地理模型896.3.4在探索模式下生成示例906.3.5不平衡的例子916.4实验验证926.4.1实验设置926.4.2实际业绩946.4.3探索时间996.4.4适应的力量996.5以前的工作1016.6摘要1027SAT105的高效并行局部搜索7.1导言. 1057.2SAT106并行局部搜索中的知识共享7.2.1使用最佳配置1077.2.2最好的朋友1077.2.2.1排名108xiii7.2.2.2标准化性能1087.2.3重新启动策略1087.3实验109内容xii7.3.1实验设置1097.3.24核的实际性能1107.3.38核的实际性能1147.3.4多样化/集约化权衡7.3.5分析硬件的局限性1187.4以前的工作1237.4.1并行SAT123的完全方法7.4.2并行SAT124的不完全方法7.4.3协作算法1257.5摘要1268结论与展望1278.1主要贡献概述1278.2前景128参考书目131xiii图目录2.1数独112.2sudoku的搜索结果树示例132.3Sudoku resolution step-by-step（Backtracking）142.4数独解决一步一步（本地搜索）182.5SAT例192.6线性支持向量机最优超平面是使到样本的最小距离最大化的超平面。.... 252.7决策树示例263.1算法选择问题的 Rice4.1弱依赖性514.2变量和传播函数525.13SDHA蛋白67的3D构象5.2传统算法组合框架715.3实验验证使用10倍交叉验证和内部for-ward selection病房选择745.4wde gVswde g+755.5使用所有可用的化学品进行实验评估785.6使用正向启发式选择的实验评估795.7全垒打，cp+生物燃料VS全垒打，cp+生物燃料806.1连续搜索场景85图目录xiv6.2dyn-CS：在每个重启点选择最佳试探866.3约束编程中的连续搜索6.4Langford数（LFN）946.5几何（geom）956.6平衡不完全区组设计（BIBD）956.7Job Shop（js）966.8护士排班（nsp）967.1在给定时间内使用4个内核的性能1127.2通过比较，每个点指示使用4cores-Prob（y轴）和4cores-No Sharing（x轴）113求解给定实例的运行时间7.3未解决实例的最佳配置成本比较每个点表示使用4核的给定实例的最佳配置（中值）成本Prob（y轴）和4核-无共享（x轴）1137.4在给定时间内使用8个内核的性能1157.5成对平均汉明距离（x轴）与每106次步骤（y轴）求解unif-k3-r4.2-v16000-c67200-S2082290699-014.cnf实例1197.6解决unif-k3-r4.2-v16000-c67200- S2082290699-014.cnf实例121的单个算法性能7.7使用并行本地搜索组合进行的并行比较，分别为1、4和8份相同的PAWS122副本xv表的列表4.1所有解决方案和最佳解决方案584.2第一个解决方案，分支和修剪策略604.3第一个解决方案，基于重启的策略614.4实验综合625.1氨基酸特征5.2总体策略解决方案成本（5分钟超时）766.1已解决的实例总数（5分钟）976.2已解决的实例总数（3分钟）986.3化学计量学模型的预测准确性（10倍交叉验证）986.4探测时间（小时）（超时3分钟）996.5探测时间（小时）（超时5分钟）996.6已解决实例总数（5分钟）1007.1使用4个核心的总体评价1147.2使用8个核心的总体评价1167.3使用8个核心的多样化-强化分析1201第1章绪论1.1动机和背景如今，人们普遍认为，为给定问题选择正确的算法可能会大大提高解决复杂组合问题的整体性能这是因为，一般来说，没有算法优于所有其他所有可能的问题。为了更准确地理解这一点，我们回顾了没有免费的午餐定理（NFL）[WM 97]，该定理指出，如果没有关于给定类别（或分布）问题的特定知识，就不可能确定给定算法平均比任何其他算法更好。如果一个算法在某一类问题上表现良好，那么它就必须为在所有问题上表现下降而付出代价。剩下的问题。-&WolpertMacready[WM97].有趣的是，在70从广义上讲，这个框架试图使用机器学习来构建一个物流模型。这样的模型主要是一个函数f（x），它将给定的实例x映射到一个算法hi∈{h1，. . .，h n}，其中h n是求解x的最合适的算法，基于某些性能标准（例如，