No label defined (Q4529649)

Normalized epistasis measures links between separate bits in binary strings. It is used in optimization. Unitarian functions (fitness functions \(f\) whose values depends only upon the number of ones rep. zeros in the optimized binary string) with extreme epistasis are theoretically studied. The epistasis of a binary string \(s = s_{l - 1} \cdots s_0\) of length \(l\) with respect to a population \( P = \{0,1 \}^l \) of size \(N\), where \(\Omega _{i,s_i }\) consists of all strings \(\Omega\) which have value \(s_i\) at position \(i\) \[ \varepsilon (s) = \varepsilon _\Omega (s) = f (s) - \sum _{i = 0}^{l - 1} 1/2^{l - 1} \sum _{t \in \Omega _{i,s_i}} f(t) + l-1/2^l\sum _{t \in \Omega } f (t). \] The global epistasis of \(f\) is defined as \[ \varepsilon _l (f): = \sqrt {\sum _{s \in \Omega } {\varepsilon ^2 (s)} }. \] The normalized epistasis of \(f\) is defined as \(\varepsilon _l^2 (f) = \varepsilon _l^2(f /|f|)\) The vector \(h\) is used, \[ h = \left ({ \begin{matrix} {f ({0 \ldots 00})} \\ {f\left ({0\ldots 01}\right)} \\ \vdots \\ {f\left ({1 \ldots 11} \right)} \end{matrix} } \right) \in \mathbb{R}^{l + 1}. \] A matrix \(G_l = ({g_{ij} })\), \(g_{ij} = l + 1 - 2d _{ij}\) for all \(0 \leq i,j \leq 2^l - 1\) is defined, where \(d_{ij}\) is the Hamming distance between binary strings \(i\) and \(j\). A square matrix \(B_l\) with dimension \(l+1\) is needed, such that \(^t fG_l f = ^t_ hB_l h\), so that the definition of the normalized epistasis is \[ \varepsilon _l^* (f) = 1 - \frac {1}{2^l} \frac {{}^thB_l h}{\sum _{p = 0}^l \binom {l}{p} h_p}. \] A theorem is proved, that for any \(0 \leq p,q \leq l\), the components of the matrix \(B_l\) are \[ b_{pq}^l = \binom {l}{p}\binom {l}{q} \left (1 + \frac {(l - 2p)(l - 2q)} {l} \right). \] Further proofs and experimental results concerning optimization of genetic algorithms are also given.