Генетические алгоритмы в Rust для автономных агентов: введение
В этой статье обсуждается возможная реализация генетического алгоритма в Rust применительно к задаче коммивояжера.
Автономные агенты, которые перемещаются по реальному миру в режиме реального времени, такие как роботы, должны иметь возможность решать, что лучше всего предпринять. Необходимо учитывать множество факторов и множество возможных комбинаций действий; какой лучший?
Например, предположим, что у вас есть робот, и вы хотите, чтобы он складывал предметы в коробку. Однако элементов много, и невозможно уместить их все в этот ящик, имеющий ограничения по размерам и весу. Как робот выбирает, какие предметы положить в эту коробку? Каждому элементу может быть присвоено значение, и робот должен максимизировать общую стоимость выбранных элементов с учетом ограничений. Это комбинаторная задача оптимизации - проблема упаковки. Учитывая множество задействованных переменных, тестирование всех возможных решений неэффективно, отнимает много времени и непрактично.
Допустим, мы решили проблему, описанную выше, и теперь робот должен подобрать все предметы, но они находятся в разных местах в комнате. Чтобы сэкономить энергию и время, робот должен найти кратчайший путь, чтобы получить все предметы, а затем подойти к ящику. Это еще одна известная задача комбинаторной оптимизации - задача коммивояжера.
Существует множество традиционных способов решения подобных проблем, не прибегая к грубой силе, например, техника лазания по холмам, основанная на исчислении и алгоритмы случайного поиска; у каждого есть свои плюсы и минусы. Один из подходов, который имеет некоторые преимущества перед традиционными методами - это использование генетических алгоритмов.
Обзор генетических алгоритмов
Генетические алгоритмы - это алгоритмы поиска, которые вдохновлены процессами, наблюдаемыми в ходе естественной эволюции. Они рандомизированы, но используют историческую информацию для интеллектуального поиска в пространстве решений, чтобы максимизировать или минимизировать конкретную функцию.
Идея состоит в том, что у нас есть population возможных решений (individuals), и они теоретически развиваются в сторону лучших решений на каждой итерации. Каждое решение-кандидат имеет свойства (DNA). Чем больше fit людей с большей вероятностью произведут children, а эти children, скорее всего, будут лучше, чем их _7 _ . Детские DNA создаются с использованием операций, вдохновленных тем, как изменяются реальные DNA. Каждое последующее population с большей вероятностью будет лучше, чем предыдущее поколение.
ДНК и ФИТНЕС
Чтобы проиллюстрировать, как работают генетические алгоритмы, давайте применим их к задаче коммивояжера. Допустим, у нас есть набор из пяти cities: 0, 1, 2, 3, и 4 каждый в месте, представленном двумя числами (Px, Py) с заданным диапазоном чисел с плавающей запятой.
Сначала давайте сделаем генетическое представление области решения (DNA). В данном случае это порядок the cities. Решение - это перестановка cities, например [1, 0, 2, 3, 4] и [4, 3, 1, 0, 2], которую мы можем представить как массив целых чисел. Мы также должны определить функцию fitness, которую мы будем использовать для количественной оценки и оценки того, является ли решение лучшим или худшим. В этом случае мы хотим получить кратчайший маршрут, мы можем определить нашу функцию fitness как деленную на сумму квадратов расстояний от одного города до следующего. .
Как это работает
Теперь мы simulate процесс эволюции.
Сначала мы инициализируем набор лиц с DNA. Мы можем заполнить первое пространство решения, если мы уже знаем, какой порядок набора cities является более вероятным кандидатом. Для простоты давайте просто случайным образом выберем набор из city заказов. Мы можем оценить individual’s fitness, учитывая его DNA и нашу fitness функцию. Самое подходящее individual в этом population - лучшее решение, которое мы видели до сих пор, назовем его champion.
Для каждой итерации мы должны генерировать новую популяцию из предыдущей. У каждого population есть свой самый подходящий человек, challenger, который мог бы заменить champion. По сути, на каждой итерации мы находим champion лучшее решение, которое мы когда-либо видели. После серии итераций DNA финального чемпиона - лучшее решение, которое мы видели. Мы можем назвать это run. Возможно, нам придется выполнить run a simulation несколько раз, чтобы получить лучшее решение, если оно вообще есть, потому что алгоритм является вероятностным по своей природе. Повторяйте это, пока не будете довольны результатом!
Размер популяции каждого и количество итераций на run - это то, что мы можем настроить.
How to generate the next population?
Как упоминалось ранее, более подходящие люди с большей вероятностью произведут children. Нам нужно определить способ вероятностного выбора individuals, которые производят children на основе их fitness. Давайте сделаем так, чтобы вероятность выбора этих individuals была пропорциональна их относительной fitness относительно population, это также известно как взвешенный выбор или выбор колеса рулетки .
Возьмем два parents и будем использовать их для создания двух children, пока не получим population размер, который мы указали. Фактически мы можем использовать любое количество parents для получения любого количества children, но для простоты давайте использовать два parents и два children.
Также упоминалось ранее, DNA children создаются с использованием операций, вдохновленных тем, как реальные DNA изменяются на основе parent’s DNA. Есть много способов сделать это, для простоты давайте изменим вероятностно, используя типы crossover и mutate операций. Мы обсудим эти два в следующем разделе. Давайте определим еще два параметра для настройки: вероятность кроссовера и вероятность мутации. Вероятность кроссовера - это вероятность того, что мы выполним crossover операцию. Нам не нужно выполнять crossover все время, мы можем напрямую clone иногда parents . Есть вероятность, что parents уже являются хорошим кандидатом на решение, а crossover - ненужная дорогостоящая операция, которая может ухудшить набор решений. Точно так же вероятность мутации - это вероятность того, что мутация будет выполнена.
Кроссовер и мутация
Операция crossover напоминает биологический кроссинговер и рекомбинацию хромосом в клеточном мейозе. Есть много способов определить crossover операцию. В этом случае мы можем сначала выбрать два parents, выбрать случайную последовательность из DNA одного родителя и скопировать ее в DNA из child , а остальное получить от другого parent. Это рекомбинирование частей хороших людей, которые, вероятно, создадут еще лучше individuals.
Мутация - это случайная модификация. Цель мутации - поддержание разнообразия в популяции. Мутация также происходит при рекомбинации DNA в биологических системах. Если мы не будем вводить мутации, мы можем сойтись к локальному максимуму, а не к глобальному максимуму. Для простоты моя функция мутации просто случайным образом выбирает город в DNA и меняет его местами на соседний город.
Собираем все вместе
A SIMULATION RUN
Initialize
- Randomly initialize a population of individuals
- Determine the fittest individual so far "CHAMPION"
Repeat for a number of iterations
- Generate the next population of individuals based on the previous
- Select parents
- Perform genetic operations such as crossover or clone
- to produce children and possibly mutate
- Get the fittest individual in this population "challenger"
- Replace the "champion" with the "challenger" if it is more fit
The champion's DNA is the best solution we've seen in this simulation run. You might need to make multiple runs to get a better solution.
Вам необходимо указать некоторые параметры для simulation run, например:
1. Number of iterations 2. Population size 3. Crossover probability 4. Mutation probability
Вы также должны определить следующее, учитывая вашу конкретную проблему:
1. DNA representing the solution 2. The fitness function 3. The selection function 4. Genetic operations such as crossover, clone, and mutation
В этой статье был представлен генетический алгоритм и показано, как его можно использовать для решения задачи коммивояжера. Для всего решения и анимированных визуализаций поиска можете проверить мой репозиторий! Звездочка, если тебе это нравится!
ВАЖНОЕ ПРИМЕЧАНИЕ: Известно, что более сложные алгоритмы, такие как эвристика Лин-Кернигана лучше подходят для решения задач коммивояжера!
Ссылки: Дженна Карр 2014 + Виджини Маллаваараччи
