Часто в промышленных сценариях необходимо определить оптимальное решение проблемы с учетом набора ресурсов и ограничений, обязательно будет максимизация прибыли или минимизация убытков, это может быть, например, минимизация расстояния движения грузовиков доставки. планирование интеллектуальных маршрутов или планирование службы общественного питания таким образом, чтобы все потребности в питании удовлетворялись с наименьшими затратами; любое испытание набора выбранных ресурсов называется решением и имеет определенную ценность, например пройденные километры или потраченные доллары.
Также дело обстоит так, что в большинстве случаев вычисление ценности нескольких предлагаемых решений может оказаться сложной задачей, поскольку пространство возможностей для решения проблем становится настолько большим и выходит за пределы любой управляемой области.
Конечно, эта обширная вселенная решений не поддается управлению людьми, а иногда даже не поддается управлению компьютерами — по крайней мере, компьютерами, использующими традиционные методы, такие как линейное программирование, которое вы можете рассматривать как продвинутый метод проб и ошибок — так что в случае огромных диапазонов возможностей , этот подход также дает сбои. Методы, которые решают эти проблемы оптимизации, называются детерминированными или стохастическими. Генетический алгоритм обычно является стохастическим алгоритмом, но далее я буду использовать его для решения простой детерминированной задачи для иллюстрации.
Чтобы подойти к детерминированной проблеме, сначала давайте установим постановку задачи.
Представьте, что есть грузовик, который вы хотите загрузить продуктами таким образом, чтобы наша загрузка была максимально возможной в денежном выражении, грузовик имеет ограниченную вместимость. Существует также ограниченный набор продуктов, которые вы можете носить с собой, например:
Для этой примерной задачи наш набор данных о доступных продуктах состоит из 14 доступных продуктов на выбор с соответствующими ценами и грузовика вместимостью 3 единицы объема.
Затем мы создадим популяцию агентов, каждый из которых имеет хромосому (массив двоичных цифр), которая содержит информацию о поведении такого агента при выборе продуктов для загрузки грузовика. Это поведение определяется аллелями хромосомы. В этом случае мы предлагаем конструкцию хромосомы, в которой каждый аллель просто определяет, является ли продукт носителем или нет.
Обратите внимание, что в нашем примере длина хромосомы будет 14, так как это количество продуктов, доступных для перевозки.
Вы можете себе представить уже сейчас, просто по названию алгоритма, что среди вновь порожденной популяции будет происходить какая-то эволюция, это будет происходить путем создания новых поколений на основе отбора и воспроизводства особей популяции. Чтобы ввести способность индивидуумов иметь какое-либо значение, скажем, у них также есть шанс мутировать.
Метод мутации хромосомы индивидуума можно определить как наличие вероятности выполнения замены битов для каждого аллеля в хромосоме.
Программно метод в объекте хромосомы:
Размножение двух особей, более известное как скрещивание, может быть выполнено разными способами, но для простого примера мы определим скрещивание как создание двух новых особей путем взятия двух существующих особей, разрезания их пополам, а затем объединения первой половины. со второй половинкой другого — получая нашу первую новую особь — и первую половину другого со второй половинкой — для нашей второй новой особи.
Не стесняйтесь взглянуть на полный файл отдельного класса в репозитории git, указанном в конце статьи.
Теперь мы подошли к концу нашего решения: мы должны выбрать наиболее подходящих особей из каждого поколения, продолжать создавать новые поколения и отслеживать лучших особей. Приспособленность определяется для индивидуума в популяции как получение суммы цен на продукты, выбранные его аллелями, в пределах ограничений грузовика.
Чтобы выбрать двух особей для размножения, мы выберем двух случайным образом и оставим одну с наилучшей приспособленностью и назовем ее нашим первым партнером по спариванию, затем выберем наугад двух других особей и оставим ту, которая лучше всего приспособлена, в качестве нашего второго партнера по спариванию. .
Один полный шаг процесса создания нового поколения состоит из отбора, скрещивания и мутации двух выбранных родителей. Этот процесс произведет двух детей, и мы будем повторять этот шаг, пока новое поколение не достигнет того же размера популяции, что и предыдущее.
Наконец, не забывайте отслеживать среднюю физическую форму вашей популяции и, что наиболее важно, отслеживать хромосому лучшего человека, который является рекордным решением вашей проблемы.
Со всеми предыдущими компонентами я разработал небольшую структуру для решения проблемы, можно увидеть, что приспособленность населения со временем увеличивается.
Самый драматический эффект наблюдается в фитнес-показателях лучших людей, которые быстро определяют оптимальное расположение продуктов в грузовике в зависимости от максимальной цены товаров.
Найдите в блокноте репозитория проекта, что хромосома ставок
[0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
это означает, что мы должны взять все продукты, кроме тех, у которых есть индекс 0, 5 и 6.
Погрузитесь в код маленького фреймворка, он состоит из всех функций, которые мы обсуждали интегрированным образом.
