Limbs are an attractive approach to certain niche robotic applications, such as urban search and rescue, that require both small size and the ability to locomote through highly rubbled terrain. Unfortunately, a large number of degrees of freedom implies there is a large space of non-optimal locomotion trajectories (gaits), making gait adaptation critical. On the other hand, these extra degrees of freedom open many possibilities for active sensing of the terrain, which is essential information for adapting the gait. In previous work, we developed a metric for terrain classification that makes use of the loping body motion (i.e. gait bounce) during locomotion. In this work we present a framework for evolving gaits to better differentiate the gait bounce signal across terrains. This framework includes a limb/terrain interaction model that estimates gait bounce based on established models of wheel/terrain interaction, and an objective function that can be optimized for terrain diseriminability. Additional objective functions for improved locomotion are presented, as well as culling agents that help guide the evolution process away from real-world impossibilities.