ПОИСК Статьи Чертежи Таблицы Методы оптимизации из "Основы теории и проектирования САПР " Управляемые параметры в своей исходной трактовке являются величинами с различными физическими размерностями. В процессе поиска необходимо их сопоставление, определение расстояний между точками и другие операции, возможные только при условии нормирования управляемых параметров. Изменение способа нормирования приводит к деформации пространства управляемых параметров, к изменению траекторий поиска. [c.71] Таким образом, содержанием любого метода или алгоритма поисковой оптимизации должны быть способы выбора направления поиска gii величины шага /г формул для нормирования управляемых параметров критерия окончания поиска. Эффективность поиска зависит от того, как сделан этот выбор. Составляющими эффективности являются надежность, точность, экономичность. Надежность определяется как вероятность достижения заданной е-окрест-ности экстремальной точки при применении данного метода точность характеризуется гарантированным значением е экономичность отождествляется с потерями на поиск. Потери на поиск выражают трудоемкость процедуры оптимизации, которую в большинстве случаев оценивают количеством обращений к ММ объекта. [c.71] В ПМК оптимизации, используемых в САПР, методы и алгоритмы поиска обычно группируются в зависимости от постановки решаемого класса задач. Имеются группы методов безусловной, условной, дискретной оптимизации, центрирования и вписывания гиперфигур. [c.71] Рассматриваемые методы являются методами поиска локальных экстремумов. Это основные методы в САПР, так как методов глобальной оптимизации, обеспечивающих нахождение глобального экстремума с приемлемыми потерями на поиск, для задачи математического программирования общего вида (3.3) не существует. В САПР поиск глобального экстремума осуществляется путем локальной оптимизации из нескольких исходных точек, выбираемых случайным образом в пределах области, задаваемой прямыми ограничениями. В многоэкстремальных задачах возможно получение нескольких локальных экстремумов, из которых выбирается наилучший. Вероятность определения глобального экстремума при подобном подходе тем меньше, чем меньше объем области притяжения глобального экстремума. Малый объем этой области, как правило, свидетельствует и о низкой стабильности выходных параметров в точке экстремума, следовательно, глобальный экстремум может оказаться малополезным. Поэтому оптимизация на основе небольшого числа вариантов локального поиска является достаточной. [c.71] Решением (3.14) является оптимальная величина шага кь, минимизирующая Р (X) на луче, выходящем в направлении из точки Х/1-1. В способе задаваемого шага величина Ни является постоянной на всей траектории поиска или только на ее частях, выделяемых в зависимости от близости к искомому экстремуму. При выполнении условий попадания в заданную окрестность экстремальной точки X значение Л уменьшается, поскольку мелкие шаги позволяют точнее определить ее положение. [c.72] В качестве условия попадания в заданную окрестность оптимальной точки X принимается условие малости расстояния, на которое произошло продвижение в пространстве управляемых параметров в результате последних г шагов. Это расстояние является нормой разности векторов нормированных управляемых параметров и ik-T. [c.72] Стратегия поиска в методах нулевого порядка основывается на переборе ограниченного множества избранных направлений поиска или на случайном выборе. [c.72] Метод конфигураций включает выполнение циклов из п шагов покоординатного спуска. После каждого цикла делается один дополнительный шаг, определяемый с помощью одномерной оптимизации (3.14), вдоль направления и, —и п, где к=п,2п,Ъп,. .., т. е. по линии, проходящей через конечные точки двух смежных циклов шагов. На рис. 3.8 показан поиск по методу конфигураций точки Х[ и Хг получены из начальной Хо с помощью покоординатного спуска, точка Хд — результат дополнительного шага. [c.73] Метод Розенброка характеризуется тем, что в нем реализована идея поворота координатных осей после каждого цикла из п шагов покоординатного спуска таким образом, чтобы одна из осей новой системы координат оказалась параллельной линии, соединяющей точки 11а и и -п, т. е. заняла положение, близкое к параллельному по отношению к линии дна оврага. Тогда заметно повышается вероятность того, что следующий цикл шагов покоординатного спуска будет успешным. [c.73] На рис. 3.9 сплошной линией показана траектория поиска минимума квадратичной целевой функции методом наискорейшего спуска. Поиск по методу сопряженных градиентов (пунктирная линия) дает более быстрое определение экстремума квадратичной функции. [c.74] Заметим, что (3.18) применимо и к методу наискорейшего спуска, если Hft — единичная матрица. Если принять Н/г=Я , где Я — обратная матрица вторых частных производных F ) по X, называемая матрицей Гессе, то имеем метод Ньютона, относящийся к методам второго порядка. Методы второго порядка в САПР практически не применяются из-за трудностей расчета матрицы Гессе. Поэтому вместо Я используется ее приближение, рассчитываемое в методе переменной метрики без использования вторых производных F(X) по X. [c.74] На рис. 3.10 показаны функции Ф(л) и F x) для одномерного случая при наличии ограничения ф(х) 0. Точка условного минимума л функции F x) в методе штрафных функций становится точкой безусловного минимума функции Ф(д ), чем и обеспечивается правильность получаемых результатов. [c.75] Идеи метода проекции градиента находят применение также для решения задач математического программирования с ограничениями типа неравенств и для поиска максимина. В этих задачах гиперповерхность 1 (Х), на которую проектируется градиент, заранее не определена и выявляется в процессе поиска. В задаче с ограничениями типа неравенств гиперповерхность определяется системой уравнений ф1(Х)=0, ге/, где /—множество индексов нарушенных ограничений. При поиске максимина в систему уравнений, задающую гиперповерхность И7(Х), включаются уравнения вида (X)—5 (Х)=0, где (X) —запас работоспособности некоторого выходного параметра, причем включение осуществляется на й-м шаге поиска, если окажется 5 (Хй) 5 Хй 1), 5 (Х) —целевая функция. [c.76] Методы дискретной оптимизации. Задача дискретного математического программирования — это задача (3.3), но с дополнительным условием дискретности пространства управляемых параметров, т. е. ХеО, где О — счетное множество точек. В ряде случаев лишь часть управляемых параметров дискретна. Тогда задача оптимизации является задачей частично дискретного программирования. Обычно для параметров вводятся двусторонние прямые ограничения (3.10), тогда О — конечное множество и задача дискретного программирования становится комбинаторной. [c.76] Дискретная оптимизация сложнее непрерывной. Комбинаторная задача общего вида относится к N9 полным, и сложность ее точного решения является экспоненциальной. Эффективные точные методы дискретной оптимизации существуют лишь для отдельных классов задач, поэтому для задач целочисленного линейного программирования и нелинейного дискретного программирования в САПР применяются приближенные методы локальной оптимизации и ветвей и границ. [c.76] Метод локальной оптимизации характеризуется тем, что один его шаг заключается в исследовании е-окрестности текущей точки поиска X при значении е, обеспечивающем нахождение в этой окрестносги по крайней мере еще одной точки. Если Г(Х ) / (Ху), где X/ — любая точка в исследуемой е-окрестности, то Хй принимается в качестве точки локального экстремума. Если же найдется точка с лучшим значением целевой функции, то она становится новой текущей точкой поиска и происходит переход к следующему шагу. Д.тя реализации метода локальной оптимизации нужно установить способы выбора начальной точки поиска, величины е, правила возможного изменения е в процессе поиска и т. п. При больших е увеличивается трудоемкость поиска, при малых е — снижается надежность определения глобального экстремума. [c.76] Идеи метода ветвей и границ находят применение во многих алгоритмах решения комбинаторных задач в процессе автоматизированного проектирования. [c.77] Вернуться к основной статье