The recently developed linear combination of atomic potentials (LCAP) approach [M. Wang et al., J. Am. Chem. Soc. 128, 3228 (2006)] allows continuous optimization in a discrete chemical space, and thus is useful in the design of molecules for targeted properties. To address further challenges arising from the rugged, continuous property surfaces in the LCAP approach, we develop a gradient-directed Monte Carlo (GDMC) strategy as an augmentation to the original LCAP optimization method. The GDMC method retains the power of exploring molecular space by utilizing local gradient information computed from the LCAP approach to jump between discrete molecular structures. It also allows random MC moves to overcome barriers between local optima on property surfaces. The combined GDMC-LCAP approach is demonstrated here for optimizing nonlinear optical properties in a class of donor-acceptor substituted benzene and porphyrin frameworks. Specifically, one molecule with four nitrogen atoms in the porphyrin ring was found to have a larger first hyperpolarizability than structures with the conventional porphyrin motif.