How to reduce the computation time and how to improve the quality of the clustering result are the two major research issues. Although several efficient and effective clustering algorithms have been presented, none of which is perfect. As such, an effective clustering algorithm, which is based on the prediction of searching information to determine the search directions at later iterations and employs the k-means as the local search operator to fine-tune the end result, is presented in this paper. Simulation results show that the proposed algorithm is less sensitive to the initial random solution; thus, it is capable of providing a better result than the other clustering algorithms compared in this paper in terms of the quality of the clustering result.