Due to the recent availability of high quality small molecule databases, such as ZINC and PubChem,1,2 virtual screening is playing an even more important role in identifying biologically relevant molecules in drug discovery campaigns. The success of pharmacophore-based virtual screening (PBVS) relies largely on the accuracy and specificity of the pharmacophore query employed. Deriving a pharmacophore query from a single structure inevitably introduces uncertainty, and the derived query is unlikely to be optimal against every collection of input compounds, especially when it is desired to discriminate among compounds with similar chemical structures. In this study, we present an optimization approach empowered by genetic algorithms (GA) to enhance the accuracy and specificity of a primary pharmacophore query. The example utilized is the human melanocortin type 4 receptor (hMC4R), for which the pharmacophore query was built on the basis of the structure of a rigid cyclic peptide agonist.(3) The optimized query is shown to be capable of identifying 37 positive hMC4R agonists with no false positives from a training set containing 55 agonists and 51 nonagonists. This represents a significant improvement from the initial query which exhibited a 37/32 hit rate. The final, optimized query is challenged with a testing set comprising of 55 hMC4R agonists and 50 nonagonists and achieves a hit rate of 33/8, that improved from 40/31. The impact of GA controlling parameters, including mutation rate, crossover rate, fitness function, population size, and convergence criterion, on performance of optimization are examined and discussed.