This paper proposes a new topology optimization algorithm based on the bi-directional evolutionary structural optimization (BESO) method to design photonic crystals with broad all-angle negative refraction (AANR) frequency range. The photonic crystals are assumed to be two-dimensional periodical structures, which consist of dielectric materials and air. The conditions for the occurrence of AANR are identified and the design objective is to enlarge the AANR frequency range. The BESO algorithm is proposed based on finite element analysis for band diagrams of photonic crystals and the derived sensitivity numbers. Starting from a simple initial design without any AANR, BESO gradually re-distributes the dielectric materials within the periodical unit cell so that the AANR property emerges and its frequency range is enlarged accordingly. The numerical results show that the proposed BESO algorithm can effectively obtain AANR photonic crystals with novel patterns. The effects of dielectric permittivity contrast of two constituent materials, mesh-refinement and filter are discussed. (C) 2016 Elsevier B.V. All rights reserved.