Answers.Body: <p>This is a very large question that could be answered in a variety of ways depending on the context.</p>
  
  <p>For some optimization problems operating under specific conditions you can make theoretical guarantees that your optimization will solve your problem.  A specific example of this is running the gradient descent algorithm on a convex function.  If the function being optimized is <a href="https://en.wikipedia.org/wiki/Convex_function" rel="nofollow noreferrer">convex</a> then gradient descent is guaranteed to converge to the correct solution.  Given the nice properties of convex functions, there are many types of optimization where you can make these theoretical guarantees.</p>
  
  <p>When evolutionary algorithms (and many non-derivative based optimizations) are run, it's much harder to make these types of guarantees.  Often in the literature I've seen people try their functions on several baseline optimization functions and report back the minimum or maximum found.  Many of these are included in Facebook's <a href="https://github.com/facebookresearch/nevergrad/blob/master/nevergrad/functions/corefuncs.py" rel="nofollow noreferrer">nevergrad</a> optimization library to be used for evaluation.  An example of one of these functions is included below,</p>
  
  <p><a href="https://i.sstatic.net/b7G0p.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/b7G0p.png" alt="The Rastrigin Function"></a></p>
  
  <p>Even if you can prove that your algorithm minimizes several objective functions you could be testing on, there could be other properties that should be considered.  Some of these include the following: the speed at which the algorithm converges; the number of evaluations of the objective function (if not closed form), and even the amount of space in memory which is required for your optimization.  All of these (and many more) factors could come into play when evaluating your algorithm.</p>
  
  <p>Scientists may use functions like this one to evaluate their optimization and compare it to other algorithms that are similar.  To answer your final question though, "How can I see if my optimization works for <strong>every</strong> problem", I would say that's a bit of a loaded question.  Most of the time these optimizations need some sort of constraint to make a generalized guarantee.  I would look at the constraints of your problem and go from there.</p>
  
  <p>If you're interested, <a href="https://www.researchgate.net/publication/317724973_Best_Practices_for_Comparing_Optimization_Algorithms" rel="nofollow noreferrer">here's</a> a good paper that goes much more in depth than I did here.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-20T17:05:42.823Z
Answers.LastActivityDate: 2019-01-24T20:36:54.703Z
Answers.LastEditDate: 2019-01-24T20:36:54.703Z
Answers.UserDisplayName: juicedatom
Body: <p>How do I check which algorithm solves my problem best?</p>
  
  <p>Given a optimaization problem, I apply different well known optimization algorithms (genetic algorithm, simulated annealing, ant colony etc.) to solve my problem. However, how do I know if my implementation ( e.g. cost function) is working for every case? How can I compare the algorithms or their goodness in the context of my problem?</p>
  
Tags: <optimization>
Title: Method to check goodness of combinatorial optimization algorithm implementation
UserDisplayName: Bryan McGill
ThreadText: # Method to check goodness of combinatorial optimization algorithm implementation
  
  (Asked by: username_0 on 2019-01-17)
  
  How do I check which algorithm solves my problem best?
  
  Given a optimaization problem, I apply different well known optimization algorithms (genetic algorithm, simulated annealing, ant colony etc.) to solve my problem. However, how do I know if my implementation ( e.g. cost function) is working for every case? How can I compare the algorithms or their goodness in the context of my problem?
  
  **Tags:** optimization
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-01-20. Score: 3
  
  This is a very large question that could be answered in a variety of ways depending on the context.
  
  For some optimization problems operating under specific conditions you can make theoretical guarantees that your optimization will solve your problem. A specific example of this is running the gradient descent algorithm on a convex function. If the function being optimized is [convex](https://en.wikipedia.org/wiki/Convex_function) then gradient descent is guaranteed to converge to the correct solution. Given the nice properties of convex functions, there are many types of optimization where you can make these theoretical guarantees.
  
  When evolutionary algorithms (and many non-derivative based optimizations) are run, it's much harder to make these types of guarantees. Often in the literature I've seen people try their functions on several baseline optimization functions and report back the minimum or maximum found. Many of these are included in Facebook's [nevergrad](https://github.com/facebookresearch/nevergrad/blob/master/nevergrad/functions/corefuncs.py) optimization library to be used for evaluation. An example of one of these functions is included below,
  
  [![The Rastrigin Function](https://i.sstatic.net/b7G0p.png)](https://i.sstatic.net/b7G0p.png)
  
  Even if you can prove that your algorithm minimizes several objective functions you could be testing on, there could be other properties that should be considered. Some of these include the following: the speed at which the algorithm converges; the number of evaluations of the objective function (if not closed form), and even the amount of space in memory which is required for your optimization. All of these (and many more) factors could come into play when evaluating your algorithm.
  
  Scientists may use functions like this one to evaluate their optimization and compare it to other algorithms that are similar. To answer your final question though, "How can I see if my optimization works for **every** problem", I would say that's a bit of a loaded question. Most of the time these optimizations need some sort of constraint to make a generalized guarantee. I would look at the constraints of your problem and go from there.
  
  If you're interested, [here's](https://www.researchgate.net/publication/317724973_Best_Practices_for_Comparing_Optimization_Algorithms) a good paper that goes much more in depth than I did here.
  
  
  ---
  
  