This study points out some weaknesses of existing Quantum-Inspired Evolutionary Algorithms (QEA) and explains in particular how hitchhiking phenomenons can slow down the discovery of optimal solutions and encourage premature convergence. A new algorithm, called Versatile Quantum-inspired Evolutionary Algorithm (vQEA), is proposed. With vQEA, the attractors moving the population through the search space are replaced at every generation without considering their fitness. The new algorithm is much more reactive. It always adapts the search toward the last promising solution found thus leading to a smoother and more efficient exploration. In this paper, vQEA is tested and compared to a Classical Genetic Algorithm CGA and to a QEA on several benchmark problems. Experiments have shown that vQEA performs better than both CGA and QEA in terms of speed and accuracy. It is a highly scalable algorithm as well. Finally, the properties of the vQEA are discussed and compared to Estimation of Distribution Algorithms (EDA). © 2007 IEEE.