I'm an undergraduate engineering student. I took the course of Optimization this semester, and the heuristic methods. My professor basically says that these methods, PSO for example have no mathematical background and they do not work! I have found nothing online supporting his views on the matter. I saw a paper that used genetic algorithm to optimize the PID coefficients (control theory), so I know these methods are being used. But if they have no proof, how can we know that we have reached an optimum point? or are there tricky special problems that they give the wrong answer to? is there a condition to using these methods?
Asked
Active
Viewed 126 times
2
-
He who? ${}{}{}$ – Mariano Suárez-Álvarez Mar 10 '17 at 17:03
-
He, my Professor :) – mehrdad Mar 10 '17 at 17:04
-
Have you asked him this? – Mariano Suárez-Álvarez Mar 10 '17 at 17:10
-
Well. It will depend on your definition of "work". What qualifies for something to "work"? Maybe he means they have not been proven mathematically to find an optimum. – mathreadler Mar 10 '17 at 17:16
1 Answers
2
As @mathreader pointed out, its a matter of definitions: you need to specify what "work" means.
If by "work" you mean find a feasible solution of good quality, then yes, heuristics work: this is what they are designed to do.
If by "work" you mean find the optimal solution, then no, heuristics cannot guarantee optimality.
However, it is possible to prove that certain heuristics are optimal for certain specific problems. For example, if you are familiar with graph coloring, you know that it is a combinatorial difficult problem (it is NP-hard). Many heuristics have been developed for this problem, the most popular ones being
- the WELSH-POWELL algorithm
- the DSATUR algorithm
- the RLF algorithm
It is possible to show that the DSATUR algorithm is optimal for a large family of graphs (bipartite graphs, cycles, trees, cacti, etc). So for these specific graphs, the heuristic does work (in the sense of the second definition).
Kuifje
- 9,584
-
you are saying that these methods will give a good answer. what is a good answer? I mean on average, how much do they miss the optimum point? is like when you set the algorithm to stop when the ratio of normalized fitnesses is (for example) greater than 0.95? @Kuifje – mehrdad Mar 10 '17 at 19:40
-
1That is a good question. For some heuristics, the worst possible theoretical gap is known, for others it is not. For the above graph coloring heuristics, the gap can be arbitrarily large on general graphs. To mention another example, for the TSP, the Christofides heuristic guarantees that its solutions will be within a factor of 3/2 of the optimal solution length. – Kuifje Mar 10 '17 at 20:04