Central pattern generators are small networks that contribute to generating animal locomotion. The models used to study gait generation and gait transition mechanisms often require biologically accurate neuron and synapse models, with high dimensionality and complex dynamics. Tuning the parameters of these models to elicit network dynamics compatible with gait features is not a trivial task, due to the impossibility of inferring a priori the effects of each parameter on the nonlinear system's emergent dynamics. In this paper we explore the use of global optimization strategies for parameter optimization in multigait central pattern generator (CPG) models with complex cell dynamics and minimal topology. We first consider an existing quadruped CPG model as a test bed for the objective function formulation, then proceed to optimize the parameters of a newly proposed multigait, interlimb hexapod CPG model. We successfully obtain hexapod gaits and prompt gait transitions by varying only control currents, while all CPG parameters, once optimized, are kept fixed. This mechanism of gait transitions is compatible with short-term synaptic plasticity.