Currently, quantum processors belong to the so-called Noisy Intermediate-Scale Quantum (NISQ) era due to the fact that they are prone to errors and characterized by a limited number of qubits. In this scenario, solving discrete optimization problems requires the use of efficient encodings capable of limiting the use of resources of NISQ devices. For this reason, a new encoding scheme has recently been proposed where discrete classical variables are encoded in non-orthogonal states of a quantum system. This idea, integrated with Variational Quantum Eigensolvers (VQEs), has shown good performance in solving complex optimization problems by significantly reducing the number of qubits used. VQEs involve parameterized circuits that are typically trained by means of gradient-based optimization techniques. However, these techniques can suffer from several issues including the barren plateau problem. In order to overcome these issues, this paper introduces, for the first time, the use of a gradient-free technique such as Genetic Algorithms (GAs) to optimize the parameters of VQEs combined with this new encoding based on non-orthogonal states. As shown in the experimental session, GAs outperform the other state-of-the-art gradient-free optimizers in solving the well-known Max k-Cut problem.