Abstract: For the difficult problems of spectrum allocation optimization and optimal convergence accuracy in cognitive radio networks, a new binary bat algorithm is proposed to basis of graph theory model and applied to the optimization of cognitive radio spectrum allocation. Firstly, two random numbers are introduced in the frequency update to control the global and local balance. Secondly, a new discrete function is introduced to disperse the velocity to the position in the process of continuous space and discrete space conversion. Finally, the new binary bat algorithm and the traditional binary bat algorithm are compared with the goal of maximizing total system benefit and fairness of secondary user. The results show that the new binary bat algorithm is superior to other algorithms in the application and can be effectively and stably used for spectrum allocation optimization.