1

「複数のセールスマン」を使用して TSP 問題の変形を解決しようとしています。一連のnウェイポイントとmドローンがあり、ドローン間のウェイポイント数のバランスを取り、許容可能な最短移動時間を返す結果を生成したいと考えています。 . 現時点では, 最適な解決策を見つけることについてあまり心配していません. この時点で機能するものが欲しいだけです. 問題を従来の TSP 実行に何度も蒸留しました. 私の例はシリーズの場合です.ウェイポイントの数:

[0,1,2,3,4,5,6,7,8,9,10,11]

0 == 11始点と終点はどこですか。ドローンが 4 つあるとします。次のようなものを生成したいとします。

Drone A = [0,1,2,3,11]
Drone B = [0,5,6,7,11]
Drone C = [0,4,8,11]
Drone D = [0,9,10,11]

ただし、クロスオーバー関数で一貫した出力を生成するのに苦労しています。私の現在の機能は次のようになります。

DNA DNA::crossover( DNA &parentB)
{ 
   // sol holds the individual solution for 
   // each drone
   std::vector<std::vector<std::size_t>> sol;
   // contains the values in flattened sol 
   // used to check for duplicates
   std::vector<std::size_t> flat_sol;
  
   // returns the number of solutions 
   // required
   int number_of_paths = this→getSolution().size();
   // limits the number of waypoints required for each drone
   // subtracting 2 to remove “0” and “11”
   std::size_t max_wp_per_drone = ((number_of_cities-2)/number_of_drones) + 1;

   for(std::size_t i = 0; i < number_of_paths; i++)
   {
     int start = rand() % (this->getSolution().at(i).size() -2) + 1;
     int end =  start + 1 + rand() % ((this->getSolution().at(i).size()-2) - start +1); 

     std::vector<std::size_t>::const_iterator first = this->getSolution().at(i).begin()+start;                              
     std::vector<std::size_t>::const_iterator second = this- >getSolution().at(i).begin()+end;

     // First Problem occurs here… Sometimes, newOrder can return nothing based on 
     //the positions of start and end. Tried to mitigate by putting a while loop 
    to regenerate the vector
    std::vector<std::size_t> newOrder(first, second);
    // RETURNS a vector from the vector of vectors sol
     flat_sol = flatten(sol);
    // compare new Order with solution and remove any duplicates..
     for(std::size_t k = 0; k < newOrder.size(); k++ )
     {
            int duplicate = newOrder.at(k);
           if(std::find(flat_sol.begin(), flat_sol.end(), duplicate) != flat_sol.end())              
            {
               // second problem is found here, sometimes, 
               // new order might only return a vector with a single value 
               // or values that have already been assigned to another drone. 
               // In this case, those values are removed and newOrder is now 0 
                    newOrder.erase(newOrder.begin()+k);
             }
     }

            
    // attempt to create the vectors here. 
    for(std::size_t j = 1; j <=parentB.getSolution().at(i).size()-2; j++)
    {
         int city = parentB.getSolution().at(i).at(j);
         if(newOrder.empty())
         {
             if(std::find(flat_sol.begin(), flat_sol.end(), city) == flat_sol.end())
             {
                  newOrder.push_back(city);
              }
          }

         else if((std::find(newOrder.begin(), newOrder.end(), city) == newOrder.end())
                &&(std::find(flat_sol.begin(), flat_sol.end(), city) == flat_sol.end())
                && newOrder.size() < max_wp_per_drone )
          {
                         newOrder.push_back(city);
          }
     }
             
    sol.push_back(newOrder);
 }  
   // waypoints and number_of drones are known, 
   //0 and 11 are appended to each vector in sol in the constructor.
 return DNA(sol, waypoints, number_of_drones);

}

以前の実行からのサンプル出力は、次を返します。

[0,7,9,8, 11]
[0, 1,2,4,11]
[0, 10, 6, 11]
[0,3,11]

// This output is missing one waypoint.

[0,10,7,5, 11]
[0, 8,3,1,11]
[0, 6, 9, 11]
[0,2,4,11]


// This output is correct.

残念ながら、これは私の次の世代の新しい子供たちを意味します. そして、正しい出力を得るのはランダムなようです。たとえば、ある世代では、40 人の正しい子供と 60 人の中間点が欠落している子供を持つ母集団サイズがありましたが、場合によっては、より正しい子供がいたこともあります。ヒントやヘルプをいただければ幸いです。

4

1 に答える 1

0

少し異なるアプローチを取ることでこれを解決しました。クロスオーバーを実行する前に一連のウェイポイントを分割する代わりに、一連のウェイポイントを渡すだけです

[0,1,2,3,4,5,6,7,8,9,10,11]

mクロスオーバーを実行し、各セットの適合度を計算するときに、ドローンに基づいてウェイポイントを分割し、各世代の最適解を見つけます。新しいクロスオーバー関数は次のようになります。

DNA DNA::crossover( DNA &parentB)
{

    int start = rand () % (this->getOrder().size()-1);
    int end =  getRandomInt<std::size_t>(start +1 , this->getOrder().size()-1);

    std::vector<std::size_t>::const_iterator first = this->getOrder().begin() + start;
    std::vector<std::size_t>::const_iterator second = this->getOrder().begin() + end;

     std::vector<std::size_t> newOrder(first, second);

     for(std::size_t i = 0; i < parentB.getOrder().size(); i++)
      {
          int city = parentB.getOrder().at(i);
          if(std::find(newOrder.begin(), newOrder.end(), city) == newOrder.end())
          {
              newOrder.push_back(city);
          }
      }

    return DNA(newOrder, waypoints, number_of_drones);

}
于 2020-10-30T15:11:53.887 に答える