Traction transformer is vital equipment in high-speed railway. Insulation status decides its safety and reliability, and the frequency-domain dielectric spectrum (FDS) test is one of the most effective methods reflecting the changing of insulation status. For field applications, the following problems should be addressed: 1) how to obtain the result of paper insulation from the combined result of the oil-paper insulation system and 2) how to discriminate the defects of insulation paper between aging and damp. In this article, the first problem was transferred to a nonlinear equation set, and a cuckoo search algorithm optimized by the differential evolution algorithm and the quadratic interpolation (QI) method (CS-DQ algorithm) was proposed to solve it. Then, the insulation states were discriminated by establishing a multiclass least-squares support vector machine (LS-SVM) model, in which the CS-DQ algorithm was also used. Finally, a diagnostic approach for the insulation paper in the traction transformer was proposed. The results in the laboratory show that the pure result of insulation paper can be obtained, and the insulation states can be discriminated effectively by using the proposed approach. Meanwhile, the proposed CS-DQ algorithm has a better performance than the conventional CS algorithm. The results of field testing also verify the proposed approach.