Thanks to their high quality factor, combined to the smallest modal volume, defect-cavities in photonic crystal slabs represent a promising, versatile tool for fundamental studies and applications in photonics. In paricular, the L3, H0, and H1 defects are the most popular and widespread cavity designs, due to their compactness, simplicity, and small mode volume. For these cavities, the current best optimal designs still result in Q-values of a few times 10(5) only, namely one order of magnitude below the bound set by fabrication imperfections and material absorption in silicon. Here, we use a genetic algorithm to find a global maximum of the quality factor of these designs, by varying the positions of few neighbouring holes. We consistently find Q-values above one million - one order of magnitude higher than previous designs. Furthermore, we study the effect of disorder on the optimal designs and conclude that a similar improvement is also expected experimentally in state-of-the-art systems.