Реферат: Методы Хука-Дживса
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
3. Модифицированный метод Хука-Дживса
5. Блок-схема единичного исследования
7. Распечатка результатов работы программы
На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий . Методы прямого поиска являются методами, в которых используются только значения функции. Мы рассмотрим подробно лишь один из них. Практика показала, что этот метод эффективен и применим для широкого числа приложений. Рассмотрим функцию двух переменных. Ее линии постоянного уровня 1
на рис. 1,
а минимум лежит в точке (x 1
*
,x 2
*
). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и , таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси . Затем, производя поиск из точки В в направлении оси , получаем точку С, производя поиск параллельно оси , получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.
Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.
Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки , за которой в случае успеха следует поиск по образцу. Он применяется для решения задачи минимизирования функции без учета ограничений .
Описание этой процедуры представлено ниже:
А. Выбрать начальную базисную точку b 1
и шаг длиной h 1
для каждой переменной x j
, j
= 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h
, однако указанная выше модификация тоже может оказаться полезной.
Б. Вычислить f
(х) в базисной точке b 1
с целью получения сведений о локальном поведении функции f
(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f
(x) в базисной точке b 1
, находится следующим образом:
1. Вычисляется значение функции f
(b 1
) в базисной точке b 1
.
2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f
(b 1
+h 1
e 1
), где e 1
– единичный вектор в направлении оси x 1
. Если это приводит к уменьшению значения функции, то b 1
заменяется на b 1
+h 1
e 1
. В противном случае вычисляется значение функции f
(b 1
-h 1
e 1
), и если ее значение уменьшилось, то b 1
заменяем на b 1
-h 1
e 1
. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1
остается неизменной и рассматриваются изменения в направлении оси х 2
, т. е. находится значение функции f
(b 1
+h 2
e 2
) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2
.
3. Если b 2
=b 1
, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1
, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
4. Если b 2
b 1
, то производится поиск по образцу.
В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
3. Разумно двигаться из базисной точки b 2
в направлении b 2
-b 1
, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
2. Затем исследование следует продолжать вокруг точки Р 1
(Р i
) .
3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b 2
(в общем случае b i+1
), то получают новую базисную точку b 3
(b i+2
), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b 2
(b i+1
), а продолжить исследования в точке b 2
(b i+1
).
Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
Этот метод нетрудно модифицировать и для учета ограничений .Было выдвинуто предложение , что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там,где ограничения нарушаются .К тому же такую идею просто реализовать с помощью програмирования .
Нужно проверить ,каждая ли точка ,полученная в процессе поиска , принадлежит области ограничений .Если каждая , то целевая функция вычисляется обычным путем . Если нет , то целевой функции присваивается очень большое значение . Таким образом , поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.
В тексте прогаммы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом :
минимизировать f
(x 1
,x 2
) = 3x 1
2
+4x 1
x 2
+5x 2
2
,
при ограничениях x 1
x 2
x 1
+x 2
.
(*** Модифицированный метод Хука-Дживса ***)
(*** (при наличии ограничений) ***)
(*** Процедура,вычисляющая функцию ***)
z:=3*sqr(x[1])+(4*x[1]*x[2])+(5*sqr(x[2]));
if (x[1]<0) or (x[2]<0) or ((x[1]+x[2])<4) then
writeln('Модифицированный метод Хука-Дживса');
writeln('( при наличии ограничений )');
writeln('Введите число переменных:');
writeln('Введите начальную точку x1,x2,…,xN');
writeln('Начальное значение функции', z:2:3);
(*** Исследование вокруг базисной точки ***)
(*** После оператора 3,если функция не уменьшилась, ***)
(*** произвести поиск по образцу ***)
(*** Но если исследование производилось вокруг точки ***)
(*** шаблона PT,и уменьшение функции не было достигнуто,***)
(*** то изменить базисную точку в операторе 4: ***)
(*** в противном случае уменьшить длину шага в операторе***)
writeln('Замена базисной точки',' ',z:2:3);
(*** (следует за последним комментарием) ***)
(*** и провести исследование вокруг новой базисной точки ***)
(*** Если поиск незакончен,то произвести новое ***)
(*** исследование вокруг новой базисной точки ***)
writeln('Поиск по образцу',' ',z:2:3);
(*** После этого произвести исследование вокруг ***)
writeln('Минимум функции равен',' ',fb:2:3);
writeln('Количество вычислений функции равно',' ',fe);
Приведенная выше программа реализует описанную процедуру. Одной или двух точек бывает недостаточно для определения начальной точки. Первая точка всегда должна выбираться осмотрительно. ЭВМ работает только с ограниченной точностью, и ошибки могут накапливаться в процессе сложных вычислений, особенно если шаг имеет “неудобную” длину. (Обычно мы будем избегать “неудобной” длины, но программа должна быть работоспособна и в таких ситуациях.) Поэтому в строке , где выясняется вопрос об изменении базисной точки, мы избегаем уменьшения длины шага из-за накапливания ошибки введением длины шага, равной . Мы отслеживаем, где производится исследование – в базисной точке (В5 = 1, Р5 = 0) или в точке образца (В5 = 0, Р5 = 1). Как можно убедиться на практике, если не принимаются такие меры предосторожности даже программа с удовлетворительной логикой будет неработоспособна.
В приведенной программе минимальная длина шага равна , но она может быть изменена . Для контроля за выполнением процедуры в программу введена печать промежуточных результатов. Для увеличения скорости счета могут быть удалены строки вывода подсказок и пояснений.
Процедура calculate
вычисляет значение минимизируемой функции ,в нашем случае : f
(x 1
,x 2
) = 3x 1
2
+4x 1
x 2
+5x 2
2
,
при ограничениях x 1
x 2
x 1
+x 2
.
Минимум, равный 44, достигается в точке (3;1) при ограничении x 1
+x 2
=4.
Для начальной точки (4;3) и при длине шага , равной единице , программой успешно решена задача минимизации .
Ниже приведена распечатка результата работы программы :
Поиск по образцу 1.70000000000001566Е+0038
Поиск по образцу 1.70000000000001566Е+0038
Для начальной точки (3;4) и длины шага , равной единице , программой также успешно решена задача минимизации .
Для начальной точки (5;6) и длины шага , равной единице , задача не решена , т.к. программа остановилась в точке (1;3) , т.е. на активном ограничении , и выдала неверный результат .
Распечатка результата работы программы приведена ниже :
Поиск по образцу 1.70000000000001566Е+0038
Пробный шаг 1.70000000000001566Е+0038
Пробный шаг 1.70000000000001566Е+0038
Поиск по образцу 1.70000000000001566Е+0038
Аналогичные неутешительные результаты были получены для начальной точки (5;6) и длины шага , равной 0.5 .Неверное решение было найдено в точке (1.5;2.5) . Для начальной точки (4;3) и длины шага , равной 0.5 ,программа работала нормально , но было получено неверное решение в точке (2.5;1.5) .
Проблема понятна . С помощью данного метода невозможно двигаться вдоль границы области ограничений и сходимость достигается в первой же точке границы , где и находится решение . Общая задача оптимизации при наличии ограничений очень сложна и для получения практического метода решения требуются более изощренные процедуры , чем приведенная выше .
2. Р.Хук , Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961 .
Название: Методы Хука-Дживса
Раздел: Рефераты по математике
Тип: реферат
Добавлен 03:53:10 24 марта 2008 Похожие работы
Просмотров: 779
Комментариев: 17
Оценило: 3 человек
Средний балл: 4
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Реферат: Методы Хука-Дживса
Сочинение Про То Что Я Люблю
Реферат: Понятие цифрового таймера
Проходной Балл По Сочинению Егэ 2022
Доклад по теме Подсолнечник
Курсовая Работа Части
Реферат: Wordsworth Essay Research Paper William Wordsworths description
Доклад: Особенности антикризисного управления персоналом
Любовь К Природе Сочинение Егэ
Курсовая Работа Доходы Бюджетов
Контрольная Работа На Тему Античная Философия Древней Греции. Проблемы Истины В Теории Познания
Отчет по практике по теме Автоматизация учета движения пациентов
Сочинение По Картине Баян Васнецова 9 Класс
Курсовая работа по теме Правовая охрана вод
Реферат: Простите нас
Курсовая работа по теме Особенности интеллектуального развития детей 5-7 лет с детским церебральным параличом
Процессуальные Сроки В Гражданском Праве Реферат
Реферат по теме Расчет тэп участка по изготовлению детали №1702050 Шток вилки переключения 3й и 4й передач
Налоговая полиция и её роль в системе правоохранительных органов
Участники Платежных Систем И Их Функции Курсовая
Курсовая работа: Международные валютно-финансовые и кредитные организации
Реферат: Девяти этажный жилой дом в городе Запорожье (Дев’ятиповерховий житловий будинок для будівництва в м. Запоріжжі)
Реферат: Морфофункциональная характеристика изменений антиадгезивных свойств брюшин в зависимости от состояния микроциркуляции
Реферат: Стоматология (Остеомиелит челюстей)