I would like to know which is the best strategy for a in "incomplete" TSP. It is incomplete because I do not know the reciprocal distances among the "cities" but I can evaluate the overall cost to travel across all "cities" (each city is visited, and only once etc..). I have to deal with ~3000 cities and the function to evaluate the path is pretty costly (~40 seconds) but I can make use of multiprocessing (I span computation on 20 processors). I have tried Tabu Search that shows I can improve solution respect to previous "greedy" attempts. Unfortunately Genetic Algorithms did not yield good solutions (the distance increases!!) likely because crossover and/or mutation inject noise instead of variable information. I used "ordered" crossover and I implemented mutation as swaps among "contiguous" cities. Maybe I would better go to Simulate Annealing but I am interested to know if for such a problem there might be a chance for GAs?!
I think in such type of problem, you should think about hybridizing GA with other methods that can guide it rapidly to the convergence.
So you don't know the distance between each city. However you the cost of one potential solution.
Could you not , at the same time as looking for an optimal solution, gain some informtion cost of each edge? Specifically, lets say one solution is
A->B->C->D->A
and has a cost of 10
While another is:
A->C->B->D->A
Which has a cost of 5
We now know, either: c(A->C) < c(A->B) or c(C->B) < (B->C) or c(BD)
Or more simply put: c(C->B->D) < c(B->C->D)
Where c is the cost of an edge.
In this way I imagine you could get some useful information about the distance between nodes which could then be used by the more traitional algorithms.
Cheers,
Jack
Let be more specific on that. I have a matrix on which I compute a measure that is sensible to the permutations among the rows. An elementary move consists in swapping two rows. Thus, each row of my matrix can be seen as a city of a TSP but no information is available on the presumed "cost" to move from one row to another one because I do not have this information and the measure is computed on the entire matrix.
You can use some machine learning methods to estimate the distances
I think you can apply a hybrid approach of genetic algorithm with any other heuristic algorithm that solves the TSP in order to get better solutions, Moreover, the ordered crossover is a slow technique. you can use DPX or GSX crossovers in order to accelerate the generation of the solutions and improve the quality of them.
I have received a lot of interesting suggestions, thanks to all. While I was still trying to improve GAs I went across some literature mentioning the need of having large populations of chromosomes in order to perform a good crossover (that make sense to me). Unfortunately, since my chromosomes are high dimensional (3004) and the computation of the fitness is pretty demanding I cannot compute it. I have therefore preferred the Tabu Search, that is at least improving any "greedy" solution.
- Badges
- Science topic