Skip to main content
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 ...
Philipp Christophel's user avatar
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 ...
Juan Pablo Mesa's user avatar
5 votes
Accepted

Is evolution algorithm suitable for combinatorial optimization problem

While pure Evolutionary algorithms might have some drawbacks, when combined with local search methods, which can make further use of the problem structure, Genetic algorithms can perform very well. ...
PeterD's user avatar
  • 1,706
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 ...
prubin's user avatar
  • 39.5k
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 ...
ChengDuum's user avatar
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 ...
worldsmithhelper's user avatar
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 ...
Hexaly's user avatar
  • 2,986
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 ...
prubin's user avatar
  • 39.5k
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 &...
Nikos Kazazakis's user avatar
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 ...
prubin's user avatar
  • 39.5k
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 ...
Andreas's user avatar
  • 313
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 (...
prubin's user avatar
  • 39.5k
2 votes
Accepted

Need help writing a metaheuristic problem

I would first try the mixed-integer linear programming approach, but if you want a metaheuristic, one possibility is a random key genetic algorithm. Given your minimum and maximum cluster sizes, you ...
prubin's user avatar
  • 39.5k
1 vote

Optimization algorithm for space debris

ACO, genetic algorithms and other metaheuristics can be adapted to constrained problems by adding to the objective function penalties for constraint violations and then treating the problem as ...
prubin's user avatar
  • 39.5k
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 ...
Hexaly's user avatar
  • 2,986

Only top scored, non community-wiki answers of a minimum length are eligible