Лучшая структура данных для генетического алгоритма в C ++?

Question

Мне нужно реализовать генетический алгоритм, адаптированный для моей задачи (проект колледжа), и в первой версии он был закодирован как матрица коротких (бит на хромосому х размер популяции).

Это был плохой дизайн, так как я объявлял short, но использовал только значения "0" и "1" ... но это был всего лишь прототип, и он работал как задумано, и теперь пришло время для меня разработать новую, улучшенную версию. Производительность здесь важна, но также ценится простота.

Я исследовал вокруг и придумал:

для хромосомы: - класс String (например, «0100100010») - массив bool - Vector (векторы, похоже, оптимизированы для bool) - Битсет (звучит наиболее естественно)

и для населения: - C Array [] - вектор - очередь

Я склонен выбирать вектор для хромосомы и массив для поп-музыки, но мне хотелось бы узнать мнение любого, кто имеет опыт в этой области.

Заранее спасибо!

Answer 1

Полагаю, вам нужен произвольный доступ к населению и генам. Вы говорите, что важна производительность, которую я интерпретирую как скорость выполнения. Так что, вероятно, лучше всего использовать vector<> для хромосом и vector<char> для генов. Причина vector<char> заключается в том, что bitset<> и vector<bool> оптимизированы для потребления памяти и поэтому работают медленно. vector<char> даст вам более высокую скорость за счет памяти x8 (при условии, что char = байт в вашей системе). Так что, если вы хотите скорость, используйте vector<char>. Если потребление памяти имеет первостепенное значение, используйте vector<bool> или bitset<>. bitset<> может показаться естественным выбором, однако, имейте в виду, что он основан на количестве битов, что означает, что a) количество генов должно быть фиксированным и известным во время компиляции (что, я думаю, является большое нет-нет) и б) если вы используете разные размеры, вы получите одну копию на bitset размер каждого из используемых вами bitset методов (хотя встраивание может свести на нет это), т. е. раздувание кода. В целом, я думаю, что vector<bool> лучше для вас, если вы не хотите vector<char>.

Если вас беспокоит эстетика vector<char>, вы можете typedef char gene;, а затем использовать vector<gene>, что выглядит более естественно.

A string похож на vector<char>, но более громоздкий.

Answer 2

Специально для ответа на ваш вопрос. Я не совсем уверен, что вы предлагаете. Вы говорите о массиве и строковом классе. Вы говорите о классах контейнеров STL, где вы можете иметь очередь, набор битов, вектор, связанный список и т. Д. Я бы предложил вектор для вашей популяции (самый близкий к массиву C) и набор битов для вашей хромосомы, если беспокоит объем памяти. Иначе, поскольку вы уже используете вектор вашего строкового представления вашей ДНК. ( "10110110")

За идеи и хороший инструмент для игры. Рекомендую вам скачать и изначально использовать эту библиотеку. Работает с основными компиляторами. Работает на Unix-вариантах. Имеет весь исходный код.

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

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

Всегда нужно учиться лечить, но оно того стоит.

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

Галиб

http://lancet.mit.edu/ga/

Answer 3

Я предлагаю написать класс для каждого члена населения, что значительно упрощает задачу, поскольку вы можете хранить все функции, относящиеся к вашему члену, в одном месте, аккуратно завернутые в фактические данные.

Если вам нужен «массив bools», я предлагаю использовать int или несколько целых чисел (затем использовать маску и побитовые операции для доступа (изменять / переворачивать) каждый бит) в зависимости от количества ваших хромосом.

Я обычно использовал какой-то класс сбора для населения, потому что просто массив членов населения не позволяет вам просто добавить к вашему населению. Я бы предложил реализовать какой-то динамический список (если вы знакомы с ArrayList, то это хороший пример).

У меня был большой успех с генетическими алгоритмами по рецепту выше. Если вы подготовите свой класс-член должным образом, это действительно может упростить вещи и позволит вам сосредоточиться на кодировании лучших генетических алгоритмов, а не беспокоиться о ваших структурах данных.

Answer 4

Предполагая, что вы хотите закодировать это самостоятельно (если вы хотите, чтобы у внешней библиотеки kingchris, похоже, была хорошая), это действительно зависит от того, какую манипуляцию вам нужно выполнить. Чтобы получить максимальную отдачу от затраченных ресурсов памяти, вы можете использовать любой целочисленный тип и устанавливать / манипулировать отдельными битами с помощью битовых масок и т. Д. Теперь этот подход, вероятно, не оптимален с точки зрения простоты использования ... Приведенный выше пример строки будет работать Хорошо, однако, опять же, это не существенно отличается от шорт, здесь вы просто представляете либо «0», либо «1» с 8-битным значением, а не с 16-битным значением. Кроме того, опять же, в зависимости от манипуляции, строковый регистр, вероятно, окажется громоздким. Так что, если бы вы могли дать больше информации об алгоритме, мы могли бы дать больше отзывов. Мне лично нравятся отдельные биты как часть целого числа (битовый набор), но если вы не привыкли к маскам, сменам и прочим хорошим вещам, это может быть вам не подходит.