Gait parameter adaptation on a physical robot is an error-prone, tedious and time-consuming process. In this paper we present a system for gait adaptation in our RHex series of hexapedal robots that renders this arduous process nearly autonomous. The robot adapts its gait parameters by recourse to a modified version of Nelder-Mead descent while managing its self-experiments and measuring the outcome by visual servoing within a partially engineered environment. The resulting performance gains extend considerably beyond what we have managed with hand tuning. For example, the hest hand tuned alternating tripod gaits never exceeded 0.8 m/s nor achieved specific resistance helow 2.0. In contrast, Nelder-Mead based tuning has yielded alternating tripod gaits at 2.7 m/s (well over 5 body lengths per second) and reduced specific resistance to 0.6 while requiring little human intervention at low and moderate speeds. Comparable gains have been achieved on the much larger ruggedized version of this machine.