This paper presents a method for optimal sizing of truss structures based on a refined self-adaptive step-size search (SASS) algorithm. An elitist self-adaptive step-size search (ESASS) algorithm is proposed wherein two approaches are considered for improving (i) convergence accuracy, and (ii) computational efficiency. In the first approach an additional randomness is incorporated into the sampling step of the technique to preserve exploration capability of the algorithm during the optimization. Furthermore, an adaptive sampling scheme is introduced to enhance quality of the final solutions. In the second approach computational efficiency of the technique is accelerated through avoiding unnecessary analyses throughout the optimization process using the so-called upper bound strategy (UBS). The numerical results indicate the efficiency of the proposed ESASS algorithm. (C) 2014 Elsevier B.V. All rights reserved.