C ++中遗传算法的最佳数据结构？ [英] Best Data Structure for Genetic Algorithm in C++?

问题描述

我需要实现为我的问题（大学项目）定制的遗传算法，第一个版本将它编码为一个短矩阵（每个染色体x的人口大小的比特）。

i need to implement a genetic algorithm customized for my problem (college project), and the first version had it coded as an matrix of short ( bits per chromosome x size of population).

这是一个糟糕的设计，因为我声明一个短，但只使用0和1值...但它只是一个原型，它的工作原理，现在是时间为我开发一个新的，改进的版本。

That was a bad design, since i am declaring a short but only using the "0" and "1" values... but it was just a prototype and it worked as intended, and now it is time for me to develop a new, improved version. Performance is important here, but simplicity is also appreciated.

我进行了研究，得出结论：

I researched around and came up with:

染色体：
- String类（如0100100010）
- bool数组
- 向量（向量似乎是针对bool优化的）
- Bitset一个）

for the chromosome : - String class (like "0100100010") - Array of bool - Vector (vectors appears to be optimized for bool) - Bitset (sounds the most natural one)

，对于群体：
- C Array []
- Vector
- Queue

and for the population: - C Array[] - Vector - Queue

我倾向于为chromossome和array的pop选择向量，但我想要任何有经验的人的意见。

I am inclined to pick vector for chromossome and array for pop, but i would like the opinion of anyone with experience on the subject.

先感谢！

推荐答案

我猜你想要随机存取群体和基因。你说性能很重要，我把它解释为执行速度。所以你可能最好使用一个向量<> 用于染色体和一个向量< char> 基因。 向量< char> 的原因是 bitset<> 和向量< bool> 针对内存消耗进行了优化，因此速度很慢。 向量< char> 将以x8内存为代价给你更高的速度（假设系统上 char = byte） 。所以如果你想要速度，用向量< char> 。如果内存消耗是最重要的，则使用向量< bool> 或 bitset<> 。 bitset<> 在这里似乎是一个自然的选择，但是要记住，它是基于位数的模板，这意味着a）基因的数量必须在编译时是固定的和已知的（我猜猜是一个大的no-no），和b）如果你使用不同的大小，你最终得到一个副本每 bitset 你使用的每个 bitset 方法的大小（虽然内联可能否定这个），即代码膨胀。总的来说，如果你不想要向量< char> ，我会猜测向量< bool>

I'm guessing you want random access to the population and to the genes. You say performance is important, which I interpret as execution speed. So you're probably best off using a vector<> for the chromosomes and a vector<char> for the genes. The reason for vector<char> is that bitset<> and vector<bool> are optimized for memory consumption, and are therefore slow. vector<char> will give you higher speed at the cost of x8 memory (assuming char = byte on your system). So if you want speed, go with vector<char>. If memory consumption is paramount, then use vector<bool> or bitset<>. bitset<> would seem like a natural choice here, however, bear in mind that it is templated on the number of bits, which means that a) the number of genes must be fixed and known at compile time (which I would guess is a big no-no), and b) if you use different sizes, you end up with one copy per bitset size of each of the bitset methods you use (though inlining might negate this), i.e., code bloat. Overall, I would guess vector<bool> is better for you if you don't want vector<char>.

如果你关心 vector< char> 的美学，你可以 typedef char基因; 然后使用载体< gene> ，看起来更自然。

If you're concerned about the aesthetics of vector<char> you could typedef char gene; and then use vector<gene>, which looks more natural.

A string 就像一个向量< char> ，但更麻烦。

A string is just like a vector<char> but more cumbersome.

这篇关于C ++中遗传算法的最佳数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！