Nowadays, due to the increased price of fossil fuels and their decreasing resources on the one hand, and the importance of environmental pollution on the other, use of electric vehicles (EVs) has been increased. Charging of EVs has imposed new loads on power systems. These new and major loads along with the deregulation of power systems, which introduces new uncertainties to grid, have caused new challenges for the frequency control and stability of power systems. Use of EVs as moving batteries in deregulated power systems is one of the ways for dealing with this problem. In this method, charging EVs is controlled and, when necessary, EV battery is discharged in grid. This concept is called vehicle to grid (V2G), which was employed in this study for the control of the frequency of a smart deregulated grid. For this purpose, an optimized fuzzy controller was used to control EVs. Using the proposed method, charging or discharging of batteries was carried out with respect to grid frequency and battery state of charge. To investigate the proposed approach, a 35-bus system as a deregulated system was assumed. Then, this system was converted into a three area system in order for the frequency analysis. Simulations were performed in MATLAB/SIMULINK environment and the results illustrated the good performance of the proposed method in terms of frequency control of deregulated system. Moreover effect of proposed method on under frequency load shedding was verified. It was illustrated that by using of proposed method under frequency load shedding is postponed.