优化算法性能的自动分析研究

We will develop a new automated experimental methodology for the field of optimization which can achieve better conclusions about algorithm performance than what researchers can do by hand. It will be applicable to any optimization problem and any optimization algorithm. As we show, the experimental analysis of optimization algorithms has several limitations and flaws. The potential of modern machine learning technologies for discovering high-level information about algorithm performance is entirely untapped. Our project will change that. Our methodology will automatically answer questions such as: Which instances of an optimization problem are hard for which the algorithms? Which features make them hard? What is the relationship of the parameter settings of an optimization algorithm and the algorithm's performance? It will automatically discover the strengths and weaknesses of optimization algorithms. It will automatically suggest additional experiments and suggest which algorithms should be hybridized with each other for better performance. We investigate robust statistics for comparing the runtime behavior of algorithms. We define machine learning and data mining techniques to extract high-level conclusions from experimental data. We will use such information to automatically make suggestions how to improve algorithm performance. We implement this as open source tool.

我们的项目将为优化研究领域研发一套全新的自动化的实验评价方法。相比于手工评价，该方法可以获得更好的关于算法性能的评价结果。本方法可广泛地应用到任何优化问题和优化算法。目前，优化算法的实验分析有不少局限和缺陷，而用现代机器学习技术来发现算法性能的高层次信息的潜力还没有被开发。我们的项目将改变这种局面。我们的方法将自动回答以下问题：某个优化问题下的哪些实例对于哪些算法来说较难？哪些特征使这些实例更难？优化算法的参数设置和算法行为之间的关系是什么？我们的研究尝试自动发现优化算法的优点和缺点，并自动给出追加实验的建议以及算法混合与组合的建议。我们将具有鲁棒性的统计方法来比较算法的运行时行为。我们将利用机器学习，数据挖掘和大数据等技术来从实验数据中获得高层次的结论，并使用这些高层次信息来给出提高算法性能的建议。我们将会实现这套方法作为开源工具。

本项目的目标是面向优化领域探究一种新的自动化实验方法，可适用于任何优化问题和任何优化算法，并较传统手工设计方法，可获得更好的算法性能结果。 经四年期的专题研究，课题组已成功实现这一目标，公开发表了该方法的相关定义与结论，并用于若干有重要意义的优化任务。 长期以来，优化算法的实验分析存在着一定的局限性和缺陷。 现代机器学习技术在发现优化算法性能的高层次信息方面的潜力尚未得到充分挖掘。 本项目的研究改变了这一现状。 近年来，课题组致力于该方向的研究，项目负责人发表了多项研究成果，积极组织了多个领域内建设性工作，主编了一本中科院SCI一区杂志的特刊，同时是篇关于优化基准测试的社区驱动最佳实践论文的章节负责人。 本项目所提出的方法可以自动回答以下问题：对于某一优化问题，不同优化算法的哪些实例是难的？何种功能使它们变得困难？优化算法的参数设置与算法性能之间是什么关系？ 可以自动发现优化算法的优点和缺点，实际上已产生了一些非常有趣的新发现，正如发表的几篇论文。 对于比较算法的运行时行为，课题组同时研究了鲁棒的数据统计，重新定义了机器学习和数据挖掘技术，以从实验数据中提取高层次的结论。 这不仅形成了有关如何提高算法性能的建议，而且还发现了优化算法模块以前未知的问题。 本项目所提出的方法皆已实现为开源工具，并发布在GitHub，可有广泛用于优化领域。