This paper proposes a new algorithm to solve multi-objective optimal operation of power systems problem. The algorithm is based on combination of general evolutionary programming and random search technique. The algorithm includes two important procedures. First, a new pattern of mutation is developed in this paper. Secondly, the developed mutation operator is Self-adaptive during optimization. Furthermore, in a multi-objective optimal operation study four objectives (cost of generation with valve point loading, transmission losses, environmental pollution and steady-state security regions) are considered for optimization, and an ideal point method is used to solve the problem. The proposed algorithm is tested on the IEEE six-bus and 30-bus systems. Numerical results and comparison demonstrate that the new method not only can deal agilely with constraints, but also can reduce the CPU time and prevent the search from being in local optima.