It is an interesting and important issue to identify a small set of useful features from a high dimensional data that can be used to design a classification mechanism. Usually, researchers prefer to find the features that have high relevance, in the sense that the correlation of each of those features with class labels is high or the mutual information between each of the features and class labels is high. Such approaches usually end up finding features that may be linearly dependent with each other. For some biological studies, it may be interesting to find a set of genes (features), which have high relevance with the class labels and also the genes are nonlinearly dependent-we explicitly want to exclude relevant genes that are linearly correlated among them. Although, our primary focus in this study is to find such genes from microarray data sets, such features may also be important in other studies. In this study, the Combinations of Relevantly Non-linear Dependency Subsets (CoRNDS) is proposed to tackle such the multi-objective problem. It opens up a good to simultaneously control selection of number of useful features, optimize the relevance between the selected features with class labels, and the non-linear dependency between the selected features. Using innovative ways we design three new objectives and optimize them by using the well-known multi-objective evolutionary algorithm based on decomposition (MOEA/D) method. To the best of our knowledge, this is the first attempt to feature (gene) selection along with identification of non-linear dependency between features via a multi-objective strategy. Experimental results show that the feasibility and effective performance on microarray cancer dataset. As to these selected gene subsets, investigate their auxiliary role of co-regulation in the biological pathways, and the occurrence in the pathogenesis of cancer are interesting future works.