Классический генетический алгоритм, также называемый элементарным или простым, включает 7 этапов [1, 2]:
• инициализация или генерация стартовой популяции;
• расчет показателей приспособленности хромосом в рамках текущей популяции;
• проверка условия остановки алгоритма;
• селекция хромосом;
• применение генетических операторов;
• формирование новой популяции;
• выбор «лучшей» хромосомы.
Стартовая популяция в классическом генетическом алгоритме формируется случайным образом. Элементами популяции могут быть гены или хромосомы. Мощность популяции заранее известна и не изменяется в процессе работы алгоритма. Каждая особь представляет собой случайную L-битную строку, где L – это длина кодировки, которая одинакова для всех особей.
Расчет показателей приспособленности заключается в нахождение оценки для каждой особи текущей популяции. Оценка равна значение функции приспособленности для рассматриваемого элемента. При помощи данного показателя выделяют наиболее приспособленные особи, характеризующие наиболее подходящие в рамках задачи решения, которые с большей вероятностью будут участвовать в скрещивании и давать потомство.
Критерий завершения алгоритма формируется на основе условий решаемой задачи. На практике чаще всего используют ограничение на число итераций алгоритма, то есть ограничивают количество возможных популяций, или критерий, сигнализирующий, что алгоритм сошелся к решению и его показатели не улучшаются. В случае если известно максимальное (или минимальное) значение функции приспособленности, остановка алгоритма может произойти после достижения ожидаемого оптимального значения, это так называемый поиск решения с заданной точностью. При достижении условия остановки алгоритма происходит переход к шагу 7, иначе – к шагу 3.
Оператор селекции является одним из наиболее важных операторов, помогающих поддерживать генетическое разнообразие популяции, которое отвечает за характер поведения популяции: широкий разброс точек в пространстве поиска, сбор точек вокруг некоторой точки и т.д. В простейшем случае оператором селекции выступает метод рулетки.
В качестве генетических операторов выступают операторы скрещивания и мутации. Результатом применения этих операторов является создание популяции потомков. Вероятность применения оператора скрещивания значительно выше, чем применение оператора мутации [3, 4].
Формирование новой популяции производится на основе двух пулов: родителей и потомков. Существует несколько схем отбора особей в новую популяцию. Рассмотрим основные из данных схем.
Стратегия элитарности
Идея метода заключается в формировании новой популяции только из лучших представителей группы родительских и дочерних особей. Преимуществом стратегии элитарности является исключение «случайных скачков в пространстве поиска», так как происходит переход: лучшая особь гарантировано переходит в следующее поколение.
Отбор с вытеснением
Метод построен на принципе, носящем бикритериальный характер – попадание особи в новую популяцию зависит не только от величины ее приспособленности, но и от наличия в уже сформированной популяции следующего поколения особи с таким же набором хромосом. В конечном итоге в новую популяцию попадает особь, оценка которой выше. Метод позволяет сохранять лучшие варианты решений, обладающие разными хромосомными наборами, а также в популяции поддерживается генетическое разнообразие.
Только потомки
Особи в новую популяцию выбираются случайным образом только из пула потомков.
Случайным образом
Особи в новую популяцию выбираются случайным образом из пулов потомков и родителей.
В рамках алгоритма возможно сочетание нескольких схем формирования новой популяции.
Выбор наилучшей особи заключается в поиске представителя популяции с наивысшим значением приспособленности. Найденная особь является решением поставленной задачи.
Преимущества и недостатки использования генетических алгоритмов
Среди преимуществ использования генетических алгоритмов для решения задач можно выделить следующие:
• для работы не требуется информации о поведении функции;
• обладают относительной стойкостью к попаданию в локальные оптимумы;
• пригодны для решения широкого класса разнообразных задач;
• достаточно просты в реализации;
• возможно применение для решения задач с изменяющейся средой;
• при формировании пространства поиска используются совместно вероятностные и детерминированные подходы;
• способность к самоорганизации;
• способность решения задач, для которых отсутствует опыт решения.
Наряду с достоинствами существует и ряд недостатков практического использования:
• решение не всегда сводится к глобальному оптимуму;
• неэффективно применять для оптимизации сложных функций с большим временем вычисления;
• сложно применять для изолированных функций, так как они не дают никакой информации относительно области максимума;
• сложность в подборе оценочной функции;
• требуют большой вычислительной мощности.
Отдельно стоит отметить, что результаты работы генетического алгоритма напрямую взаимосвязаны от выставленных параметров. Основные параметры это:
• размер популяции;
• разновидность оператора скрещивания;
• метод селекции;
• вероятности мутации и кроссинговера.
Параметры алгоритма главным образом сказываются на исследовании пространства поиска и вариантах использования найденных решений. Первый аспект отражает эффективность поиска решения и характеризует способность алгоритма избегать локальных оптимумов. Второй отвечает за постепенное улучшение уже найденных решений в следующих поколениях. Основная задача настройки алгоритма заключается в поиске баланса между выделенными аспектами, так как пренебрежение исследовательскими способностями метода может повлечь к увеличению времени работы и ухудшения результатов (преждевременной сходимости), а игнорирование найденных «хороших» решений превратит работу в случайный поиск.
Некорректная настройка параметров алгоритма может стать причиной множества проблем в работе алгоритма. Ниже приведен список основных проблем и возможные пути их решения.
Проблема 1 – низкая приспособленность особей. Решение: увеличение числа поколений поиска; увеличение численности популяции; изменение оценочной функции; использование другого метода селекции; выбор другого оператора скрещивания и способа формирования нового поколения.
Проблема 2 – преждевременная сходимость. Решение: изменение метода селекции; удаление повторяющихся особей; увеличение вероятности мутации.
Проблема 3 – резкие скачки приспособленности особей между поколениями. Решение: введение элитарной стратегии при формировании новой популяции; уменьшение вероятности мутации; использование кроссинговера со слабой разрушающей способностью.
Проблема 4 – преобладание удовлетворительных результатов над хорошими. Решение: выбор другого метода селекции; замена оператора скрещивания и/или метода мутации; распараллеливание процедуры поиска.
Библиографический список
- Нейронные сети и генетический алгоритма – введение в теорию [Электронный ресурс] // URL: http://www.neuroproject.ru/articles.php. Дата просмотра 25.11.2022.
- Непрерывные генетические алгоритмы — математический аппарат [Электронный ресурс] // URL: https://basegroup.ru/community/articles/real-coded-ga. Дата просмотра 25.11.2022.
- Операторы генетического алгоритма [Электронный ресурс] // URL: http://lazysmart.ru/iskusstvenny-j-intellekst/geneticheskie-operatory/. Дата просмотра 25.11.2022.
- Основы генетических алгоритмов [Электронный ресурс] // URL: https://www.intuit.ru/studies/courses/14227/1284/lecture/24168?page=12#sect23. Дата просмотра 25.11.2022.
Количество просмотров публикации: Please wait