Currently, research on the evolution of heterogeneous combat networks (HCNs) mainly focuses on the modeling process, with little attention paid to the impact of changes in network topology on operational capabilities. Link prediction can provide a fair and unified comparison standard for network evolution mechanisms. This paper uses link prediction methods to study the evolution of HCNs. Firstly, according to the characteristics of HCNs, a link prediction index based on frequent subgraphs (LPFS) is proposed. LPFS have been demonstrated on a real combat network to be superior to 26 baseline methods. The main driving force of research on evolution is to improve the operational capabilities of combat networks. Adding the same number of nodes and edges, 100 iterative experiments demonstrate that the evolutionary method (HCNE) proposed in this paper outperforms random evolution and preferential evolution in improving the operational capabilities of combat networks. Furthermore, the new network generated after evolution is more consistent with the characteristics of a real network.