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

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

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

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

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

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

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

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

4 3
c++ data-structures artificial-intelligence genetic-algorithm

4 ответа:

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

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

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

7

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

Для идей и хороший инструмент, чтобы баловаться. Рекомендуем вам скачать и изначально использовать эту библиотеку. Он работает с основными компиляторами. Работает на UNIX системы. Имеет весь исходный код.

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

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

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

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

Галиб

Http://lancet.mit.edu/ga/

1

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

0

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

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

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

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

0