Building-block identification by simultaneity matrix

Abstract

The simultaneity matrix is an l x l matrix of numbers. The matrix is constructed according to a set of l-bit solutions. The matrix element m[subscript ij] is the degree of linkage between bit positions i and j. We partition {0,...,l-1} by putting i and j in the same partition subset if m[subscript ij] is significantly high. The partition represents the bit positions of building blocks. The partition is exploited in solution recombination so that the bits governed by the same partition subset are passed together. It can be shown that identifying building blocks by the simultaneity matrix can solve the additively decomposable functions (ADFs) and hierarchically decomposable functions (HDFs) in a polynomial relationship between the number of function evaluations required to reach the optimum and the problem size. A comparison to the hierarchical Bayesian optimization algorithm (hBOA) is made. The hBOA uses less number of function evaluations than that ofour algorithm. However, computing the matrix is 10 times faster and uses 10 times less memory than constructing Bayesian network