Digital watermarking had been well recognized as an effective measure for the copyright protection of multimedia data. Numerous schemes in the domain of vector quantization had been proposed to achieve the desired goal. A new scheme, also in the domain of vector quantization, is developed and presented in this article. The proposed approach use genetic algorithms to reassign the indices of code words. As a result, embedded information will be diffused more evenly across the image to be protected, and therefore possible security leakage can be avoided. Experimental results reveal that the proposed scheme is free from the potential limitations in previous approaches, while maintaining the robustness against various kinds of attacks.