In fractal image compression a partitioning of the image into ranges is required. In our previous work [SR96] we have proposed to find good partitionings by means of a split-and-merge process guided by evolutionary computing. In this approach ranges are connected sets of small square image blocks. Far better rate-distortion curves can be obtained as compared to traditional quadtree partitionings, however, at the expense of an increase of computing time. In this paper we show how conventional acceleration techniques and a deterministic version of the evolution reduce the time-complexity of the method without degrading the encoding quality. Furthermore, we report on techniques to improve the rate-distortion performance and evaluate the results visually.