• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Метод дихотомії

Методи однопараметричної оптимізації

Метод дихотомії використовується для унімодальних цільових функцій. Він полягає в наступному. На інтервалі [a, b] вибирається дві точки відносно середини інтервалу x₁ = (a+ b)/ 2 - e / 2 і x₂ = (a+ b)/ 2 +e / 2, де e - задана точність, деяка мала величина e > 0. Далі обчислюються значення функції в цих точках і порівнюються між собою.

Рис. 6.2. Схема алгоритму оптимізації методом дихотомії

Якщо f(x₁) < f(x₂), то оптимум знаходиться на інтервалі [a, x₂],

якщо f(x₁) > f(x₂), то оптимум x_опт знаходиться на інтервалі [x₁, b],

якщо f(x₁) = f(x₂), то оптимум x_опт знаходиться на інтервалі [x₁, x₂].

Після цього звужується довжина відрізку перенесенням точки a або b в середину відрізку. Відрізок звужується на пополам до тих пір, поки його довжина не стане менше заданої точності. Схема алгоритму вирішення задачі оптимізації даним методом показана на рис.6.2.

Недоліком даного методу є подвійне обчислення значення цільової функції в точках x₁ і x₂, а перевагою - висока надійність методу.

6.3.2. Метод “золотого розтину”

“Золотим розтином” у геометрії називається поділ відрізка на дві нерівні частини таким чином, щоб відношення довжини всього відрізка до його більшої частини дорівнювало відношенню цієї більшої частини до меншої.

Рис. 6.3. Схема “золотого розтину”

Метод “золотого розтину” полягає в тому що, виконуємо поділ відрізку [a, b] на дві частини і одержуємо точку x₂ ( рис. 6.3). Більшу одержану частину знову ділимо методом “золотого розтину” і одержуємо точку x₁. Також можна виконувати поділ відрізка „золотим розтином” на дві нерівні частини, щоб менша частина була з боку точки а з одержанням точки x₁ і з боку точки b з одержанням точки x₂. Числові значення одержаних точок рахуємо за формулами:

x₁ = a + t₁ * ( a - b); i x₂ = a + t₂ * ( a - b);

де

Для кожної точки x₁ і x₂ розраховують значення цільової функції f(x₁) і f(x₂), порівнюють їх між собою і звужують відрізок. Якщо f(x₁) £ f(x₂), то відкидають інтервал [x₂, b]. Якщо f(x₁) > f(x₂), то відкидають інтервал [a, x₁]. Після перейменування точок нової області екстремуму - ліва точка повинна називатися a, а права точка b, операція повторюється. Поділ відрізку продовжується до тих пір, поки довжина відрізку не стане | b - a | £ e , де e > 0 - наперед задана точність обчислень.

Алгоритм даного методу полягає в наступному:

1. Задаємося границями параметра оптимізації a i b і точністю обчислень e.

2. Обчислюємо внутрішні точки поділу x₁ і x₂ і відповідні їм значення функцій f(x₁) і f(x₂).

3. Порівнюємо значення функцій між собою і:

якщо f(x₁) £ f(x₂), то звужуємо інтервал справа і обчислюємо нове значення x₁ і f(x₁) і переходимо на п. 4.

якщо f(x₁) > f(x₂), то звужуємо інтервал зліва і обчислюємо нове значення x₂ і f(x₂) і переходимо на п. 4.

4. Перевіряємо можливість припинення пошуку мінімального значення порівнюючи довжину відрізку [a, b] з точністю e.

Якщо | b - a | £ e, то переходимо на п. 5,

якщо | b - a | > e, то повертаємось на п. 3.

5. Обчислюємо наближене значення параметра оптимізації :

x_опт = (a+ b) / 2,

оптимальне значення цільової функції y_опт = f(x_опт) і закінчуємо обчислення.

Блок схема алгоритму наведена на рис. 6.4.

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

Рис. 6.4. Схема алгоритму оптимізації методом “золотого розтину”

6.3.3. Метод з використанням квадратичної апроксимації (Пауелла)

Використання раніше розглянутих методів однопараметричної оптимізації вимагає наявності унімодальної функції. Даний метод підвищує ефективність пошуку оптимуму, але крім того ще вимагає виконання умови гладкості і безперервності функції. Основна ідея методу полягає у можливості апроксимації гладкої функції поліномом, наприклад квадратичним, з наступним його використанням для визначення координати точки оптимуму. Квадратичний поліном будується з використанням крайніх точок інтервалу [a, b] і заданої точки с, вибраної на інтервалі. Пошук оптимуму визначається положенням екстремальної точки x_пол відносно точки с. Ілюстрація пошуку мінімуму з викорис­танням квадратичної апроксимації показана на рис. 6.5.

Рис. 6.5. Використання квадратичного поліному при оптимізації

методом Пауелла

Алгоритм рішення задачі оптимізації методом Пауелла полягає у виконанні наступних етапів:

1. Задається точка с на інтервалі [a, b]. При цьому a < c < b; f(c) £ f(a); f(c) £ f(b).

2. По точках a, b, c будується графік параболи P(x) = a₀ + a₁ x + a₂ x² . Коефіцієнти параболи знайдемо за допомогою полінома Лагранжа.

, (6.3)

де a₀ = [c b (b - c) f(a) + a b (a - b) f(c) + a c (c - a) f(b)] / d

a₁= [ (с² - b²) f(a) + (b² - a²) f(c) + (a² - c²) f(b)] / d

a₂= [ (b - c) f(a) + (a - b) f(c) + (c - a) f(b)] / d

d = (a - c) (c - b) (b - a).

Точка мінімуму полінома знаходиться за допомогою диференціювання , звідки значення .

Підставивши в останнє рівняння значення a₁ і a₂ можна знайти:

( 6.4 )

3. Знаходимо значення f( x_пол).

4. Перевіряємо умови:

якщо x_пол < c i f( x_пол) < f(c), тоді b = c, c= x_пол ;

якщо x_пол < c i f( x_пол) ³ f(c), тоді a= x_пол ;

якщо x_пол > c i f( x_пол) < f(c), тоді a = c, c= x_пол ;

якщо x_пол > c i f( x_пол) ³ f(c), тоді b= x_пол ;

5. Перевіряємо можливість припинення пошуку мінімального значення порівнюючи відстань від точки с до точки x_пол з точністю e.

Якщо | x_пол - с | £ e, то переходимо на п. 6,

якщо | x_пол - с | > e, то повертаємось на п. 2.

Рис. 6.6. Схема алгоритму оптимізації методом Пауелла

6. Наближене значення параметра оптимізації вважаємо рівним x_опт = x_пол, а оптимальне значення цільової функції y_опт = f(x_пол) і закінчуємо обчислення.

Схема алгоритму метода наведена на рис. 6.6.

Слід зауважити, що цей метод самий складний по алгоритму. В ньому чотири розгалуження, бо крім порівняння значень функцій в точках x₁ і x₂ порівнюються між собою значення самих точок x_пол і с, які тут грають роль точок x₁ і x₂. За умовою x₁ < x₂.

Читайте також:

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 1470