В рамках задачи многомерной оптимизации первоначальный интервал поиска точки экстремума представляет собой множество положительных действительных чисел (интервал вида (0, ¥ )). Поэтому первый этап обычно организуется как процесс шагового движения из точки 0 с постоянным шагом h , сопровождающийся расчетом значения ЦФ в конце каждого шага. В процессе такой процедуры производится сравнение значений ЦФ и выделяется интервал, на котором нарушается процесс убывания (возрастания) ЦФ. В результате этого определяется интервал [a ; b] шириной h, содержащий точку экстремума ЦФ.
Далее производится уточнение положения точки оптимума. Для этой цели используются ряд методов, обычно и называемых методами одномерной оптимизации или методами оптимизации функции одной переменной. Эти методы подробно освещены в многочисленной литературе [4,15,17,18,20,22,26,35,40,44]. (С этими методами рекомендуется ознакомиться самостоятельно).
Далее будут рассматриваться только методы оптимизации функций многих переменных.
4.2.3.2. Общие особенности численных методов оптимизации функций многих переменных
Необходимость использования численных методов вызвана тем, что аналитическая зависимость между функцией критерия и переменными оптимизации часто бывает либо неизвестна, либо сложна [33]. В частности, характерной ситуацией для САПР является наличие алгоритмических математических моделей, описывающих ЦФ [ ].
Основная идея численных методов состоит в построении последовательности точек в n-мерном пространстве, обладающей той особенностью, что значения ЦФ, подсчитанные для последовательности таких точек, оказываются все ближе и ближе к точке оптимума.
Такие методы имеют много названий. Наиболее употребительными из них являются следующие:
- шаговые методы (шаговые методы поиска, многошаговые методы);
- итерационные (итеративные) методы;
- методы поисковой оптимизации [21,33,40].
Рассматриваемые методы называются также релаксационными [14], рекуррентными [ ], методами последовательного улучшения исходного (начального) решения.
Использование первого названия вызвано тем, что переход от одной к другой точек последовательности осуществляется последовательными шагами, ведущими из исходной (начальной) точки X0 через изображающие точки Xk в заданную окрестность точки экстремума Xопт.
Второе название методов связано с тем, что вычисление точек последовательности осуществляется в процессе итераций - многократного выполнения последовательности одних и тех же действий. При этом каждая итерация выполняется по одному и тому же алгоритму на базе результатов, полученных на предыдущей итерации. В таких методах точка оптимума достигается за бесконечное число шагов. (При этом приходится рассматривать такую характеристику методов, как их сходимость).
З а м е ч а н и е 4.8. Точные методы, позволяющие отыскивать решение за конечное число шагов, разработаны в настоящее время только для минимизации квадратичных функций.
Третье название методов вызвано тем, что движение к экстремальной точке может трактоваться как ее поиск
Приведем математические соотношения, лежащие в основе рассматриваемых методов.
Шаговые или итерационные методы сводят задачу минимизации заданной функции z(X) к построению последовательности точек n-мерного пространства X1,X2, …, Xk, Xk+1 … такой, что на каждом следующем члене последовательности значение функции убывает
z(Xk+1) < z(Xk), k = 0,1,2, … (4.10)
где k – номер итерации (шага).
Условие (4.10) называют условием монотонности [ 4 ]. Значения ЦФ, удовлетворяющие соотношению (4.10), образуют убывающую последовательность {z k}. (Поэтому соотношение (4.10) было бы точнее называть условием монотонности убывания ЦФ).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.