In order to optimize the formation of large-scale unmanned combat aircraft vehicle (UCAV) in complex constraint environment, an algorithm for formation optimization based on bi-level programming model was proposed. According to the existing UCAV formation combat mode of air to ground, the upper-level model of UCAV formation in combat environment was established. The discrete particle swarm optimization and simulated annealing (DPSO-SA) algorithm was used to obtain the number of UCAV and the best formation of each task. According to the existing formation library, the lower-level model of the UCAV location was built, and the UCAV position in the formation was obtained by using the genetic algorithm. The simulation results show that the improved simulated annealing algorithm can solve the problem that the discrete particle swarm optimization is easy to fall into local minimum, and the slow convergence rate of DPSO-SA can be solved with the design of a bi-level programming model. Compared with the single-level programming model, the bi-level programming model has faster convergence speed and better optimization effect on solving large-scale UCAV formation optimization problems.