Water injection development is the primary mode for enhancing the productivity of sandstone reservoirs, and the quality of the injected water significantly impacts the development outcome. Field practice demonstrates that pollutants such as suspended solid particles and emulsified oil in the injected water can clog the pores of the oil reservoir. Due to water quality influences, the permeability of reservoirs with an extended water injection history diverges from the initial permeability, necessitating re-evaluation. Combining the injected water quality standard (SY/T 5329-2012) with laboratory experiments using sandstone cores of varying permeability, a sample database was established encompassing injection history, water quality factors, and permeability ratios. The random forest algorithm was employed to analyze the sample data and determine the importance of each influencing factor. By comparing the BP neural network, random forest algorithm, and particle swarm optimization random forest (PSO-RF) machine learning algorithms, a prediction model for the time-varying characteristics of permeability was developed. The results show that the PSO-RF algorithm excels in predicting the time-varying characteristics of permeability. Integrating the Gaussian filtering algorithm, data clustering, and denoising processes, the PSO-RF deep learning method effectively balances model practicality and accuracy. Consequently, a method for predicting the time-varying characteristics of reservoir permeability during high water cut periods was established. The accuracy of this method was validated by comparing it with numerical simulation results, providing a novel approach for the re-evaluation of permeability.