22
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
The answer to the question is: No.
(Although one can debate what exactly is a "metaheuristic")
The "gold standard" for finding high quality feasible solutions for the TSP is the ...
- 3,158
7
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
Take a look at the Concorde https://www.math.uwaterloo.ca/tsp/concorde.html.
If it's a TSP problem, not a variant, Concorde can solve it and it is a beast.
When you say "versions of the ...
5
votes
Use GA for Assignment Problem?
I agree with @RobPratt that a GA is not the ideal way to solve an assignment problem. The Wikipedia entry for assignment problems lists a few alternatives, and as Rob points out an LP solver should ...
- 36.4k
4
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
There's been a brilliant development in the Traveling Salesman problem recently leveraging neuromorphic computing. Essentially, neuromorphic chips contain a massive array of (often) physical neurons ...
- 49
4
votes
Prove NP Hardness for non-convex multi-objective optimization
The notion of NP-hardness relates to whether one class of problems can be solved by a solver for another class of problems where the translation overhead is negligible.
The problem you presented is ...
- 3,945
4
votes
Measuring performance of Genetic Algorithms
There is no magic. Considering that the algorithm is carefully designed, it is a matter of solution quality versus running time. If each run needs a lot of time to converge, running it 30 times could ...
- 2,865
3
votes
Prove NP Hardness for non-convex multi-objective optimization
NP-hardness is an asymptotic result of increasing problem dimensions. It is not a property of one fixed problem instance. So to ask whether your problem class is NP-hard, you would have to explain how ...
- 36.4k
3
votes
Measuring performance of Genetic Algorithms
Assuming the random seed is different every time, genetic algorithms (and by extension stochastic algorithms) are non-deterministic by nature, which is why they need to be run many times until we get &...
- 11.8k
3
votes
Accepted
Genetic Algorithm
GAs tend to "converge" in the sense that the population tends to become homogeneous after a while (which I believe is known as "stagnation"). There are various things implemented ...
- 36.4k
3
votes
Accepted
I didn't understand my problem with PSO and GA
First, let me state that it is difficult to write an answer to this question as it is very vague and lacks necessary detail. The real question here is not that GA and PSO perform differently (that's ...
- 303
2
votes
Job scheduling for a 2 stage job with 2 machines available for each stage
Since you did not say otherwise, I am going to assume that (a) all jobs are available for release at time 0, (b) each machine can handle any of the jobs and (c) your criterion is minimizing makespan (...
- 36.4k
1
vote
Accepted
Prove NP Hardness for non-convex multi-objective optimization
Considering the first given objective function, the problem is trivial to solve. The decision variables X1 and X2 are positive. Because polynomial with positive coefficients only, the objective ...
- 2,865
Only top scored, non community-wiki answers of a minimum length are eligible