1

我正在使用一个点交叉来交叉两个人。假设我有两个人，例如

I1='10010011' 
I2='11001101'

tmp_P是向量存储两个个体I1和I2。我想在 C++ 中实现一个点交叉。这样对吗？

这是算法描述

fori=1 to N/2 (N is number of individual=2 in my case)
   if random[0,1]<=Pc //cross prob.
       pos=random_int[1,n-1]
       for k=pos+1 to n //Length of individual=8 in my case
          aux=tmp_P_i[k]
          tmp_P_i[k]=tmp_P_(i+N/2)[k]
          tmp_P_(i+N/2)[k]=aux;
       end
   end
end

我的问题是我混淆了pos. 它是从 [0 到 n-2] 随机的吗？这样对吗？ 

 //Random integer in range [min max]
int random_int(int min, int max) //range : [min, max]
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(min, max);
    return dis(gen);
}
//One-point Crossover
vector< vector<int> > crossover(vector< vector<int> > tmp_P)
{
    int pos=0;
    for (int i=0;i<N/2;i++)
    {
        //If random number smaller than crossover probability then do Crossover
        if(RND()<=Pc)
        {
            pos=random_int(0,n-2);//Index in C++ from 0
            int aux=0;
            for (int k=pos+1;k<n;k++)
            {
                //swat
                aux=tmp_P[i][k];
                tmp_P[i][k]=tmp_P[i+N/2][k];
                tmp_P[i+N/2][k]=aux;
            }
        }
    }
    return tmp_P;
}
4

1 回答 1

1

  • random_int

    出于调试目的（可重复性），您不应总是调用rd(). 此外，您在每次通话时都在重新创建伪 RNG。

    只需调用一次随机设备，然后使用（随机）播种的伪 RNG 执行其他所有操作。作为奖励，您应该将种子值存储在日志文件中，以便以后可以重播伪随机序列。

    它应该是这样的：

    int random_int(int min, int max)
{
#if defined(NDEBUG)
  static std::mt19937 gen(std::random_device());  // or thread_local  
#else
  static std::mt19937 gen(1234);  // or, better, thread_local
#endif

  std::uniform_int_distribution<> dis(min, max);
  return dis(gen);
}

  • crossover

    • pos是正确的（在[0;n-2]范围内）；实际的交叉位置在[1;n-1]范围内（跳过 0 索引是正确的，因为它会交换整个基因组）。

      您可以直接初始化pos：

       unsigned pos = random_int(1, n-1);

 for (unsigned k = pos; k < n; ++k)
 { /* ... */ }

      这更简单。

    • 你可以使用这个std::swap功能

    • 如果变量在第一次出现在代码中时被习惯性地分配了一个有意义的值，那么它们就不会意外地与一个无意义或未初始化的值一起使用（例如pos/ aux，请参阅为什么在一行中声明一个变量，并在下一行中分配给它? )
    • 如果个人的长度是固定的，您还可以考虑使用std::bitset来存储基因组

所以这样的事情应该有效：

unsigned random_int(unsigned min, unsigned max)
{
#if defined(NDEBUG)
  static std::mt19937 gen(std::random_device());
#else
  static std::mt19937 gen(1234u);
#endif

  std::uniform_int_distribution<> dis(min, max);
  return dis(gen);
}

std::vector<std::vector<int>> crossover(std::vector<std::vector<int>> tmp_P)
{
  const auto N = tmp_P.size();
  const auto n = tmp_P[0].size();

  for (unsigned i = 0; i < N/2; ++i)
  {
    assert(tmp_P[i].size() == n);

    // If random number smaller than crossover probability then do Crossover
    if (RND() <= Pc)
      for (unsigned k = random_int(1, n-1); k < n; ++k)
        std::swap(tmp_P[i][k], tmp_P[i + N/2][k]);
  }

  return tmp_P;
}
于 2015-05-06T08:36:54.510 回答