A test problem with difficulty in decomposing into sub-problems for model-based genetic algorithms

Fully or nearly decomposable problems have been often used as test problems in genetic algorithm (GA) researches. The two types of problems have the common feature that all bits in each sub-problem are used for calculating its fitness value. The present model-based GAs appropriately decompose the whole of such a problem into parts and efficiently solve it. However, so far there has not been a test problem in which sub-problems are overlapped and bits of each sub-problem in the overlapped parts used for calculating a fitness value of the sub-problem vary depending on a bit pattern of a given solution candidate. This type of problems might cause difficulty in the decomposition to model-based GAs. In the study we propose the overlapped chains problem (OCP) as this type of problem. The results of applying several GAs to instances of the OCP show that some model-based GA cannot yield better search performance than a simple operator-based GA.