C++遗传算法解决8皇后问题

问题描述 投票：0回答：1

我正在尝试用 C++ 实现 8 个皇后问题。 这是我的代码

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

我感觉我的选择方法和交叉方法有问题但不知道问题出在哪里？有人可以帮忙吗？我的轮盘选择是否正确，我可以在那里更改什么？这是一个要求，所以我无法选择另一种方法。

c++ genetic-algorithm roulette-wheel-selection
1个回答
0
投票

此答案描述了让程序运行所需的最少更改集。

如果某件事可以做得更好，但以某种方式设法在当前程序中工作，那么这个答案不会改变它。例如，这里没有任何内容可以解决有关随机数生成的许多设计缺陷。

预赛

  • 按字母顺序排列 
    #include
    指令。
  • 添加
    #include <iomanip>
    。
  • 将 
    <stdlib.h>
    更改为 
    <cstdlib>
    。
  • 将 
    <time.h>
    更改为 
    <ctime>
    。
  • 将 
    MUTATE
    概率从 
    0.5
    更改为 
    0.05
    。
  • 将 
    MAX_ITER
    从 
    100'000
    更改为 
    5'000
    。
  • 删除功能
    shuffle
    。它从来没有被调用过。
  • 删除所有日志记录/调试输出语句。

更新功能
main

这些更新改进了函数 

main
输出的消息。

int main() {
    std::cout
        << "Solve " << nQueens
        << "-Queens Puzzle using a Genetic Algorithm"
        << "\n\nSolving ";
    srand(time(NULL));
    population = generatePopulation(100);

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

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

更新功能
stop

由于无法保证遗传算法能够找到 N 皇后难题的解决方案，因此必须在 

MAX_ITER
次迭代后停止。此更新恢复了功能 
stop
中的测试。请注意，在上面的预备中，
MAX_ITER
已减少为 
5'000
。

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

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

    return false;
}

更新功能
GA

函数 

GA
有一个严重的遗漏：当孩子被添加到 
newpopulation
时，它无法计算孩子的适应度。这是修复方法：

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

更新功能
reproduce_crossover

正如OP中编码的那样，函数

reproduce_crossover
有很大的问题。尝试将 
parent2
复制到 
child
并跳过从 
parent1
复制的元素的循环严重失败。调用
std::find
没有任何目的，因此应该省略测试。内部 while 循环看起来应该是一个简单的 if-else 语句。

这是重写：

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;
    child.sequence = parent2;       // Copy all of `parent2`.
    std::copy(                      // Overwrite the crossover parts by 
        parent1.begin() + cross1,   // copying from `parent1`.
        parent1.begin() + cross2,
        child.sequence.begin() + cross1);
    return child;
}

更新功能
get_parent

如OP中编码的那样，函数

get_parent
（选择函数）有几个严重错误。

    在扫描
  1. offset

    和 

    0.0
    的每个循环之前，需要将变量 
    parent1
    重置为 
    parent2
    。
    

  2. parent2
    的循环需要以与
    parent1
    的循环相同的方式累积偏移量。
    

    3. 当前使用 
  3. offset
     的两个 
    <=
     测试应该使用 
    >
    。否则，您几乎每次都会选择 
    population
     的第一个元素。此错误导致“几乎”无限循环，因为 
    parent1
     和 
    parent2
     几乎总是选择为 
    population[0]
    。
    

    

    4. 解决方法如下：


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;
    while (true) {
        offset = 0.0;
        double parent1_random = distribution(generator);
        for (auto& x : population) {
            offset += x.survival;
            if (offset > parent1_random) {
                parent1 = x;
                break;
            }
        }
        offset = 0.0;
        double parent2_random = distribution(generator);
        for (auto& x : population) {
            offset += x.survival;
            if (offset > parent2_random) {
                parent2 = x;
                break;
            }
        }

        if (parent1.sequence != parent2.sequence) {
            break;
        }
    }
    return make_pair(parent1, parent2);
}



输出示例：


Solve 8-Queens Puzzle using a Genetic Algorithm

Solving .

Iterations: 132

Solution: 3 1 6 2 5 7 4 0



运行 2：


Solve 8-Queens Puzzle using a Genetic Algorithm

Solving ...

Iterations: 382

Solution: 3 5 7 1 6 0 2 4



完整的程序


// main.cpp
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <stdlib.h>
#include <time.h>
#include <vector>

using namespace std;

const int nQueens = 8;
const int STOP_CTR = 28;
const double MUTATE = 0.05;
const bool MUTATE_FLAG = true;
const int MAX_ITER = 5'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 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;
    while (true) {
        offset = 0.0;
        double parent1_random = distribution(generator);
        for (auto& x : population) {
            offset += x.survival;
            if (offset > parent1_random) {
                parent1 = x;
                break;
            }
        }
        offset = 0.0;
        double parent2_random = distribution(generator);
        for (auto& x : population) {
            offset += x.survival;
            if (offset > parent2_random) {
                parent2 = x;
                break;
            }
        }

        if (parent1.sequence != parent2.sequence) {
            break;
        }
        // if (!parent2.sequence.empty() && parent2.sequence != parent1.sequence) {
        //   break;
        //}
    }
    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;
    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);
        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) {
        return true;
    }

    return false;
}

int main() {
    std::cout
        << "Solve " << nQueens
        << "-Queens Puzzle using a Genetic Algorithm"
        << "\n\nSolving ";
    srand(time(NULL));
    population = generatePopulation(100);

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

    for (auto& each : population) {
        if (each.fitness == 28) {
            std::cout << "Solution: ";
            for (auto& seq : each.sequence) {
                cout << seq << " ";
            }
            cout << endl;
        }
    }
    return 0;
}
// end file: main.cpp



更新了随机数函数


如果您雄心勃勃，您可以尝试将以下随机数函数集成到您的程序中。它们被设计为共享 
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());
}



随机父级

遗传算法的
选择
步骤为当前“群体”的“孩子”选择“父母”。 
轮盘赌选择随机选择父母，权重有利于“最适合”的父母。
std::discrete_distribution
非常适合这项任务。给定一个具有 
n
 元素的权重向量，它返回 
0
 和 
n - 1
 之间的整数。


std::discrete_distribution
 生成区间 [0, n) 上的随机整数，其中每个整数 i 的概率定义为权重 [i] 除以所有 n 权重之和。 – 改编自
CppReference
。


函数 
random_parent
（如下）返回的值是可用于对 
population
 向量进行键入的下标。请注意，函数 
random_parent
 调用函数 
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());
}



权重向量是通过从 
population
 向量复制“适应度”分数而形成的。


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



请注意，这种选择父级的技术消除了结构体 
survival
 中对成员 
BoardPosition
 的需要。


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



随机布尔
在下一代“孩子”中变异的决定是随机做出的，概率为
MUTATE
。


函数
random_bool
将该概率转换为离散的“是/否”选择。它使用一个静态分发对象，该对象仅在第一次调用函数 
random_bool
 期间实例化一次。再次注意，函数 
random_bool
 调用函数 
random_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;
}



随机位置
随机位置可以是行号或列号。位置范围在 
0
 和 
nQueens - 1
 之间。


函数
random_position
有一个静态分布对象，仅在第一次调用函数
random_position
期间实例化一次。和以前一样，它调用函数 
random_engine
 来获取引擎。


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


    





      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.