To tackle the problem of low solving efficiency in interval optimization for multi-method condition-based maintenance, an algorithm based on fitting and random global search was put forward. Firstly, based on the traditional multi-method condition-based maintenance model, a maintenance strategy considering imperfect detection was constructed, in which the detection interval of each method was taken as the decision variable, the fault detection in time was taken as the constraint condition of the safety during the operation of the system, and the minimum expected total cost within the maximum time was taken as the decision goal. Secondly, simulated annealing algorithm was used to optimize the above model to obtain the best detection strategy. In addition, a prediction algorithm based on BP neural network is designed, and the mapping relationship between detection interval and detection cost and reliability is established, which is used to replace the re-calculation part of the simulated annealing algorithm in each optimization. Finally, the proposed algorithm is verified and the accuracy of the algorithm is analyzed by taking a system degradation as an example. The analysis shows that the proposed method has a very important reference value for improving the computational efficiency of multi-method detection optimization problem under combinatorial optimization and optimizing the detection interval of multi-method detection.