By considering locomotion as a set of coordinated oscillations, a method for generating a wide variety of periodic linear gait trajectories is proposed. The shape of the generated trajectory can be defined as a set of features such as symmetry, skewness, signal width, duality and squareness, along with amplitude, offset, phase and frequency parameters. Taking previously proven nonlinear bipedal gait trajectories as reference, a set of linear approximates are modeled, and is tested on a simulated humanoid robot. Then, gait trajectories for producing stable and faster bipedal gait on the same humanoid robot are learned using Genetic Algorithm, through a bottom-up approach.