1
$\begingroup$

I would like to know under optimization taxonomy, where do the following method fall?

I have a combinatarial optimization problem, that I am trying to solve, Maximize an objective value for the finite set of configurations. (object orientation and position and another parameter). Currently I am doing the following,

Randomly sample from each configuration and then apply the objective function and find the parameters that maximze this function.Ofcourse, I dont claim optimalty guarantee here, but an approximation is fine.

Does this fall under Monte Carlo methods?

Thanks

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

This sounds like random search: randomly sample a solution, and check for its fitness.

The main recommendation for random search is that it's extremely simple to implement and has a nice probability guarantee associated with it: you only need 60 experiments to have a 95% chance of finding a solution among the best 5% of solutions.

More information:

Improve this answer
$\endgroup$
3
  • $\begingroup$ Awesome! Thank you so much for the quick reply. Will take a look at the links. $\endgroup$
    – Krishnan
    Commented Jul 27, 2019 at 16:38
  • 1
    $\begingroup$ "you only need 60 experiments to have a 95% chance of finding a solution among the best 5% of solutions." I think this statement is largely misleading (or maybe I don't understand the context). What exactly "best 5% of solutions" means is hard to define, but, to formally define things, suppose we have a Bayesian problem and we sample parameters randomly 60 parameter vectors from the prior and evaluate the likelihood over those points. If the data is strongly informative compared with the prior, with high probability we will have a very suboptimal solution. $\endgroup$
    – Cliff AB
    Commented Jul 27, 2019 at 18:27
  • $\begingroup$ @CliffAB I don’t think you fully understand the context; this is not a Bayesian setting. The links provide more details. $\endgroup$
    – Sycorax ♦
    Commented Jul 27, 2019 at 21:47
0
$\begingroup$

I suppose in Machine Learning taxonomy this would be a 'grid search' across the parameter space, albeit the grid search is random in nature in your case whereas it normally is more structured in a loop-like fashion.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for writing. Grid search across the parameter space with random samples, is random search, right? en.wikipedia.org/wiki/Random_search $\endgroup$
    – Krishnan
    Commented Jul 29, 2019 at 11:15
  • $\begingroup$ Yes, indeed! I just wanted to add that a pure random search is always a matter of perspective ;). $\endgroup$
    – Mark Verhagen
    Commented Jul 31, 2019 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.