A Pareto-based evolutionary multi-objective approach is adopted to optimize the functionals in the Trace Transform for extracting image features that are robust to noise and invariant to geometric deformations such as rotation, scale and translation (RST). To this end, sample images with noise and with RST distortion are employed in the evolutionary optimization of the Trace Transform, which is termed evolutionary Trace Transform with noise (ETTN). Experimental studies on a fish image database and the Columbia COIL-20 image database show that the ETTN optimized on a few low-resolution images from the fish database can extract robust and RST invariant features from the standard images in the fish database as well as in the COIL-20 database. These results demonstrate that the proposed ETTN is very promising in that it is computationally efficient, invariant to RST deformation, robust to noise and generalizable.