Most studies in the past on the control of biped locomotion considered only level surfaces. However, in the real world the ground is rarely completely flat. More research on locomotion on less structured surfaces is needed. In this study, we investigated a control design method that searches for suitable control and trajectory parameters using a Genetic Algorithm (GA). Many sets of parameters are generated through the search and the best set is selected based on a robustness measure developed from the linearized Poincaré map. This technique reduces tedious analysis and is favorably applicable to the design for locomotion on unstructured surfaces, for which analytical approaches are less appropriate. Simulations have been performed. Control parameters for different slopes were obtained and stored in a database. During the control, the control parameters suitable for the current surface slope were retrieved and the trajectory for a level surface was modified according to the surface slope. The control parameters changed values according to the terrain. Simulation results were promising.