约束求解算法自动配置研究

发布时间：2020-07-22 13:42

【摘要】：各种经典、元启发式约束求解算法在求解NP难题(NP-hard)时的性能通常取决于其参数配置。事实上,为一个算法配置一个合适的参数一直以来都被认为是一个重要的任务,这就给每个算法设计者和用户留下了一个问题:如何正确配置算法参数?在过去,人们一直使用手动方式进行参数配置,通过对各种算法的研究发现,手动处理参数事实上是个很复杂的问题,需要不断在运行过程中改变参数,开销大量的时间去测试程序以使之达到理想效果。这无疑是件很麻烦的事情,既浪费人力、物力、财力,也给程序员的编程带来了困扰。而且通过经验法或者试错法来进行优化,不仅耗时耗力还很容易出错,有时,它通常还会导致不同算法的不均匀优化。此外,通过试错法优化过度依赖直觉和算法开发者的经验,而该方法难以和严格的数学证明对应起来,因此手动参数配置不具有推广性。近些年,参数优化算法逐渐成为算法发展过程的重要组成部分。许多高性能算法都具有众多参数,参数配置对控制算法行为有重要影响,特别对于难解优化问题的求解算法尤是如此。寻找启发式算法性能优化的参数配置通常需要耗费相当大的开销。在多数情况下,参数配置都是以繁琐复杂的手工操作进行,对于配置人员的素质要求极高,因此自动化参数配置研究具有重要的实用意义。不仅如此,算法自动配置还有如下优点,它能够减少开发时间和人为的主动干预;能够为算法设计提供更加有力的技术支持;能够利用计算能力探索算法设计空间;能够为更高层次的任务释放人类的创造力;能够为算法设计者在设计程序时提供帮助。配置复杂算法参数是一个高度劳动密集型的工作,消耗整体开发时间的很大一部分。使用算法自动配置方法可以显著节省时间,甚至得到潜在的更好结果。在比较启发式算法性能时的核心问题是:如何使算法在本质上更胜一筹,该算法的成功原因是开发人员更成功地优化了其参数。算法的自动配置方法可以减轻不公平比较这个问题,从而促进更有意义的比较研究。复杂启发式算法求解困难实例的能力往往取决于参数的合适配置。而用户往往很少了解有关于算法参数配置对其性能的影响,因此简单地使用默认配置。即使算法已经经过标准的基准组精心优化,默认配置可能不是遇到的特定问题的实例的最佳配置,算法也就不能呈现最佳性能。算法的自动配置方法可以以一种根本性的便捷的方式改善算法性能。本文首先介绍了算法配置,算法配置问题的定义和相关概念,接下来又介绍了解决算法配置问题的一些方法,主要进行了两个方面的研究:(1)深入研究了目前流行的并有重要影响的算法自动配置参数的软件irace。使用irace软件为acotsp程序自动的配置参数,通过对参数在不同的配置下得到的结果进行细致的分析,相互比较,使得我们对算法自动配置有了更深一步的理解。(2)基于流行的ParamlLS算法配置框架,进行了约束求解器级别的算法自动配置的尝试,实验结果表明,约束求解器级别的算法自动配置对于约束求解效率提升明显。当然,约束求解算法以及约束求解器的自动配置还处于一个比较初级的水平,未来希望能对于约束求解算法进行更为深入的研究,从算法自动配置的角度为研究高效约束求解算法提供一种可能。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP301.6
【图文】：

实验结果

第 3 章 基于 irace 的约束求解算法自动配置在第二次迭代结束后，软件挑选出 26 个候选配置，并对候选配置各个参数进行描述，还生成了 2 个精英候选配置。如图 3.4

第 3 章 基于 irace 的约束求解算法自动配置在第三次迭代结束后，软件挑选出 6 个候选配置，并对候选配置各个参数进行描述，还生成了 4 个精英候选配置。如图 3.5

【相似文献】

相关期刊论文 前10条

1 李康乐;;算法“塑造世界”客观吗[J];中国报业;2018年11期

2 ;聚焦核心素养案例研讨专题二:体验编程计算,初步了解算法[J];中国信息技术教育;2017年08期

3 李亚娟;刘建贞;张兴刚;邓重阳;;结合科研的计算机辅助几何设计教学[J];数学学习与研究;2017年17期

4 何克晶;张星明;郑运平;;算法设计与分析课程全方位实践教学改革探索[J];计算机教育;2017年02期

5 李勇;;基于实践性教学的《算法设计与分析》教学研究[J];曲靖师范学院学报;2015年06期

6 张远平;邱丽娜;;在算法设计与分析课程教学中融入计算思维[J];价值工程;2016年08期

7 秦丹;;算法设计与分析教学常见问题分析[J];电脑知识与技术;2014年24期

8 黄如兵;杨鹤标;;算法设计与分析课程的教学与实践探索与研究[J];科教文汇(上旬刊);2015年03期

9 纪颖;;算法设计与分析课程教学改革探讨[J];黑龙江教育学院学报;2014年08期

10 李秦;;建构主义教学模式与算法设计与分析课程教学[J];甘肃科技;2013年24期

相关会议论文 前10条

1 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

2 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

3 韩进宏;张先峰;王运凯;;表面粗糙度频谱分析C++算法设计[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

4 高文超;孙宇清;韩冬雪;;一种改进的素数寻找问题的算法设计与实现[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

5 杨俊;关旭东;;板形控制液压弯辊系统的特性分析与控制算法设计[A];1996中国控制与决策学术年会论文集[C];1996年

6 黄翔东;李海亮;王玲;;光时域反射仪的事件检测算法设计[A];第六届全国信号和智能信息处理与应用学术会议论文集[C];2012年

7 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

8 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

9 宋琦;陈璞;;有限元分析中结构修改的算法设计[A];北京力学会第18届学术年会论文集[C];2012年

10 杨利容;;用优化算法设计双工器[A];中国航海学会通信导航专业委员会2005年学术年会论文集[C];2005年

相关重要报纸文章 前8条

1 赵丹;大数据算法的困境[N];学习时报;2017年

2 ;算法设计的策略[N];电脑报;2003年

3 武卫;通过算法来思考世界[N];财会信报;2018年

4 陆峰;大数据健康发展需要新机制护航[N];学习时报;2019年

5 李健 周胜利;懂算法才能打“算法战”[N];解放军报;2019年

6 本报记者 霍光;从算法设计角度推进网络节能[N];中国计算机报;2012年

7 林东;迎接算法决定战法的时代[N];解放军报;2018年

8 胡捷递　记者 姜雪松;“计算机奥运会”将在哈举行[N];哈尔滨日报;2010年

相关博士学位论文 前10条

1 王子玉;网络异常检测算法研究[D];清华大学;2017年

2 陈培;探测复杂疾病临界点的算法[D];华南理工大学;2018年

3 李莹玉;基于分布式ADMM算法的无线网络资源管理与大数据分析[D];西安电子科技大学;2018年

4 蒋海青;开放式低碳选址—路径模型及其算法研究[D];浙江工业大学;2019年

5 张雪;图像处理中的若干非凸建模，算法及应用[D];上海交通大学;2017年

6 王普;多标记学习算法研究及在生物医学数据挖掘中的应用[D];中国科学院大学(中国科学院深圳先进技术研究院);2017年

7 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

8 张磊;约束优化算法的关键技术研究及应用[D];哈尔滨工程大学;2016年

9 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

10 刘院英;社会网络影响最大化方法研究[D];燕山大学;2017年

相关硕士学位论文 前10条

1 吴云鹏;约束求解算法自动配置研究[D];吉林大学;2019年

2 夏志雄;动力电池管理单元及其SOC估算算法的研究与实现[D];武汉理工大学;2018年

3 初星汉;基于蚁群算法的专家抽取系统设计与实现[D];大连理工大学;2018年

4 刘凌云;基于Q-学习算法的序列决策模型研究[D];河北大学;2019年

5 李鹏清;基于SimRank及密度的聚类算法[D];广西师范大学;2019年

6 张煜;强化学习中基于函数逼近的多步统一算法研究[D];浙江大学;2019年

7 房永峰;基于深度学习的牲畜目标检测与跟踪算法研究[D];中国科学技术大学;2019年

8 忻晓雯;LTE系统资源分配的算法研究[D];上海交通大学;2017年

9 杨欣;基于正交化学反应优化算法的社团检测研究与实现[D];河南大学;2018年

10 曾凤华;护士周排班算法研究及其系统实现[D];华南理工大学;2018年

本文编号：2765890