NELDER –
MEAD METODU
Bu metot, Nelder ve Mead tarafından oluşturulan birkaç
değişken fonksiyonun yerel minimum noktasını bulmak için kullanılan bir simplex
metodudur. İki değişken için, simplex bir üçgen oluşturur ve bu üçgenin üç köşe
noktalarındaki fonksiyon değerlerini karşılaştıran örnek araştırma metodudur.
F(x,y) fonksiyon değerinin en büyük olduğu yer olan tepe
değeri reddedilir ve yeni bir tepe değer tayin edilir. Böylece yeni bir üçgen
oluşturulur ve araştırmaya devam edilir.
Köşe noktalardaki fonksiyon değerinin küçülmesini sağlayan
değerleri bulabilmek için, süreç farklı şekiller alabilecek olan bir üçgenler
dizisi meydana getirir.
Üçgenin boyutları küçültülür ve minimum noktaların
koordinatları bulunur. Algoritma, simplex terimini kullanarak oluşturulmuştur
ve bu algoritma N değişkenleri fonksiyonun minimum noktasını buldurur. ( N
boyutta genelleştirilmiş bir üçgen.).
Bu, hesaplamayla oluşturulmuştur ve etkili bir çözümdür.
İLK ÜÇGEN BGW
Minimize
edilecek olan f(x,y) fonksiyonunu oluşturalım. Başlangıç için, üçgenin köşe
noktası değerlerini veririz. Vk=(xk,yk)
k=1,2,3. F(x,y) fonksiyonu k=1,2,3 için her 3 noktada fonksiyonun değerini buldurur.
z1≤z2≤z3
sıralamasını oluşturmak için kabul edilen değerler yeniden düzenlenir.
B’nin en iyi değer, G’nin iyi değer (en iyiye yakın) ve
W’nun en kötü değer olduğunu hatırlamak için;
(1) B(x1,y1) G(x2,y2) W(x3,y3) notasyonunu
kullanırız.
Oluşturulan yöntem, B ve G noktalarının birleşmesiyle
oluşan doğru parçasının orta noktasını bulmak amacıyla kullanılır. Bu nokta,
koordinatların ortalamasının alınmasıyla bulunur:
(2)
M = (B+G) / 2 = [ (x1+x2)/2
, (y1+y2)/2 ] .
R NOKTASINI KULLANARAK
YANSITMA
Fonksiyonun değeri üçgenin kenarını W noktasından B
noktasına doğru taşırken ve W noktasından G noktasına taşırken azalır. F(x,y)
fonksiyonunun W noktası karşısında bulunan BG doğrusu üzerinde, W noktasının
aldığı değerlerden daha küçük değerler
alması mümkündür. Üçgenin BG doğrusu boyunca simetri (yansıtma) ile elde edilen
bir “R” deneme noktasını seçelim. R’yi bulabilmek için ilk önce, BG doğrusunun
orta noktası olan M noktasını buluruz. Sonra W noktasından M noktasına kadar
olan “d” uzaklığını çizeriz. M boyunca d kadar uzatılarak çizilen doğru parçası
R noktasını bulduran son parçadır.
(Şekil 1) R için vektör formülü;
(2)
R = M + ( M – W ) =
2M – W
R
noktasındaki fonksiyon değeri W noktasındaki değerden küçükse, minimum
noktasına doğru, bir doğru çizeriz. Belki minimum nokta R noktasından çok az
bir uzaklıktadır. Bu yüzden doğru parçasını MR boyunca E noktasına kadar uzatırız.
Bu yapı, genişletilmiş bir BGE üçgenidir. E noktası M ve R noktalarının
birleştirilmesinden oluşan doğru parçasına bir d uzaklığı kadar ilave edilerek
taşınması ile bulunur. ( Şekil 2)
Eğer E noktasındaki fonksiyon değeri R noktasındaki
fonksiyon değerinden küçükse, R’den daha iyi değerler elde edebileceğimiz bir
tepe noktası bulmamız gerekir. E vektörü için formül;
(3)
E = R + ( R – M ) =
2R – M
Eğer R
ve W noktalarındaki değerler aynıysa, başka nokta test edilmelidir. Belki
fonksiyon M noktasında daha küçük değer alır. Fakat M ile W noktasının yerini alamayız çünkü bir üçgen
oluşturmak zorundayız. Farzedelim ki, WM ve MR doğru parçalarının orta noktaları
sırasıyla, C1 ve C2 olsun. (Şekil 3) Daha küçük fonksiyon
değerine sahip olan nokta C noktasıdır ve yeni üçgenimiz BCG üçgenidir.
Not: C1 ve C2 noktaları arasındaki
seçim 2 boyutlu durum için uygun olmayan bir halde gözüküyor olabilir fakat
daha çok boyutlu durumlar için önemlidir.
HER ADIM İÇİN MANTIKLI KARARLAR
Sadece gerektiği hallerde bir hesaplamayla yeterli
algoritma, fonksiyon değerlendirme uygulamalarını yapmalıdır. Her bir adımda W ile yer
değiştirme yapacak olan yeni tepe noktası değerleri bulunur. Bulunabildiği yani
daha ileri araştırmaya ihtiyaç duyulmayıncaya kadar ve iterasyon adımları
tamamlanıncaya kadar işlemlere devam edilir. İki boyutlu durumlar için
ayrıntılı mantıklı adımlar Tablo 1’
de verilmiştir.
Örnek:
Nelder – Mead metodunu kullanarak f(x,y)=x2-4x+y2-y-xy fonksiyonun minimum
noktasını bulun. Aşağıdaki V1,V2,V3
köşe noktası değerleri ile başlayın.
V1=(0,0) V2 = (1.2,0.0) V3 = (0.0,0.8)
Bu değerler için f(x,y)
fonksiyonu aşağıdaki değerleri aldırır.
f(0,0)=0.0 f(1.2,0.0)=-3.36 f(0.0,0.8)=-0.16
B,G,W noktalarını belirlemek için fonksiyon değerleri
karşılaştırılmalıdır.
B=(1.2,0.0) G=(0.0,0.8) W=(0,0)
W=(0,0) değeri yer
değiştirilecektir. M ve R noktaları;
M = (B+G)/2 = (0.6,0.4) R
= 2M – W = (1.2, 0.8)
R fonksiyonunun değeri f (R) = f (1.2,0.8 ) = -4.48
, f(G) değerinden azdır dolayısıyla
1. durum geçerlidir.
f ( R ) ≤ f ( B ) sağ yöne taşırız ve E noktasının tepe değeri
şu şekilde oluşturulmalıdır:
E = 2R-M = 2(1.2,0.8) -
(0.6,0.4) = (1.8,1.2)
f(E) =
f(1.8,1.2)=-5.88 fonksiyonunun değeri F(B)
değerinden azdır ve yeni üçgen aşağıdaki tepe noktası değerlerini alır.
V1=(1.8,1.2) V2=(1.2,0.0) V3=(0.0,0.8)
Bu süreç devam eder ve çözüm noktası (3,2) noktasına yaklaşan bir üçgenler
dizisi oluşturur. Tablo 8.4’te iterasyonun bir çok adımı için üçgenin tepe
noktalarındaki fonksiyon değeri verilmiştir. En iyi B tepe noktası ve f(B)
değerleri sırasıyla B=(2.99996456,1.99983839)
ve f(B) =-6.99999998 değerlerine
ulaşıncaya kadar 33 adım boyunca algoritmanın bilgisayar uygulaması devam eder.
Bu değereler 8.3 örneğinde f(3,2) =-7
değerlerine yaklaşık değerlerdir.
Hiç yorum yok:
Yorum Gönder