We present a new iterative feature construction approach for supervised learning model based on the meta-heuristic Harmony Search (HS) algorithm and Cartesian Genetic Programming. We propose a novel method to incorporate soft information about the relevance of the constructed features in the HS algorithm so as to enhance its convergence. The performance of the proposed scheme is assessed over datasets from the literature, with promising results that support its suitability to deal with legacy datasets.