通过长度尺度分析和比较黑箱优化的问题景观( Analysing and comparing problem landscapes for black-box optimization via length scale )

R Morgan Length scale Black-box optimization Problem analysis Fitness landscapes Information distance

优化问题具有基本的实际意义，几乎可以在人类努力的各个方面找到。然而，值得注意的是，我们对优化问题的本质以及不同算法如何、为什么和何时表现良好或较差的理解非常有限。问题景观的概念抓住了目标函数和问题变量之间的关系。很明显，这种景观的结构对于理解优化问题至关重要，然而对这种结构的分析提出了重大挑战。除了问题场景通常是高维的外，黑箱设置中可用的信息仅限于可行搜索空间中的解及其各自的目标函数值。景观分析在优化文献中受到了一些关注，主要是在进化计算中。然而，这项工作有一些重要的局限性，以及围绕其实际效用的许多开放问题。本文提出了一种利用黑箱信息分析优化问题的新框架和实用技术。提出了长度尺度的概念，作为组合优化问题和连续优化问题的基本特征。建立了给定问题的长度尺度及其分布的解析性质。采用统计学、集合论、可视化和机器学习等技术对采样长度尺度值进行总结和解释。从长度尺度分布出发，利用熵Jeffrey散度提出了一种问题相似度量。这提供了一种方法来比较任意的黑箱优化问题，在组合或连续问题之间可能不同的维数。基于Kolmogorov复杂性理论中的信息距离概念，提出了一种通过长度尺度信息量化优化问题相似度的方法。信息距离是两个任意物体之间的通用距离度量，在实践中可以通过归一化压缩距离来近似，这依赖于感兴趣问题的二进制表示和无损压缩器。提出了一种在最优化环境下计算归一化压缩距离的新方法。所提出的技术通过连续人工、基准和现实世界代表性问题的实验以及NP难类组合问题的实例得到了实现和广泛的评价。结果表明，长度尺度特征对于比较和刻画优化问题具有很高的有效性和鲁棒性。计算的长度尺度分布之间的Jeffrey发散和归一化压缩距离能够识别问题之间已知的相似性，也为问题之间的关系提供了有价值的见解。两种相似度量的结果都清楚地反映了组合问题实例的难度和结构的已知相变。考虑到在分析中只使用黑箱信息，这是值得注意的。最后，研究了Jeffrey散度与归一化压缩距离之间的理论和经验关系。这些特征是不同的，但在概念上是相关的，并提供了补充的经验信息。

SciDown文献求助系统（解决99%问题） Public Download 掌桥科研 espace.library.uq.edu.au espace.library.uq.edu.au