为什么TSP的遗传算法实现不能有效工作？ [英] Why the Genetic Algorithym implementation for TSP doesn't work efficiently?

问题描述

我正致力于遗传算法来解决旅行商问题。我的chromosom表示就像32415一样是城市的顺序。我尝试了3种Crossing-Over方法。这些是Classic，OX1和Greedy。但是他们中任何一个都无法帮助我有效地解决TSP问题。基本问题是算法总是留下不固定的交叉路径。这意味着它不好用。



要明确说明，请参阅此图片。如您所见，可以修复带圆圈的路径以获得更好的解决方案。但GA不会这样做。我该如何解决这个问题呢？



我正在使用5人组的锦标赛来选择父母，一般是％3变异赔率和10000固定人口规模。

我的交叉，变异和GA程序代码：

I am working on Genetic Algorithyms to solve Travelling Salesman Problem. My chromosom representation is like 32415 as the order of the cities. I have tried 3 Crossing-Over methods.These are Classic, OX1 and Greedy. But any of them couldnt help me to solve TSP efficiently. The basic problem is that the algorithym always leaves an unfixed crossed path. This means it doesnt works good.

To be clearly understanded, please see this image. The circled paths can be fixed to get a better solution as you see.But GA doesn't do that. How can I fix this problem?

I am using tournament with group of 5 to select parents, generally %3 mutation odds and 10000 fixed population size.
My code for Crossing Over, Mutation and GA Procedure:

Tour OrderingCrossingOver(Tour mother, Tour father)
{
   //Selected number of gens for CO
    int numberOfGens = rnd.Next(1, N - 2);
    //Selected position to start for CO
    int pos = rnd.Next(0, N - numberOfGens);
    City[] gens = new City[N];

    List<City> noneGens = new List<City>(father.Cities);
    List<int> nonePos = new List<int>();
    for (int i = 0; i < N; i++)
    {
        if (i < pos || i >= pos + numberOfGens)
        {
            //Get gen positions to be empty
            nonePos.Add(i);
            continue;
        }
        gens[i] = mother.Cities[i];
        noneGens.Remove(gens[i]);
    }
    for (int i = 0; i < noneGens.Count; i++)
    {
        //Fill empty gens using father
        gens[nonePos[i]] = noneGens[i];
    }
    noneGens.Clear();
    nonePos.Clear();
    return new Tour(map) { Cities = gens };
}
void Mutation(Tour tour)
{
    int i = rnd.Next(N - 1);
    int j = rnd.Next(N - 1);

    City temp = tour.Cities[i];
    tour.Cities[i] = tour.Cities[j];
    tour.Cities[j] = temp;

    mut++;
}
public void StartAsync()
{
    Task.Run(() =>
    {
        isRunning = true;
        CreatePopulation();
        int st = 0;
        while (currentProducedPopSize < maxPopNumber && !stopped)
        {
            //Get parents ascending
            int[] nums = selectParents();

            //Get best two chromosomes
            Tour parent1 = population[nums[0]];
            Tour parent2 = population[nums[1]];

            #region First Child

            Tour child = OrderingCrossingOver(parent1, parent2);
            Tour old = new Tour(map) { Cities = child.Cities };
            if (mutPosibility >= rnd.Next(1, 100))
                Mutation(child);

            population[nums[nums.Length - 1]] = child;

            if (this.Best.Value > child.Value)
                this.Best = child;

            #endregion

            #region Second Child

            child = OrderingCrossingOver(parent2, parent1);

            if (mutPosibility >= rnd.Next(1, 100))
                Mutation(child);

            population[nums[nums.Length - 2]] = child;

            if (this.Best.Value > child.Value)
                this.Best = child;

            #endregion

            currentProducedPopSize += 2;
            st++;
            this.Progress = double.Parse((currentProducedPopSize * 1.0 / maxPopNumber * 100).ToString("00.00"));

        }

        isRunning = false;
        stopped = false;
        this.Best = population[population.Length - 1];
        if (GACompleted != null)
            GACompleted(this, EventArgs.Empty);
    });
}

推荐答案

我认为现在是时候停止猜测你的代码在做什么了。是时候看到你的代码正在执行并确保它能达到预期的效果。



调试器是你的朋友。它会告诉你你的代码到底在做什么。

一步一步地执行，检查变量，你会发现它有一个停止做你期望的点。

掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]

http://docs.oracle .com / javase / 7 / docs / technotes / tools / windows / jdb.html [ ^ ]

https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]



选择一个能够解决问题的染色体并在调试器中运行（逐步）你的程序以查看追加的内容。

I think it is time for you to stop guessing what your code is doing. It is time to see your code executing and ensuring that it does what you expect.

The debugger is your friend. It will show you what your code is really doing.
Follow the execution step by step, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

Select a chromosome that hexibit your problem and run (step by step) your program in debugger to see what append.

这篇关于为什么TSP的遗传算法实现不能有效工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！