In this paper, we propose an improved excitation generation algorithm for the full configuration interaction quantum Monte Carlo method, which is particularly effective in systems described by localized orbitals. The method is an extension of the precomputed heat-bath strategy of Holmes et al., with more effective sampling of double excitations and a novel approach for nonuniform sampling of single excitations. We demonstrate the effectiveness of the algorithm for a chain of 30 hydrogen atoms with atom-localized orbitals, a stack of benzene molecules, and an Fe(II)-porphyrin model complex, whereby we show an overall efficiency gain by a factor of two to four, as measured by variance reduction per wall-clock time.