The evolutionary algorithms have been used to improve the energy consumption of executable code of embedded software by searching the optimal compilation options of GCC compiler. However, such algorithms do not consider the possible interaction between multiple compilation options so that the quality of their solutions is not high, and their convergence speed is slow. To solve this problem, this study designs an evolutionary algorithm based on frequent pattern mining, called GA-FP. In the process of evolution, GA-FP uses frequent pattern mining to obtain a set of compilation options which are of high-frequency and contribute to significant improvement on energy consumption. The derived options are used as the heuristic information and two mutation operators of ADD and DELETE are designed to increase the quality of solution and accelerate the convergence speed. The comparative experiments are done on 8 typical cases in 5 different fields between Tree-EDA and GA-FP. The experimental results indicate that the GA-FP can not only reduce the energy consumption of software more effectively (the average and maximal reduction ratios are 2.5% and 21.1% respectively), but also converge faster (the average of 34.5% faster and up to 83.3% faster) when the energy optimization effect obtained by GA-FP is no less than that of Tree-EDA. The correlation analysis of compilation options in the optimal solution further validates the effectiveness of the designed mutation operators.