Frequency optimization is of great importance in the design of machines and structures subjected to dynamic loading. When the natural frequencies of considered structures are maximized using the solid isotropic material with penalization (SIMP) model, artificial localized modes may occur in areas where elements are assigned with lower density values. In this paper, a modified SIMP model is developed to effectively avoid the artificial modes. Based on this model, a new bi-directional evolutionary structural optimization (BESO) method combining with rigorous optimality criteria is developed for topology frequency optimization problems. Numerical results show that the proposed BESO method is efficient, and convergent solid-void or bi-material optimal solutions can be achieved for a variety of frequency optimization problems of continuum structures.