In this paper, we propose intelligent change operators and integrate them into an evolutionary multi-objective search algorithm to recommend valid refactorings that address conflicting quality objectives such as understandability and effectiveness. The proposed intelligent crossover and mutation operators incorporate refactoring dependencies to avoid creating invalid refactorings or invalidating existing refactorings. Further, the intelligent crossover operator is augmented to create offspring that improve solution quality by exchanging blocks of valid refactorings that improve a solution’s weakest objectives. We used our intelligent change operators to generate refactoring recommendations for four widely used open-source projects. The results show that our intelligent change operators improve the diversity of solutions. Diversity is important in genetic algorithms because crossing over a homogeneous population does not yield new solutions. Given the inherent nature of design trade-offs in software, giving developers choices that reflect these trade-offs is important. Higher diversity makes better use of developers time than lots of incredibly similar solutions. Our intelligent change operators also accelerate solution convergence to a feasible solution that optimizes the trade-off between the conflicting quality objectives. Finally, they reduce the number of invalid refactorings by up to 71.52% compared to existing search-based refactoring approaches, and increase the quality of the solutions. Our approach outperformed the state-of-the-art search-based refactoring approaches and an existing deterministic refactoring tool based on manual validation by developers with an average manual correctness, precision and recall of 0.89, 0.82, and 0.87.