In complex reaction systems, such as those found in heterogeneous catalytic reactions, several alternative kinetic models are usually considered in an effort to describe reaction kinetics. The number of plausible mechanisms can be very large, even for systems with a small number of reactions and components. Usually, only a restricted number of models are investigated in detail, since the evaluation of a large number of complex models is extremely time-consuming. In this work, a methodology is described, which allows performing efficiently a global search within all plausible models and parameter sets using the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The developed methodology is applied to the parameter estimation and model optimization of the partial oxidation of ethane reaction network. The present approach allows the reliable investigation of a considerable number of models mechanisms in an automatic manner and in a short computational time. It appears to be a very effective way to optimize complex reaction mechanisms.