c++ - 如何用 C++ 编写高效的遗传算法

Question

我正在尝试为 canonical genetic algorithm 编写一个 C++ 程序，其中有一群长度为 N 的个体(染色体)，其中每个元素都是 O 或 1。

我已经开始使用STL vector 编写我的程序，但在我更深入地研究它之前，我想询问您对如何以最有效的方式编写函数和数据结构的意见.

内存占用不是问题，我有大约 100 个人，其中每个人都是 64 个字符长的 0-s 和 1-s 字符串。另一方面，性能非常重要，因为大约有几千代，每一代都有数千次操作。

到目前为止，这是我的实现(只是最重要的功能和数据结构):

typedef vector<int> chromosome;
typedef vector<chromosome> population;

population popul;
float eval[number];

void cross_chromosomes( const chromosome &parent_a, const chromosome &parent_b, chromosome &child_a, chromosome &child_b )
{
    int crossing_point = crossing_point_gen( gen );

    child_a.reserve( length );
    child_a.insert( child_a.end(), parent_a.cbegin(), parent_a.cbegin() + crossing_point );
    child_a.insert( child_a.end(), parent_b.cbegin() + crossing_point, parent_b.cend() );

    child_b.reserve( length );
    child_b.insert( child_b.end(), parent_b.cbegin(), parent_b.cbegin() + crossing_point );
    child_b.insert( child_b.end(), parent_a.cbegin() + crossing_point, parent_a.cend() );
}

void calculate_eval()
{
    for( int i = 0; i < number; i++ )
    {
        eval[i] = evaluate_chromosome( popul[i] );
    }
}

你认为它是实现这个算法的有效方式吗？ 我最初使用 vector 作为染色体，但我读到了这个问题:C++ Vector vs Array (Time)我将代码更新为 vector<int> .

您认为我应该对我的代码进行其他优化以使其更高效吗？交叉代码是否像现在这样高效？

Answer 1

如何利用进化算法中令人尴尬的并行性。尝试将您的解决方案移植到 GPU 上怎么样？正如 chetan 和 David 所说，使用现有框架可能比编写自己的快速框架耗时少得多。

OpenBeagle和 EO是众所周知的得到良好支持且非常高效的框架。

请注意，在进化算法中真正需要快速的唯一部分是评估，其他一切通常都不耗时。您也可以寻找DEAP这允许在 super 计算机上非常轻松地分发评估(以及更多)(我们通过更改串行算法中的一行代码在 Colosse super 计算机的 1024 个内核上进行了测试)。