Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации

Одной из задач интеллектуальных систем является поиск оптимального решения: когда на систему влияет множество внешних и внутренних факторов, интеллектуальное устройство должно учесть их все и выбрать оптимальное поведение с точки зрения своей выгоды. Допустим, если Вы — хозяин склада, Вам необходимо учитывать много факторов (стоимость единиц товаров, спрос, издержки на хранение различных товаров на складе и т.д.) для минимизации издержек и получение наибольшей прибыли.

Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

В системах искусственного интеллекта для решения подобных задач применяются генетические алгоритмы.

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

Скажем проще: по сути, генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).генетический алгоритм

Причём тут биология?

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

Особь – одно решение задачи.

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

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

Это вариация задачи о коммивояжёре (путешественнике) – относится к классу NP-полных, проще говоря, не может быть решена с помощью математических формул.

Решение задачи – это последовательность прохождения контрольных точек. Возьмём несколько возможных решений (особей)– это и есть начальная популяция.

испльзование генетических алгоритмов

Определения качества решений

Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

ФП = Р(1)+Р(2)+Р(3)+Р(4)+Р(5)+Р(6),

где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

Давайте посчитаем функции пригодности. Для первой особи:

функция пригодности генетического алгоритма

Для остальных особей таким же образом получаем:

ФП(2) = 111

ФП(3) = 47

ФП(4) = 125

Тут всё очевидно: особь №3 – лучшая, а №4 – самая плохая.

Генетические операторы

Дальше согласно алгоритму необходимо слегка изменить исходных особей, так чтобы они были похожи на своих родителей, но немного отличались. Так реализуется биологическое понятие «изменчивость».

Генетические операторы – определённые правила, по которым изменяются особи в следующей популяции. Среди них выделяют операторы скрещивания и мутации. Подробнее об этих операторах речь пойдёт в одной из следующих статей. Сейчас главное запомнить, что после их применения мы получим еще несколько особей – потомков. Допустим таких:

операторы генетического алгортма

Для потомков тоже посчитаны функции пригодности.

Оператор селекции

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

Алгоритмы селекции тоже могут быть различны, не будем пока заострять на этом внимание. Просто возьмем и отбросим из первой популяции (родители + потомки) четыре худших особи. Останутся родитель 1 и 3, и потомки 1 и 2. Эти особи сформируют новую популяцию. Далее алгоритм будет повторяться. Для наглядности посмотрим на блок-схему классического генетического алгоритма:

алгоритм

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

Вспомним, что мы искали кратчайший путь прохождения робота через все контрольные точки. Абсолютно правильный ответ будет получен, только если перебрать все варианты, а их очень много даже для шести точек (а если точек будет больше?). Поэтому генетический алгоритм ищет не правильное решение, а оптимальное, исходя из условий, которые задаёт пользователь.

Критерий останова – условие, по которому генетический алгоритм останавливает свою работу.

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

В нашем случае мы можем указать, например, один из следующих критериев останова:

  • Суммарный путь меньше 50
  • Время работы алгоритма 1 час
  • Число циклов алгоритма 10
  • В течение 3 поколений не появляются особи лучше тех, которые были
  • и т.д.

Ещё немного о функции пригодности

На практике далеко не всегда получается составить функцию пригодности так же просто, как в нашем примере. Например, вы —  хозяин завода. Ваша цель увеличение прибыли. Для достижения этой цели вы можете варьировать много различных параметров: количество закупаемого сырья, план выпуска, зарплата рабочих, количество денег, выделяемых на модернизацию производства, повышение квалификации персонала, на рекламу и т.д. Набор конкретных значений этих параметров и будет стратегией, скажем, на месяц. Однако нет точной математической формулы, связывающей эти параметры между собой. Поэтому в данном случае для подсчёта функции пригодности необходима имитационная модель завода. Как видно из названия, это модель, имитирующая работу заводу, все его бизнес-процессы. Подробную информацию об имитационном моделировании вы также сможете найти на страницах LAZY SMART. А пока для краткости изложения скажем, что если на вход имитационной модели задать входные значения искомых параметров, то на выходе получим итоговую прибыль. Компьютер как бы проиграет всю деятельность завода, допустим, за месяц в убыстренной перемотке. Эта итоговая прибыль и будет значением функции пригодности для генетического алгоритма. Представим работу связки «Генетический алгоритм – Модель» на схеме.

применение генетических алгоритмов

Применение генетических алгоритмов

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

Такие алгоритмы могут стать хорошим помощником в бизнесе, сократить убытки и увеличить прибыль за счёт выбора оптимальных стратегий.


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *