用GA（遺傳算法）實現解決TSP是否正常需要很長時間？

Question

我正在爲一個項目的GA工作。我正在嘗試使用GA來解決旅行商問題。我用array[]來存儲數據，我認爲Array s比List快得多。但由於任何原因，它需要太多時間。例如用MaxPopulation = 100000,StartPopulation=1000該程序持續約1分鐘完成。我想知道這是否是一個問題。如果是這樣，我該如何解決這個問題？

守則的一部分，從我的實現：

 public void StartAsync() 
     { 
      Task.Run(() => 
      { 
       CreatePopulation(); 
       currentPopSize = startPopNumber; 

       while (currentPopSize < maxPopNumber) 
       { 
        Tour[] elits = ElitChromosoms(); 

        for (int i = 0; i < maxCrossingOver; i++) 
        { 
         if (currentPopSize >= maxPopNumber) 
          break; 
         int x = rnd.Next(elits.Length - 1); 
         int y = rnd.Next(elits.Length - 1); 

         Tour parent1 = elits[x]; 
         Tour parent2 = elits[y]; 

         Tour child = CrossingOver(parent1, parent2); 

         int mut = rnd.Next(100); 

         if (mutPosibility >= mut) 
         { 
          child = Mutation(child); 
         } 
         population[currentPopSize] = child; 
         currentPopSize++; 
        } 
        progress = currentPopSize * 100/population.Length; 
        this.Progress = progress; 
        GC.Collect(); 
       } 
       if (GACompleted != null) 
        GACompleted(this, EventArgs.Empty); 
      }); 
     } 

在這裏「葉利茨」是具有比人口的平均擬合值擬合值的chromosoms。

Answer 1

好的。我剛剛找到了一個解決方案。不要使用大小爲maxPopulation的數組，而要改變那些適應性差的老人和壞人。現在，我正在處理一個尺寸較小的數組，它的長度爲10000.之前的長度爲1,000.000，時間太長。現在，在每一次迭代中，選擇最好的1000條染色體，並使用這些染色體作爲親本來創建新的染色體，並替換爲老的和壞的染色體。這工作完美。

代碼示例：

public void StartAsync() 
      { 
       CreatePopulation(); //Creates chromosoms for starting 
       currentProducedPopSize = popNumber; //produced chromosom number, starts with the length of the starting population 

       while (currentProducedPopSize < maxPopNumber && !stopped) 
       { 
        Tour[] elits = ElitChromosoms();//Gets best 1000 chromosoms 
        Array.Reverse(population);//Orders by descending 
        this.Best = elits[0]; 
       //Create new chromosom as many as the number of bad chromosoms 
        for (int i = 0; i < population.Length - elits.Length; i++) 
        { 
         if (currentProducedPopSize >= maxPopNumber || stopped) 
          break; 
         int x = rnd.Next(elits.Length - 1); 
         int y = rnd.Next(elits.Length - 1); 

         Tour parent1 = elits[x]; 
         Tour parent2 = elits[y]; 

         Tour child = CrossingOver(parent1, parent2); 

         int mut = rnd.Next(100); 

         if (mutPosibility <= mut) 
         { 
          child = Mutation(child); 
         } 
         population[i] = child;//Replace new chromosoms 
         currentProducedPopSize++;//Increase produced chromosom number 
        } 

        progress = currentProducedPopSize * 100/maxPopNumber; 
        this.Progress = progress; 
        GC.Collect(); 
       } 
       stopped = false; 
       this.Best = population[population.Length - 1]; 
       if (GACompleted != null) 
        GACompleted(this, EventArgs.Empty); 
      } 

      Tour[] ElitChromosoms() 
      { 
       Array.Sort(population); 
       Tour[] elits = new Tour[popNumber/10]; 

       Array.Copy(population, elits, elits.Length); 
       return elits; 

      } 

Answer 2

科學論文提出人口較少。也許你應該遵循其他作者寫的內容。人口衆多並沒有給你帶來任何好處。

TSP可以通過GA來解決，但也許這不是解決這個問題最有效的方法。看看這個TSP-GA的視覺表示：http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php