A hyper-heuristic algorithm is a general solution framework that adaptively selects the optimizer to address complex problems. A classical hyper-heuristic framework consists of two levels, including the high-level heuristic and a set of low-level heuristics. The low-level heuristics to be used in the optimization process are chosen by the high-level tactics in the hyper-heuristic. In this study, a Cooperative Multi-Stage Hyper-Heuristic (CMS-HH) algorithm is proposed to address certain combinatorial optimization problems. In the CMS-HH, a genetic algorithm is introduced to perturb the initial solution to increase the diversity of the solution. In the search phase, an online learning mechanism based on the multi-armed bandits and relay hybridization technology are proposed to improve the quality of the solution. In addition, a multi-point search is introduced to cooperatively search with a single-point search when the state of the solution does not change in continuous time. The performance of the CMS-HH algorithm is assessed in six specific combinatorial optimization problems, including Boolean satisfiability problems, one-dimensional packing problems, permutation flow-shop scheduling problems, personnel scheduling problems, traveling salesman problems, and vehicle routing problems. The experimental results demonstrate the efficiency and significance of the proposed CMS-HH algorithm.