Creating effective locomotion for a legged robot is a challenging task. Central pattern generators have been widely used to control robot locomotion. However, one significant disadvantage of the central pattern generator method is its inability to design high-quality walks because it only produces sine or quasi-sine signals for motor control as compared to most cases in which the expected control signals are more advanced. Control accuracy is therefore diminished when traditional methods are replaced by central pattern generators resulting in unaesthetically pleasing walking robots. In this paper, we present a set of solutions, based on testings of Sony’s four-legged robotic dog (AIBO), which produces the same walking quality as traditional methods. First, we designed a method based on both evolution and learning to optimize the walking gait. Second, a central pattern generator model was put forth to enabled AIBO to learn from arbitrary periodic inputs, which resulted in the replication of the optimized gait to ensure high-quality walking. Lastly, an accelerator sensor feedback was introduced so that AIBO could detect uphill and downhill terrains and change its gait according to the surrounding environment. Simulations were performed to verify this method.