Hyperparameter optimization with random search I would like to do a random search for hyperparameter optimization. The procedure can be found in link. One possibility is to define a fine grid and take random combinations. A better approach would be to define a distribution for each parameter.
I'm thinking about optimizing SVM with parameters C and gamma (RBF kernel) and also k-nearest neighbours. Of course C and gamma are continuous while k is discrete.
What distributions can be choosen for C, gamma and k?
Second, let's assume a random search optimization over parameters which have to sum to one. How could one incorporate this constraint into the search?
 A: 
What distributions can be choosen for C, gamma and k?

To reproduce results from other methods, define a box and sample uniformly in the box. This will parallel the procedure of grid search, or any other tuning method, since each point is equally likely a priori. 
But if you want some distributions more informative than these, then you'll have to work that out for the problem at hand because that is inherently a context-dependent question: some problems have larger/smaller $\gamma$ and $C$ than others, which is why we tune hyper-parameters in the first place.
If you decide to make this a fully Bayesian problem with informative probabilities over hyper-parameters, embedding the problem as a logistic regression can create a direct path to probability models.

Second, let's assume a random search optimization over parameters which have to sum to one. How could one incorporate this constraint into the search?

Use a stick-breaking process. You start with a unit interval, and pick a point in the interval according to a probabiltiy distribution over the unit interval. Then you iterate $k-1$ times the process for the interval "to the right" (or left) of the chosen point. At the end, you'll have $k$ value which sum to 1.
You could also review the stan documentation pertaining to sampling of simplex random variables for an alternative presentation of the concept.
A: There are full bayesian formulations for SVMs. Why not using those?. In the case of SVM you may consider Relevance Vector Machines.
kNN is not bayesian, and independent of the underlying probability distribution. How to define a prior then?.
Bayesian models are generative models, that is, they model a complete pdf from which the data is supposed to be sampled from. Therefore, I find it would be more natural to consider GMM or some other more modern non-parametric technique. The question becomes then on how to determine the optimal number of components. The standard way is to sample from a Dirichlet prior, and then sample from the particular mixture obtained from it. 
A: You are basically describing a Bayesian Optimization (updating the distributions of parameters as you observe fitness values). The GPyOpt devel branch has a tutorial on how to fit SVM with it.
Constraints should be relatively straightforward to add.
However, all this might be an overkill. If you are simply interested in how search might improve fitting you might just as well start simple with something like a genetic algorithm.
