I’d like to bring up a wonderful field to keep in mind when you try to bring randomness and random solution generation into creative processes: genetic algorithms.
Genetic algorithms show two interesting things, relative to randomness. First, genetic algorithms are scored based on how much faster they are than generating random solutions and checking them. Second, you don’t actually need randomness to implement genetic algorithms!
All you need to pull off a genetic algorithm—or any similar search algorithm—is /a means of generating solutions similar to your current best solution(s)/. This process does not have to be random! If your algorithm enumerated all of the neighboring solutions to a given solution, and tried them in turn, it would work just as well (more or less) as a genetic algorithm which mutated its solutions randomly.