Применение генетических алгоритмов

Чтобы использовать генетический алгоритм для решения практических задач, необходимо рассматривать более сложные варианты введенных выше понятий. Поясним это на примере задачи коммивояжера для 20 городов.
В качестве индивидуумов будем рассматривать маршруты обхода. Информацию о маршруте можно записать в виде одной хромосомы — вектора длины 20, где в первой позиции стоит номер первого города на пути следования, затем — номер второго города и т. д. Первое затруднение возникает, когда мы пытаемся определить мутации для таких хромосом — стандартная операция, изменяющая только одну позицию вектора, недопустима, так как приводит к некорректному маршруту. Но можно определить мутацию как перестановку значений двух случайно выбранных генов. При таком преобразовании путь следования меняется только в двух городах.
По условию задачи в рассматриваемых хромосомах каждый ген (номер города) должен встречаться только один раз. Такая разновидность хромосом называется “перечислимые хромосомы с уникальными генами” и часто используется в комбинаторных задачах. Стандартная операция скрещивания для этого типа хромосом опять же некорректна, поэтому здесь используется более сложная схема двухточечного скрещивания. За недостатком места мы не излагаем эту схему и рекомендуем заинтересованному читателю обратиться к специальной литературе.
На рис. 3 изображен результат работы генетического алгоритма в задаче коммивояжера (мы использовали демонстрационную программу к пакету GeneHunter). Указанные на рисунке значения параметров достаточно типичны — как и в природе, мутации происходят гораздо реже, чем скрещивания. В правом нижнем окне можно наблюдать, как изменялась длина кратчайшего в популяции маршрута в процессе эволюции. Эта длина монотонно убывает до некоторого момента, а затем стабилизируется. Найденный маршрут, вероятно, не является самым оптимальным, но близок к нему по длине — как правило, генетические алгоритмы “ошибаются” не более чем на 5—10%. Этот недостаток компенсируется для комбинаторных задач относительно высокой скоростью работы — в нашем примере ответ был получен за 25 секунд. На практике генетические алгоритмы нередко используют совместно с другими методами, которые позволяют повысить их точность.
Генетические алгоритмы используются не только в задачах комбинаторного типа (как TSP), но и в тех случаях, когда подбираемые параметры могут быть любыми действительными числами. Такова, например, задача оптимального распределения инвестиций; один из вариантов ее мы кратко опишем.
Пусть имеется некоторый капитал R, который нужно распределить между несколькими проектами с целью получения максимального дохода через определенный срок. Для каждого проекта задана функция дохода, приносимого проектом за этот срок, в зависимости от вложенной суммы. Используется также диверсификация, т. е. запрещено вкладывать в любой проект слишком большую сумму. В данной задаче целевой функцией является суммарная прибыль от инвестиций, а управляемыми параметрами — объемы вложений в каждый из проектов.
Подобные модели являются стандартными для экономистов, но в них рассматриваются только линейные функции доходности. В этом случае точное решение можно получить с помощью линейного программирования (симплекс-метод). Однако в реальных задачах нет оснований считать все функции линейными — более того, они могут быть даже разрывными. При этом целевая функция имеет сложный вид и не является унимодальной. В такой нелинейной ситуации стандартные методики работают плохо — в частности, симплекс-метод неприменим принципиально, а градиентный метод чаще всего приводит к неоптимальному решению.
Рассмотрим, каким образом решается эта задача для 10 проектов с помощью генетического алгоритма. Пусть каждый индивидуум имеет 10 хромосом, где k-я хромосома — это вектор из нулей и единиц, содержащий двоичную запись объема вложений в k-й проект. Если длина хромосомы равна 8 двоичным разрядам, то понадобится предварительная нормировка всех чисел в диапазон от 0 до 255. Такие хромосомы называются непрерывными и позволяют представлять значения произвольных числовых параметров. Мутации непрерывных хромосом случайным образом изменяют один бит (ген) в них, влияя таким образом на значение параметра. Кроссинговер также можно осуществлять стандартным образом, объединяя части соответствующих хромосом (с одинаковыми номерами) различных индивидуумов. Особенностью этой задачи является то, что суммарный инвестируемый капитал фиксирован и равен некоторому числу R. Очевидно, при мутациях и скрещивании могут получаться решения, для реализации которых требуется капитал больше или меньше R. В генетическом алгоритме используется специальный механизм работы с такими решениями, позволяющий учитывать ограничения типа “суммарный капитал = R” при подсчете приспособленности индивидуума. В процессе эволюции особи с сильным нарушением указанных ограничений вымирают. В результате работы алгоритма получается решение с суммарным капиталом, быть может, не равным в точности, но близким к заданному R. Как и в случае с задачей коммивояжера, эту погрешность следует считать платой за скорость поиска решения. Отметим, что полный перебор всех вариантов инвестирования в 10 проектов (для функций доходности, заданных на 256 точках) включает в себя более 1020 решений и нереализуем на практике.