Методи кука Джийвс

3. Модифициран метод на Хук-Джийвс

4. Блок-схема на метода

5. блокова диаграма на едно проучване

6. Текстът на програмата

7. Отпечатване на резултатите от работната програма

За развитието на преки методи за търсене за определяне на минималните функции и променливи са изразходвани много усилия. Директни методи за търсене са методи, които се използват само функционални стойности. Ние считаме, че само един от тях в детайли. Практиката показва, че този метод е ефективен и приложим към широк кръг от приложения.

Да разгледаме функцията на две променливи. Нейната линия на постоянно ниво 1 на фиг. 1

и минималната е в (х1 *, x2 *). Най-простият начин е да се намери начин за произход. От точка А ние произвеждаме минимално търсене по оста. По този начин, ние откриваме, точка Б, в които допирателната към линия, успоредна на оста на постоянно ниво. След това, чрез търсене от точка Б по посока на ос. Качваме се на точка С, като търсите успоредно на оста. получите точка D, в т. е. Така стигаме до оптималната точка. Най-очевидният начин това iduyu може да се използва за функции п-променливи.

На теория, този метод е ефективен в случай на един минимум на функцията. Но на практика се оказва твърде бавен. Ето защо той е разработен по-сложни методи, които използват повече информация, въз основа на вече получените стойности на функцията.

метод на Хук-Jeeves е разработен през 1961 г., но все още е много ефективен и оригинален. Търсене състои от серия проучване на търсенето стъпки около базова точка. за които, ако са успешни, трябва да се търси модел. Той се използва за решаването на проблема с минимизиране на функцията без да се взима ограничения по вашата сметка.

Тази процедура е представена по-долу:

А. Избор на базова точка b1 и дължината на стъпалото h1 за всяка променлива XJ. к = 1, 2, ..., п. В следната програма за всяка променлива използва стъпка часа. но модификация може да бъде полезен, както е посочено по-горе.

Б. Изчисли е (х) на база точка Ь1 да получи информация за местната поведението на функция е (х). Тази информация ще се използва, за да се намери подходяща посока на търсене на модела, с което можем да се надяваме да се постигне по-голямо намаление на стойността на функцията. F функцията (х) на база точка Ь1. Това е, както следва:

1. Изчислява се стойността на F функция (Ь1) при базовата точка Ь1.

2. Всяка променлива в даден момент се променя чрез добавяне на крачка дължина. По този начин, ние се изчисли стойността на F функция (b1 + h1 е1), където Е1 - единица вектор по посока на оста X1. Ако това води до намаляване на стойността на функцията, той се заменя с b1 b1 + h1 е1. В противен случай, изчислената стойност на F функция (b1 -Н-1 е1), и ако е по-малка, тогава b1 се заменя със b1 -H1 е1. Ако нито един от свършената стъпки не намалява стойността на функцията, точка Б-1 остава непроменена и разглежда промени в посока на ос X2. т. е. е стойността на функцията F (b1 + h2 е2), и така нататък. г. Когато ще разгледа всички п променливи, ще имаме нова базова точка b2.

3. Ако b2 = b1. т. е. намаляване на функция не се постига, изследването се повтаря по същата базова точка В1. но с намалена дължина стъпка. На практика задоволително етапа на редукция (стъпки) в десет пъти от първоначалната дължина.

b1. търсене се извършва на извадката.

Въпрос: Когато търсите модел използва информацията, получена в хода на проучването, както и за свеждане до минимум на функцията завършва търсенето в посока на дадена проба. Тази процедура е както следва:

3. Разумно е да се премине от референтната точка в посока на b2 b2 -Б-1. защото търсенето в тази посока вече е довело до намаляване на стойността на функцията. Ето защо ние се изчисли точката на функция в пробата

2. След това учи трябва да продължи около P1 (P I) точка.

3. Ако най-малката стойност в стъпка Б, 2 по-малки от базовата точка В2 (обикновено два пъти + 1), а след това получи точка b3 нова основа (BI + 2), а след това повторете стъпка Б 1. В обратния случай търсене на модела на точка b2 (BI + 1), и по-нататъшни изследвания в точка В2 (BI + 1).

G. Край този процес, когато дължината на етап (етап дължина) се понижава до предварително определена малка стойност.

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

Този метод е лесно да се променят и да се вземе предвид ограничения .Bylo предложение. че това ще бъде достатъчно, за да се реши проблема на намаляването на целевата функция за присвояване голямо значение, когато ограниченията са нарушени .K Освен това подобна идея просто реализиран от програмиране.

Ние трябва да се провери дали всяка точка, получена в процеса на търсене. Той принадлежи към полеви ограничения Ако всеки. целевата функция се изчислява по обичайния начин. Ако не. целевата функция се задава голямо значение. По този начин. търсене ще се извършва отново в допустимия регион в посока на минималната точка в тази област.

Текстовият PROSCALE модифициран метод на търсене на Хук-Jeeves опит да се приложи такава процедура. Проблемът въпросната има следното съдържание:

за ограничения x1

writeln ( "Минимална функция равен", '', еб: 2: 3);

writeln ( "равен брой изчислителни функции ',' ', ед);

повтаря, докато keypressed;

Горната програма изпълнява тази процедура. Една или две точки не са достатъчни, за да се определи началната точка. Първата точка винаги трябва да бъде избран внимателно. Компютърна работи само с ограничена точност и грешки могат да се натрупват в процеса на сложни изчисления, особено ако терена е "неудобно" дължина. (Обикновено ние се избегне "неудобни" с дължина, но програмата трябва да се оперира и в такива ситуации.) Ето защо, в съответствие. където тя се появява въпросът за промяна на базовата точка, ние избягваме намаляване дължина на крачката се дължи на натрупване на грешки чрез въвеждане на дължина, равна стъпка

. Ние следим където изследването се провежда - в базовата точка (H5 = 1, R5 = 0) или точката на пробата (В5 = 0, Р5 = 1). Както може да се види на практика, ако не се вземат такива мерки с задоволително дори логика програма ще бъде неизползваема.

В по-горе програма, минималната продължителност на една крачка е

, но тя може да бъде променена. За да се следи за изпълнението на процедурите за програма, приведена в печат на междинни резултати. Извод на съвети и обяснения могат да бъдат отстранени, за да се увеличи скоростта на броене.

Изчисли процедура изчислява стойността на целевата функция в този случай. F (х1, х2) = 3x1 + 4x 2-1 х2 + 5x2 2

за ограничения x1

Най-малко равна на 44, се достига при точка (3: 1) под ограничение X1 + х2 = 4.

За началната точка (4, 3) и дължината на стъпка. единство. Програмата успешно решен проблема за минимизиране.

По-долу е списък на резултатите от работната програма:

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

Въведете броя на променливите

Въведете началната точка x1, x2, ..., Xn

Въведете дължина на крачката

Минимална функция е равна на 44,000

Броят на изчисления се равнява на 74

За началната точка (3, 4) и дължина стъпка. единство. Програмата също така успешно решен проблема за минимизиране.

За началната точка (5, 6) и дължината на стъпка. единство. проблемът не е решен. защото програма е спряло в точката (1; 3). т.е. активни ограничения. и даде грешен резултат.

Отпечатване на резултатите от работната програма, посочени по-долу:

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

Въведете броя на променливите

Въведете началната точка x1, x2, ..., Xn

Въведете дължина на крачката

Първоначалната стойност на функцията 375,000

стъпка Тест 324,000

стъпка Тест 253,000

Търсене шарени 155,000

стъпка Тест 124,000

стъпка Тест 81,000

моделира Търсене 1.70000000000001566E + 0038

стъпка Тест 1.70000000000001566E + 0038

Смяна на отправна точка 81.000

стъпка Тест 60,000

моделира Търсене 1.70000000000001566E + 0038

стъпка Тест 60,000

Смяна на отправна точка 60.000

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

стъпка Тест 60,000

дължина Намалете терен

Минимална функция е равна на 60,000

Броят на изчисления се равнява на 89

Подобни разочароващи резултати са получени за начална точка (5, 6) и дължината на стъпка. равна на 0,5 разтвор .Nevernoe е намерено в точката (1,5; 2,5). За началната точка (4, 3) и дължината на стъпка. равно на 0.5, програмата ще работи правилно. но погрешно решение е било получено в точката (2,5; 1,5).

Проблемът е ясен. С този метод не е възможно да се движи по границата на ограниченията и конвергенция се постига в първата точка граница. когато има решение. Оптимизиране на общите проблеми с ограничения е много трудно и за осигуряване на практически метод за решаване на необходимостта от по-сложни процедури. от по-горе.

1. B.Bandi "оптимизация"

2. R.Huk. T.A.Dzhivs "Преки решения от търсенето за числови и статични проблеми", 212-219 секунди. 1961.