Optimizing cheap functions on mixed search space
In general you can't. Optimization is a tricky business and proper solutions are only known if your $f$ and/or your search space belong to some restricted class.

You can try various heuristics. Things to google for include "genetic algorithms", "evolutionary algorithms", and "simulated annealing".