Genome-scale stoichiometric models are useful predictive tools for redesigning metabolic networks. However, the high computational cost of identifying appropriate metabolic engineering strategies restricts the applicability of computational models to the optimization with a limited number of modifications. By mimicking adaptation phenomena in nature, we developed a novel optimization framework named EvoKO that can find optimal knockout strategies with an unlimited number of knockouts. EvoKO was successfully applied to the identification of an optimal metabolic engineering strategy for the production of hydrogen using $\it{Escherichia coli}$. The predicted hydrogen yield of the mutant suggested by EvoKO was about 77.4% of the theoretical maximum, which is about two-fold higher than those suggested using previous optimization frameworks.