The compressed air energy storage (CAES) system, considered as one method for peaking shaving and load-levelling of the electricity system, has excellent characteristics of energy storage and utilization. However, due to the waste heat existing in compressed air during the charge stage and exhaust gas during the discharge stage, the efficient operation of the conventional CAES system has been greatly restricted. The Kalina cycle (KC) and organic Rankine cycle (ORC) have been proven to be two worthwhile technologies to fulfill the different residual heat recovery for energy systems. To capture and reuse the waste heat from the CAES system, two systems (the CAES system combined with KC and ORC, respectively) are proposed in this paper. The sensitivity analysis shows the effect of the compression ratio and the temperature of the exhaust on the system performance: the KC-CAES system can achieve more efficient operation than the ORC-CAES system under the same temperature of exhaust gas; meanwhile, the larger compression ratio can lead to the higher efficiency for the KC-CAES system than that of ORC-CAES with the constant temperature of the exhaust gas. In addition, the evolutionary multi-objective algorithm is conducted between the thermodynamic and economic performances to find the optimal parameters of the two systems. The optimum results indicate that the solutions with an exergy efficiency of around 59.74% and 53.56% are promising for KC-CAES and ORC-CAES system practical designs, respectively.