Методы пассивного поиска

Метод сканирования (упорядоченного перебора). В соответствии с этим методом осуществляется последовательный просмотр всех узлов m-мерной решетки в заданной обла-сти изменения параметров оптимизации, которая определяется условиями:

Х_{i min} < = Х _i < = Х_{i max,} . (4.10)

где i= 1,..., m

При этом диапазоны изменения внутренних параметров (4.10) разбиваются на неко-торое устанавливаемое исследователем количество отрезков N_j чаще всего с равномерным шагом h_xi.

(4.11)

Пример построения решетки в пространстве двух параметров показанных на рис. 4.11.

Рис. 4.11. Пример построения решетке пространстве двух параметров по методу канирования

Во всех узлах решетки кроме тех, в которых не выполняются ограничения, опреде-ляются значения функции цепи и путем сравнения выбирается узел с лучшим значением целевой функции F(х). Алгоритм, реализующий метод сканирования, может быть построен как совокупность вложенных друг в друга циклов, общим для которых является участок по расчету и проверке ограничений и функции цепи. Количество таких циклов равно числу параметров оптимизации m.

Количество обращений к модели N_р

(4.12)

где N_j - количество отрезков.

При N_j = 100 для m = 2 получим N_р = 100 ∙ 100 = 10⁴

Окончание поиска - просмотр всех N_р точек и выбор наибольшего значения функции цели F(х).

Метод статических испытаний (метод случайного перебора или методМонте-Карло) в практической постановке сводится к многократному «разыгрыванию» случайных значений X_i и определению для каждого случайного их набора соответствующих значений F(х). По завершению требуемого числа испытаний производится статическая обработка случайных значений F(х), позволяющая определить математическое описание М(F_х), вероятностные границы разброса F(х)_min ÷ F(х)_mах и прочее.

Число входных параметров и выходных показателей не ограничивается и связано практически лишь с небольшими дополнительными затратами на выработку случайных значений x_i и обработку результатов.

Минимальное число испытаний N_тр, необходимы для построения требуемых распре-делений с заданной точностью Δ и вероятностью Р_в ее обеспечения приведено на рис. 4.12.

Рис. 4.12. График определения минимального числа испытаний

В практических расчетах речь идет обычно о выполнении (3... 5)∙10³ вариантов ра-счета.

Нахождение количества случайных чисел просмотра при оптимизации по методу Монте-Карло можно определить по формуле:

(4.13)

где Δ - точность приближения к точке условного экстремума.

(4.14)

Пример. Определить число обращений к математической модели при оптимизации

по двум параметра (m = 2), если известно, что X₁ изменяется в пределах от 1 до 6, а Х₂ - от 1 до 3 с одинаковым шагом, равным 0,1, для вероятностей Р_в = 0,95 и Р_в = 0,99. Рассчитаем точность приближения к точке условного экстремума (А).

Для реализации метода необходим датчик случайных чисел (ДСЧ). Эти значения могут быть получены на ЭВМ с помощью специальных программных функций RND или полностью RANDJMIZE (рандомайз).

Условием окончания поиска является просмотр требуемого числа изображающих

точек N_р.

4.2.3. Сопоставление эффективности алгоритмов коньковой оптимизации

Поскольку поисковые методы предполагают пошаговое, итеративное решение задачи, то объем вычислений характеризует затраты времени на поиск. Из логической схемы алгоритма поиска, основной объем вычислений составляют расчеты значений ограничений к функции цели, проводимые с помощью математической модели объекта проектирования. Они и определяют основные затраты времени на поиск, поэтому затраты эти принять как универсальная характеристика рассматриваемых методов оптимизации. В табл. 4.1 приве-дены результаты сопоставления методов поиска.

Если при m= 3 еще методы пассивного поиска работают, то уже при m =5 методами пассивного поиска не удается получить решение на ЭВМ за приемлемое время, в то же время метод градиента имеет всего обращений к модели порядка 81.

Необходимо еще отметить, что метод случайных направлений (случайного градиента) практически не зависит от размерности области поиска и момент оказаться более эффектив-ным, чем градиентный метод в случае роста числа параметров m. Меньшей эффективностью из методов направления поиска обладает метод Гаусса-Зейделя, однако уже при m > 3 этот метод позволяет получать решение за приемлемое время при дискретно изменяющихся параметрах. Таким образом, различные методы поиска имеют определенные сферы действия в решении задач оптимизации решений.

Поиск по сайту: