We report on the experimental realization of ultra-high quality factor (Q) designs of the L3-type photonic crystal nanocavity. Based on genetic optimization of the positions of few nearby holes, our design drastically improves the performance of the conventional L3 as experimentally confirmed by direct measurement of Q similar or equal to 2 x 10(6) in a silicon-based photonic crystal membrane. Our devices rank among the highest Q/V ratios ever reported in photonic crystal cavities, holding great promise for the realization of integrated photonic platforms based on ultra-high-Q resonators. (C) 2014 AIP Publishing LLC.