Analysis and evaluation of land use patterns are of prime importance for natural resources management. Recent studies on land use allocation have been mainly based on linear programming optimization. Although these methods have the ability to solve multi-objective problems, spatial aspects of optimization are not considered when they are used for land use management. This study applied the non-dominated sorting genetic algorithm II (NSGA-II) to optimize land-use allocation in the Taleghan watershed, northwest of Karaj, Iran. The four land use classes of irrigated farming, dry farming, rangeland, and other uses were extracted from the ETM+ image. The objective functions of the proposed model were erosion, economic return, suitability, and compactness-compatibility. A novel crossover operator called exchange randomly block (ERB) was used to exchange information between individuals. Results showed that the optimization model can find a set of optimal land use combinations in accordance with the proposed conditions. For comparison purposes, land use allocation was also done using the combined goal attainment-multi-objective land allocation (GoA-MOLA) approach. The results showed that NSGA-II performance acceptably when compared to GoA-MOLA.