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

Question

我正在尝试为 规范遗传算法编写一个 C++ 程序，其中您有长度为 N 的个体（染色体），其中每个元素都是 O 或 1。

我已经开始使用 STL 向量编写我的程序，但在更深入地研究它之前，我想询问您的意见怎么写以最有效的方式处理函数和数据结构。

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

这是我迄今为止的实现（仅是最重要的函数和数据结构）：

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

你认为这是实现该算法的有效方法吗？我最初使用向量作为染色体，但我读过这个问题：C++ 矢量与数组（时间） 并将我的代码更新为 vector。

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

Answer 1

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

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

请注意，进化算法中真正需要快速的唯一部分是评估，其他所有部分通常并不耗时。您还可以寻找 DEAP，它允许在超级计算机（我们在 1024 上测试）上轻松分发评估（以及更多内容）通过更改串行算法中的一行代码来实现 Colosse 超级计算机的核心）。

Answer 2

对于您尝试对向量执行的操作来说，交叉代码似乎具有最高效率。根据我使用遗传算法的经验，适应度函数和选择运算符是最耗时的。由于您将对总体样本使用交叉和变异，因此您不必太担心交叉算子的效率。专注于为数据定义良好的表示和最佳的适应度函数实现。

Answer 3

如果您已经知道数组的大小，那么使用数组将比使用向量快得多。向量比数组需要更多的开销。

Answer 4

你可以稍微压缩一下你的内存：使用 4 个字节来表示一个二进制值是相当浪费的。我建议用 std::array 或 std::bitset<64> 替换 chromosome 来打包它更多的。

尽管您声称不担心内存，但压缩内存可以更好地使用 CPU 中的缓存，从而可以加快程序速度。

然而，如果你真的想优化你的程序，唯一明智的方法就是使用成熟的分析器。我过去已经连续使用过 callgrind，但是还有其他的，具体取决于您的开发环境。