The design of adaptive, scalable, and low cost routing protocols presents one of the most challenging research problems in mobile ad hoc networks (MANETs). Many routing protocols for MANETs have been proposed in the literature, which are based mainly on selecting the shortest path between communication endpoints. In this paper, a new evolution-based routing metric called EVO is proposed. This metric is generated automatically by means of genetic programming. In the evolution process of this metric, mobility- and traffic-related features are employed. In this study, the metric is applied to the Ad hoc On-Demand Distance Vector (AODV) protocol, one of the most popular on-demand routing algorithms for MANETs. The modified version of AODV, called EVO-AODV, ranks and selects routes according to the evolved multi-featured metric between communication endpoints. The performance of the proposed metric has been tested on networks with varying mobility and traffic patterns. The metric is also compared with AODV and two recently proposed routing metrics, the hop change metric (HOC) (Zangabad 2014) and encounter-based routing metric (PER) (Son et al. in Ad Hoc Netw 14:2-14, 2014). The extensive simulation results demonstrate that the proposed approach improves the packet delivery ratio significantly and also decreases the packet drop rate, routing overhead, and end-to-end delay, especially on networks under medium traffic.