To address the optimization of tool combination in the NC machining of complex pockets, we propose a tool optimization method for complex pocket parts based on the genetic algorithm in this study. First, a feasible tool set for pocket machining is constructed by an offset loop algorithm. Secondly, with machining efficiency and tool cost as the optimization objective, an optimization model of tool combination for complex pocket parts is established to decrease the difference between each feature of the pocket parts and the overall optimal tool combination. Furthermore, a directed graph and an improved genetic algorithm are developed to solve the optimization model of tool combination. Finally, the feasibility of the proposed method is verified by testing the optimization of NC machined tool combination for a complex pocket part.