Scatter Search is a population-based metaheuristic that emphasizes systematic processes against random procedures. A local search procedure is added to a Scatter Search for Biclustering in order to improve the quality of biclusters. This local search constitutes the existing Improvement Method in most of Scatter Search schemes which intensifies the optimization process, and, consequently, improves the quality of biclusters according to a fitness function. The fitness function is based on linear correlations among genes and, therefore, biclusters with shifting and scaling patterns are obtained. Thus, the improvement of a bicluster consists in removing every pair of genes of such bicluster that has a correlation lower than a given threshold which is automatically chosen by the algorithm. Experimental results from a Yeast microarray data set with different stress conditions have been reported and compared to another algorithm based on Scatter Search recently published in the literature. Experiments show a remarkable performance of the Biclustering algorithm with the proposed local search. © 2011 IEEE.