For areas with high population density such as urban areas, natural gas leaks will bring huge casualties and property damage. Therefore, a positioning algorithm that can quickly and accurately predict the source of natural gas leaks can further reduce the expansion of risks. This article employs a Gaussian bagging model to train a gas diffusion model for leaks and proposes a Flow Regime-Particle Swarm Optimization (FR-MSPSO) algorithm, which integrates multiple improvement strategies to address the issue of anti-localization in leak scenarios. We validated the algorithm’s feasibility using simulation scenarios that varied in wind speed and leakage source intensity. The experimental results have demonstrated that by leading in corresponding improvement strategies, the FR-MSPSSO algorithm has achieved higher prediction accuracy and optimization efficiency compared to the PSO algorithm in solving single extreme value, multi extreme value. And achieved smaller positioning errors and source estimation errors in the solution of the leakage source localization problem.