Molecular signatures of cancer, e.g., genes or microRNAs (miRNAs), have been recognized very important in predicting the occurrence of cancer. From gene-expression and miRNA-expression data, the challenge of identifying molecular signatures lies in the huge number of molecules compared to the small number of samples. To address this issue, in this paper, we propose a heuristic algorithm to identify molecular signatures, termed HAMS, for cancer diagnosis by modeling it as a multi-objective optimization problem. In the proposed HAMS, an elitist-guided individual update strategy is proposed to obtain a small number of molecular signatures, which are closely related with cancer and contain less redundant signatures. Experimental results demonstrate that the proposed HAMS achieves superior performance over seven state-of-the-art algorithms on both gene-expression and miRNA-expression datasets. We also validate the biological significance of the molecular signatures obtained by the proposed HAMS through biological analysis.