search

thieu1995 / MHA-TSP

Meta-Heuristic Algorithm for Travelling Salesman Problem
GNU General Public License v3.0
8 stars 4 forks source link

Help may be required #1

Open brunolnetto opened 2 years ago

brunolnetto commented 2 years ago

Hi,

Your heuristics seem very promising, but the gif videos say otherwise. I suspect you may need some expert advice. You can ask this guy for some help: https://www.linkedin.com/in/thiagomoretto/

HIs github repository is here: https://github.com/thiagomoretto

brunolnetto commented 2 years ago

I recommend strongly that you read this article: https://mathworld.wolfram.com/NP-Problem.html

thieu1995 commented 2 years ago

Hi @brunolnetto, First, thanks for your suggestion. I will take a note. Second, this is not my algorithm. I read research papers and implement exactly what is written in the paper. So the result of an algorithm for a specific problem is good or not good depending on the problem and the algorithm's strategy itself. Third, Metaheuristic algorithms (MHA) (Nature-inspired computing, swarm intellegence, population-based methods) belongs to Heuristics (1 of the largest branch of the optimization field), but Heuristics in general for solving discrete problems. MHA is for continuous problems. What I am doing here is forcing MHA to solve the discrete problem by using the Round Off method with real-coded representation. Therefore, the results are obviously not looking good because the purpose of MHA is not for discrete problems. Also, I trained the optimizer only for 10 generations. Just for the simple purpose of visualization. You can try to increase number of generations or try different Optimizers.

brunolnetto commented 2 years ago

Great, you seem to know about the caveats. 2017 I thought about developing a library like yours. I talked about it with the person tagged on this issue but he was concerned more with work rather with academic task. At the time, he implemented Simulated Annealing, Ant Colony, Evolutionary Algorithm and Bee Colony, among others to solve the routing TSP problem. It worked well. I do not know which you have here. We performed firstly a greedy solution like 2-opt [1] and afterwards performed a meta-heutistics like I aforementioned.

[1] https://en.m.wikipedia.org/wiki/3-opt