Seven different stochastic binary optimizers--based on the concepts of genetic algorithms and evolutionary strategies--are developed, applied to determine defect locations in several photonic crystal structures that serve as test cases, and compared by extensive statistical analysis. In addition to the stochastic optimizers, a quasi-deterministic optimizer based on an algorithm inspired by hill-climbing algorithms was implemented. The test cases include the prominent 90 degrees photonic crystal waveguide bend and a photonic crystal power divider. The analysis of the results shows that many different photonic crystal structures with high transmission may be found for any operating frequency. All of the eight optimizers outperform standard codes-because they maintain an incomplete fitness table-and find the global optima with a high probability even when the number of fitness evaluations is much smaller than the number of potential solutions contained in the discrete search space. Based on the incomplete fitness table, an algorithm to estimate bit-fitness values is presented. The bit-fitness values are then used to improve the performance of some algorithms. The four best algorithms-an extended microgenetic algorithm, two mutation-based algorithms, and the quasi-deterministic algorithm inspired by hill-climbing algorithms-are considered to be of high value for the optimization of defects in photonic crystals and for similar binary optimization problems.