The emergence of digital cameras in recent years has led to an exponential increase in the amount of digital photographic images and the need for automatic image indexing and retrieval systems. In this paper, an efficient genetic algorithm-based image retrieval strategy is proposed where user relevance feedback based on regions of interest is employed to improve the retrieval efficiency. The combination of low-level features from the selected regions forms the chromosomes of the genetic algorithm used for retrieving the target images. The user relevance feedback is used to direct the advanced search. Furthermore, the retrieval performance is improved by mining association rules from the recorded feedback. Experimental results verify the effectiveness and scalability of the approach both in terms of retrieval precision and recall rates.