The coefficients in previous local filters are mostly heuristically optimized, which leads to artifacts in the denoised image when the optimization is not adaptive enough to the image content. Compared to parametric filters, learning-based denoising methods are more capable of tackling the conflicting problem of noise reduction and artifact suppression. In this paper, a patch-based Evolved Local Adaptive (ELA) filter is proposed for natural image denoising. In the training process, a patch clustering is used and the genetic programming (GP) is applied afterwards for determining the optimal filter (linear or nonlinear in a tree structure) for each cluster. In the testing stage, the optimal filter trained beforehand by GP will be retrieved and employed on the input noisy patch. In addition, this adaptive scheme can be used for different noise models. Extensive experiments verify that our method can compete with and outperform the state-of-the-art local denoising methods in the presence of Gaussian or salt-and-pepper noise. Additionally, the computational efficiency has been improved significantly because of the separation of the offline training and the online testing processes.