A mutual information estimation of distribution algorithm(MIEDA) with hybrid sampling mechanism is proposed to overcome premature convergence of second order estimation of distribution algorithms. The MIEDA firstly uses mutual information to measure the interaction between two variables, which can generate mutual information tree model. Then, based on the concept of sporadic model building and a reward and punishment scheme in the selfish gene, the MIEDA can accelerate the convergence speed. Finally, a hybrid sampling mechanism is also adopted in the MIEDA to improve the efficiency of sampling, which combines stochastic sampling, the opposition-based learning(OBL) scheme and mutation on the current optimal individual. The simulation results show that, compared with several other second order algorithms, the MIEDA often performs better in convergent reliability and search ability.