In this paper, we present a scheme for efficient hummingbased music retrieval. For that purpose, we first describe how to extract a sequence of pitch and duration pairs as its feature information from sung or hummed query accurately and automatically. And then, we propose a novel scheme for reformulating user query to improve retrieval performance. The scheme is based on user relevance feedback with genetic algorithm. We implemented a prototype system based on these scheme and performed various experiments. Experimental result shows that our proposed scheme achieves an impressive performance.