A Quantitative Approach for Validating the Building-block Hypothesis
Chatchawit Aporntewan, Prabhas Chongstitvatana · 2005
The building blocks are common structures of high-quality solutions. Genetic algorithms often assume the building-block hypothesis. It is hypothesized that the high-quality solutions are composed of building blocks and the solution quality can be improved by composing building blocks. The studies of building blocks are limited to some artificial optimization functions in which it is obvious that the building blocks exist. A large number of successful applications have been reported without a strong evidence that proves the hypothesis. This paper proposes a quantitative approach for validating the building-block hypothesis. We define the quantity of building blocks and the degree of discontinuity by using the chi-square matrix. We test the building-block hypothesis with 15-bit onemax, 5/spl times/3-trap, parabola 1 -(x/sup 2//10/sup 10/), and two-dimensional Euclidian traveling salesman problem (TSP). The building-block hypothesis holds for onemax, 5/spl times/3-trap, and parabola. In the case of parabola, Gray coding gives a higher quantity of building blocks than that of binary coding. The hypothesis is accepted for random instances of TSP with a low confidence.