A very easy simple improvement over random search is to use a low discrepancy sequence. They were designed almost for this purpose (avoiding the problems caused by irrelevant dimensions). I don't know why I never see it suggested... it's not as good as gaussian process modeling, but it's very easy to implement and it clearly dominates random search for this application.