Применение генетических алгоритмов для решения оптимизационных задач

Размещено на http://www.allbest.ru/

Российский государственный гуманитарный университет

Применение генетических алгоритмов для решения оптимизационных задач

Л.О. Шашкин

Аннотация

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

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

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

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

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

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

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

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

Мутация - изменяется случайный двоичный символ или группа символов (ген) в некоторой хромосоме.

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

Репродукция - хромосома копируется без изменений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача поиска наибольшего значения функции. Приведем пример такой согласованности, когда генетический алгоритм может работать вполне успешно (проблему остановки алгоритма оставим в стороне). Рассмотрим решение задачи о поиске точки x₀, в которой достигается наибольшее значение непрерывной на отрезке [0, 1] функции F(x).

Пространством поиска будем считать множество всех двоичных рациональных чисел вида 0,a₁a₂a_n (количество используемых разрядов определяется допустимой погрешностью). Назовем хромосомами последовательности длины n, состоящие из нулей и единиц. Любой такой последовательности соответствует некоторое число на отрезке [0, 1], что значительно облегчает применение генетических операторов, поскольку в этом случае все вновь построенные (потенциальные) решения окажутся допустимыми. алгоритм генетический кроссинговер хромосома

Проанализируем условия эффективной работы каждого оператора в соответствии с его ролью в «эволюционном процессе». На начальном этапе действие кроссинговера и мутации оказывается сходным, поскольку начальная популяция состоит из хромосом, выбранных случайным образом. Мутация изменяет значение одного из разрядов двоичного числа x, «мутировавшее» значение переменной отличается от исходного на величину 2- ^k (где k - номер измененного разряда), что обеспечивает возможность поиска больших значений F(x) на всем отрезке. В результате применения кроссинговера числа 0,a₁a_ka_k+1a_n и 0,b₁b_kb_k+1b_n преобразуются в 0,a₁a_kb_k+1b_n и 0,b₁b_ka_k+1a_n. Различие между старым и новым поколениями в этом случае также можно оценить величиной 2- ^k, однако разница может быть меньше, если хромосомы a₁a₂a_n и b₁b₂b_n имеют совпадающие участки. В частности, начальные фрагменты хромосом, соответствующих близким по величине числам (близлежащим точкам), совпадают. Для таких хромосом мутация и кроссинговер существенно различаются по результатам.

Селекция хромосом приводит к изменению структуры популяции, так как на заключительном этапе появляется значительное количество решений, лежащих в окрестности точек максимума. В этих условиях остается неизменной роль оператора мутации, заключающаяся в выявлении новых направлений поиска. Однако при появлении перспективных решений данный оператор не способен действовать целенаправленно, уточняя случайно полученные результаты («шаг алгоритма» при мутации является случайной величиной, характеристики которой не изменяются при работе алгоритма). Появление значительного числа решений с относительно высоким значением целевой функции может означать, что алгоритм попал в окрестность искомой точки x₀. В этом случае максимальное количество новых решений появится именно в указанной окрестности, и поиск будет сосредоточен на перспективном участке. Подобная «самонастройка» алгоритма в рассматриваемом примере осуществляется благодаря оператору кроссинговера. У близких по величине чисел несколько первых разрядов совпадают, пара таких чисел имеет вид 0,a₁a_ma_m+1a_n и 0,a₁a_mb_m+1b_n, поэтому их потомки, порожденные при кроссинговере, не могут отличаться от родителей более чем на 2- ^m (в действительности не более 2- ^(m+1), в других случаях потомок совпадает с одним из родителей). Следовательно, при появлении нескольких близких к оптимальному решений действия кроссинговера сводятся к уточнению последних разрядов числа x₀ (либо к копированию существующих хромосом, что приведет к замедлению поиска на последних этапах). Худшие решения, лежащие вне исследуемого промежутка, «вымирают» как менее приспособленные, в результате вероятность применения оператора к подходящим парам хромосом повышается. Если же исследуемый максимум функции оказывается локальным, алгоритм способен выйти из него при помощи мутации (обнаружив большие значения функции на другом промежутке).

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

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

Преобразование множества ДСМ-гипотез. В качестве другого примера рассмотрим задачу оптимизации множества ДСМ-гипотез. ДСМ-системы порождают гипотезы, отображающие причинно-следственные связи между фрагментами структур объектов и их свойствами [Аншаков, 1999]. Анализ результатов работы ДСМ-метода иногда предполагает изучение множества гипотез, достигающего значительных размеров. Однако в рамках ДСМ отсутствует механизм, формально отсеивающий посторонние гипотезы.

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

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

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

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

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

Заключение

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

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

Список литературы

1. Аншаков О.М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез // НТИ. Сер. 2. 1999. № 1-2.

2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под. ред. В.М. Курейчика. - М.: ФИЗМАТЛИТ, 2006.

Размещено на Allbest.ru