Investigation on efficiency of optimal mixing on various linkage sets

The optimal mixing operator (OM) utilizes linkage sets (LSs) to exchange the information of variables between a pair of solutions, and the result of such exchange is adopted only if the exchange leads to improvement of the solution quality. The performance of OM highly depends on the LS it uses. This paper demonstrates that previously proposed LS, the linkage tree model (LT), does not yield the optimal performance. To measure the efficiency of OM on different LSs, the cost-performance (CP) index is defined. Both our CP index and experiments indicate (1) that for fully separable problems, the most suitable LS is the marginal product model (MP), and (2) that for separable problems with overlap, LT is more suitable than MP, and (3) that properly pruned LT leads to higher efficiency and yields a better performance, and (4) that the LS that properly reflects the problem structure yields the best performance on both fully separable problems and problems with overlap.