Full waveform inversion (FWI) is a state-of-the-art method used to estimate subsurface parameters, such as the seismic velocity. FWI is an iterative method that requires an adequate starting velocity (SV) model as input, to converge to the correct solution. A SV model is considered adequate for the FWI when its low frequencies are correctly estimated or cycle-skipping events are not present. Currently, some strategies have been used to build SV models such as analytical methods, reflection tomography, and global optimization methods. In this work, we focus on the use of particle swarm optimization (PSO), which estimates a SV model by minimizing the number of cycle-skipping events can be measured in three different domains: time, frequency and complex trace domain. The computational cost of the proposed PSO method for SV estimation is reduced through the use of graphical processor units (GPUs). We show that, among the analyzed metrics and domains, the least square error metric of the cycle-skipping in the complex trace domain outperforms the others domains in the estimation of adequate SVMs.