Nelder-Mead Metodu

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.

İYİ KENARIN ORTA NOKTASI

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

E NOKTASINI KULLANARAK UZATMA

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 

C NOKTASINI KULLANARAK KISALTMA

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.