Одноточечный переход в генетическом алгоритме

Question

Одноточечный переход в генетическом алгоритме

Я использую одну точку пересечения, чтобы пересечь два человека. Предположим, что у меня есть два человека, такие как

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;
}

1

c++c++11 crossover evolutionary-algorithm genetic-algorithm

Решение

Другие решения

Источник

Accepted Answer

random_int

В целях отладки (повторяемость) не всегда следует вызывать rd(), Кроме того, вы воссоздаете псевдо-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, увидеть Зачем объявлять переменную в одной строке, а присваивать ей в следующей?)
- если длина людей фиксирована, вы также можете рассмотреть станд :: 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;
}

1