GA: Traveling Salesman Problem

[NickThissen]

So, I decided to try your approach, but it's not really giving me a desired result. In fact, the result is usually more or less the same as without your method, which was also not very good. That makes me think the problem is not with your idea, but with my original code.

The problem I'm seeing is the following. I can generate the locations of let's say 10 cities randomly. If I run my GA, I update the picturebox with the best tour after each generation, so I can see the progress being made. That probably isn't very good for speed, but that's not an issue at the moment.

What I'm seeing is that most of the times the tour looks pretty good. It looks like what I would have chosen as the shortest if I would have to do it visually. But occasionally a much worse tour crops up for a split second (I can see it jump into view for a tiny amount of time before the much better tour takes over again). I thought that's not really a problem, probably a quirk of the mutation where it mutates into a much worse tour. I thought those bad tours would be weeded out eventually.

But I guess i was wrong, because most of the time, when the algorithm stops (after 2000 runs at the moment), it stops on one of the bad tours! Even though it had much better tours just seconds before...

I can't really understand this. Is it just a coincidence that the 2000th population is a bad one? I am not seeing this behavior every time, but I think more than one would expect from coincidence...



Here is what I'm doing at the moment, perhaps someone can see something wrong:

Dim tours As New List(Of Tour)
        Dim p As Population
 
        'Run 'populationSize' generations 25 times, each time picking the best tour
        'Add those best tours to the 'tours' list
        'Finally use THAT list of tours as the initial population for the real run.
        For i As Integer = 0 To My.Settings.PopulationSize - 1
            p = New Population()
            p.Initialize(Me.cities)
 
            For n As Integer = 0 To 24
                p.RunGeneration()
            Next
 
            Dim bestTour As Tour = (From t As Tour In p.Tours _
                                        Order By t.Fitness _
                                        Select t).First()
            tours.Add(bestTour)
        Next
 
        'Create new Population based on these tours:
        Dim finalPop As Population = New Population(tours)
 
        'Finally run this population lots of times:
        For i As Integer = 0 To 1999
            finalPop.RunGeneration()
 
            Dim bestTour As Tour = (From t As Tour In finalPop.Tours _
                            Order By t.Fitness _
                            Select t).First()
            Me.cities = bestTour.Cities
            lblTourLength.Text = Math.Round(bestTour.Length, 1).ToString()
            pic.Refresh()
        Next

The purpose of the classes should be obvious from their names. The Initialize method of the Population class creates a number (100) of new tours and randomizes the order of the cities in each tour.

The RunGeneration method runs a single generation (selection, recombination, mutation)

Then I select the best tour after 25 generations (perhaps not enough but it's taking quite some time, I'm experimenting with more) and add it to a new Tours collection.

Finally, after I have 100 (population size) tours in my collection, I use those tours in a new Population (this time they are not randomized).
I run 2000 generations using that population, and I update the picturebox with the cities of the best tour after each run so I can see some progress.

Seems ok, no?



The problem I can see with this approach though is that, perhaps, all 100 initial tours (selected from 100 "pre-runs") are too similar. If you start off with individuals who are too similar you won't often get radically different individuals (unless your mutation rate is very high), so if you happen to start off in a local minimum, you often can't get out of it. If that local minimum is not the best minimum then the algorithm is doomed from the start...