Генетический алгоритм.
- 07.12.24 г.
- 9772225665000 24032
В общем случае алгоритм решения задач оптимизации представляет собой итеративный вычислительный процесс, который асимптотически приближается к оптимальному решению. Традиционные методы оптимизации преимущественно строятся на детерминированных последовательностях вычислений, основанных на градиенте или производных высших порядков целевой функции. Эти методы начинаются с одной начальной точки в пространстве поиска и постепенно улучшают решение, двигаясь в направлении наискорейшего возрастания или убывания целевой функции. Однако такой локальный подход может привести к попаданию в локальный оптимум.
Генетический алгоритм реализует параллельный поиск оптимальных значений параметров путем работы с популяцией потенциальных решений. Переход от одной популяции к другой предотвращает застревание в локальном оптимуме. Процесс эволюции популяции имитируется: в каждом поколении наиболее эффективные решения «размножаются», а менее эффективные «вымирают». Для того чтобы направлять поиск в сторону улучшения целевой функции, генетические алгоритмы применяют вероятностные правила отбора хромосом для репликации или удаления.
1. Генетический алгоритм. Общие положения.
Генетические алгоритмы представляют собой класс эвристических поисковых алгоритмов, применяемых для решения задач оптимизации и моделирования. Они основаны на имитации процессов естественного отбора, таких как наследование, мутация и селекция.
Генетические алгоритмы является разновидностью эволюционных алгоритмов, которые используют принципы естественной эволюции для решения задач оптимизации и которые, в свою очередь, являются частью более широкой области – искусственного интеллекта.
Генетические алгоритмы представляют собой адаптивные методы поиска, основанные на принципах, аналогичных генетическим процессам в биологических популяциях. В этих алгоритмах имитируется эволюционный процесс: множество потенциальных решений развивается на протяжении нескольких поколений, подчиняясь механизмам отбора по принципу «выживает наиболее приспособленный». Индивиды, демонстрирующие наилучшую приспособленность к заданным условиям, имеют повышенные шансы на воспроизводство потомков, то есть на передачу своих характеристик следующим поколениям. Напротив, менее приспособленные индивиды либо не производят потомство, либо их вклад в следующее поколение незначителен. В целом вид развивается, все лучше и лучше приспосабливаясь к среде обитания.
Таким образом, обозначенный подход приводит к накоплению и распространению благоприятных признаков, что способствует постепенному совершенствованию решений с течением времени.
Ключевой характеристикой генетических алгоритмов является применение процедуры скрещивания, функционально схожей с биологическим процессом рекомбинации генов.
Преимуществами генетического алгоритма являются возможности одновременной оптимизации множества параметров.
2. Генетический алгоритм. Реализация.
Начальная популяция в генетическом алгоритме формируется случайным образом и характеризуется значительным разнообразием своих элементов. Это позволяет на основе процедуры скрещивания осуществлять широкое использование пространства возможных решений. По мере роста значения функции соответствия полученных решений, процедура скрещивания фокусируется на исследовании окрестностей каждого из них. Иными словами, характер поисковой стратегии процедуры скрещивания определяется разнообразием популяции, а не самой этой процедурой.
Если говорить кратко, то процесс работы генетического алгоритма можно описать следующим образом:
– определяется исходное состояние – формируется начальная популяция,
– вычисляется значение пригодности популяции – значение функции приспособленности,
– выясняется, выполнено ли заданное условие завершения работы алгоритма,
– если условие не выполнено, то происходит формирование новой популяции на основе селекции, кроссинговера и мутации, после чего алгоритм возвращается ко второму пункту,
– если условие выполнено, то процесс завершается, и фиксируется наилучшее найденное решение.
Более подробное описание процесса включает в себя детальное рассмотрение механизмов селекции, кроссинговера и мутации, используемых для формирования новой популяции; его положения приведены ниже.
а. Вначале определяется функция приспособленности (целевая функция), предназначенная для оценки качества особей в популяции. Эта функция сопоставляет каждой новой популяции (генотипу) определенное числовое значение, называемое «приспособленность». Это значение отражает степень эффективности фенотипа, описываемого данной популяцией.
б. Далее формируется начальная популяция, как правило, случайным образом. При этом для предотвращения преждевременного прекращения вычислений в ближайшем экстремуме необходимо соблюдать условие достаточной численности и разнообразия особей (членов генетического алгоритма). И даже если начальная популяция не обладает высокой конкурентоспособностью, генетический алгоритм способен преобразовать ее в более жизнеспособную. Следовательно, начальным особям достаточно просто соответствовать общему формату особей популяции, чтобы можно было рассчитать значение пригодности популяции (через функцию приспособленности).
в. Если текущее значение пригодности популяции не удовлетворяет заданным требованиям, то инициируется повторный процесс размножения (увеличения популяции) в рамках генетического алгоритма.
Процесс увеличения популяции предусматривает отбор нескольких особей в качестве «родителей» для производства потомства. Обычно число «родителей» – два.
Существуют различные стратегии выбора «родителей»:
– панмиксия – оба «родителя» выбираются случайным образом, при этом каждая особь популяции имеет равную вероятность быть отобранной.
– инбридинг – первый «родитель» выбирается случайным образом, а второй – на основе максимального сходства с первым.
– аутбридинг – первый «родитель» выбирается случайным образом, а второй – на основе максимальной различимости с первым.
Панмиксия, являясь простым и универсальным методом, способна обеспечить решения для широкого спектра задач. Однако ее эффективность снижается по мере увеличения численности популяции.
Альтернативный подход, основанный на селективном отборе «родителей», – селективный способ выбора особей родительской пары – предусматривает то, что в качестве таковых могут выступать лишь особи, чей показатель приспособленности не ниже среднего значения по популяции при равной вероятности кандидатов составить «родительскую» пару. Данный метод обеспечивает более быструю сходимость алгоритма. Но в то же время, из-за высокой скорости сходимости селективный отбор «родителей» не подходит для задач, требующих определения нескольких экстремумов, поскольку этот алгоритм, как правило, быстро сходится к одному из возможных решений. Кроме того, в некоторых случаях быстрая сходимость может привести к преждевременной конвергенции к локальному решению. Данный недостаток может быть частично компенсирован использованием соответствующего механизма отбора, замедляющего чрезмерно быструю сходимость алгоритма.
При инбридинге первый член пары выбирается случайным образом, а второй – из числа особей, максимально близких к первому. Такой подход способствует локализации поиска в ограниченных областях пространства решений, что может привести к образованию изолированных групп вокруг потенциальных оптимумов.
Аутбридинг, напротив, предполагает выбор пар на основе максимального генетического различия: «родители» выбираются из наиболее удаленных друг от друга особей. Цель аутбридинга – предотвратить преждевременную сходимость алгоритма к уже найденным решениям, побуждая его исследовать новые, неизученные области поиска.
г. Далее процесс увеличения популяции запускается непосредственно: размножение (скрещивание).
Для этого из текущего поколения отбираются отдельные решения (индивиды), к которым применяются генетические процедуры (операторы, обычно скрещивание и мутация). В результате этого процесса формируются новые поколения, представляющие собой модифицированные копии исходных решений.
Механизм размножения зависит от данных и специфики задачи и может варьироваться в различных алгоритмах, однако, ключевым требованием является передача потомкам характеристик «родителей».
Скрещивание, как правило, осуществляется между двумя наиболее приспособленными особями. В результате этого процесса образуются новые особи, наследующие генетическую информацию от своих «предков».
Основная цель скрещивания заключается в распространении благоприятных признаков (генов) по популяции и концентрации плотности решений в областях наибольшей эффективности.
При отборе особей для размножения в генетических алгоритмах обычно используется вся популяция, а не только выжившие на предыдущем этапе. Это связано с одним из основных недостатков таких алгоритмов – потерей генетического разнообразия, так как достаточно быстро выделяется один генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция состоит из копий этой особи, и популяция становится однородной.
Поэтому часто применяются методы отбора, которые позволяют размножаться не только самым приспособленным особям, но и менее успешным. В этом случае более важную роль в поддержании генетического разнообразия популяции играют мутации.
Суть мутаций заключается в случайной замене определенного количества элементов у особи другими случайными элементами.
Мутации можно рассматривать как диссипативный фактор, который, с одной стороны, позволяет популяции выходить из локальных оптимумов, а с другой – обогащает ее новой информацией.
К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов, являющаяся параметром (образцом) генетического алгоритма, и на этапе мутаций нужно выбрать определяемое число особей, а затем изменить их в соответствии с заранее определенными операциями мутации.
д. Формирование нового поколения (селекция).
В ходе формирования нового поколения происходит селекция (отбор) лучших решений для включения в следующее поколение.
После завершения этапа размножения, для каждой особи вычисляется значение функции приспособленности. На основе этого значения осуществляется отбор, то есть выделение определенной части популяции, которая будет участвовать в дальнейшем эволюционном процессе. При этом отдается предпочтение особям с наивысшей приспособленностью.
Для обеспечения генетического разнообразия популяции, целесообразно исключить клоны – особей с идентичным генотипом.
Существуют различные методы проведения селекции.
Классический (одноточечный) кроссинговер.
Традиционный генетический алгоритм использует одноточечный кроссинговер, в котором две скрещиваемые хромосомы рассекаются в одной точке, после чего фрагменты обмениваются местами.
Однако существуют и другие, более сложные алгоритмы, использующие различные типы кроссовера, которые могут включать несколько точек пересечения.
Унифицированный (однородный) кроссинговер.
Унифицированный кроссинговер существенно отличается от одноточечного кроссовера. В данном подходе каждый ген «потомка» формируется путем копирования соответствующего гена одного из «родителей», выбор которого осуществляется на основе случайным образом сгенерированной маски кроссовера. Копирование гена происходит в зависимости от заданных условий этой маски. Для формирования второго потомка процедура повторяется с заменой исходных родителей. При этом для каждой пары родителей генерируется новая случайная маска кроссовера.
Двухточечный кроссинговер.
В двухточечном кроссинговере (и многоточечном кроссинговере вообще) хромосомы расцениваются как циклы, которые формируются соединением участков линейной хромосомы. В контексте генетических алгоритмов с использованием кроссинговера, моделирование хромосом в виде циклов, образованных соединением концов линейных хромосом, позволяет рассматривать обмен участков хромосомы как выбор двух точек разреза для замены сегмента одного цикла на сегмент другого.
Одноточечный кроссинговер может быть интерпретирован как частный случай двухточечного, где одна точка разреза фиксирована.
Двухточечный кроссинговер обеспечивает более полное решение той же задачи. Циклическая структура хромосом допускает наличие большего количества стандартных блоков, способных к «циклическому возврату». Поэтому двухточечный кроссинговер считается более эффективным, чем одноточечный.
В то же время, увеличение числа точек кроссинговера может привести к снижению эффективности генетического алгоритма, поскольку стандартные блоки могут быть нарушены.
Преимущество многоточечного кроссинговера заключается в более детальном и полном исследовании пространства состояний.
Дифференциальное скрещивание.
Помимо кроссовера, в области генетических алгоритмов применяются и иные методы скрещивания. Так, для поиска экстремума (минимума или максимума) функции многих переменных, выраженных вещественными числами, эффективным методом является «дифференциальное скрещивание». Данный метод заключается в прибавлении к генотипу особи случайной генетической добавки малой величины, поэтому его модель демонстрирует высокую эффективность при непрерывности исходной функции и достигает еще более лучших результатов, если функция обладает свойством гладкости.
Инверсия.
Инверсия представляет собой метод кроссинговера, который заключается в изменении порядка расположения генов на хромосоме. Данный процесс реализуется посредством реверсирования последовательности генов между двумя произвольно выбранными точками на хромосоме. Целью инверсии является поиск более эффективной конфигурации генов с точки зрения эволюционного потенциала.
Переупорядочение.
Переупорядочение в генетических алгоритмах расширяет спектр поиска оптимальных решений, поскольку алгоритм не только ищет наилучшие значения генов, но также стремится определить их оптимальную последовательность. Однако это значительно усложняет задачу поиска, хотя повышает вероятность нахождения глобального оптимума.
е. В генетическом алгоритме предусмотрена итеративная процедура, которая реализуется в различных модификациях до достижения одного из условий завершения.
Условиями завершения алгоритма являются:
– нахождение глобального или локально-оптимального решения.
– стабилизация популяции, когда дальнейшие изменения несут незначительный характер.
– выполнение заданного количества поколений эволюции.
– истечение времени работы алгоритма.
– исчерпание допустимого числа вызовов целевой функции.
3. Заключительные положения.
Существует множество разновидностей генетических алгоритмов, таких как классический, простой генетический алгоритм, гибридный, CHC и другие. Они отличаются подходами к отбору и формированию нового поколения, используемыми процедурами, способами кодирования генов и т. д. В связи с этим, термин «генетические алгоритмы» обозначает не единую модель, а довольно широкий класс алгоритмов, порой существенно отличающихся друг от друга.
Генетические алгоритмы представляют собой мощный инструмент для решения широкого спектра задач в различных областях. К числу таких задач относятся:
– оптимизация функций: поиск наилучших значений параметров функции,
– оптимизация запросов в базах данных: повышение эффективности извлечения информации из баз данных,
– разнообразные задачи на графах: задачи коммивояжера, раскраска графов и поиск оптимальных сочетаний пар вершин и др.,
– настройка и обучение искусственной нейронной сети: оптимизация параметров нейросети для повышения ее точности и эффективности,
– задачи компоновки: определение оптимального размещения элементов в пространстве,
– составление расписаний: поиск оптимальных вариантов распределения ресурсов во времени,
– игровые стратегии: создание алгоритмов, обеспечивающих наилучшее поведение в играх,
– теория приближений: построение аппроксимаций функций и данных.
Основные недостатки генетических алгоритмов:
– эвристический характер отбора: критерии выбора хромосом и применяемые процедуры основаны на эвристических соображениях, что не гарантирует выявления глобального оптимума,
– непредсказуемость поведения: существует риск неконтролируемого развития процесса вычислений, что может привести к нежелательным результатам, хотя, в то же время, возможно и неожиданное получение высококачественного решения.
4. Для диалектики генетические алгоритмы представляют собой инструмент с гораздо более широким спектром применения, чем в науках, например, возможно исследование логических структур и операций, чему в науках не уделено никакого внимания, а на сайте в рамках Проекта ДИАЛЕКТИКА позже будут обсуждаться его положения.
Дискуссии и конференции. Методы