The optimization of compilation options provides a feasible and effective solution to reduce the energy consumption of embedded software. GA-FP algorithm applies frequent pattern mining into the evolutionary process and has achieved better results than other algorithms. However, GA-FP still has the disadvantages, such as the large size of transaction table, incomplete and obsolete heuristic information provided by frequent option patterns and inefficient single point mutation, which potentially affects the solution quality and convergence rate. Aiming to these problems, this study proposes an evolutionary optimization algorithm for embedded software energy consumption at GCC compile time, called GA-MFPM. GA-MFPM replaces the reference point and transaction table mechanism by generation to reduce size of the transaction table. Further, a frequent compilation option mining algorithm is designed to acquire more heuristic information. It adopts a generation-by-generation mining strategy to help maintain the timeliness of frequent option patterns. Based on the frequent option patterns, a maximum frequent pattern matching algorithm is designed to perform multi-point mutation to improve optimization quality and convergence rate. The comparative experiments are done on 8 typical cases in 5 different fields between GA-MFPM and GA-FP. The experimental results indicate that the GA-MFPM can not only reduce the energy consumption of software more effectively (the average and maximal reduction ratios are 2.4% and 16.1% respectively), but also converge faster (the average of 57.6% faster and up to 97.5% faster) than GA-FP in this study.