This work is concerned with complex cooperative robot actions by recursive optimal motion composition. According to the intelligent composite motion control (ICMC), a complex action is gradually realized from fundamental motions. It, is not easy to obtain the action intelligence of such a complex cooperation at once, hence in this work the intelligence is constructed through multi-stage action intelligence optimization. For optimization Multi-stage genetic algorithm, MGA, is used to repeatedly solve optimal motion composition problems. The cooperative action realization is a large-scale optimization problem with complicated constraints. The MGA solves it as combinatorial optimizations for the component motions with simple constraints, which are solved by GA to generate their suboptimal solution sets. The empirical knowledge obtained is effectively utilized to solve similar problems efficiently and moreover to compose more complex actions. The method is successfully applied to optimal realization of cooperative robot soccer actions.