Fitness Landscape Analysis for Optimum Multiuser Detection Problem

摘要

Optimum multiuser detection (OMD) for CDMA systems is an NP-complete combinatorial optimization problem. Fitness landscape has been proven to be very useful for understanding the behavior of combinatorial optimization algorithms and can help in predicting their performance. This paper analyzes the statistic properties of the fitness landscape of the OMD problem by performing autocorrelation analysis, fitness distance correlation test and epistasis measure. The analysis results explain why some randomsearch algorithms are effective methods for OMD problem and give hints how to design more efficient randomized search heuristic algorithms for OMD.