Truss optimization under natural frequency constraints allows a designer to control the selected frequencies in order to improve the dynamic characteristics of a structure. Therefore, the truss optimization with frequency constraints has been receiving multiple efforts in the last decades. On the other hand, to decrease the truss mass, abrupt frequency changes are generated. Thereby, traditional gradient-based methods present difficulty in truss optimization, often converging to local optima. Thus, many researches have been applying evolutionary algorithms to this task of optimizing trusses with frequency constraints. Therefore, this work has used 4 algorithms, Genetic Algorithm (GA), Simulated Annealing (SA), Particle Swarm Optimization (PSO) e Heuristic Kalman algorithm (HKA), in order to optimize two truss models that are typical benchmarks in the literature, the 10-bar planar truss and the 72-bar spatial truss. From the present study, statistical graphs were generated for the performance of these algorithms in each problem, which were also compared to results in the literature that have used other algorithms for this same purpose. Among the studied algorithms, HKA has obtained the best average value for the objective function for both trusses. Furthermore, some pure algorithms from the present work have obtained better results than recent improved algorithms in the literature. Thus, the no free lunch (NFL) theorem was verified, that affirms that there is no better algorithm than other when evaluated in an average of all possible problems.