Biped locomotion for humanoid robots is a challenging problem that has come into prominence in recent years. As the degrees of freedom of a humanoid robot approaches to that of humans, the need for a better, flexible and robust maneuverability becomes inevitable for real or realistic environments. This paper presents new motion types for a humanoid robot in coronal plane on the basis of Partial Fourier Series model. To the best of our knowledge, this is the first time that omni-directionality has been achieved for this motion model. Three different nature-inspired optimization algorithms have been used to improve the gait quality by tuning the parameters of the proposed model. It has been empirically shown that the trajectories of the two specific motion types, namely side walk and diagonal walk, can be successfully improved by using these optimization methods. The best results are obtained by the Simulated Annealing procedure with restarting.