MOEA/D with chain-based random local search for sparse optimization

The goal in sparse approximation is to find a sparse representation of a system. This can be done by minimizing a data-fitting term and a sparsity term at the same time. This sparse term imposes penalty for sparsity. In classical iterative thresholding methods, these two terms are often combined into a single function, where a relaxed parameter is used to balance the error and the sparsity. It is acknowledged that the setting of relaxed parameter is sensitive to the performance of iterative thresholding methods. In this paper, we proposed to address this difficulty by finding a set of nondominated solutions with different sparsity levels via multiobjective evolutionary algorithms (MOEAs). A new MOEA/D is developed specifically for sparse optimization, in which a chain-based random local search (CRLS) is employed for optimizing subproblems with various sparsity levels. The performance of the proposed algorithm, denoted by MOEA/D-CRLS, is tested on a set of sixteen noise-free or noisy test problems. Our experimental results suggest that MOEA/D-CRLS is competitive regarding the solution precision on the noise-free test problems, and clearly superior on the noisy test problems against three existing representative sparse optimization methods.