Predicting Epistasis from Mathematical Models
Predicting Epistasis from Mathematical Models
复制标题
DOI：
10.1162/evco.1999.7.1.69
复制
发表时间：
1999-03-01
影响因子：
6.8
通讯作者：
Whitley, Darrell
中科院分区：
文献类型：
--
作者：
Heckendorn, Robert B.;Whitley, Darrell
传统上，上位性要么通过沃尔什系数精确计算，要么通过抽样估计。精确计算通常具有理论意义，因为计算通常随域中比特数呈指数增长。给定评价函数，上位性也可以通过抽样来估计。然而，这种方法使我们对上位性的起源了解甚少，而且容易产生抽样误差。本文给出了可以用数学表达式表示的问题的上位界的定理。这将导致大量的计算节省，以限制问题的难度。此外，在数学背景下使用这些定理，人们可以深入了解上位性的数学起源，以及如何减少问题的上位性。我们提出了几个新的度量上位性，并给出了经验证据和例子来证明定理的应用。特别地，我们证明了一些函数显示“奇偶性”，这样通过选择一个定义良好的表示，奇数或偶数索引的所有Walsh系数都变为零，从而减少了函数的非线性。
Classically, epistasis is either computed exactly by Walsh coefficients or estimated by sampling. Exact computation is usually of theoretical interest since the computation typically grows exponentially with the number of bits in the domain. Given an evaluation function, epistasis also can be estimated by sampling. However this approach gives us little insight into the origin of the epistasis and is prone to sampling error.This paper presents theorems establishing the bounds of epistasis for problems that can be stated as mathematical expressions. This leads to substantial computational savings for bounding the difficulty of a problem. Furthermore, working with these theorems in a mathematical context, one can gain insight into the mathematical origins of epistasis and how a problem's epistasis might be reduced. We present several new measures for epistasis and give empirical evidence and examples to demonstrate the application of the theorems. In particular, we show that some functions display "parity" such that by picking a well-defined representation, all Walsh coefficients of either odd or even index become zero, thereby reducing the nonlinearity of the function.