Building-block identification by simultaneity matrix

doi:10.1007/s00500-006-0097-z

Building-block identification by simultaneity matrix

2006-05-24

7

PRE

AI

C

Chatchawit Aporntewan *

DOI：10.1007/s00500-006-0097-z

原文链接

原文求助

摘要

En 中文

This paper presents a study of building blocks (BBs) in the context of genetic algorithms (GAs). In GAs literature, the BBs are common structures of high-quality solutions. The aim is to identify and maintain the BBs while performing solution recombination. To identify the BBs, we construct an l x l simultaneity matrix according to a set of l-bit solutions. The matrix element in row i and column j denoted by m(i j) is the degree of dependency between bit i and bit j. We search for a partition of {0,..., l - 1} for the matrix. The main idea of partitioning is to put i and j of which mi j is significantly high in the same partition subset. The partition represents the bit positions of BBs. 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 by exploiting the simultaneity matrix the additively decomposable functions can be solved in a polynomial relationship between the number of function evaluations required to reach the optimum and the problem size. A comparison to the Bayesian optimization algorithm (BOA) is made. Empirical results show that the BOA uses less number of function evaluations than that of our algorithm. However, computing the matrix is ten times faster than constructing the Bayesian network.

Building-block identification by simultaneity matrix

摘要

期刊

机构

引用论文