Integration between energy storage systems (ESSs) and renewable energy sources (RESs) can effectively smooth natural fluctuations of the latter and ensure better frequency regulation. Optimal performance of the plug-in hybrid electric vehicle (PEHV) battery, having longer plug-in than driving time, makes it a good candidate for integration with RESs. Decentralized model predictive control (MPC) is proposed here for frequency regulation in a smart three-area interconnected power system comprising PHEVs. Two MPCs in each area are considered to manipulate the input signals of the governor and PHEV in order to tolerate frequency perturbations subject to load disturbances and RES fluctuations. Setting the parameters of the six MPC controllers is carried out simultaneously based on imperialist competitive algorithm (ICA) and bat-inspired algorithm (BIA). Time-domain based objective function is suggested to account for system nonlinearities emanating from governor dead bands (GDBs) and turbine generation rate constraints (GRCs). The proposed tuning procedures utilizing ICA and BIA are completely accomplished off-line. Comparative simulation results are presented to confirm the effectiveness of the proposed design.