Как написать эффективные генетические алгоритмы на 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 vs Array (Time) , и я обновил свой код до vector<int>.

Как вы думаете, есть ли другие оптимизации, которые я должен сделать с моим кодом, чтобы сделать его более эффективным?Эффективен ли код пересечения, как сейчас?

Answer 1

Как насчет использования смущающего параллелизма в эволюционном алгоритме.А как насчет того, чтобы попытаться перенести ваше решение на GPU?И, как сказали Четан и Дэвид, использование существующей среды может занять гораздо меньше времени, чем написание собственной fast one.

OpenBeagle и EO - это хорошо известные хорошо поддерживаемые и очень эффективные фреймворки.

Обратите внимание, что единственная часть, которая действительно должна быть быстрой в эволюционном алгоритме, - это оценка, все остальное обычно не занимает много времени.Вы также можете найти DEAP , который позволяет очень легко распределить оценку (и даже больше) на суперкомпьютере (мы протестировали на 1024 ядрах суперкомпьютера Colosse, изменив одну строку кода в нашем последовательном алгоритме).

Answer 2

Код кроссовера выглядит максимально эффективно для того, что вы пытаетесь сделать с векторами. Исходя из моего опыта работы с генетическими алгоритмами, функция фитнеса и оператор отбора наиболее трудоемки. Поскольку вы будете использовать кроссовер и мутацию в выборке населения, вам не нужно слишком беспокоиться об эффективности оператора кроссовера. Сосредоточьтесь на определении хорошего представления ваших данных и оптимальной реализации фитнес-функции.

Answer 3

Вы можете несколько сжать свою память: использование 4 байтов для представления двоичного значения довольно расточительно. Я бы предложил заменить chromosome на std::array<unsigned char, 64> или std::bitset<64>, чтобы упаковать его больше.

Даже если вы заявляете, что не беспокоитесь о памяти, сжатие памяти приводит к более эффективному использованию кэша в ЦП, что может ускорить выполнение программы.

Однако, если вы действительно хотите оптимизировать свою программу, единственный разумный способ - использовать полнофункциональный профилировщик. В прошлом я довольно последовательно использовал callgrind, но есть и другие, в зависимости от вашей среды разработки.

Answer 4

Если вы уже знаете, каким будет размер ваших массивов, то использование массивов будет намного быстрее, чем использование векторов. Векторы требуют гораздо больше накладных расходов, чем массивы.