The finite element method (FEM) and the genetic algorithm (GA) have been used to solve the inverse problem involving absolute photonic band gap (PBG) searching and optimization. Square and triangular lattices composed by Tellurium (anisotropic material) and air have been analyzed. In order to avoid the requirements of high computational efforts and resources needed in these kind of tasks, the PBGs have been computed only at key positions along the first region of Brillouin and we obtained absolute midgap ratio, considering PBGs between the TE 1-2 and TM 3-4 modes, of 18.00% and 23.49% for the square and triangular lattices, respectively. © 2006 IEEE.