This paper presents a new, differential-evolution-based method for solving the problem of optimal selection of cluster-heads and cluster-members in mobile ad hoc networks. A novel encoding scheme is used to represent nodes in the network graph, and randomly-generated networks of different sizes are solved. The present method handles problems of much larger sizes than do the best-known methods in the literature. Empirical results show the superiority of this method over state-of-the-art approaches on two counts: quality of the solution and time to find the solution.