Printable View
I've been doodling on a GA lately, solving the travelling salesman problem. The difficulty is.. I don't know if the answers are right! How can I check? :eek2: :rolleyes:
Here:
Random points are generated, and each genome has a different order between them, the shortest path wins.
I know the premise, and have read about how it was solved for 3800 cities, but they must have started by picking all of the cities and calculating the distance between them.
How does this code work, and how long does it run.
I let it run for 5 minutes and then killed it. Not sure what I was looking for/at.
It picks a random number of cities (determined by a constant at the bottom of general declarations in functionals called "GenomeLength") and then creates a population with genomes which each have GenomeLength * GeneLength genes (genelength is 6, enough to go from -127 to 127) and when it is testing a genome it:
Starts at city 0 (the start point) and then walks to city 0 + gene 1 (if it's 010000 it goes to city 0 + 127 = 127). Then it checks the next gene and goes to the next city (if it's 100001 = -1 then it would go to 127 - 1 = 126)
Note that when it's heading to the "next" city it skips cities that have already been visited and 0 is considered to be 1.
Then it takes the total path length and does:
Fitness = (1000/Pathlength)^3
So that longer paths give a lower fitness. (^3 makes worse paths have much lower fitnesses than good ones)
I was testing it by making each city in a straight line (city 1 is at (1,0), 2 is at (2,0) etc and checking if the final fitness was right)
Uh, ya...
sorry, but I wouldn't know if it was right or wrong...