Условия успешной работы генетических операторов

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

Как правило, перед применением генетического алгоритма решаемую задачу необходимо формализовать. Возможные состояния исследуемой системы должны быть описаны с помощью переменных, значения которых образуют в совокупности допустимое множество решений. Сравнение допустимых решений и выбор среди них наилучшего производятся на основании значений целевой функции. При ее задании следует учитывать необходимость прогнозирования результатов «искусственной эволюции», в ходе которой требуется получить объект с определенными свойствами. Постепенное улучшение значений функции приспособленности должно обеспечивать целенаправленное изменение популяции.

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

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

Возможно, формулировка условия задачи изначально содержит описание целевой функции. В этом случае необходимо учитывать, что используя двоичные коды (хромосомы) вместо исходных значений переменных, мы получаем новую целевую функцию (функцию приспособленности), являющуюся композицией декодирующего отображения и исходной целевой функции. Выбирая различные способы кодирования решений, можно произвольно изменять свойства этой композиции. В простейшем случае можно говорить об изменении последовательности записи аргументов функции нескольких переменных, что существенно для кроссинговера. Способ кодирования решений влияет на скорость и результат работы генетического алгоритма, если существует окрестность оптимального решения, в которой значения целевой функции оказываются близкими к максимальному. Попав в эту окрестность, алгоритм будет комбинировать фрагменты похожих на оптимальное решений и, внося в них небольшие изменения, быстро получит желаемый результат. Однако неудачный способ кодирования может нарушить эту «непрерывность», присвоив близким решениям сильно различающиеся коды, в результате чего поиск станет случайным. Следовательно, способ кодирования решений желательно выбирать, учитывая как особенности решаемой задачи, так и необходимость дальнейшего преобразования кодов при помощи генетических операторов.

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

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

Рассмотрим решение задачи, найденное генетическим алгоритмом. Пусть хромосома, соответствующая оптимальному решению, получена в результате применения оператора кроссинговера (для мутации рассуждение повторяется почти дословно). Каждый из родителей этой хромосомы содержит фрагмент оптимального решения. Таким образом, генетический алгоритм не сможет решить задачу, если для скрещивания не будут отобраны хромосомы, содержащие фрагменты оптимальной. При этом чем больше хромосом, обладающих таким свойством, будет отобрано для размножения, тем выше вероятность получения оптимального решения. Этот отбор выполняет оператор селекции, который способен учитывать только значения целевой функции. Следовательно, действительная цель, которая заключается в выборе хромосом, содержащих фрагменты оптимальной, должна совпадать с формальной (получением хромосом с высокими значениями целевой функции). Причем не только в момент получения оптимального решения, а на каждом шаге алгоритма. Поэтому хромосоме, содержащей фрагмент оптимального решения, должно соответствовать достаточное, с учетом критерия отбора, значение целевой функции независимо от оставшейся части (этот остаток может быть каким угодно, поскольку не используется в окончательном решении). При этом предпочтение следует отдавать тем хромосомам, которые имеют больше общих элементов с оптимальной. Фактически работа алгоритма заключается в замене отдельных частей слабо приспособленных хромосом фрагментами оптимального решения. Такие модификации должны сопровождаться увеличением целевой функции, иначе решение задачи может быть найдено лишь случайно, а не создано в ходе эволюции. Фрагмент хромосомы оказывается в некотором смысле самостоятельным объектом, влияя на оценку всего решения. Конечно, невозможно заранее выяснить, как выглядят фрагменты оптимального решения, поскольку это означало бы, что задача уже решена.

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

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