Abstract: Random search algorithms are useful for many ill-structured global optimization problems with continuous and/or discrete variables. Successful random search algorithms have made use of Hit-and-Run, a Markov chain Monte Carol sampler known to be the most efficient method for sampling from log-concave distributions over convex bodies in Euclidean space. We discuss previous and new algorithms using Hit-and-Run in a simulated annealing type context as well as a population-based methodology. The algorithms have been based on theoretical analyses, which is extended to mixed continuous/discrete domains. Computational results will also be presented.