Генетический алгоритм

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

В этом примере мы сосредоточимся на следующей проблеме, чтобы проверить нашу реализацию GA:

Каждому из вас дается по 10 карточек, пронумерованных от 1 до 10. Вас просят разделить карточки на две группы, где сумма чисел на карточках в первой группе максимально близка к 36, а произведение чисел во второй группе максимально близко к можно 360.

GA разделен на 5 процессов, каждый из которых может различаться по реализации, а это означает, что вы можете полностью контролировать то, как работают отдельные процессы GA и сколько в них вносится случайностей. Цель этого поста в блоге — каким-то образом определить эти процессы с помощью некоторого кода на C++, и я попытался это реализовать.

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

Ниже приведен общий обзор компонентов, необходимых для реализации GA.

Инициализировать население

Здесь нам нужно создать что-то, называемое хромосомой, которая будет содержать все количество карт, то есть генов, поскольку нам нужно разделить карты на две группы, которые нам нужно будет затем назначить им случайным образом, поэтому 0 и 1. Это означает, что наше пространство поиска будет иметь 2¹⁰ (1024) возможных комбинаций для проверки, чтобы найти правильное решение, 2 возможные группы на выбор в 10 карт.

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

Оценить файлы

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

Здесь я просматриваю все гены для каждой хромосомы в популяции и вычисляю общие значения для обеих групп. Затем мы берем абсолютное значение этого, чтобы избавиться от отрицательных результатов. Следует отметить, что в этой задаче нам нужно рассчитать две субприспособленности: одну для цели группы 0 и одну для цели и группы 1.

Я также обнаружил, что в классе из-за того, что группа 1 имеет большее целевое значение, это может создать смещение в хромосоме и, таким образом, уменьшить его до аналогичного размера (т.е. целевое значение 2 * 0,1 = 36), поэтому другая цель будет помогите не выделять эту группу над другой. если, конечно, у вас нет для этого оснований.

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

Выбор

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

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

Опять же, это область, которая может быть полностью определена программистом. Здесь следует использовать любой процесс выбора, который принесет пользу пригодности и поиску решения.

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

Кроссовер/мутация

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

Кроссовер по существу разделяет гены на две половины, где гены с одной стороны затем берутся от одного родителя, а с другой стороны - от другого родителя.

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

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

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

Отсюда мы заменяем детей текущим населением, и цикл завершается. Теперь все, что осталось, — это проверить, сколько итераций осталось до того, как будет найдено решение цели 36 для 0 и 360 для 1. Благодаря этим экспериментам я обнаружил, что с большей популяцией было быстрее найти целевое решение, что кажется довольно очевидным, поскольку в начале процесса существует гораздо больше комбинаций.