The detailed knowledge of C. elegans connectome for 3 decades has not contributed dramatically to our understanding of worm's behavior. One of main reasons for this situation has been the lack of data on the type of synaptic signaling between particular neurons in the worm's connectome. The aim of this study was to determine synaptic polarities for each connection in a small pre-motor circuit controlling locomotion. Even in this compact network of just 7 neurons the space of all possible patterns of connection types (excitation vs. inhibition) is huge. To deal effectively with this combinatorial problem we devised a novel and relatively fast technique based on genetic algorithms and large-scale parallel computations, which we combined with detailed neurophysiological modeling of interneuron dynamics and compared the theory to the available behavioral data. As a result of these massive computations, we found that the optimal connectivity pattern that matches the best locomotory data is the one in which all interneuron connections are inhibitory, even those terminating on motor neurons. This finding is consistent with recent experimental data on cholinergic signaling in C. elegans, and it suggests that the system controlling locomotion is designed to save metabolic energy. Moreover, this result provides a solid basis for a more realistic modeling of neural control in these worms, and our novel powerful computational technique can in principle be applied (possibly with some modifications) to other small-scale functional circuits in C. elegans.