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 回答