r/algorithms • • Dec 07 '18

Genetic Algorithm - Applications & Examples

https://codecampanion.blogspot.com/2018/12/genetic-algorithm-explained.html
28 Upvotes

5 comments sorted by

3

u/[deleted] Dec 08 '18

I mean, I guess I'll be the contrarian. Can we just stop saying that genetic algorithms are good for solving TSP instances? They're not. Branch and cut algorithms can solve (to provable optimality) TSP instances on hundreds of nodes in seconds on a laptop. Concorde, arguable the best TSP solver out there, has solved (again, provable optimality) an instance with 85900 nodes, using branch and cut.

Genetic algorithms have their place. But if your problem can be easily modeled as an integer linear program, you're almost surely better off using branch and cut.

7

u/[deleted] Dec 08 '18

William J. Cook the author of Concorde had the following to say:

"The world champions in the area are without a doubt Keld Halsgaun of Denmark and Yuichi Nagata of Japan... Nagata's implementation of a genetic algorithm for the TSP has produced the best-known tour in the Mona Lisa TSP challenge as well a record solution for the two largest examples in the National TSP Collection."

FYI: in order to solve the instance with 85900. Concorde had a running time of 2 years and a combined run time of ~150 years. Lin–Kernighan heuristic and a genetic algorithm with edge assembly crossover are a lot faster and far more suited for large TSP problems.

But if your problem can be easily modeled as an integer linear program, you're almost surely better off using branch and cut.

That is a weird statement. I think almost every problem can be modeled as a integer linear program and lunch can never be free.

1

u/[deleted] Dec 08 '18

I'm aware of the running time. The algorithm also finds the optimal solution, as in "here is the solution, and here is a certificate that no other solution can do better". If we're talking about solving the instance, genetic algorithms just aren't going to do it. They can be used as part of a framework to do the job, but they aren't a standalone solution.

I'll agree that almost everything can be modeled as an ILP. I didn't want to write a paragraph clarifying what I meant because it was late, so I just tacked "easily" on the front and hoped for the best. What I mean is basically this: if you can model the problem without using big M constraints and lots of binary variables to stitch multiple aspects of the problem together, and the resulting formulation isn't huge, then branch and cut is a good candidate solution approach. If your formulation is also tight, then branch and cut is a great first choice.

2

u/e_for_oil-er Dec 07 '18

I implemented a genetic algorithm in an Optimization class, and I was surprised of the efficiency and precision it had! In some cases (bumpy functions with a lot of local minimums), the algorithm (differential evolution) was better than traditional gradient descent methods because it could go "uphill" when reaching a local convexity zone, something gradient methods do not usually allow.

1

u/successbux Dec 07 '18

I am implementing a genetic algorithm for travelling salesman problem with modified cycle crossover Man it's real tough