Open Beagle TSP

[Clerton]

Mr. Gagn�
Since along this year I'm studying the framework OpenBeagle. In the last
60 days I have done tests with a view to approval of it to use it in my
research masters. In these last three weeks lead tests with the example
of a Salesman. Everything went well, except because of the results
obtained, compared to the TSPLIB. In an instance with 51 cities, the
"tour" of the TSPLIB results in a distance of 423.9007 and the same
instance with OpenBeagle results in a distance of 1539.3582 for 10000
generations, without changing any parameter (I'm using the example of
OpenBeagle ). What could be wrong? Any idea why this discrepancy?

ANTONIO CLERTON SANTANA DE ARAUJO
IMPERATRIZ - MARANH�O
BRASIL

[Christian Gagné]

Dear Antonio,

The TSP example in Open BEAGLE is presented to illustrate the use of permutation representations. It is by no mean made to be very efficient for the TSP. The evolutionary algorithm implemented in this example is a generic metaheuristics not specialized at all for the TSP. There have been several proposals for customizing evolutionary algorithm by including in it TSP-specific heuristics, but that was not the objective of the example. The objective with the example was really to show how to make coding with Open BEAGLE.

TSPLIB is made for solving the TSP problem, and only this problem. It certainly includes high performance heuristics made specifically to achieve excellent performances. Open BEAGLE is not made for this at all, so it is expected that the results will differ significantly. You just cannot compare these two like that, these are apples and oranges.

If you want to do efficiently TSP-type problems with an evolutionary algorithms, then you can consider to make custom variation operators that would include heuristics for solving that problem. Open BEAGLE is made to be customized, so for that purpose, that's a good tool.

Finally, I also find the difference between the distance found with TSPLIB (423) and Open BEAGLE (1539) quite large, although it needs to be compared with the values obtained from a random Hamiltonian cycle in the graph. Be sure that exactly the same distance measure is computed, as there might be some factors (e.g. square root, normalization factor) that may be missing from one or another implementation.

Hope this help,

Christian


On Nov 25, 2013, at 12:43 PM, Clerton <clert...@gmail.com> wrote:

> Mr. Gagné

> Since along this year I'm studying the framework OpenBeagle. In the last 60 days I have done tests with a view to approval of it to use it in my research masters. In these last three weeks lead tests with the example of a Salesman. Everything went well, except because of the results obtained, compared to the TSPLIB. In an instance with 51 cities, the "tour" of the TSPLIB results in a distance of 423.9007 and the same instance with OpenBeagle results in a distance of 1539.3582 for 10000 generations, without changing any parameter (I'm using the example of OpenBeagle ). What could be wrong? Any idea why this discrepancy?
>
> ANTONIO CLERTON SANTANA DE ARAUJO

> IMPERATRIZ - MARANHÃO
> BRASIL

--
Christian Gagné
http://vision.gel.ulaval.ca/~cgagne