The influence of stress, which is one of the constitutive variables that governs unsaturated soil behavior, on the permeability has been recognized by various researchers. Stress factor is essential to study as it drastically alters the soil matrix which includes macropores, minipores and micropores and thus affecting the ability of soils to retain water and also permeability. An evolutionary approach of multi-gene genetic programming (MGGP), which automatically evolves model structure and coefficients can also be applied. However, the effective functioning of MGGP may be affected by the formulation of robust-multi-gene model and the poor selection of the best model. Therefore, a new evolutionary approach of MGGP (E-MGGP) is proposed by incorporating the stepwise and the classification strategies and applied to formulate the functional relationship between the permeability and input variables (stress and initial void ratio). The results reveal that the E-MGGP model outperformed the other three models (MGGP, support vector regression and artificial neural network). Further, the parametric and sensitivity analysis conducted validates the robustness of our proposed model by unveiling dominant input process variables and hidden nonlinear relationships.