Golden Section Metodu

fonksiyon

Şekil 1

Golden Section, Verilen fonksiyonda iki nokta arasında ( yani [A,B] aralığında ) optimum noktayı bulmak için kullanacağımız bir optimizasyon tekniğidir. (Foksiyon konkav olsaydı maksimum’ u araştırırdık.)

Bu noktayı r^2-r=1 (altın oran ile) bulacağız. (r=0,618) Bu noktayı bulurken alanı sürekli altın oran ile daraltarak bulmaya yarayan bir metod yazacağız. 

1

Şekil 2

a ile b arasında bir x1 ve x2 noktası belirleyelim.

r=0.618 olarak hesaplanmıştı (2 bilinmeyenli denklemden)

x1=a+(b-a)*(1-r)

x2=a+(b-a)*r

bağlı olarak hesaplanır.

Amacımız [a,b] aralığının minumum noktasıydı. x1 ve x2′ yi baz alarak bu optimum minimum noktasına yaklaşmaya çalışacağız.

f(x)=ax+b tarzında herhangi bir fonksiyon olsun

x1 ve x2′ yi sırayla f(x) fonksiyonunda x yerine koyup hesaplayacağız.

f1=f(x1) ve f2=f(x2)

Eğer f1>f2 ise

f1, f2 den büyüktür. Amaç küçük olana gitmek olduğu için Şekil 2 üzerinde sağa doğru kaydırma yapacağız.

a=x1,

x1=x2,

f1=f2 olacak ve x2=a+(b-a)*r (yeni a değerine bağlı olarak yeniden hesaplanacak)

f2=f(x2) yerine konularak f2 hesaplanacak.

Değilse yani f2>f1 ise

b=x2, 

x2=x1,

f2=f1, 

x1=a+(b-a)*(1-r)

ve f1=f(x1) olarak hesaplanır.

Bu şekilde hep alanı daraltarak en küçük noktayı bulmaya yarar.

goldensection

Her iterasyonda çözüm aralığı (1- altın oran) yani (1-0.618=0.382) olarak azaltılır yani %38 kadar alan daraltılmış olunur.

ÖRNEK:

f(x)= 3*x^2+4x-1 fonksiyonu verilsin. a=3 ve b=2 ise ilk iterasyonu çözünüz?

Çözümleme:

Şimdi öncelikle a ve b aralığında bir x1 ve x2 noktaları ele alacağız. Ve bu x1, x2 noktalarını fonksiyonda x yerine koyup büyüklük/küçüklük durumuna göre eleme yapacağız.

O halde,

x1= a+(b-a)*0.312 = 3+(2-3)*0.382= 2.61 olarak elde edilir.

x2= a+(b-a)*0.618= 3+(2-3)*0.618= 2.38‘ dir

a ve b aralığında x1 ve x2 noktalarını elde ettik. Şimdi fonksiyonda yerine koyarak f1 ve f2′ yi elde edelim.

f1=f(x1)=f(2.61)=3*(2.61)^2+4*(2.61)-1=29.87

f2=f(x2)=f(2.38)=3*(2.38)^2+4*(2.38)-1=25.51

Program döngüsü şu şekildedir: (sözde kod) [tol değeri soru öncesinde belirtilir, ben sadece genel olarak kalıptan bahsetmek istedim]

while(abs(a-b>tol)){

Eğer f1>f2 ise

f1, f2 den büyüktür. Amaç küçük olana gitmek olduğu için Şekil 2 üzerinde sağa doğru kaydırma yapacağız.

a=x1,

x1=x2,

f1=f2 olacak ve x2=a+(b-a)*r (yeni a değerine bağlı olarak yeniden hesaplanacak)

f2=f(x2) yerine konularak f2 hesaplanacak.


f1=29.87>f2=25.51   ? Evet o halde

a=x1=2.61   (a nın eski değeri 3 idi)

x1=x2=2.38  (x1 in eski değeri 2.61 idi)

f1=f2=25.51  (f1 in eski değeri 29.87 idi)

f2=f(x2)= a+(b-a)*0.618=2.61+(2-2.61)*0.618=2.23 olarak yeni a değerine bağlı bir şekilde elde edilmiştir.

[Dikkat: b sabittir. Çünkü fonksiyon b ye doğru hareket ederek minumum a ulaşmayı hedefler.]


Değilse yani f2>f1 ise

b=x2, 

x2=x1,

f2=f1, 

x1=a+(b-a)*(1-r)

ve f1=f(x1) olarak hesaplanır.

[Dikkat: a sabittir. Çünkü fonksiyon a ya doğru hareket ederek minumum a ulaşmayı hedefler.]

}

bu şekilde 1 iterasyon için fonksiyonun yakınsaması verilmiştir. Sonuç olarak Tek değişkenli optimizasyon problemlerinde Golden Section çok önemli bir yere sahiptir.

Kaynak:

Bu anlatım Doçent Doktor Bilal Alataş‘ ın Optimizasyon Teknikleri ders notlarından özetlenmiştir.

Melih Hilmi Uludağ

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir