A Binomial Niching Algorithm for Linkage Learning in Estimation of Distribution Algorithm

This paper investigates the diculty for linkage learning with restricted tournament re-placement (RTR), which is the well-known niching on the success of solving dicult problems, such as hierarchical trap problems. It is mysterious that RTR has diculty dealing with concatenated parity function (CPF) problem that is easy for simple GA casually. The cir-cumstance raises the interesting on the behavior of RTR and aiming to discover a new niching mechanism for linkage learning suitably. Due to less literatures discussing about the charac-teristic of RTR, the paper further examines the behavior of RTR and proposes a new niching algorithm to resolve this mysterious case. RTR that has ability to keep diversity on local optimums however stealthily raises the re-lation of independent pairs and results in spurious linkages which cause failure on no-pairwise-linkage CPF problem. The paper proposes a binomial RTR (BRTR) that will conquer dicult problems as well as RTR and meliorate the weakness of RTR to reduce the spurious linkage. As empirical results, BRTR could keep niching ability as well as RTR and resolve the CPF problem as easy as simple GA. This paper gives the idea that it is necessary to design a suited niching for linkage learning techniques