Tensor network states (TNS) methods combined with the Monte Carlo (MC) technique have been proven a powerful algorithm for simulating quantum many-body systems. However, because the ground state energy is a highly non-linear function of the tensors, it is easy to get stuck in local minima when optimizing the TNS of the simulated physical systems. To overcome this difficulty, we introduce a replica-exchange molecular dynamics optimization algorithm to obtain the TNS ground state, based on the MC sampling technique, by mapping the energy function of the TNS to that of a classical mechanical system. The method is expected to effectively avoid local minima. We make benchmark tests on a 1D Hubbard model based on matrix product states (MPS) and a Heisenberg J1-J2 model on square lattice based on string bond states (SBS). The results show that the optimization method is robust and efficient compared to the existing results.