Virtual machine (VM) allocation is the process of allocating virtual machines to suitable hosts. This problem is an NP-Hard problem. It can be considered as a variation of the bin-packing problem. Among various solutions that attempt to solve this problem, several approaches that apply Genetic Algorithm have been proposed. This paper proposes a method to improve the efficiency of such approaches. Implementation of the proposed approach shows significant improvements in the runtime, memory used, energy efficiency and SLA violations.