Merhabalar, bu yazıda optimizasyonun giriş konularından olan ve yerel maksimum-minimum noktalarının bulunmasını amaçlayan aralığa alma metodundan bahsedeceğim. Daha önceki yazımda aynı amacın farklı bir yöntemi olan quadratic approximationdan bahsetmiştim. Okumak isterseniz buradan erişebilirsiniz.
Aralığa alma metodu, belirli bir aralıktaki yerel maksimum ve minimumun bulunması için bu aralıkta değişken adım uzunluklarıyla gezinilen ve bu gezinme esnasında elde edilen yeni noktadaki güncel değerle önceki değerin karşılaştırıldığı bir yönerge izler.
Amaç yerel ekstremum noktasının bulunması olduğundan bu ekstremumun genel olarak nerelerde aranacağına karar vermek oldukça önemlidir. Bu sebeple bu ekstremum noktanın bulunduğu kabaca bir aralık edinmek yöntemdeki ilk adımdır. Varsayalım ki f(x) fonksiyonunun a noktasında bir yerel maksimumu mevcut ve x ≥ a olsun. Daha önce bu yöntemde değişken adım uzunlukları ile elde edilen yeni noktalarda gezinmekten bahsetmiştim. Bu adım uzunluğu başlangıç için h olsun. x₁ = a, x₂ = x + h, x₃ = x₂ + 2h, x₄ = x₃ + 4h… olmak üzere yeni nokta değerleri her adımda, adım uzunluğu ikiye katlanarak tayin edilir. ( Bu durumda algoritmanın koşturulmasındaki her iterasyon için yeni nokta değerleri, x₁ = a, x₂ = x + h, x₃ = x₂ + 2h, x₄ = x₃ + 4h… şeklinde hesaplanır.)
Bir yerel maksimumu ararken o noktanın, bölgesindeki en büyük değer olduğunu biliriz. Bu sebeple f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) olmak üzere yerel maksimum değerimizin xi-1 ve xi+1 noktaları arasında bir yerde olduğunu söyleyebiliriz. Öyleyse aralığımız (xi-1, xi+1) diyebiliriz.
Artık yerel maksimum noktamızı bu aralıkta daha küçük adımlarla arayabiliriz. Adım uzunluklarımızı küçültmeme durumunda aralığı aşarız. Sonuçta kaba bir tahminden kesin bir noktaya doğru gitmemiz gerekiyor.
Aslında bu aşamada yöntemin algoritmasını da çıkarmış olduk. Özetlemek gerekirse bir başlangıç aralığı ve adım uzunluğu belirleyip sonrasında yeni noktaları x₁ = a, x₂ = x + h, x₃ = x₂ + 2h, x₄ = x₃ + 4h… olacak şekilde hesaplıyoruz. Bulduğumuz bu yeni x noktalarında fonksiyonun değerini hesaplıyoruz. Fonksiyonun değerini elde ettiğimiz anda f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) ifadesinden faydalanabilir hale geliriz. Bu ifadede görüyoruz ki xi, xi-1 ve xi+1 olmak üzere 3 nokta mevcut. Dolayısıyla bir iterasyon için 3 adet x noktasını bilmek ve bu noktalarda fonksiyonun değerini hesaplamak bizim için yeterli olacaktır. Bu değerleri hesapladıktan sonra yapılması gereken tek şey belirli durma koşulları gerçekleşene kadar iteratif olarak f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) koşulunu sağlayan (xi-1, xi+1) aralıklarını bulmak olacaktır.
Peki nedir bu durma koşulu? Her epochta aynı h (adım uzunluğu) değeri üzerinden bir döngüye gireriz. İşte bu döngü j. epochtaki aralığı bulmak içindir. Bir aralık bulunduğunda epoch tamamlanır. Bir sonraki epochta, bir başka ifadeyle güncel aralığa dahil daha küçük aralığı bulurken adım uzunluğu kısaltılır. Aralığın bulunması iterasyonlar içerisinde gerçekleşir. Bu iterasyonun durma koşulu ise hesaplanan xi+1 değerinin, bir önceki aralığın kapanış değerinden büyük eşit olmasıdır. Sonuçta bulduğumuz bu noktanın aralığımızın içerisinde yer alması gerekir. Eğer hesapladığımız yeni nokta aralık değerini aşıyorsa bu bize arama için daha küçük adımlarla çalışmamız gerektiğini söyler. Dolayısıyla bu durma koşulu gerçekleştiği anda son hesaplanan aralık değerini kapsayan yeni bir süreç başlatılır ve algoritma daha küçük adım uzunluğuyla yeniden yürütülür.
Peki tüm algoritmanın durma koşulu nedir? Ne zaman aradığımız noktayı bulduğumuzu varsayabiliriz? Algoritmanın sonlanması için şu 3 bilgi kullanılabilir: Epoch sayısı, iterasyon sayısı, aralık boyutunun genişliği. Epoch veya iterasyon sayısı belli bir değer ile limitlendirilebilir ve bu değer aşıldığında algoritmayı sonlandırılabiliriz. Bir başka ve daha önemli sonlandırma kriteri ise aralık boyutunun yakınsama değeri. Algoritmada belirleyeceğimiz bir epsilon değeri ile aralığımızın artık yeterince daraldığını ve yerel maksimum noktasına oldukça yakınsadığımızı varsayabiliriz.
Şimdi tüm bu bilgiler ışığında bir örnek üzerinden algoritmayı koşturalım ve de kodlayalım. Kodladıktan sonra program çıktıları üzerinden algoritmamızın çalışma yapısını gözlemleyebiliriz ve doğruluğunu teyit edebiliriz.
Algoritmayı Gerçekleme ve Kodlama:
Örnek Fonksiyon: tanh(x)/1 + x² olsun.
Görüyoruz ki fonksiyonun (0,2) aralığında bir yerlerde yerel maksimum değeri bulunmakta.
Algoritmayı koşturmak için örnek değerlerimiz şu şekilde olsun. a: 0 (x başlangıç değeri), h: 0.1.
İlk olarak 3 adet x noktasına ve bu noktalardaki fonksiyon değerlerine ihtiyacımız var. Bu değerleri x₁ = a, x₂ = x + h, x₃ = x₂ + 2h, x₄ = x₃ + 4h… şeklinde hesaplıyorduk. Bu bilgilerden ve verilen değerlerden yola çıkarak:
x₁ = 0.1, f(x₁) = 0.0986
x₂ = 0.1+ 0.1 = 0.2, f(x₂) = 0.1897
x₃ = 0.2+ 2*(0.1) = 0.4, f(x₃) = 0.327
şeklinde ihtiyacımız olan noktaları buluruz. Bu aşamada elimizdeki diğer bilgiden faydalanıyoruz. f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) koşulu sağlanıyor mu?
0.1897 > 0.0986 ve 0.1897 < 0.327 olduğundan aralığımız koşulu sağlamamakta o halde yerel maksimum noktamız (x₁, x₃) bir başka deyişle (0.1, 0.4) aralığında bir yerde değil. (Peki koşul sağlansaydı? Bu durumda bu aralık değerimizi atayıp bir sonraki epochta adım uzunluğunu küçülterek aynı işlemlere tekrar başlayacaktık.)
f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) koşulunu sağlayan x değerlerini ve buna bağlı olarak aralığımızı bulana kadar yeni nokta hesaplamaya devam etmemiz gerekir.
Aralık bulma eylemini sonlandırma kriterimiz, aralığın kapanış değerinin bir önceki aralığın kapanış değerinden daha büyük olmasıdır. Dolayısıyla yeni aralık noktasını bulurken bu bilgiden faydalanacağız. Eğer yeni aralık değerimizi hesaplarken bulduğumuz yeni x noktası bu aralığın dışında olarak hesaplanıyorsa adım uzunluğunu küçülterek devam edeceğiz.
Devam edelim, son olarak x₃ değerini hesaplamıştık ve bir aralık bulamamıştık.
Bir sonraki değer x₄ = x₃ + 4*(0.1) = 0.4 + 0.4 = 0.8, f( x₄) = 0.4049
Şimdi hesapladığımız son 3 x değeri, x₂, x₃, x₄ oldu. Bu noktalarda f değerleri sırasıyla 0.1897, 0.3275, 0.4049. Tekrar yerel maksimum koşulu kontrol ediyoruz (f(x₃) ≥ f(x₂) ve f(x₃) ≥ f(₄) mü?) 0.3275 > 0.1897 ve 0.3275 < 0.4049 olduğundan yerel maksimuma uygun değildir dolayısıyla yeni nokta hesaplamaya devam ederiz.
Bir sonraki adımda x₅ = x₄ + 8*(0.1) = 1.6, f(x₅) = 0.2589 olarak hesaplanır.
Son hesaplanan değerler için x₃, x₄, x₅, f(x₄) ≥ f(x₃) ve f(x₄) < f(x₅) kontrolü yapılır. 0.4049 > 0.327 ve 0.4049 >0.2589 olduğundan yerel maksimum koşulu sağlanır ve aralık değeri (x₃, x₅) = (0.4, 1.6) olarak bulunur. Artık bir aralık değeri hesapladığımızdan yeni bir epocha geçebiliriz. Burada en önemli durum adım uzunluğunun küçültülmesidir. Adım değeri, her adımda 0.1 katı olarak güncellenebilir. Aralığın bulunamadığı iterasyonlarda ise hesaplanan xi+1 değerinin bir önceki aralığın kapanış değerinden büyük eşit olması koşuluna bağlı olarak yeni bir epocha geçilebilir.
Her yeni epochta aralığın başlangıç değeri x₁’miş gibi düşünülerek aynı işlemler tekrar edilir. Bu algoritma koşturması epsilon farkı, iterasyon ve epoch sayısı kriterlerinden biri veya birkaçı gözetilerek durdurulur. Son hesaplanan aralığın kapanış değeri yerel maksimum noktası olarak kabul edilir.
Şimdi algoritmamızı kodlayabiliriz.
Kodlama
Örnek fonksiyonumuzun yerel maksimum değeri yaklaşık olarak x ≈ 0.406531 noktasında ≈0.741596 şeklindedir.
İlk döngü epochları, ikinci döngü ise iterasyonları kontrol etmek içindir. Başlangıç için aralık başlangıç ve bitişi (0,0) olsun. Bu programda durdurma koşulu aralık boyutunun epsilona yakınsaması olacak.
if (range_start != 0 and range_stop != 0):x_start = range_startx_vals = [None,None, None]y_vals = [None,None, None]h = h / 10
Kısmı ilk koşturma esnasında h değerinin azaltılmaması için bir koşul. Çünkü adım uzunluğu ilk aralığı bulduktan sonra küçültülmeli. Ayrıca her epoch için x ve y (fonksiyonun x noktasında aldığı değer) değerleri resetlenir. Çünkü her bir epochta yeni adım uzunluğu ile yeni x değerleri ve buna bağlı olarak da y değerleri hesaplanmalı.
Sonrasında her iterasyonda x₁ = a, x₂ = x + h, x₃ = x₂ + 2h kuralını oluşturacak bir katsayı ile (inc = 2**i) x ve y değerleri hesaplanır. x_vals[0] = x_vals[1] if (x_vals[1] != None) else round(x_start, 5) buradaki koşulun anlamı ise şudur: eğer yeni bir epocha girilmişse ve ilk iterasyon koşturuluyorsa ilk 3 değer hesaplanmak zorundadır. Fakat sonraki iterasyonlarda son 3 değer kontrol edileceğinden kaydırma yapılır.
Örneğin x₁, x₂, x₃’ bağlı olarak yerel maksimum kontrolü yapıldı. (if(y_vals[1] > y_vals[0] and y_vals[2] < y_vals[1])) Bir sonraki iterasyonda x₄ hesaplanarak x₂, x₃, x₄ üzerinden kontrol gerçekleştirilecektir. Dolayısıyla zaten hesaplanmış olan x₂ ve x₃ değerini hesaplamaya gerek yoktur. Kaydırma ile baştan x₁ çıkarılıp sona x₄ koyulur. Dolayısıyla burada queue veri yapısı kullanılması uygun olabilir. Çünkü burada bir FIFO yönetimi vardır. Kod iyileştirmeye açık.
x değerleri hesaplandıktan sonra aynı şekilde y değerleri de hesaplanır. Ve aynı kaydırma işlemi y değerleri için de geçerlidir.
Ve son olarak algoritmanın özü olan:
if(y_vals[1] > y_vals[0] and y_vals[2] < y_vals[1]):range_start = x_vals[0]range_stop = x_vals[2]break
Kısmında f(xi) ≥ f(xi-1) ve f(xi) ≥ f(xi+1) koşulu kontrol edilir. Eğer bu koşulu sağlayan değerler ile çalışıyorsak aralık (xi, xi+1) olarak atanır. Fakat eğer bu koşul sağlanmıyorsa bu koşulu sağlayan x değerlerini bulana kadar iterasyon for döngüsü içerisinde devam eder. Peki bu for döngüsü sonsuza kadar mı çalışır? Hayır, bu döngü, yazının önceki bölümlerinde de bahsedildiği gibi yeni bulanan x değeri bir önceki aralık değerinin kapanış değerinden daha büyükse biter. Ve daha küçük adım uzunluğuyla yeni bir epoch başlatılır. Aşağıda bunu kontrol eden koşul mevcuttur.
if(x_vals[2] >= range_stop and range_stop != 0): breakAşağıda ilgili kodun 2 farklı değer seti ile ürettiği sonuçlar bulunmaktadır.
Peki yerel minima değerleri nasıl bulunur? Yerel minima değerleri için algoritma neredeyse tamamen aynıdır sadece matematiksel olarak yerel maksimum olma koşulunun yerini yerel minimum olma koşulu alır.
Bir başka deyişle yerel minimumda, f(xi) ≤ f(xi-1) ve f(xi) ≤ f(xi+1) olmalıdır.
Tüm kodlara buradan erişebilirsiniz. Iterasyon ve epoch kontrolü eklenebilir. Alternatif fonksiyon değeri ile çalıştırabilirsiniz. Verilen adım uzunluğu ve x başlangıç değerlerinin ilk aralığa uygun olması gerektiğini unutmayalım.
Kaynak:
Studies in Optimization: D. M. Burley
