Have you tried using markov chain monte carlo to perform a weighted random walk of solution space?