Cheat Engine

[HomerSexual]

new version: http://rapidshare.com/files/423238992/TSP.rar


As most people here probably know, there's a tricky problem out there
referred to as the Traveling Salesperson Problem.

@see http://en.wikipedia.org/wiki/Travelling_salesman_problem

I have taken an interest in genetic computation recently so i decided to make a basic GA to "solve" this problem. By solve I mean give the best solution in a given number of evolutions.

A Swap mutation is used as the mutation algorithm.
The genes are filled with alleles referring to an integer represented city.
A vector is filled with Points of these cities.
The fitness is given by 1/distance of tour.

http://rapidshare.com/files/422766857/TSP.rar

I would love to get some discussion to this problem or maybe someone link me to a place with a large input test file and a verified solution so i can run my code against it.

[Jorg hi]

Hmm I have an idea.

Why don't you order the locations by the points that are closest to each other. Example
if you have

0,0
10,10
100,100
15,11

You would go this route

0,0
10,10
15,11
100,00


Probably to order them out you could use a loop to test each location to each location.


OR

BRUTE FORCE EVERYTHING until you get the shortest distance...
You could just brute

[atom0s]

A* pathing could help with this to determine the shortest route to the given destination.
http://en.wikipedia.org/wiki/A*_search_algorithm

As linked on that wiki article here's a site with a Java applet that has an example showing A*, Dijkstra, and 'Depth First' pathing:
http://www.stackframe.com/software/PathFinder

Getting the best route possible is going to land up requiring some amount of bruteforcing either way you go about doing something like this. Without calculation specific paths ahead of time you have no real method of getting the best possible / shortest route.

[HomerSexual]

The problem with the bruteforce is that the TSP is an O(2^x) type problem. It would take a very long time (more time than you will live) to just calculate 30 cities bruteforced.

That is the beauty of this problem, bruteforcing is technically the best way to find the optimal path, but it would take so long and so much computing power for small datasets that it's not possible. Genetic algorithms provide a O(1) efficiency and give a GOOD (usually 2% - 3% difference) path with large datasets

Also going to the closest points does make sense, for CERTAIN datasets, but it is certainly not valid for some datasets, it also requires some form of bruteforce which makes it impractical.

[justa_dude]

[HomerSexual]

I said that genetic algorithms are 95% efficient, I can't prove my way because I don't have any way of checking it. Regardless my algorithm tends to find at least a 100% improvement over the stock 1>2>3>4>5>6>etc layout everytime. If the initial distance is 12000 mine will usually find something < 6000.

Like I said I don't have a dataset large enough to test and lets face it, i'm not going to make one

This was my first attempt at the problem and it doesn't have any "smart" mutation like the best GA's do. I also haven't optimized the population, evolutions, mutation %, what gets mutated, etc. For as SIMPLE of an implementation as mine is, it works quite well

[Flyte]

[tombana]

[HomerSexual]

[justa_dude]

[HomerSexual]

[HomerSexual]

http://rapidshare.com/files/423166758/TSP.rar

New version uploaded which generates a graph of the tour

[justa_dude]

FYI, I just looked at the code and the nested loops that check for duplicate cities mean that your algorithm runs slower than n^2, definitely slower than O(1) (constant). You can trade space for speed and store data in a search tree instead.

Cheers,
adude

[HomerSexual]

uh no part in my code searchs for duplicate cities...it doesn't have to. The algorithm is filled up with value from 0->citylen and a swap mutation is applied therefore it's impossible to have duplicates. Any of the inefficiencies probably happen outside of the main algorithm and are only run once...just sayin

Edit: I just looked at the code for the problem area and there's no nested for loops in my code lawl...editedit. I see what you mean now and that function sholud have been removed. My oringal algorithm wasn't using a swap and therefore two cities could occur twice. I just removed it without any side effect to output.

Thanks for pointing that out but realize it shouldn't have been used so i removed it

http://rapidshare.com/files/423238992/TSP.rar

Edit again: Another improvement i just added is the fintess is 1/ 5*distance instead of 1 / distance. This puts more pressure on the population to evolve and i noticed lower distances immediately

[Jorg hi]

Mathematical intervention should not be creating solutions based of problems, but creating solutions based upon reason.