Аннотация
В статье рассмотрены генетические алгоритмы, принципы их работы, основные операторы, приведен пример построения генетического алгоритма, формирование исходной популяции, и ее переход в новую популяцию посредством функции приспособленности, наглядно показана параллельность поиска решения генетическим алгоритмом и его способность работы с задачами из области нечетких множеств.
История создания и сущность генетических алгоритмов
Генетические алгоритмы ставят своей целью преодоление существующих проблем решения оптимизационных задач, таких как проблема преждевременной сходимости и проблема затраты времени на проведение вычислений. Генетические алгоритмы впервые предложены в 1975 году — Джоном Холландом, основаны на принципах естественного отбора Ч. Дарвина, относятся к группе стохастических методов. Определение генетического алгоритма можно дать, следующим образом, это адаптивный метод поиска, который используется для решения задач оптимизации, основанные на механизме генетического наследования, позаимствованный у природы. Так же генетический алгоритм представляет собой последовательность управляющих действий и операций, моделирующий эволюционные процессы на основе аналогов механизмов генетического наследования и естественного отбора. Степень адаптации зависит от набора хромосом, полученных от родителей [6].
Генетические алгоритмы позволяют строить модели сложных систем (экономических, инженерных, математических и т.д.). Расширение области поиска решений в сравнении со стандартными подходами, возникает за счет наличия механизма скрещивания. Естественный отбор избирает только лучшие решения, позволяя им развиваться дальше, за счет скрещивания друг с другом. Поэтому генетические алгоритмы позволяют решать задачи оптимизации для n-мерных систем нелинейных уравнений.
Генетический алгоритм является алгоритмом направленного поиска, поэтому в отличие от алгоритма полного перебора, рассматривающего все возможные варианты решения, алгоритм направленного поиска стремится отыскать окрестность оптимального решения. Следовательно, решение займет меньше времени, чем в случае полного перебора вариантов потенциальных решений. Однако, практика использование генетических алгоритмов для решения NP-полных задач имеет множество трудностей возникающих вследствие стремления алгоритма направленного поиска к локально оптимальному решению. Данная проблема вытекает из отсутствия информации у алгоритма о локальности или глобальности обнаруженного оптимума, из-за чего алгоритмы направленного поиска не гарантируют нахождение глобально оптимального решения.
Операторами генетического алгоритма являются: оператор выбора родителей; оператор скрещивания; оператор мутации; оператор селекции, их последовательное выполнение обеспечивает работу алгоритма. Задачами данных операторов являются манипуляции с данными таким образом, чтобы полученные решения качественно улучшались, вплоть до достижения необходимого уровня качества [1].
Эффективность работы генетического алгоритма
В исследовании Федорова Е.А. наглядно показано преимущество генетического алгоритма над алгоритмом полного перебора при численности популяции более 20 особей. При количестве особей в популяции более 20 алгоритм полного перебора имеет экспоненциальный рост времени на поиск решения, время работы генетического алгоритма продолжает увеличиваться линейно [7].
Любой найденный вариант решения и сохраненный в памяти генетического алгоритма, называется индивидом. Множество таких решений в памяти алгоритма, называется популяцией. Индивид имеет степень приспособленности, что детерминирует его в качестве решения задачи. Степень пригодности выражается в виде действительного числа. Количество индивидов в популяции не ограничено теоретически, но на практике бесконечно большая популяция не реализуема в техническом плане. Для поддержания мощности популяции в приемлемых масштабах используют оператор селекции, удаляющего из популяции столько же индивидов старшего поколения, сколько было добавлено новых.
Последовательность поколений это последовательные изменения состояния популяции индивидов. В процессе работы генетического алгоритма происходит улучшение качества популяции, где индивиды в каждом новом поколении окажутся более приспособленными по сравнению с индивидами из прошлых поколений. Чем меньше поколений требуется генетическому алгоритму для получения решения необходимого качества, тем лучше и быстрее он работает.
Индивид состоит из хромосом, которые содержат гены. Данная организация позволяет легко представить вариант решения некоторой задачи в виде, приемлемом для генетического алгоритма. Если операторы, связанные с выбором индивидов из популяции, оперируют целыми индивидами и не изменяют их содержимого, то операторы скрещивания и мутации должны редактировать содержимое генов. Содержимое генов и их набор в хромосоме сильно зависят от задачи, тем не менее, существуют три основных типа генов: действительный, целочисленный и логический. Действительный ген реализован одним действительным числом, целочисленный – целым числом, а логический – логической переменной. Генетический алгоритм допускает применение собственных генов, однако необходимо предоставить реализации операторов скрещивания и мутации, способные обрабатывать данный вид генов [2].
В начале работы генетического алгоритма необходимо создать новую популяцию, которая определяет первое поколение, индивиды в ней могут быть любого качества. Генератор первичной популяции должен создать таких индивидов, с которыми корректно смогут работать остальные операторы. Генератор новой популяции допускает наличие эвристик, потенциально приводящих к ускорению процесса поиска решения приемлемого качества. Эвристики снижают генный потенциал индивидов популяции, что приводит к вычислению лишь локально оптимального решения задачи, но экономит время, затраченное на решение.
В основе генетического алгоритма лежит принцип сравнения имеющихся решений. Для применения генетического алгоритма необходимо составлять варианты решения поставленной задачи и сравнивать их между собой. Выгоднее всего применять данный алгоритм по отношению к таким задачам, у которых нет способа нахождения оптимального решения без использования сравнений среди множества вариантов решений. Оценка генетического алгоритма имеет сравнительный характер, ему неизвестна близость данного решения к оптимальному.
Операторы выбора родителей и селекции управляют множеством индивидов, переходящих из одного поколения в следующее. Так на основе выбранных родителей будут созданы потомки, а выбранные в ходе селекции жертвы будут удалены из популяции. Предполагается, что родителями выбираются такие индивиды, которые потенциально приведут к образованию лучше приспособленного потомка, а жертвами – потенциально тормозящие развитие популяции. Основной сложностью разработки оператора выбора родителей является незнание генетическим алгоритмом таких индивидов, которые наилучшим образом подошли бы в качестве родителей [3].
Похожим по устройству и противоположным по назначению является оператор селекции. Данный оператор может быть описан в двух формулировках: как оператор выбора жертв и как оператор селекции. Оператор выбора жертв выбирает индивиды, которые необходимо удалить из популяции, после чего удаляет их. Оператор селекции выбирает индивиды, которые необходимо перенести в новое поколение, он каждый раз заново составляет очередное поколение.
Оператор скрещивания служит для обработки индивидов-родителей и создания на их основе потомков. Целью оператора скрещивания является создание таких потомков, которые бы превосходили своих родителей в степени приспособленности. Для повышения эффективности получаемых решений применяется усложненный оператор скрещивания, создающий несколько вариантов потомков. В таком случае происходит сравнение различных потомков между собой, после чего из них выбирается наилучший. С другой стороны, применение такого оператора скрещивания может значительно замелить алгоритм в случае работы с медленной функцией приспособленности.
Работа оператора мутации заключается в редактировании значений генов у создаваемых потомков. Данный оператор служит для внесения в популяцию новых вариантов значений генов. Если бы данный оператор отсутствовал, то новые гены создавались бы только в результате генерации начальной популяции или при некоторых вариантах реализации оператора скрещивания, что привело бы к неприемлемому сужению области поиска и выводу в качестве решения заведомо некачественного результата. Реализация данного оператора сильно зависит от конкретной задачи, так как она связана с редактированием содержимого генов. Как правило, в основе оператора мутации лежит случайная величина, определяющая степень изменения полученных после скрещивания значений. Чем сильнее оператор мутации изменяет содержимое генов, тем он считается мощнее [4].
После получения алгоритмом решения приемлемого качества, необходимо остановить работу поискового цикла. Условие, при котором популяция начинает обладать необходимым решением, называется условием остановки генетического алгоритма. Существуют различные признаки, на которые может опираться условие остановки: достижение необходимой точности решения; уменьшение изменения состояния популяции; превышение лимита количества поколений; превышение лимита затраченного времени [5].
Пример построения генетического алгоритма
Рассмотрим пример работы генетического алгоритма на примере решения задачи оптимизации по нахождению максимума. Задача формулируется следующим образом:
где n – размер популяции.
Первичная популяция представляет собой формируемое случайно пространство потенциальных решений имеющейся задачи. Генетический алгоритм посредством операторов будет преобразовывать данную популяцию до тех пор, пока не будет, достигнут критерий остановки, или будет достигнуто максимальное количество поколений. Индивиды каждого поколения отбираются исходя из их уровня приспособленности. Функцией приспособленности является целевая функция поставленной задачи. Затем гены индивидов попарно скрещиваются и получаются индивиды нового поколения, далее новые индивиды подвергаются мутации. Полученное таким образом решение добавляется к популяции и отбрасывается то значение, для которого целевая функция имеет наименьший показатель.
Представим работу генетического алгоритма в виде схемы:
1. Выбираем исходную популяцию
??(0)={??1,??2,...,???},
где ? – длина цепи. Будем считать, что:
?∗ =max{?(??)|?? ∈??(?)},? ≔0
2. До достижения критерия остановки необходимо выполнять следующие шаги: выбираем родителей ??1,??2 из общей популяции ?? (?) путём скрещивания получаем особь ??′ с помощью ??1,??2; модифицируем ??′, т.е. производим мутацию; проверяем, если ?∗<?(??′), то ?∗≔?(??′); производим обновление популяции, полагая, что ?≔?+1.
На первом шаге необходимо корректно сформировать исходную популяцию. Индивиды, которой состоят из определенного набора хромосом, представленных в виде битовых строк или векторов. Далее генетический алгоритм декодирует значения и получает множество значений, удовлетворяющих субоптимальному значению поставленной задачи. Следовательно, генетический алгоритм, по сути, является множественно-вероятностной моделью. Что позволяет генерировать множество решений задачи лежащих в определенной окрестности от истинного решения. Данный факт позволяет работать в тех областях, где точка экстремума задачи не может быть четко задана.
Рассмотрим обмен хромосомами между родительскими индивидами популяции, с целью определения значения приспособленности. Для этого рассмотрим двух родителей и их наборы хромосом, так:
?1 =(?11,?12,...?1?) и ?2 =(?21,?22,...?2?).
Точка разрыва хромосом задана случайно. Затем родительские индивиды делятся относительно случайно заданной точки и обмениваются хромосомами. В результате возникают два потомка со следующими наборами хромосом:
(?11,...,?1?,?2?+1,...,?2?) и (?21,...,?2?,?1?+1,...,?1?),
т.е. участки после точки разрыва скрещиваются между хромосомами родителей.
Далее происходит мутация индивидов нового поколения. Мутация осуществляется следующим образом: в каждой строке один из геном меняется на противоположный. Первый из созданных потомков будет хранить символы хромосом родителей ?1 или ?2, произвольные для любой позиции символов. Второй потомок получит символы разности. Например, пусть потомки имеют следующий вид:
?1 =(?11,?12,?13,?14...?2?) и ?2 =(?21,?22,?23,?24,...?1?).
Таким образом, генетические алгоритмы обладают, способны производить параллельный поиск генов во всех комбинациях. Соответственно время поиска прямопропорционально объему популяции.
Заключение
В заключении отметим, что мы рассмотрели принципы работы генетического алгоритма, убедились, что генетический алгоритм при большом объеме популяции имеет преимущество над алгоритмом полного перебора по времени работы. Отметили, что генетический алгоритм обладает возможностями для работы с множественно-вероятностными задачами, что делает его применимым для решения задач нечетких множеств.
Список литературы
1. Гончаров, Е.Н. Генетический алгоритм для задачи календарного планирования с ограниченными ресурсами // Автомат. и телемех., № 6, 2017. – С. 173–189.
2. Гончаров, Е.Н. Стохастический жадный алгоритм для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций, Т. 21, № 3, 2014. – С. 11–24.
3. Дивеев, А.И. Метод бинарного генетического программирования для поиска математического выражения // Вестник Российского университета дружбы народов. Серия: Инженерные исследования, Т. 18, № 1, 2017. – С. 125—134.
4. Евсютин, О.О. Алгоритм встраивания информации в сжатые цифровые изображения на основе операции замены с применением оптимизации // Компьютерная оптика, Т. 41, № 3, 2017. – С. 412–421.
5. Загинайло, М.В., Фатхи, В.А. Генетический алгоритм как эффективный инструмент эволюционных алгоритмов // Инновации. Наука. Образование. 2020. № 22. – С. 513-518.
6. Панченко, Т. В. Генетические алгоритмы [Текст]: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 [3] с.
7. Федоров Е. А. Исследование скорости работы генетического алгоритма и алгоритма полного перебора // Сборник избранных статей научной сессии ТУСУР. №1. 2019. – С. 107-109.
