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

Пример 2.

Пример 1.

Преподаватель В.Ф. Катаев

Итого 90 минут

Дата

Подпись

Порядок выполнения работы

1. Внимательно изучить общие теоретические сведения (10 минут).

2. Прорешать на доске под руководством преподавателя 4 задания. (25 минут).

3. Самостоятельно, на основе алгоритма решения по п.2 выполнить задания1,4,5,6 в соответствии с вариантом. (40 минут).

Вариант выбирается в соответствии с номером в журнале.

4. Оформить решения в соответствии с примером и сдать преподавателю. (10 минут).

Пример оформления самостоятельного задания

Студент: Ф.И.О., гр.ЭЭ-14-З1, Вариант 1

Определить эквивалентное сопротивление R_Э (рисунки 7,8,9) относительно указанных зажимов, если сопротивления равны 10 Ом.

Задание 1.

Дано: Исходная схема

R₇ = 0;

R₁,R₂,R₃,R₄,R₅,R₆ = 10 Oм.

R_Эab =?

Решение:

1. Промежуточные схемы пошагово.

2. Расчет по действиям с комментариями.

Ответ: R_Эab =

Задание 2…………………………………………………………………………

Задание 3…………………………………………………………………………

Подведение итогов (5 минут)

Рассмотрим выпуклую квадратичную функцию . Легко видеть, что эта функция достигает в точке (0,0) минимума, равного нулю. Но это же значение функция принимает во всех точках вида - см. рис. 5.

Рис. 5. К прим. 1.

Критерий оптимальности (), имеющий в области определения несколько локальных минимумов, называется многоэкстремальным критерим оптимальности или мультимодальным критерием оптимальности (см. прим. 2).

Если размерность вектора варьируемых параметров больше единицы ( >1), то критерий оптимальности () может быть в своей области допустимых значений "овражным" критерием оптимальности. Критерий оптимальности называется овражным в своей области допустимых значений, если в этой области имеют место слабые изменения частных производных функции () по одним направлениям и значительные изменения этих производных по другим направлениям.

Рассмотрим функцию Розенброка (, )=100( - )²+(1- )² ( =2). Легко видеть, что минимум этой функции достигается в точке (0,0) и равен нулю. Линии уровня функции приведены на рис. 6.

ис. 6. Линии уровня функции Розенброка. Функция медленно изменяется вдоль дна V-образного оврага и быстро – перпендикулярно этому дну.

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

Критерий оптимальности () называется позиномиальным критерием оптимальности, если функция () есть позином, т.е. если

где и все компоненты вектора – положительные действительные числа, а функции () имеют вид

- любые действительные числа.

3. Одномерная задача оптимизации

Рассмотрим задачу поиска минимума одномерной функции (), определенной на интервале :

Как известно из курса математического анализа, внутренние точки локального и глобального минимума функции () являются стационарными точками критерия оптимальности () (см. рис. 1) или, что то же самое, решениями уравнения

(1)

Рис. 1. Локальные минимумы(x ₁^*, x ₃^*), локальный максимум (x ₂^*) и точка перегиба (x_c ^*) функции Φ(x).

Но, решениями уравнения (1) являются не только точки минимума, но и точки максимума и точки перегиба функции () (см. рис. 1). Следовательно, уравнение (1) является только необходимым условием минимума, но не является достаточным условием.

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

Таким образом, имеем следующую теорему:

Теорема 1. Если функция () определена и дважды непрерывно дифференцируема на интервале [ , ], то необходимыми и достаточными условиями минимума этой функции в точке являются условия

Приведем доказательство справедливости последнего условия. Для этого рассмотрим разложение функции () в ряд Тейлора в окрестности точки :

(2)

Здесь – некоторая достаточно малая величина.

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

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

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

4. Классификация методов решения детерминированных задач оптимизации

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

Рассмотрим для простоты записи только ограничения типа неравенств:

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

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

· по очереди при =0,1,2,…, -1 производятся испытания в точках

(1)

где — начальное приближение;

· в качестве решения задачи берется вектор , который находится из условия

(2)

Классификация по наличию или отсутствию ограничений на вектор варьируемых параметров.

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

Классификация по размерности вектора X.

Если в формулах (1), (2) есть скаляр, то метод поиска называется одномерным методом поиска; если есть вектор ( >1), то метод поиска называется многопараметрическим методом поиска.

Классификация по характеру искомого решения.

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

Классификация по характеру функции Fr.

Если функции , являются детерминированными, то метод поиска называется детерминированным методом поиска. Если функции содержат случайные параметры, то метод поиска называется стохастическим методом поиска.

Если все точки , =0,1,2,…, назначаются заранее (до проведения испытаний), то метод поиска называется пассивным методом поиска. Если точка определяется на основе всей или части информации об испытаниях в предыдущих точках, то метод называется последовательным методом поиска.

Классификация по количеству предыдущих учитываемых шагов.

Если при вычислении координат точки учитывается информация только об одном (предыдущем) испытании, то метод поиска называется одношаговым методом поиска.

Схема одношагового последовательного метода поиска:

Если при вычислении координат точки учитывается информация о >1 предыдущих испытаниях, то метод поиска называется многошаговым методом поиска (конкретнее, -шаговым).

Классификация по виду функций Fr.

Если функции на всех шагах одинаковы, то метод поиска называется итерационным методом поиска.

Схема одношагового итерационного метода последовательного поиска:

Если функции различны на различных шагах поиска, то метод называется не итерационным методом поиска.

Классификация по "близости" соседних точек, в которых производятся испытания.

Если точка принадлежит некоторой малой окрестности точки , т.е. , то метод поиска называется локальным методом поиска. Если точка может принадлежать любой точки множества , т.е. , то метод поиска называется нелокальным методом поиска.

Классификация по порядку используемых производных.

Если при вычислении значений функции производные не используются, то метод поиска называется прямым методом поиска или методом поиска нулевого порядка. Если при этом используются производные -го порядка, то метод поиска называется методом поиска k-го порядка. Метод поиска первого порядка называется также градиентным методом поиска.

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

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

(3)

где — константа, определяющая требуемую точность решения по ;

(4)

где — константа, определяющая требуемую точность решения по . Здесь — некоторая векторная норма (например, евклидова).

Будем далее условия окончания поиска (3), (4) называть стандартными условиями окончания поиска (стандартными критериями окончания поиска).

Дата добавления: 2017-02-01; Просмотров: 104; Нарушение авторских прав?; Мы поможем в написании вашей работы!