With the rapid advancement of air transport aviation and general aviation, the frequency assignment of air navigation stations has become increasingly crucial. A comprehensive algorithm was presented for assigning frequencies to individual air navigation stations. Subsequently, in order to address the issue of frequency assignment for multiple aviation navigation stations, a model was established specifically for civil aviation navigation stations. Finally, considering the limitations of traditional multi-objective genetic algorithms such as slow convergence speed and susceptibility to local optimal solutions, a multi-objective genetic algorithm along with a multi-objective genetic local search algorithm based on optimal weight allocation was proposed to effectively solve the frequency assignment problem faced by aviation navigation stations. The problem encompasses several objectives including minimizing frequency interference and utilizing the minimum number of frequencies required. Simulation results demonstrate that our proposed multi-objective genetic local search algorithm successfully resolves the frequency assignment problem encountered by air navigation stations. In comparison with traditional multi-objective genetic algorithms and those incorporating optimized weight allocation, our proposed algorithm significantly enhances solution quality, convergence speed, and stability.