Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Локальный и глобальный экстремумы функций. Нахождение экстремумов методом общего поиска
Рассмотрим две задачи, возникающие при проектировании сетей связи. Задача 1. Проектируется канал передачи данных с решающей обратной связью. Узел А отправляет информационные пакеты узлу В. Узел В проверяет правильность каждого полученного пакета и при правильном или неправильном приеме отправляет узлу А, соответственно, положительные или отрицательные квитанции. При получении положительной квитанции узел А отправляет следующий пакет, при получении отрицательной - повторяет передачу предыдущего пакета. Каждый пакет состоит из информационной части длиной k символов и проверочной части длиной r символов. Эффективность работы канала передачи данных (КПД) оценивается по относительной скорости передачи R - эквиваленту коэффициента полезного использования пропускной способности канала передачи данных, R = f (k). В самом деле, если k = 0, т.е. информации в пакете нет и он содержит только проверочную часть, то R = 0. При увеличении k будет расти и R. Однако, если k чрезмерно велико, то пакеты имеют большую длину и, при вероятности искажения сообщений в КПД отличной от нуля, будут чаще поражаться ошибками, а, следовательно, и чаще повторяться. Таким образом, при изменении k от 0 до ¥ зависимость R = f (k) будет иметь вид показанный на рисунке 1. Естественным является желание найти такое значение k, при котором R (k) достигает максимума.
Рис. 4.1 Задача 2. Задача о максимальной достоверности передаваемой информации при заданной длине пакета. Пусть длина пакета составляет n = k + r = const. Очевидно, что k и r могут изменяться от 0 до n. При этом общая длина пакета не должна быть отличной от n. Достоверность определяется вероятностью необнаружения ошибки P ош. Зависимость P ош от отношения r/k имеет вид Рис. 4.2 Требуется найти такое соотношение между r и k, при котором вероятность искажения пакета в канале передачи данных минимальна P* ош = min P (r/k). Видно, что задачи 1 и 2 - задачи поиска экстремума некоторой функции в заданной области изменения ее аргумента (области исследования). Разрабатывая методы поиска, стремятся найти экстремум как можно быстрее, сделав как можно меньше попыток. В дальнейшем рассмотрим методы поиска экстремума целевой функции - функции одного аргумента (одномерной функции).
Локальным экстремумом будем называть точку пространства исследования, в которой целевая функция имеет наибольшее (наименьшее) значение по сравнению с ее значениями во всех других точках ближайшей окрестности. На рис.4.1 показана одномерная функция, имеющая пять локальных экстремумов. Часть пространства исследования может содержать много локальных экстремумов и следует сохранять осторожность, чтобы не принять первый из них за решение задачи. Рис.4.3 Глобальным экстремумом будем называть точку пространства исследования, в которой целевая функция имеет большее (меньшее) значение по сравнению с любой другой точкой пространства исследования. Таким образом, глобальный оптимум - это оптимальное решение для всего пространства исследования. Оно лучше всех других решений, соответствующих локальным оптимумам, и именно его ищет исследователь. Задачу одномерной оптимизации можно поставить следующим образом. Пусть значения переменной x заключены в интервале [ a; b ]. Интервал значений переменной x, в котором производится поиск оптимума целевой функции, будем называть интервалом неопределенности. В начале процесса оптимизации этот интервал имеет длину b-a. Необходимо определить значения оптимума функции с погрешностью e, то есть найти в интервале [ a; b ] точку x, такую что f (x -e) < f (x) > f (x +e) - при поиске максимума, или f (x -e) > f (x) < f (x +e) - при поиске минимума.
Таким образом, нам необходимо иметь план действий, неизбежно приводящий к определению x* с точностью e, где бы эта точка не лежала в области поиска. Рассматриваемые в дальнейшем методы и являются такими планами действий по поиску оптимумов функций. Очевидно, наиболее естественным и простым способом сужения интервала неопределенности для одномерной унимодальной функции является его деление на несколько равных частей с последующим вычислением значений целевой функции в узлах полученной сетки.
Рис. 4.5 В результате интервал неопределенности сужается до двух шагов сетки. Обычно говорят о дроблении интервала неопределенности, которое характеризуется коэффициентом дробления f д. Коэффициент дробления показывает, какую часть от исходного интервала неопределенности составляет новый интервал неопределенности.
Проводя N измерений получим (N +1) частей интервала неопределенности и тогда: где 2 – осталось частей интервала неопределенности; N +1 – было частей интервала неопределенности. Чтобы получить значение f д = 0,01 потребуется вычислить целевую функцию в 199 точках, а при f д = 0,001 - N =1999. Видно, что эффективность этого метода при уменьшении интервала неопределенности быстро падает. Сам собой напрашивается другой путь: чтобы получить f д=0,01, вычислим сначала функцию в 19 точках и получим f д=0,1, а затем, вычислив еще 19 значений на сокращенном интервале получим f д=0,01, сделав при этом всего 38, а не 199 вычислений. Таким образом, при некоторой изобретательности эффективность поиска можно резко повысить. Фактически мы перешли от одношагового алгоритма к многошаговому алгоритму.
|
||||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 1731; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.12.161.77 (0.004 с.) |