Головна
Банківська справа  |  БЖД  |  Біографії  |  Біологія  |  Біохімія  |  Ботаніка та с/г  |  Будівництво  |  Військова кафедра  |  Географія  |  Геологія  |  Екологія  |  Економіка  |  Етика  |  Журналістика  |  Історія техніки  |  Історія  |  Комунікації  |  Кулінарія  |  Культурологія  |  Література  |  Маркетинг  |  Математика  |  Медицина  |  Менеджмент  |  Мистецтво  |  Моделювання  |  Музика  |  Наука і техніка  |  Педагогіка  |  Підприємництво  |  Політекономія  |  Промисловість  |  Психологія, педагогіка  |  Психологія  |  Радіоелектроніка  |  Реклама  |  Релігія  |  Різне  |  Сексологія  |  Соціологія  |  Спорт  |  Технологія  |  Транспорт  |  Фізика  |  Філософія  |  Фінанси  |  Фінансові науки  |  Хімія

Методи Хука-Дживса - Математика

Зміст: Вступ Метод Хука-Дживса Модифікований метод Хука-Дживса Блок-схема даного методу Блок-схема одиничного дослідження Текст програми Роздруківка результатів роботи програми Література Введення

На розробку методів прямого пошуку для визначення мінімуму функцій і змінних було витрачено багато зусиль. Методи прямого пошуку є методами, в яких використовуються тільки значення функції. Ми розглянемо докладно лише один з них. Практика показала, що цей метод ефективний і застосуємо для широкого числа додатків. Розглянемо функцію двох змінних. Її лінії постійного уровня1 на рис. 1,

а мінімум лежить в точці (x1 *, x2 *). Найпростішим методом пошуку є метод покоординатного спуску. З точки А ми виробляємо пошук мінімуму уздовж напрямку осі і, таким чином, знаходимо точку В, в якій дотична до лінії постійного рівня паралельна осі. Потім, роблячи пошук з точки В в напрямку осі, отримуємо точку С, виробляючи пошук паралельно осі, отримуємо точку D, і т. Д. Таким чином, ми приходимо до оптимальної точці. Очевидним чином цю идую можна застосувати для функцій n-змінних.

Теоретично даний метод ефективний у випадку єдиного мінімуму функції. Але на практиці він виявляється занадто повільним. Тому були розроблені складніші методи, використовують більше інформації на підставі вже отриманих значень функціі.Метод Хука-Дживса

Метод Хука-Дживса був розроблений в 1961 році, але до цих пір є досить ефективним і оригінальним. Пошук складається з послідовності кроків исследующего пошуку навколо базисної точки, за якою в разі успіху слід пошук за зразком. Він застосовується для вирішення завдання мінімізації функції без врахування обмежень.

Опис цієї процедури представлено нижче:

А. Вибрати початкову базисну точку b1 і крок довжиною h1 для кожної змінної xj, j = 1, 2, ..., n. У наведеній нижче програмі для кожної змінної використовується крок h, однак зазначена вище модифікація теж може виявитися корисною.

Б. Обчислити f (х) в базисної точці b1 з метою отримання відомостей про локальний поведінці функції f (x). Ці відомості будуть використовуватися для знаходження підходящого напрямку пошуку за зразком, за допомогою якого можна сподіватися досягти більшого убування значення функції. Функція f (x) в базисної точці b1, перебуває наступним чином:

1. Обчислюється значення функції f (b1) в базисної точці b1.

2. Кожна змінна по черзі змінюється додатком довжини кроку. Таким чином, ми обчислюємо значення функції f (b1 + h1e1), де e1 - одиничний вектор у напрямку осі x1. Якщо це призводить до зменшення значення функції, то b1 замінюється на b1 + h1e1. В іншому випадку обчислюється значення функції f (b1-h1e1), і якщо її значення зменшилось, то b1 замінюємо на b1-h1e1. Якщо жоден з пророблених кроків не приводить до зменшення значення функції, то точка b1 залишається незмінною і розглядаються зміни в напрямку осі х2, т. Е. Знаходиться значення функції f (b1 + h2e2) і т. Д. Коли будуть розглянуті всі n змінні , ми будемо мати нову базисну точку b2.

3. Якщо b2 = b1, т. Е. Зменшення функції не було досягнуто, то дослідження повторюється навколо тієї ж базисної точки b1, але зі зменшеною довжиною кроку. На практиці задовільним є зменшення кроку (кроків) у десять разів від початкової довжини.

4. Якщо b2b1, то проводиться пошук за зразком.

В. При пошуку за зразком використовується інформація, отримана в процесі дослідження, і мінімізація функції завершується пошуком у напрямку, заданому зразком. Ця процедура проводиться таким чином: 1. Розумно рухатися з базисної точки b2 у напрямку b2-b1, оскільки пошук у цьому напрямі вже призвів до зменшення значення функції. Тому обчислимо функцію у точці зразка

P1 = b1 + 2 (b2-b1).

У загальному випадку

Pi = bi + 2 (bi + 1-bi).

2. Потім дослідження слід продовжувати навколо точки Р1 (Рi).

3. Якщо найменше значення на кроці В, 2 менше значення в базисної точці b2 (у загальному випадку bi + 1), то отримують нову базисну точку b3 (bi + 2), після чого слід повторити крок В, 1. У противному випадку не проводити пошук за зразком з точки b2 (bi + 1), а продовжити дослідження в точці b2 (bi + 1).

Г. Завершити цей процес, коли довжина кроку (довжини кроків) буде зменшена до заданого малого значенія.Модіфіцірованний метод Хука-Дживса

Цей метод неважко модифікувати і для врахування обмежень .Було висунуто пропозицію, що для цього буде цілком достатньо при рішенні завдання мінімізації привласнити цільової функції дуже велике значення там, де обмеження порушуються .До того ж таку ідею просто реалізувати за допомогою програмирования.

Потрібно перевірити, чи кожна точка, отримана в процесі пошуку, належить області обмежень .Якщо кожна, то цільова функція обчислюється звичайним шляхом. Якщо ні, то цільової функції присвоюється дуже велике значення. Таким чином, пошук буде здійснюватися знову в допустимій області в напрямку до мінімальної точці всередині цієї області.

У тексті прогамм модифікованого методу прямого пошуку Хука-Дживса зроблена спроба реалізувати таку процедуру. Розглянута задача формулюється наступним чином:

мінімізувати f (x1, x2) = 3x12 + 4x1x2 + 5x22,

при обмеженнях x1x2x1 + x2.

Текст програми

program HuDjMody;

(*** Модифікований метод Хука-Дживса ***)

(*** (За наявності обмежень) ***)

uses crt;

label 0,1,2,3,4,5,6,7;

var k, h, z, ps, bs, fb, fi: real;

i, j, n, fe: integer;

x, y, b, p: array [1..10] of real;

(*** Процедура, що обчислює функцію ***)

procedure calculate;

begin

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

z: = 1.7e + 38;

fe: = fe + 1; (*** Лічильник ***)

end;

begin

clrscr;

gotoxy (20,2);

writeln ('Модифікований метод Хука-Дживса');

gotoxy (23,3);

writeln ('(за наявності обмежень)');

writeln;

writeln ('Введіть число змінних:');

readln (n);

writeln;

writeln ('Введіть початкову точку x1, x2, ..., xN');

for i: = 1 to n do

readln (x [i]);

writeln;

writeln ('Введіть довжину кроку');

readln (h);

writeln;

k: = h;

fe: = 0;

for i: = 1 to n do

begin

y [i]: = x [i];

p [i]: = x [i];

b [i]: = x [i];

end;

calculate;

fi: = z;

writeln ('Початкове значення функції', z: 2: 3);

for i: = 1 to n do

writeln (x [i]: 2: 3);

ps: = 0;

bs: = 1;

(*** Дослідження навколо базисної точки ***)

j: = 1;

fb: = fi;

0: x [j]: = y [j] + k;

calculate;

if zx [j]: = y [j] -k;

calculate;

if zx [j]: = y [j];

goto 2;

1: y [j]: = x [j];

2: calculate;

fi: = z;

writeln ('Пробний крок', '', z: 2: 3);

for i: = 1 to n do

writeln (x [i]: 2: 3);

if j = n then goto 3;

j: = j + 1;

goto 0;

3: if fi(*** Після оператора 3, якщо функція не зменшилася, ***)

(*** Провести пошук за зразком ***)

if (ps = 1) and (bs = 0) then

goto 4;

(*** Але якщо дослідження проводилося навколо точки ***)

(*** Шаблона PT, і зменшення функції не було досягнуто, ***)

(*** То змінити базисну точку в операторі 4: ***)

(*** В іншому випадку зменшити довжину кроку в операторі ***)

(*** 5: ***)

goto 5;

4: for i: = 1 to n do

begin

p [i]: = b [i];

y [i]: = b [i];

x [i]: = b [i];

end;

calculate;

bs: = 1;

ps: = 0;

fi: = z;

fb: = z;

writeln ('Заміна базисної точки', '', z: 2: 3);

for i: = 1 to n do

writeln (x [i]: 1: 3);

(*** (Слід за останнім коментарем) ***)

(*** І провести дослідження навколо нової базисної точки ***)

j: = 1;

goto 0;

5: k: = k / 10;

writeln ('Зменшити довжину кроку');

if k <1e-08 then goto 7;

(*** Якщо пошук незакінчений, то провести нове ***)

(*** Дослідження навколо нової базисної точки ***)

j: = 1;

goto 0;

(*** Пошук за зразком ***)

6: for i: = 1 to n do

begin

p [i]: = 2 * y [i] -b [i];

b [i]: = y [i];

x [i]: = p [i];

y [i]: = x [i];

end;

calculate;

fb: = fi;

ps: = 1;

bs: = 0;

fi: = z;

writeln ('Пошук за зразком', '', z: 2: 3);

for i: = 1 to n do

writeln (x [i]: 2: 3);

(*** Після цього провести дослідження навколо ***)

(*** Останньої точки зразка ***)

j: = 1;

goto 0;

7: writeln ('Мінімум знайдений');

for i: = 1 to n do

writeln ('x (', i, ') =', p [i]: 2: 3);

writeln;

writeln ('Мінімум функції дорівнює', '', fb: 2: 3);

writeln ('Кількість обчислень функції одно', '', fe);

repeat until keypressed;

end.

Наведена вище програма реалізує описану процедуру. Однієї або двох точок буває недостатньо для визначення початкової точки. Перша точка завжди повинна вибиратися обачно. ЕОМ працює тільки з обмеженою точністю, і помилки можуть накопичуватися в процесі складних обчислень, особливо якщо крок має "незручну" довжину. (Зазвичай ми будемо уникати "незручної" довжини, але програма повинна бути працездатна і в таких ситуаціях.) Тому в рядку, де з'ясовується питання про зміну базисної точки, ми уникаємо зменшення довжини кроку через накопичення помилки введенням довжини кроку, рівної. Ми відстежуємо, де виробляється дослідження - в базисної точці (В5 = 1, Р5 = 0) або в точці зразка (В5 = 0, Р5 = 1). Як можна переконатися на практиці, якщо не приймаються такі запобіжні заходи навіть програма з задовільною логікою буде непрацездатна.

У наведеній програмі мінімальна довжина кроку дорівнює, але вона може бути змінена. Для контролю за виконанням процедури в програму введена друк проміжних результатів. Для збільшення швидкості рахунки можуть бути видалені рядки виведення підказок і пояснень.

Процедура calculate обчислює значення функції, що мінімізується, в нашому випадку: f (x1, x2) = 3x12 + 4x1x2 + 5x22,

при обмеженнях x1x2x1 + x2.

Мінімум, рівний 44, досягається в точці (3; 1) при обмеженні x1 + x2 = 4.

Для початкової точки (4, 3) і при довжині кроку, рівній одиниці, програмою успішно вирішена задача мінімізації.

Нижче наведена роздруківка результату роботи програми:

Модифікований метод Хука-Дживса

(При налічііограніченій)

Введіть число змінних

2

Введіть початкову точку х1, х2, ..., хn

4

3

Введіть довжину кроку

1

Початкове значення функції 141.000

4.000

3.000

Пробний крок 108.000

3.000

3.000

Пробний крок 71.000

3.000

2.000

Пошук за зразком 1.70000000000001566Е + 0038

2.000

1.000

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Пошук за зразком 1.70000000000001566Е + 0038

3.000

0.000

Пробний крок 48.000

4.000

0.000

Пробний крок 48.000

4.000

0.000

Заміна базисної точки 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Пробний крок 44.000

3.000

1.000

Пробний крок 44.000

3.000

1.000

Зменшити довжину кроку

Мінімум знайдений

х (1) = 3.000

г (2) = 1.000

Мінімум функції дорівнює 44.000

Кількість обчислень одно 74

Для початкової точки (3, 4) і довжини кроку, рівній одиниці, програмою також успішно вирішена задача мінімізації.

Для початкової точки (5; 6) і довжини кроку, рівній одиниці, завдання не вирішена, тому програма зупинилася у точці (1; 3), тобто на активному обмеження, і видала невірний результат.

Роздруківка результату роботи програми наведена нижче:

Модифікований метод Хука-Дживса

(При налічііограніченій)

Введіть число змінних

2

Введіть початкову точку х1, х2, ..., хn

5

6

Введіть довжину кроку

1

Початкове значення функції 375.000

5.000

6.000

Пробний крок 324.000

4.000

6.000

Пробний крок 253.000

4.000

5.000

Пошук за зразком 155.000

3.000

4.000

Пробний крок 124.000

2.000

4.000

Пробний крок 81.000

2.000

3.000

Пошук за зразком 1.70000000000001566Е + 0038

0.000

1.000

Пробний крок 1.70000000000001566Е + 0038

0.000

1.000

Пробний крок 1.70000000000001566Е + 0038

0.000

1.000

Заміна базисної точки 81.000

2.000

3.000

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Пошук за зразком 1.70000000000001566Е + 0038

0.000

3.000

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Заміна базисної точки 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Пробний крок 60.000

1.000

3.000

Пробний крок 60.000

1.000

3.000

Зменшити довжину кроку

Мінімум знайдений

х (1) = 1.000

г (2) = 3.000

Мінімум функції дорівнює 60.000

Кількість обчислень дорівнює 89

Аналогічні невтішні результати були отримані для початкової точки (5; 6) і довжини кроку, рівної 0.5 .Неверное рішення було знайдено в точці (1.5; 2.5). Для початкової точки (4, 3) і довжини кроку, рівної 0.5, програма працювала нормально, але було отримано невірне рішення в точці (2.5; 1.5).

Проблема зрозуміла. За допомогою даного методу неможливо рухатися вздовж кордону області обмежень і збіжність досягається в першій же точці кордону, де і знаходиться рішення. Загальна задача оптимізації за наявності обмежень дуже складна і для отримання практичного методу вирішення потрібні більш витончені процедури, ніж наведена вище .Література: Б.Банді "Методи оптимізації" Р.Хук, Т.А.Джівс "Прямий пошук рішення для числових і статичних проблем ", 212-219 с., 1961.
Кореляційно-регресивний аналіз
Ieienoa?noai aunoaai ia?aciaaiey ?inneeneie Oaaa?aoee IAOO Eaoaa?a AO ?an ? aoii - a?aoe ? aneay ?aaioa ii niaoeaeuiui aeaaai iaoaiaoeee. Oaeoeuoao: AAO A?oiia: A-59 Nooaaio: No?ia A.I. I?aiiaaaaoaeu: Cuaa?aa A.I. Iiaineae?ne 1996 Розрахунково-гpафической АДВОКАТУРИ по Спецглави математики

Оцінка надійності
ЗМІСТ ВСТУП МЕТОДИКА ОЦІНКИ ВЕРЯТНОСТІ ВИЗНАЧЕННЯ ІМОВІРНОСТІ руйнується при заданих запас міцності. Список використаних джерел 1.ВВЕДЕНИЕ Досконалість методів і засобів діагностики дозволяє виявляти в елементах конструкцій дефекти різного походження. У зв'язку з цим виникає завдання про допустимість

Планета Уран
Маса: 8,7 * 10 (25) кг. (14,5 мас Землі); Діаметр екватора: 51000 км. (4 діаметра екватора Землі); Щільність: 1,27 г / см3 Температура поверхні: -220 ° С Відстань від Сонця (середнє): 19,2 ae, тобто 2860000000 км Період обертання по орбіті (рік): 84 роки Період обертання навколо

Шкала електромагнітних хвиль
Умови випромінювання і поглинання хвиль Джерелом електромагнітних хвиль в дійсності може бути будь-який електричний коливальний контур або провідник, по якому тече змінний електричний струм, так як для збудження електромагнітних хвиль необхідно створити в просторі змінне електричне поле (струм

Ряди й інтеграл Фур'є
ГЛАВА 1 ЛАВИ І ІНТЕГРАЛ ФУР'Є Основні відомості Функція f (x), визначена на всій числовій осі називається періодичною, якщо існує таке число, що при будь-якому значенні х виконується рівність. Число Т називається періодом функції. Відзначимо деякі з в про і з тонн на а цієї функції: 1) Сума,

Теорема Штольца
Зміст роботи: Формулювання і доказ теореми Штольца. Застосування теореми Штольца :; знаходження межі "середнього арифметичного" перших n значень варіанти ;;. Застосування теореми Штольца до знаходження деяких меж відносини послідовностей. Знаходження деяких меж відносини функцій за

Державин Михайло Михайлович
Народний артист Росії Народився 15 червня 1936 року в Москві. Батько - Державін Михайло Степанович (1904-1951), народний артист РСФСР, був одним з ведучих акторів Театру імені Е. Вахтангова. Мати - Державіна Іраїда Іванівна (1916-2000). Дружина - Державіна (Бабаян) Роксана Рубеновна (1946

© 2014-2022  8ref.com - українські реферати