Методи за оптимизация

[Mozo]

Химикотехнологичен и металургичен университет
Гр.София

КУРСОВА ЗАДАЧА

Тема:МЕТОДИ ЗА ОПТИМИЗАЦИЯ

Метод на Кифер-Джонсън при непрекъснат управляващ параметър

Изработил: Приел:
Марко Марков ст.ас. Н. Илиева
АУ0828, 22 гр.

1.Теоретична част:

Един от най-ефективните методи за оптимизация при едноекстремалните целеви функции със зададени граници за управляващия параметър е разработен от Кифер и Джонсън с използване на някои свойства от числсата на Фибоначи.
Всяко число от реда на Фибоначи се получава от сумата на предходните две по рекурентното съотношение
Fn=F(n-1)+F(n-2)

При F1=F2=1
В разработената от Кифер и Джонсън стратегия за търсене на екстремума се изчислява точността на локализация на екстремума да бъде зададена предварително.След реализиране на S=n-1 изчисления на целевата функция Q(x) екстремумът се локализира в 1/Fn от интервала (b-a) , където Fn е n-тото число от реда на Фибоначи.

Алгоритъмът , които гарантира сходимост при унимодални целеви функции, е следния:
1. Зададени са Q(x),a,b,del min.
2. Изчислява се помощно число M:
M= b-a/del min
3.Избира се най-близкото по-голямо или равно число от реда на Фибоначи, така че
Fn≥M
4.Изчислява се действителната точност за локализация на максимума:
Del m = b – a / Fn
5.Изчислява се целевата функция в началото на интервала.Тази стойност се приема за текущ максимум
Qm = Q(a)

6.Прави се първа стъпка с големина del m*F(n-2), тоест
X(1) = a + del m*F(n-2)

7.Изчислява се стойността на целевата функция
Q(1) = Q{x(1)}

8.Проверява се дали направената стъпка е успешна, тоест дали Q(1) > Qm.Ако стъпката е успешна, по добрия резултат се запомня като Qm , а условията x за него – като xm.
9.При сполучлива стъпка следващата се прави в същото направление с число на Фибоначи, номерът на което е с единица по – малък от предишното, или за k-тата стъпка (k =0, 1, 2 , … ,n - 2 )

x(k+1) = xm + del m*Fn – (k+2)

Изчислява се целевата функция

Q(k+1) = Q(x(k+1))

И ако стъпката е успешна, тоест Q(k+1) > Qm , запомня се Q(k+1) и се прави следваща стъпка с числото на Фибуначи, номерът на което е с единица по малък от този на предишното.Тази процедура се повтаря до изчерпване на числата на Фибуначи или до получаване на неуспешна стъпка.
10.При неуспешна стъпка, тоест Q(k+1) > Qm , следващата стъпка се прави от последната успешна в обратна посока с число на Фибуначи, чийто номер е с единица по – малък от този на предишното, използвано в неуспешна стъпка

x(k+1) = xm – del m*Fn – (k+2)

След F(n-2) числата на Фибуначи се изчерпват последователно по едно на всяка стъпка независимо дали тя е успешна или не. Ако новата стъпка е успешна, продължава се в същата посока, до изчерпване на реда на Фибуначи или до получаване на неуспешна стъпка, след което стъпките се продължава в обратна посока.

11.След като се изчерпи редът на Фибуначи, тоест n – (k+2)<1, резултатът за целевата функция в последната успешна стъпка Qm и координатите xm определят търсения максимум с точност ± del m.

12.Ако още първата стъпка е неуспешна, тоест Q(1)≤Qm, търсенето започва пак отначало с числата на Фибуначи, което е равнозначно на преместване на горната граница b в точка x(1) и повтаряне на цялата процедура отначало.

Целият материал: