Anytime Multi-Agent Path Finding (MAPF) is a promising paradigm for finding fast and (near-)optimal solutions to large-scale multi-agent systems within a fixed time budget. The currently leading approach builds on Large Neighborhood Search (LNS), which iteratively optimizes a quickly generated initial solution by repeatedly selecting and replanning paths of subsets of agents using randomized destroy heuristics and Prioritized Planning (PP). In this study, we examine the impact of initial solutions on the quality of final solutions in a state-of-the-art LNS-based anytime MAPF algorithm. Our findings demonstrate that its effectiveness is significantly influenced by the choice of the initial solution. Building on this insight, we propose to run PP many times to create a larger pool of potential initial solutions, from which we then select by means of an offline-trained Machine Learning (ML) model a most promising solution to run the LNS on. Empirical results on well-established MAPF benchmark instances show that the ML model successfully selects a most promising solution from the pool of potential initial solutions. This leads to improved performance of the state-of-the-art LNS-based anytime MAPF method in terms of both the final solution quality and the Area Under the Curve when initiated from the selected solution.