C++ genetic algorithm for 8 queens problem

Question

I am trying to implement 8 queens problems in c++. This is my code

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <random>
#include <numeric>

using namespace std;

const int nQueens = 8;
const int STOP_CTR = 28;
const double MUTATE = 0.5;
const bool MUTATE_FLAG = true;
const int MAX_ITER = 100000;
int POPULATION = 0;

std::random_device rd;
std::mt19937 gen(rd());

class BoardPosition {
public:
    vector<int> sequence;
    int fitness;
    double survival;

    BoardPosition() {
        sequence.resize(nQueens);
        fitness = 0;
        survival = 0.0;
    }
};

vector<BoardPosition> population;

void shuffle(vector<int>& array) {
    random_device rd;
    default_random_engine engine(rd());
    shuffle(array.begin(), array.end(), engine);
}

int fitness(const std::vector<int>& individual) {
    int attacks = 0;
    for (int i = 0; i < nQueens; i++) {
        for (int j = i + 1; j < nQueens; j++) {
            if (individual[i] == individual[j] || abs(individual[i] - individual[j]) == j - i) {
                attacks++;
            }
        }
    }
    return 28 - attacks;
}

vector<int> generateChromosome() {
    vector<int> init_distribution(nQueens);

    for (int i = 0; i < nQueens; i++) {
        default_random_engine generator(rd());
        uniform_int_distribution<int> distribution(0, nQueens - 1);
        init_distribution[i] = distribution(generator);
    }
    return init_distribution;
}

vector<BoardPosition> generatePopulation(int population_size = 100) {
    POPULATION = population_size;
    vector<BoardPosition> population(population_size);
    for (int i = 0; i < population_size; ++i) {
        population[i].sequence = generateChromosome();
        population[i].fitness = fitness(population[i].sequence);
    }
    return population;
}

pair<BoardPosition, BoardPosition> getParent() {
    double summation_fitness = 0;
    for (auto& x : population) {
        summation_fitness += x.fitness;
    }
    for (auto& each : population) {
        each.survival = each.fitness / summation_fitness;
    }

    // random_device rd;
    default_random_engine generator(rd());
    uniform_real_distribution<double> distribution(0.0, 1.0);

    BoardPosition parent1, parent2;
    double offset = 0.0;
    while (true) {
        double parent1_random = distribution(generator);
        for (auto& x : population) {
            offset += x.survival;
            if (offset <= parent1_random) {
                //          cout << "Here parent1" << endl;
                parent1 = x;
                break;
            }
        }
        double parent2_random = distribution(generator);
        for (auto& x : population) {
            if (x.survival <= parent2_random) {
                //     cout << "Selected parent2: " << x.fitness << endl;
                parent2 = x;
                break;
            }
        }

        if (parent1.sequence != parent2.sequence) {
            break;
        }
        // if (!parent2.sequence.empty() && parent2.sequence != parent1.sequence) {
        //   break;
        //}
    }
    // cout<<"Here " <<endl;
    return make_pair(parent1, parent2);
}

BoardPosition reproduce_crossover(std::vector<int>& parent1, std::vector<int>& parent2) {
    std::uniform_int_distribution<> dist(0, nQueens - 1);
    int cross1 = dist(gen);
    int cross2 = dist(gen);
    if (cross1 > cross2) std::swap(cross1, cross2);
    else if (cross1 == cross2) cross2++;

    BoardPosition child;
    std::copy(parent1.begin() + cross1, parent1.begin() + cross2, child.sequence.begin() + cross1);
    int pos = 0;
    for (int i = 0; i < nQueens; i++) {
        if (std::find(child.sequence.begin() + cross1, child.sequence.begin() + cross2, parent2[i]) == child.sequence.begin() + cross2) {
            while (pos < cross1 || pos >= cross2) pos++;
            child.sequence[pos++] = parent2[i];
        }
    }
    return child;
}

BoardPosition mutate(BoardPosition child) {
    default_random_engine generator(rd());
    for (int i = 0; i < nQueens - 1; i++) {
        double r = ((double)rand() / (RAND_MAX));
        //cout<<"mutation probability " << r << endl;
        if (r < MUTATE) {
            uniform_int_distribution<int> distribution(0, nQueens - 1);
            child.sequence[i] = distribution(generator);
        }
    }
    return child;
}

vector<BoardPosition> GA(int iteration) {
    vector<BoardPosition> newpopulation;
    for (int i = 0; i < population.size(); ++i) {
        auto parents = getParent();
        cout << "Getting parent is done" << endl;
        BoardPosition child = reproduce_crossover(parents.first.sequence, parents.second.sequence);
        cout << "Crossover is done" << endl;

        if (MUTATE_FLAG) {
            child = mutate(child);
        }

        newpopulation.push_back(child);
    }
    return newpopulation;
}

bool stop(int& iteration) {
    for (auto& pos : population) {
        // cout << "Pos.fitness " << pos.fitness << endl;
        if (pos.fitness == STOP_CTR) {
            return true;
        }
    }

    /* if (MAX_ITER == iteration) {
         return true;
     }*/

    return false;
}

int main() {
    srand(time(NULL));
    population = generatePopulation(100);

    int iteration = 0;
    while (!stop(iteration)) {
        population = GA(iteration);
        cout << "iteration number" << iteration << endl;
        iteration++;
    }

    //
    for (auto& each : population) {
        if (each.fitness == 28) {
            for (auto& seq : each.sequence) {
                cout << seq << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

I feel like my selection method and crossover method has an issues but not sure where? Anyone can help here? Am I doing my roullete wheel selection correctly what can I change it there? It is one requirements to have it like that so another method I can't select.

Answer 1

This answer describes the minimum set of changes you need to get your program running.

If something could be done better, but somehow manages to work in the present program, this answer does not change it. For instance, nothing here addresses the many design flaws regarding random number generation.

There are, however, a few suggestions concerning random numbers at the end of this answer.

Preliminaries

• Alphabetize #include directives.
• Add #include <iomanip>.
• Change <stdlib.h> to <cstdlib>.
• Change <time.h> to <ctime>.
• Change MUTATE probability from 0.5 to 0.25 / nQueens.
• Change NULL to nullptr.
• Delete function shuffle. It is never called.
• Strip out all logging/debugging output statements.

By far, the most important of these preliminary changes is to reduce the probability that one of the "genes" in a child "sequence" mutates. With the original value of MUTATE set to 0.5, roughly half the genes in every child will be selected for mutation. In the case where nQueens is 8, that means four of the queens will be randomly repositioned. Such a high rate of mutation creates a chaotic situation where the progress made by selectively crossing over the genes of a child's parents is swamped by mutation.

With MUTATE set to 0.25 / nQueens, only about one fourth of the children in a new generation will undergo any mutations at all. Those that do mutate will typically have only one queen repositioned.

Are these preliminaries really needed?

Most of them probably are not. However, as they are changes I made to the OP's program, I thought it necessary to document them. You can see them all in the complete program below.

One of the preliminaries is absolutely necessary. That is the change to parameter MUTATE. The need for this is explained above. After a commenter suggested that, "Really, none of the 'preliminaries' are required," I decided I better run some (more) tests. The table below summarizes the results.

With a sample size of only 10 runs, these results must be described as anecdotal. It is worth noting, however, that for MUTATE == 0.5, no solution was found in 6 of the 10 cases.

Iteration counts when `nQueens == 10`
(100,000 means that the program stopped without finding a solution.)

| MUTATE 0.5  | MUTATE 0.25 / nQueens |
| ----------- | --------------------- |
| 100,000     | 23,999                |
| 100,000     |  8,064                |
| 100,000     |  1,503                |
|  70,117     | 27,068                |
|  55,231     |  8,995                |
|  15,939     | 15,771                |
| 100,000     |  5,869                |
| 100,000     | 18,390                |
| 100,000     |  2,494                |
|  74,568     | 27,928                |
| ----------- | --------------------- |
| Average                             |
| ----------- | --------------------- |
|  81,586     | 14,008                |

Although these results are only ancecdotal, they are enough to convince this non-statistician. The change to MUTATE was "really required."

A problem with STOP_CTR

STOP_CTR is the "fitness" score obtained when no pair of queens attack each other. It is the highest "fitness" score you can get. It is the fitness score for a position that solves the n queens puzzle.

The fitness score for a given position is found by counting the number of pairs of queens that attack each other, and subtracting from STOP_CTR. If we denote the number of pairs of mutually attacking queens as n_attacking_pairs, then fitness is STOP_CTR - n_attacking_pairs.

In the OP, STOP_CTR is set to 28, but that value is only correct when nQueens is 8.

When all the queens attack each other, as occurs when they are all placed in the same row, the number of attacking pairs is "nQueens choose 2". Let's call that n_attacking_pairs_max. When nQueens is 8, n_attacking_pairs_max is 28. Thus, the lowest fitness score you can get (when nQueens == 8) is 0.

The desire to make the lowest fitness equal to 0 is the reason that STOP_CTR was chosen to be 28. That only works, however, for nQueens == 8. For other values of nQueens, STOP_CTR should be set to n_attacking_pairs_max, i.e., it should be set to "nQueens choose 2".

const int STOP_CTR = nQueens * (nQueens - 1) / 2;  // nQueens choose 2

Otherwise, if you always use 28 as the value of STOP_CTR, the lowest fitness will not always be 0. For values of nQueens that are larger than 8, the lowest fitness score will be a negative number. Many other fitness scores will also be negative.

This plays havoc with the calculation of BoardPosition::survival that is made in function getParent. That calculation requires that fitness scores be zero-based.

After changing the value of the "global" constant STOP_CTR, it is also necessary replace the hard-coded value 28 that appears in two places in the program. Instead of 28, functions fitness and main should use STOP_CTR.

int fitness(const std::vector<int>& individual) {
    int attacks = 0;
    for (int i = 0; i < nQueens; i++) {
        for (int j = i + 1; j < nQueens; j++) {
            if (individual[i] == individual[j] ||
                abs(individual[i] - individual[j]) == j - i) {
                attacks++;
            }
        }
    }
    return STOP_CTR - attacks;  // Use `STOP_CTR`, rather than `28`.
}

Updates to function main

The argument to srand now uses a static_cast. This prevents the compiler from issuing a warning about a narrowing conversion.

Other updates improve the messages that are output by function main. All of the std::cout statements are new. As the search for a solution progresses, a growing row of dots marks the progress. For those systems that support ANSI escape codes, function put_board displays the solution on a chess board where red squares mark the positions of the queens.

int main() {
    std::cout
        << "Solve " << nQueens
        << " Queens "
        << (nQueens == 8 ? "Puzzle" : "Problem")
        << " using a Genetic Algorithm"
        << "\n\nSolving (each dot = 100 iterations; each row, 10,000): \n";
    srand(static_cast<unsigned>(time(nullptr)));       // Use a `static_cast`.
    population = generatePopulation(100);

    int iteration = 0;
    while (!stop(iteration)) {
        population = GA(iteration);
        if (++iteration % 100 == 0)
        {
            std::cout << '.';                          // Display "progress bar."
            if (iteration % 10'000 == 0)
                std::cout << '\n';
        }
    }
    std::cout << "\n\nIterations: " << iteration << "\n\n";

    for (auto& each : population) {
        if (each.fitness == STOP_CTR) {                // Use `STOP_CTR`, rather than `28`.
            std::cout << "Solution: ";
            for (auto& seq : each.sequence) {
                cout << seq << " ";
            }
            std::cout << endl;
            std::cout << '\n';                         // Delete these three lines 
            void put_board(std::vector<int> const&);   // if your terminal does not 
            put_board(each.sequence);                  // support ANSI escape codes.
        }
    }
    return 0;
}

Updates to function stop

As there is no guarantee that the genetic algorithm will find a solution to the n queens problem, it is essential to stop after MAX_ITER iterations. This update reinstates that test in function stop.

bool stop(int& iteration) {
    for (auto& pos : population) {
        if (pos.fitness == STOP_CTR) {
            return true;
        }
    }

    if (MAX_ITER == iteration) {  // Reinstate this stop test.
        return true;
    }

    return false;
}

Updates to function GA

Function GA has a critical omission: it fails to calculate the fitness of children as they are added to the newpopulation. Here is the fix:

vector<BoardPosition> GA(int iteration) {
    vector<BoardPosition> newpopulation;
    for (int i = 0; i < population.size(); ++i) {
        auto parents = getParent();
        BoardPosition child = reproduce_crossover(
            parents.first.sequence,
            parents.second.sequence);

        if (MUTATE_FLAG) {
            child = mutate(child);
        }
        child.fitness = fitness(child.sequence);  // Calculate "fitness".
        newpopulation.push_back(child);
    }
    return newpopulation;
}

Updates to function reproduce_crossover

As coded in the OP, function reproduce_crossover has big problems. The loop that attempts to copy parent2 into the child, while skipping over the elements that were copied from parent1, fails badly.

// From the OP:
BoardPosition reproduce_crossover(std::vector<int>& parent1, std::vector<int>& parent2) {
    std::uniform_int_distribution<> dist(0, nQueens - 1);  // biased range
    int cross1 = dist(gen);
    int cross2 = dist(gen);
    if (cross1 > cross2) std::swap(cross1, cross2);
    else if (cross1 == cross2) cross2++;                   // should redraw

    BoardPosition child;
    std::copy(
        parent1.begin() + cross1, 
        parent1.begin() + cross2, 
        child.sequence.begin() + cross1);
    int pos = 0;
    for (int i = 0; i < nQueens; i++)
    {
        // This loop attempts to skip over the elements that were 
        // copied from `parent1`, but fails badly. There is no 
        // purpose in calling `std::find`, so that test should be 
        // omitted. The while loop looks like it should be some 
        // sort of if-else-statement.

        if (std::find(
            child.sequence.begin() + cross1,
            child.sequence.begin() + cross2,
            parent2[i]) == child.sequence.begin() + cross2)
        {
            while (pos < cross1 || pos >= cross2) pos++;
            child.sequence[pos++] = parent2[i];
        }
    }
    return child;
}

In addition, there is a subtle bias in the way cross1 and cross2 are selected. One consequence is that the final element of parent1 will only participate in a crossover when both cross1 and cross2 are chosen to be nQueens - 1.

The increment of cross2 introduces another bias that causes crossover ranges containing a single element to be preferred over other ranges. Rather than incrementing cross2, it should be redrawn.

Here is the rewrite:

BoardPosition reproduce_crossover(
    std::vector<int>& parent1,
    std::vector<int>& parent2)
{
    std::uniform_int_distribution<> dist(0, nQueens);  // Change distribution range.
    int cross1 = dist(gen);
    int cross2 = dist(gen);
    while (cross1 == cross2)
        cross2 = dist(gen);         // Redraw `cross2`.
    if (cross1 > cross2)
        std::swap(cross1, cross2);

    BoardPosition child;
    child.sequence = parent2;       // Copy all of `parent2`.
    std::copy(                      // Overwrite the crossover parts by 
        parent1.begin() + cross1,   // copying from from `parent1`.
        parent1.begin() + cross2,
        child.sequence.begin() + cross1);
    return child;
}

Note that only one child is produced from each set of parents. This is unusual, because the genetic algorithm for the n queens problem normally produces two, with second getting the "genes" from the two parents that were discarded by the first child.

    BoardPosition child2;
    child2.sequence = parent1;      // Copy all of `parent1`.
    std::copy(                      // Overwrite the crossover parts by 
        parent2.begin() + cross1,   // copying from from `parent2`.
        parent2.begin() + cross2,
        child2.sequence.begin() + cross1);

As the OP's program runs without making this change, I did not added a second child.

Updates to function getParent

As coded in the OP, function getParent, the selection function, has several critical errors.

1. Variable offset needs to be reset to 0.0 prior to each of the loops that scan for parent1 and parent2.

2. The loop for parent2 needs to accumulate offsets in the same way as the loop for parent1.

3. The two offset tests, which currently use <=, should use >. Otherwise, you end up choosing the first element of the population almost every time. This error results in a "nearly" infinite loop, because both parent1 and parent2 are almost always chosen to be population[0].

4. It is possible that the accumulation of round-off errors in the calculation of offset will produce a value that never exceeds the randomly chosen threshold (parent1_random or parent2_random), in which case, no parent will be selected.

There are enough changes to warrant the creation of an new function, random_parent, which returns the subscript of a randomly selected parent. In the rewrite below, two calls to function random_parent replace the two loops in the OP.

After two parents are selected, they are tested make sure they are distinct elements from vector population (with different subscripts). Unlike the OP, however, no test is made to require that they hold different sequences.

std::size_t random_parent()
{
    double const threshold{ std::uniform_real_distribution<double>{}(gen) };
    double offset{};
    for (std::size_t i{}; i < population.size(); ++i)
    {
        offset += population[i].survival;
        if (offset > threshold)          // Test with `>`, rather than `<=`.
            return i;
    }
    enum : std::size_t { one = 1u };     // Correct for round-off errors, 
    return population.size() - one;      // by choosing the final element.
}

pair<BoardPosition, BoardPosition> getParent() {
    double summation_fitness = 0;
    for (auto& x : population) {
        summation_fitness += x.fitness;
    }
    for (auto& each : population) {
        each.survival = each.fitness / summation_fitness;
    }
    std::size_t i{ random_parent() };
    std::size_t j{ random_parent() };
    while (i == j)                       // Redraw when i == j, rather than 
        j = random_parent();             // when the two sequences are equal.
    return { population.at(i), population.at(j) };
}

Note that the loops that calculate survival should not be repeated every time you get two new parents. Those loops belong in function GA. Putting them here, slows things down unnecesarily. As it does not cause the program to fail, however, I have not made any correction.

Sample output

That's it! With those changes the program successfully solves the n queens problem.

I tested with values of nQueens as high as 12. Using a variation where parents are selected from only the fittest half of the population, I was able get solutions with nQueens == 100.

Here are a couple of runs with nQueens set to 8.

Solve 8 Queens Puzzle using a Genetic Algorithm

Solving (each dot = 100 iterations; each row, 10,000):
.

Iterations: 102

Solution: 3 6 4 2 0 5 7 1

(chess board goes here)

Run 2:

Solve 8 Queens Puzzle using a Genetic Algorithm

Solving (each dot = 100 iterations; each row, 10,000):
...

Iterations: 305

Solution: 5 2 0 6 4 7 1 3

(chess board goes here)

The complete program

// main.cpp
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

using namespace std;

const int nQueens = 8;
const int STOP_CTR = nQueens * (nQueens - 1) / 2;  // nQueens choose 2
const double MUTATE = 0.25 / nQueens;
const bool MUTATE_FLAG = true;
const int MAX_ITER = 100'000;
int POPULATION = 0;

std::random_device rd;
std::mt19937 gen(rd());

class BoardPosition {
public:
    vector<int> sequence;
    int fitness;
    double survival;

    BoardPosition() {
        sequence.resize(nQueens);
        fitness = 0;
        survival = 0.0;
    }
};

vector<BoardPosition> population;

int fitness(const std::vector<int>& individual) {
    int attacks = 0;
    for (int i = 0; i < nQueens; i++) {
        for (int j = i + 1; j < nQueens; j++) {
            if (individual[i] == individual[j] ||
                abs(individual[i] - individual[j]) == j - i) {
                attacks++;
            }
        }
    }
    return STOP_CTR - attacks;  // Use `STOP_CTR`, rather than `28`.
}

vector<int> generateChromosome() {
    vector<int> init_distribution(nQueens);

    for (int i = 0; i < nQueens; i++) {
        default_random_engine generator(rd());
        uniform_int_distribution<int> distribution(0, nQueens - 1);
        init_distribution[i] = distribution(generator);
    }
    return init_distribution;
}

vector<BoardPosition> generatePopulation(int population_size = 100) {
    POPULATION = population_size;
    vector<BoardPosition> population(population_size);
    for (int i = 0; i < population_size; ++i) {
        population[i].sequence = generateChromosome();
        population[i].fitness = fitness(population[i].sequence);
    }
    return population;
}

std::size_t random_parent()
{
    double const threshold{ std::uniform_real_distribution<double>{}(gen) };
    double offset{};
    for (std::size_t i{}; i < population.size(); ++i)
    {
        offset += population[i].survival;
        if (offset > threshold)          // Test with `>`, rather than `<=`.
            return i;
    }
    enum : std::size_t { one = 1u };     // Correct for round-off errors, 
    return population.size() - one;      // by choosing the final element.
}

pair<BoardPosition, BoardPosition> getParent() {
    double summation_fitness = 0;
    for (auto& x : population) {
        summation_fitness += x.fitness;
    }
    for (auto& each : population) {
        each.survival = each.fitness / summation_fitness;
    }
    std::size_t i{ random_parent() };
    std::size_t j{ random_parent() };
    while (i == j)                       // Redraw when i == j, rather than 
        j = random_parent();             // when the two sequences are equal.
    return { population.at(i), population.at(j) };
}

BoardPosition reproduce_crossover(
    std::vector<int>& parent1,
    std::vector<int>& parent2)
{
    std::uniform_int_distribution<> dist(0, nQueens);  // Change distribution range.
    int cross1 = dist(gen);
    int cross2 = dist(gen);
    while (cross1 == cross2)
        cross2 = dist(gen);         // Redraw `cross2`.
    if (cross1 > cross2)
        std::swap(cross1, cross2);

    BoardPosition child;
    child.sequence = parent2;       // Copy all of `parent2`.
    std::copy(                      // Overwrite the crossover parts by 
        parent1.begin() + cross1,   // copying from from `parent1`.
        parent1.begin() + cross2,
        child.sequence.begin() + cross1);
    return child;
}

BoardPosition mutate(BoardPosition child) {
    default_random_engine generator(rd());
    for (int i = 0; i < nQueens - 1; i++) {
        double r = ((double)rand() / (RAND_MAX));
        if (r < MUTATE) {
            uniform_int_distribution<int> distribution(0, nQueens - 1);
            child.sequence[i] = distribution(generator);
        }
    }
    return child;
}

vector<BoardPosition> GA(int iteration) {
    vector<BoardPosition> newpopulation;
    for (int i = 0; i < population.size(); ++i) {
        auto parents = getParent();
        BoardPosition child = reproduce_crossover(
            parents.first.sequence,
            parents.second.sequence);

        if (MUTATE_FLAG) {
            child = mutate(child);
        }
        child.fitness = fitness(child.sequence);  // Calculate "fitness".
        newpopulation.push_back(child);
    }
    return newpopulation;
}

bool stop(int& iteration) {
    for (auto& pos : population) {
        if (pos.fitness == STOP_CTR) {
            return true;
        }
    }

    if (MAX_ITER == iteration) {  // Reinstate this stop test.
        return true;
    }

    return false;
}

int main() {
    std::cout
        << "Solve " << nQueens
        << " Queens "
        << (nQueens == 8 ? "Puzzle" : "Problem")
        << " using a Genetic Algorithm"
        << "\n\nSolving (each dot = 100 iterations; each row, 10,000): \n";
    srand(static_cast<unsigned>(time(nullptr)));       // Use a `static_cast`.
    population = generatePopulation(100);

    int iteration = 0;
    while (!stop(iteration)) {
        population = GA(iteration);
        if (++iteration % 100 == 0)
        {
            std::cout << '.';                          // Display "progress bar."
            if (iteration % 10'000 == 0)
                std::cout << '\n';
        }
    }
    std::cout << "\n\nIterations: " << iteration << "\n\n";

    for (auto& each : population) {
        if (each.fitness == STOP_CTR) {                // Use `STOP_CTR`, rather than `28`.
            std::cout << "Solution: ";
            for (auto& seq : each.sequence) {
                cout << seq << " ";
            }
            std::cout << endl;
            std::cout << '\n';                         // Delete these three lines 
            void put_board(std::vector<int> const&);   // if your terminal does not 
            put_board(each.sequence);                  // support ANSI escape codes.
        }
    }
    return 0;
}
// end file: main.cpp

Function put_board

Function put_board uses ANSI escape codes to display a chess board showing the solution. However, not every system supports ANSI. In order to make it easy to remove function put_board from the program, its source code has been placed into a separate translation unit.

Function main is the only place where function put_board is referenced. As noted in function main, the call to function put_board can be removed by deleting the three lines that are marked with comments.

// put_board.cpp
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

namespace
{
    void put_board_row(
        int const col_of_queen,
        char const* const bg1,
        char const* const bg2,
        std::size_t const n_cols)
    {
        // ANSI background color sequences
        constexpr char const* const bg_red{ "\033[41m" };
        constexpr char const* const bg_default{ "\033[49m" };

        std::string s;
        int col{};
        while (col < n_cols)
        {
            s += (col++ == col_of_queen ? bg_red : bg1);
            s += "    ";
            if (col >= n_cols)
                break;
            s += (col++ == col_of_queen ? bg_red : bg2);
            s += "    ";
        }
        std::cout
            << s << bg_default << '\n'
            << s << bg_default << '\n';
    }

    std::vector<int> transpose(std::vector<int> const& p)
    {
        std::vector<int> q(p.size());
        for (std::size_t i{}; i < q.size(); ++i)
            q.at(static_cast<std::size_t>(p.at(i))) = static_cast<int>(i);
        return q;
    }
}

void put_board(std::vector<int> const& p)
{
    // ANSI background color sequences
    constexpr char const* const bg_white{ "\033[47m" };
    constexpr char const* const bg_bright_black{ "\033[100m" };  // gray
    constexpr auto const dark_bg{ bg_bright_black };
    constexpr auto const light_bg{ bg_white };

    auto s{ transpose(p) };
    std::size_t row{};
    while (row < s.size())
    {
        put_board_row(s.at(row++), light_bg, dark_bg, s.size());
        if (row >= s.size())
            break;
        put_board_row(s.at(row++), dark_bg, light_bg, s.size());
    }
    std::cout << '\n';
}
// end file: put_board.cpp

Improved random number functions

If you are feeling ambitious, you might try integrating the following random number functions into your program. They are designed to share a single instantiation of std::mt19937.

std::mt19937& random_engine() {
    static std::mt19937 engine{ std::random_device{}() };
    return engine;
}
bool random_bool(double const probability_of_true = 0.5) {
    static std::uniform_real_distribution<double> d{ 0.0, 1.0 };
    return d(random_engine()) < probability_of_true;
}
std::size_t random_parent(std::vector<double> const& weights) {
    std::discrete_distribution<std::size_t> d{ weights.cbegin(), weights.cend() };
    return d(random_engine());
}
int random_position() {
    static std::uniform_int_distribution<int> d{ 0, nQueens - 1 };
    return d(random_engine());
}
int random_crossover_offset() {
    static std::uniform_int_distribution<int> dist(0, n_queens);
    return dist(random_engine());
}

Random parent

The selection step of the genetic algorithm chooses "parents" for the "children" of the current "population." Roulette wheel selection picks parents randomly, weighting in favor of the "fittest" parents.

std::discrete_distribution is perfect for this task. Given a vector of weights with n elements, it returns an integer between 0 and n - 1.

std::discrete_distribution produces random integers on the interval [0, n), where the probability of each individual integer i is defined as the weight[i] divided by the sum of all n weights. – Adapted from CppReference.

The values returned by function random_parent (below) are subscripts that can be used to key the population vector. Note that function random_parent calls function random_engine to get a reference to the random engine.

std::size_t random_parent(std::vector<double> const& weights) {
    std::discrete_distribution<std::size_t> d{ weights.cbegin(), weights.cend() };
    return d(random_engine());
}

The vector of weights is formed by copying the "fitness" scores from the population vector.

std::vector<double> weights;
weights.reserve(population.size());
for (auto const& p : population)
    weights.emplace_back(p.fitness);

Note that this technique of choosing a parent obviates the need for member survival in struct BoardPosition.

class BoardPosition {
public:
    vector<int> sequence;
    int fitness;
    double survival;  // no longer needed
    //...
};

Random bool

The decision to mutate a "child" in the next "generation" is made randomly, with probability MUTATE.

Function random_bool converts that probability into a discrete "yes/no" choice. It uses a static distribution object that is instantiated only once, during the first call to function random_bool. Once again, note that function random_bool calls function random_engine to get a reference to the shared engine.

bool random_bool(double const probability_of_true = 0.5) {
    static std::uniform_real_distribution<double> d{ 0.0, 1.0 };
    return d(random_engine()) < probability_of_true;
}

Random position and random crossover offset

A random position can be either a row or column number. Positions range between 0 and nQueens - 1.

Function random_position has a static distribution object that is instantiated only once, during the first call to function random_position. As before, it calls function random_engine to get the engine.

int random_position() {
    static std::uniform_int_distribution<int> d{ 0, nQueens - 1 };
    return d(random_engine());
}

Function random_crossover_offset is similar to function random_position. The only difference is that the range extends out to nQueens.

The values generated by function random_crossover_offset are intended to be used in calls to std::copy, as part of the specification of the range to be copied.

auto cross1{ random_crossover_offset() };
auto cross2{ random_crossover_offset() };
// ...
std::copy(
    parent1.begin() + cross1, 
    parent1.begin() + cross2, 
    child.begin() + cross1);

When cross2 == nQueens, the iterator expression parent1.begin() + cross2 has the same value as parent1.end(), i.e., it is an iterator to one position beyond the end of vector parent1.