This paper proposes a novel approach for gait pattern generation of a small biped robot to enhance its walking behavior. This is to aim to make the robot gait more natural and more stable in the walking process. In this study, we mention the approximated optimization method which applied the Differential Evolution algorithm (DE) to objective function approximated by Artificial Neural Network (ANN). In addition, we also present a new humanlike foot structure with toes for the biped robot in this paper. To evaluate this method achievement, the robot was simulated by multi-body dynamics simulation software, Adams (MSC software, USA). As a result, we confirmed that the biped robot with the proposed foot structure can walk naturally. The approximated optimization method based on DE algorithm and ANN is an effective approach to generate a gait pattern for the locomotion of the biped robot. This method is simpler than the conventional methods using Zero Moment Point (ZMP) criterion.