This paper presents evolutionary multi-objective approaches to tune parameters in Trace transform for invariant feature construction. It is well-known that the Trace transform involves three functionals applied consecutively to the image to produce real numbers called Triple features representing the input image. Traditionally, these functionals are chosen empirically, and the image sampling parameters are fixed. These parameters play important roles in the transform because they directly affect the computational complexity and robustness. In this paper, we propose tuning the Trace sampling parameters in addition to choosing the three functionals. First, by adopting two-objective evolutionary algorithms using the within-class variance and between-class variance. Second, by adopting three-objective evolutionary algorithms to consider the computational complexity as a third objective. Two different coding schemes are considered, which are integer-coding and real-coding schemes. Experimental results show that integer coding scheme presents a better performance compared to the real coding scheme. Moreover, while the three-objective approach enforces a balance between robustness and computational complexity, without enforcing a minimum acceptable accuracy, features extracted tend to have a lower computational complexity at the expense of the accuracy, compared with the two-objective case.