Метод проектирования градиента

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

Приведем один из вариантов метода проектирования градиента сначала для задачи с ограничениями-равенствами, а затем для общего случая. Метод применим, если целевая функция и все функции ограничений дифференцируемы.

Пусть ограничения заданы в виде

(8.55)

Найдем возможное направление l, на котором скорость изменения целевой функции максимальна:

(8.56)

В допустимой области D функции y_j постоянны. Поэтому искомое направление должно удовлетворять системе равенств

(8.57)

Из связи направления с координатами следует:

что перепишем в виде

(8.58)

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

Запишем функцию Лагранжа:

. (8.59)

Неизвестными в ней являются векторы и L. Взяв производные и приравняв их нулю, получаем

Отсюда выразим компоненты искомого вектора:

(8.60)

Подставив (8.60) в (8.58), находим:

С учетом этого выражения формула (8.60) принимает вид

(8.61)

Для определения неизвестных множителей l_j воспользуемся системой (8.57). Подставив в нее (8.61), получаем:

После раскрытия скобок окончательно имеем:

(8.62)

Так как направление ищется в конкретной точке, то все производные в (8.62) – известные константы. Поэтому система уравнений (8.62) является линейной системой относительно l_j. Ее решение не вызывает затруднений (при условии, что матрица системы не является особенной). Найдя значения l_j и подставив их в (8.61), получаем компоненты проекции градиента (в знаменателе (8.61) имеем длину проекции градиента). Движение осуществляется в направлении, противоположном проекции.

Аналогично градиентному методу новая точка вычисляется по формуле

. (8.63)

Алгоритм.

1. Задать начальную точку, удовлетворяющую системе (8.55), начальное значение h⁰ и точность по величине проекции градиента e.

2. В текущей точке вычислить градиенты всех функций (f и y_j) и решить систему (8.62).

3. Вычислить проекцию градиента по формуле (8.61).

4. Проверить: если завершить поиск.

5. Вычислить новую точку по формуле (8.63).

6. Проверить: если значение целевой функции улучшилось, перейти на шаг 2, иначе уменьшить h^k в два раза и перейти на шаг 5.▲

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

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

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

(8.64)

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

Теперь рассмотрим случай, когда ограничения заданы в виде неравенств j_j (x)£0. Поиск начинается из точки, в которой удовлетворяются все ограничения. Пока они выполняются как строгие, движение осуществляется по градиентному методу. Когда достигается граница допустимого множества, одно или несколько ограничений обращаются в равенства. Такие ограничения называют активными. В точках с активными ограничениями направление движения определяется по проекции градиента на поверхность этих ограничений, то есть применяется вышеприведенный алгоритм. Пример поиска минимума при двух линейных неравенствах показан на рис. 8.40. Очевидно, что при смешанных и нелинейных ограничениях алгоритм весьма существенно усложняется и требует большого объема вычислений. Поэтому метод проектирования градиентов целесообразно применять при линейных ограничениях.

45. Генетические алгоритмы

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

Идея генетических алгоритмов была высказана Д.Холландом в 60-е годы и затем развита им в фундаментальной работе "Адаптация в естественных и искусственных системах"(1975). Ипользовать их в численной оптимизации предложил Д.Гольдберг (1995). Но в основном генетические алгоритмы находят применение для обучения нейронных сетей. Поэтому здесь они будут рассмотрены только на уровне идей.

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

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

Основными параметрами конкретного алгоритма являются размер популяции и вероятности применения операторов. Первоначально по содержанию задачи формируется генотип и создается исходная популяция. Размер популяции N рекомендуется брать исходя из оценки числа возможных альтернатив r:

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

(8.54)

где f_i – значение критерия на i- й особи.

Для создания потомков используется оператор скрещивания, моделирующий процесс наследования за счет передачи части свойств от родителей к потомкам. Вероятность его применения рекомендуется брать не ниже 0,9. Он производит обмен подстроками родительских особей и, следовательно, от пары родителей образуется два потомка. Как это происходит, зависит от выбранной процедуры скрещивания. Например, при длине строки n из первых n- 1 равновероятных натуральных чисел разыгрывается одно число, которое принимается за точку разбиения. Затем подстроки родителей, находящиеся справа от точки разбиения, меняются местами.

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

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

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

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

Отличительной чертой генетических алгоритмов является одновременное использование набора точек в пространстве поиска вместо перехода от точки к точке в традиционных методах. Эта особенность позволяет применять такие алгоритмы для решения многоэкстремальных задач.

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

Пример 8.7. Найти целочисленный максимум функции f (x ₁, x ₂)=675- x ₁²- x ₂²+20 x ₁+10 x ₂ на области 5£ x ₁£36, 2£ x ₂£17.

Сначала сделаем преобразования: x ₁= y ₁+5, x ₂= y ₂+2, тогда 0£ y ₁£31, 0£ y ₂£15. В этом случае новые аргументы функции y ₁, y ₂ можно представить в двоичной системе, а за код принять строку из 9 бит. Первые 5 бит будут отражать y ₁, остальные – y ₂. Определим размер популяции: N =2log₂(16*32)=18. Ограничимся N =10. Используя датчик случайных чисел, создаем исходную популяцию и для всех ее особей вычисляем значение f и вероятность отбора p_i (табл. 8.1).

Таблица 8.1

№ строки	Экз. кода	y 1	y 2	x 1	x 2	f	pi
							0,1199
							0,0989
							0,0545
							0,1283
							0,1242
							0,1186
							0,0902
							0,0376
							0,1158
							0,1119

Действия оператора отбора, использующего распределение p_i, привели к выбору родительских пар (2,7), (5,10), (6,9), (1,4), (4,9). В каждой паре точки разбиения выбираются независимо с помощью датчика целых случайных чисел от 1 до 8 с равными вероятностями. Результаты работы оператора скрещивания приведены в табл. 8.2. Точки разбиения показаны косой чертой. Значения аргументов и функции даны для потомков.

 

 

Таблица 8.2

№ строки	Экз. кода родителей	Экз. кода потомков	y 1	y 2	x 1	x 2	f
	100/001101 101/010111
	0100010/11 1000100/10
	01110/1000 00110/1110
	01/1001010 00/1011010
	00101/1010 00110/1110

Теперь предположим, что оператор мутации сработал для 7 потомка, поменяв местами биты 1 и 2. Код этого потомка сменился с 011101110 на 101011010, значение функции стало 495. Расширенная популяция включает 10 исходных особей и 10 потомков. Сокращаем популяцию до принятого размера, отбрасывая особи с меньшими значениями функции. Полученная после этого популяция первого поколения представлена в табл. 8.3. В ней только первые 4 особи из исходной популяции.

Таблица 8.3

№ строки	Экз. кода	x 1	x 2	f

Из сравнения данных в таблицах 8.1 и 8.3 видно, что новая популяция лучше исходной. Если среднее значение целевой функции на начальной популяции было равно 585,3, то на новом поколении оно возросло до 725,6.

Следующий шаг заключается в проверке условия окончания поиска. Оно может быть представлено в разных вариантах: min f_i > f _min или max f_i -min f_i < e_f, или n ³ n _задан. В первом варианте все особи должны быть лучше заданного уровня качества, во втором критерием выступает близость особей, в третьем – число поколений (итераций). Если предположить, что выбранное условие выполняется на первом поколении, то поиск на этом заканчивается. За решение принимаем лучший результат: x ₁=11, x ₂=10, f =774. Оптимальному решению соответствуют значения: x ₁=10, x ₂=5, f =800. Сравнение показывает, что по значению критерия получено неплохое приближение к оптимуму. Понятно, что продолжение итераций приведет к дальнейшему улучшению популяции и получению более близкого к оптимальному решения.▲

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