A wireless mesh network (WMN) composed of multiple access-points (APs) that communicate mutually using radio transmissions, and all the traffics to/from the Internet are aggregated and go through the limited number of gateway APs. The meshed topology provides good reliability, market coverage, and scalability, as well as low upfront investment. However, due to the nature of routing algorithm the traffic load for a access point may be extremely heavy during particular periods while the other access points are in very light load. Consequently, the overall performance of the network are poor even the total traffic load is far below the system capacity. The performance can be improved dramatically by Traffic Balancing. Strategically placing and connecting the gateways to the wired backbone is critical to the management and efficient operation of a WMN. In this paper, we address the problem of gateway access-points placement, consisting in placing a minimum number of gateways such that quality-of-service (QoS) requirements are satisfied. We propose a genetic algorithm that consistently preserves QoS requirements. We evaluate the performance of our algorithm using both analysis and simulation, and show that it outperforms other alternative schemes by comparing the number of gateways placed in different scenarios.