МЕТОДЫ ЭВОЛЮЦИОННОГО ПРОГРАММИРОВАНИЯ В КОМБИНАТОРНЫХ И ЭКОНОМИЧЕСКИХ ЗАДАЧАХ
И.В. Злобина, А.В. Розанов
имени ,
г.
Эволюция – это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию часть этого потомства сохранит высокую приспособленность родителей, обладая и некоторыми новыми свойствами. Если новые свойства окажутся полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособляемости биологического вида в целом. Зная, как решается задача оптимизации видов в природе, можно применить аналогичный метод для решения различных практически важных задач.
В задачах оптимизации можно управлять некоторыми параметрами х1, х2,…, хn, а целью является максимизация (или минимизация) некоторой функции f (х1, х2,…, хn), называемой целевой функцией, и зависящей от этих параметров. Например, если требуется максимизировать целевую функцию «доход компании», то управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т.д. В случае если целевая функция достаточно гладкая и имеет только один локальный максимум (унимодальная функция), то оптимальное решение можно получить методом градиентного спуска. Недостатком градиентных методов являются слишком высокие требования к функции – на практике унимодальность встречается крайне редко, а для негладкой функции градиентный метод часто приводит к неоптимальному ответу. Во многих важных задачах параметры могут принимать лишь некоторые определенные значения, причем во всех остальных точках целевая функция не определена. Здесь требуются принципиально другие подходы.
Классический пример, известный как «задача коммивояжера», формулируется так: коммивояжеру (агенту по сбыту) необходимо объехать несколько городов, побывав в каждом один раз, и вернуться в исходную точку. Нужно найти кратчайший маршрут. Самый простой способ найти оптимальное решение – перебрать все возможные значения параметров. При этом не нужно делать никаких предположений о свойствах целевой функции, задав ее просто с помощью таблицы. Однако чтобы решить таким способом задачу коммивояжера, например, для 20 городов, потребуется перебрать около 1019 маршрутов, что весьма затруднительно даже для современного суперкомпьютера.
Определим понятия, принятые в эволюционном программировании [1]. Хромосома – это некоторый числовой вектор, соответствующий подбираемому параметру, а набор хромосом данной особи определяет решение задачи. Каждая из позиций вектора хромосомы называется геном. Мутацией принято называть преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций – случайное изменение только одного из генов хромосомы. Скрещивание (кроссинговер или кроссовер) – это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии. Хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы f1(1, 1, 1, 1, 1) и f2(2, 2, 2, 2, 2) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки f12(1, 1, 1, 2, 2) и f21 (2, 2, 2, 1, 1).
Прежде всего, генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем необходимо смоделировать размножение внутри популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора – чем лучше приспособлен индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Далее моделируются мутации – в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Старая популяция частично или полностью удаляется, и происходит переход к рассмотрению следующего поколения. Популяция нового поколения обычно содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Описанные выше процессы отбора, скрещивания и мутации повторяются теперь для этой новой популяции и т.д.
Рассмотрим особенности применения генетических алгоритмов на примере задачи коммивояжера для 20 городов [2]. В качестве индивидуумов будем рассматривать маршруты обхода. Информацию о маршруте можно записать в виде одной хромосомы – вектора длины 20, где в первой позиции стоит номер первого города на пути следования, затем – номер второго города и т.д. Мутацию определим как перестановку значений двух случайно выбранных генов. При таком преобразовании путь следования меняется только в двух городах. По условию задачи в рассматриваемых хромосомах каждый ген (номер города) должен встречаться только один раз. Такая разновидность хромосом называется «перечислимые хромосомы с уникальными генами» и часто используется в комбинаторных задачах [1, 2].
На рисунке изображен результат работы генетического алгоритма в задаче коммивояжера (использована демонстрационная программа к пакету Gene-Hunter). Найденный маршрут, вероятно, не является самым оптимальным, но близок к нему по длине — как правило, генетические алгоритмы «ошибаются» не более чем на 5–10 %. Этот недостаток компенсируется для комбинаторных задач относительно высокой скоростью работы – в нашем примере ответ был получен за 25 секунд.
Генетические алгоритмы используются не только в задачах комбинаторного типа, но и в тех случаях, когда искомые параметры могут быть любыми действительными числами, например, в задачах оптимального распределения инвестиций. Пусть имеется некоторый капитал V0, который нужно распределить между несколькими проектами с целью получения максимального дохода через определенный срок. Для каждого проекта задана функция дохода, приносимого проектом за этот срок, в зависимости от вложенной суммы. В данной задаче целевой функцией является суммарная прибыль от инвестиций, а управляемыми параметрами – объемы вложений в каждый из проектов. Подобные модели являются стандартными для экономистов, но в них рассматриваются только линейные функции доходности, когда точное решение можно получить с помощью линейного программирования (симплекс-метод). Однако в реальных задачах не все функции являются линейными, а некоторые могут быть даже разрывными. При этом целевая функция имеет сложный вид и не является унимодальной. В такой нелинейной ситуации стандартные методики работают плохо – в частности, симплекс-метод неприменим принципиально, а градиентный метод чаще всего приводит к неоптимальному решению.
Рассмотрим, каким образом решается эта задача для 10 проектов с помощью генетического алгоритма [3]. Пусть каждый индивидуум имеет 10 хромосом, где k-я хромосома – это вектор из нулей и единиц, содержащий двоичную запись объема вложений в k-й проект. Если длина хромосомы равна 8 двоичным разрядам, то понадобится предварительная нормировка всех чисел в диапазон от 0 до 255. Такие хромосомы называются непрерывными и позволяют представлять значения произвольных числовых параметров. Мутации непрерывных хромосом случайным образом изменяют один бит (ген) в них, влияя, таким образом, на значение параметра. Кроссинговер также можно осуществлять стандартным образом, объединяя части соответствующих хромосом (с одинаковыми номерами) различных индивидуумов. Особенностью этой задачи является то, что суммарный инвестируемый капитал фиксирован и равен некоторому числу V0. Очевидно, при мутациях и скрещивании могут получаться решения, для реализации которых требуется капитал больше или меньше V0. В генетическом алгоритме используется специальный механизм работы с такими решениями, позволяющий учитывать ограничения типа «суммарный капитал = V0 » при подсчете приспособленности индивидуума. В процессе эволюции особи с сильным нарушением указанных ограничений быстро вымирают. В результате работы алгоритма получается решение с суммарным капиталом, близким к заданному V0. Как и в случае с задачей коммивояжера, эту погрешность следует считать платой за скорость поиска решения. Отметим, что полный перебор всех вариантов инвестирования в 10 проектов (для функций доходности, заданных на 256 точках) включает в себя более 1020 решений, и с большим трудом реализуем на практике.
СПИСОК ЛИТЕРАТУРЫ
1.
Holland, J. H. Adaptation in Natural and Artificial Systems / J. H. Holland. –The University of Michigan, 1975.
2.
Струйков, Т. Что такое генетические алгоритмы / Т. Струйков. –PC Week/RE. – № 19. – 1999.
3.
Масалович, А. И. Прогноз дает… компьютер / А. И. Масалович// Софтмаркет. – № 23. – 1996.
Похожие статьи: