In this paper, the construction of non binary cyclic One-Step Majority-Logic decoding codes from the dual domain and idempotents is investigated. This had led us to propose a new design algorithm based on Genetic Algorithms, as an extension to previous works on the binary field. With the proposed algorithm, we were able to obtain long new non-binary cyclic OSMLD codes with high coding rates and good correction capacities. In fact, two powerful properties of the algebraic construction are provided, firstly, the designed codes have their minimal distances dmin and dimensions calculated analyticaly, secondly, they can be decoded with a low-complexity majority-voting decoding scheme.