ABSTRACT Researching the satellite network link allocation problem to meet interstellar communication demands is an important subject. In this study, we first analyzed the characteristics of satellite networks and designed a topology processing mechanism based on finite state automata (FSA). Then, with the visibility of the satellite as the constraint and the communication delay performance of the inter‐satellite link as the optimization goal, the link allocation problem of the navigation satellite network is modeled as a multi‐objective optimization problem. Finally, for the established multi‐objective optimization problem, an algorithm based on the combination of Q‐learning and non‐dominated genetic algorithm (NSGA‐II) is proposed to solve the link allocation problem. The simulation results show that the network delay performance of the optimized link allocation obtained through the algorithm combining reinforcement learning and NSGA‐II has been improved, and the link communication delay is better than the traditional multi‐objective optimization algorithm. At the same time, the state duration of the FSA is reduced, which facilitates the acquisition of satellite links with good network delay performance. These research results show that the RL‐NSGA‐II algorithm based on the combination of Q‐learning and non‐dominated genetic algorithms has great potential in solving satellite network link allocation problems, providing better performance and effects for satellite networks that meet the needs of interstellar communications.