论文标题
基于沃尔什系数的新型度量，以测量分布算法估计问题难度
Novel Metric based on Walsh Coefficients for measuring problem difficulty in Estimation of Distribution Algorithms
论文作者
论文摘要
分布算法的估计是进化算法，这些算法使用从人群中提取的信息而不是传统的遗传算子来生成新的解决方案。该信息表示为概率模型，这些算法的有效性取决于这些模型的质量。但是，一些研究表明，即使多元EDA也无法在某些问题中构建适当的模型。通常，在这些问题中，变量之间存在内在的成对独立性。在文献中，很少有研究研究问题无法解决问题的难度和性质。本文提出了一个新的指标，用于通过检查EDA中的模型构建机制的特性来衡量问题难度。为此，我们使用依赖和自变量的估计沃尔什系数。该指标用于评估EDA中一些众所周知的基准问题的难度。使用不同指标（例如健身距离相关性（FDC））来比较提出的指标测量方法的EDA难度。结果表明，所提出的指标可以准确地预测EDA在不同问题中的性能。
Estimation of distribution algorithms are evolutionary algorithms that use extracted information from the population instead of traditional genetic operators to generate new solutions. This information is represented as a probabilistic model and the effectiveness of these algorithms is dependent on the quality of these models. However, some studies have shown that even multivariate EDAs fail to build a proper model in some problems. Usually, in these problems, there is intrinsic pairwise independence between variables. In the literature, there are few studies that investigate the difficulty and the nature of problems that can not be solved by EDAs easily. This paper proposes a new metric for measuring problem difficulty by examining the properties of model-building mechanisms in EDAs. For this purpose, we use the estimated Walsh coefficients of dependent and independent variables. The proposed metric is used to evaluate the difficulty of some well-known benchmark problems in EDAs. Different metrics like Fitness Distance Correlation (FDC) are used to compare how well the proposed metric measures problem difficulty for EDAs. Results indicate that the proposed metric can accurately predict the EDA's performance in different problems.
