Regional Navigation System (RNS) is an important backup and enhancement means of GNSS. Due to the close distance between the Reference Station (RS) and the user, the Geometric Dilution of Precision (GDOP) of the RS has a significant impact on the performance of the RNS. In order to improve the positioning accuracy, the deployment scheme of RS based on genetic algorithm is studied. Firstly, the Deployment Location (DL) of the RS is encoded, a fitness function that can reflect god or bad of GDOP is designed, and appropriate selection operators, crossover operators, and mutation operators are selected. Then, genetic evolution is used to obtain the DL of the RS. The simulation results show that the method proposed can quickly obtain the required DL of RSs in the case of changes in the service area, deployment area, and number of RSs, and can solve the problem of DL of RSs in practical scenarios.