In order to support multimedia communication over high speed networks, it is necessary to develop routing algorithms which use for routing more than one QoS parameter. This is because new services such as video on demand and remote meeting systems require better QoS. However, the problem of QoS routing is difficult and to find a feasible route with two independent path constraints is NP-complete. Therefore, QoS routing algorithms for high speed networks must be adaptive, flexible, and intelligent for efficient network management. In a previous work, we proposed a Genetic Algorithm (GA) based routing method. This method used only the delay time as a routing parameter. In this paper, we improve the previous work in three aspects. The new QoS routing method uses two QoS parameters for routing. We implemented a new tree generat-ing algorithm which generates and reduces the tree automatically. Furthermore, we carried out the simulations for different kinds of networks. The simulation results show that proposed method has a better performance than a conventional GA based routing algorithm.