Fast Internet connections and the widespread use of high performance graphic cards are making Distributed Virtual Environments (DVE) very common nowadays. The architecture and behavior of these systems are very similar to new grid computing applications where concepts such as sharing and high scalability are extremely exploited. However, there are several key issues in these systems that should still be improved in order to design a scalable and cost-effective DVE system. One of these key issues is the partitioning problem. This problem consists of efficiently assigning clients (3-D avatars) to the arbiters (servers) in the system. As an alternative to the ad-hoc heuristic proposed in the literature, this paper presents a comparison study of two evolutionary heuristics for solving the partitioning problem in DVE systems. Performance evaluation results show that heuristic methods can greatly improve the performance of the partitioning method, particularly for large DVE systems. In this way, efficiency and scalability of DVE systems can be significantly improved.