Forests are vital global carbon sinks and provide critical ecosystem services for soil conservation. Reforestation is a critical strategy for mitigating land degradation, yet prioritizing areas for restoration to maximize erosion control at the watershed level remains a key challenge in environmental management. This study introduces a novel spatial optimization framework that integrates the Unit Stream Power Erosion Deposition (USPED) model with a Genetic Algorithm (GA) to guide reforestation planning in the Serido River Basin, within Brazil's semi-arid Caatinga biome. Our objective was to identify an optimal forest cover configuration that minimizes soil loss. The optimized scenario increased forest cover by 20%, reducing gross soil loss from 105,000 to 75,000 tons per year. The extent of stable areas increased from 39.48% to 43.07%, and areas under extreme erosion risk were significantly reduced. Landscape pattern analysis revealed a trade-off: the Landscape Shape Index increased from 245.80 to 307.20, indicating more complex forest fragments, while the Contagion Index showed stable connectivity. The findings confirm that the strategic spatial allocation of forests is more critical than simply expanding cover. The proposed heuristic-based spatial optimization framework provides land managers and policymakers with a powerful, data-driven tool for designing targeted reforestation interventions that effectively enhance soil conservation and ecosystem service provision in vulnerable dry forest ecosystems.