在遗传算法中实现多个 "Salesmen" TSP 的交叉函数

Question

我正在尝试用“多个销售员”解决 TSP 问题的变体。我有一系列 n waypoints 和 m 无人机，我想生成结果在某种程度上平衡了无人机之间的 waypoints 数量和 returns 可接受的最短旅行时间。目前，我不太担心找到最佳解决方案，我只是想要一些东西在这一点上有效。我已经多次将我的问题提炼为传统的 TSP 运行。我的示例是针对一系列 waypoints:

[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);

}

我之前运行s return 的样本输出如下：

[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.

不幸的是，这意味着在我的后代新children。我得到正确的输出似乎是随机的。例如，对于一代人，我的人口规模有 40 个正确 children 和 60 个 children 缺少 waypoints 而在某些情况下，我有更多正确 children.任何提示或帮助表示赞赏。

Answer 1

通过采用稍微不同的方法解决了这个问题。我没有在执行交叉之前拆分 waypoints 的系列，而是简单地传递 waypoints

的系列

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

进行交叉，在计算每组适应度时，我将waypoints基于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);

}

在遗传算法中实现多个 "Salesmen" TSP 的交叉函数

Implementing a crossover function for multiple "Salesmen" TSP in a genetic algorithm

c++

algorithm

traveling-salesman

genetic-algorithm

crossover