The heuristic test case generation method that combines machine learning-related technologies can significantly improve the test efficiency. Existing studies focus on building efficient surrogate models with partial test cases, but ignore the influence of both the initial population quality and surrogate models on the multi-path testing efficiency. Therefore, this study proposes a test case reduction and generation method combining K-means and support vector machine regression (SVR). The randomly generated test cases are clustered into several clusters by adopting K-means, and only the test cases that are within a particular distance away from the cluster center are retained, with the path coverage matrix for these test cases constructed. This matrix is employed to evaluate the path coverage potential of test cases and the coverage difficulty of paths. Additionally, based on these two conditions, the test cases are ranked, and several test cases are selected from different clusters to construct the test case reduction set, which is taken as the initial genetic population. This not only increases the diversity of the initial population and reduces its redundancy, but also helps to reduce the iteration number for multi-path coverage test cases. Meanwhile, the test cases before clustering and their fitness are employed as the samples to train the SVR fitness prediction model designed for multi-path coverage, and then the new test cases generated by genetic evolution are utilized to update the model, thus improving the model accuracy and reducing the time consumed due to the instrumentation program execution. In this way, both population quality and test efficiency can be improved. The experimental results show that on fifteen programs, the proposed method has better improvements in terms of indicators such as the coverage rate and average evolutionary generation. Specifically, in terms of the coverage rate, the proposed method demonstrates an improvement of at least 7% and up to 49% compared to three types of baseline methods, and shows the enhancement of approximately 10% to a maximum of 25% compared to five competitive methods. The proposed method provides guidance for the research on multi-path testing that combines machine learning.