With increasing concern of environmental protection, renewable energy sources especially wind power are widely applied as a mean to reach emission reduction. Although wind generation does not produce harmful emissions, its effect on the generation dispatch of conventional plants can actually cause an increase of emission especially during low and middle power demand period. A multi-objective generation dispatch that considering environment and fuel cost under large penetration of wind power was proposed. An efficient encoding/decoding scheme is applied that could effectively prevent obtaining infeasible solutions through the application of stochastic search methods, thereby dramatically improving search efficiency and solution quality. The nonlinear characteristics of power generators, and their operational constraints, such as generation limitations, ramp rate limits, prohibited operating zones, and transmission loss could be considered for practical operation. The effectiveness and feasibility of the proposed approach were demonstrated by IEEE 30-bus test system study. The experiment showed encouraging results, suggesting that the proposed approach was capable of providing higher quality and wilder range of pareto-optimal solutions such that the decision makers can have a more flexible and reasonable choice.