Nelder Mead Algoritması ve Sınırlandırılmış Optimizasyon

Utku Kubilay ÇINAR 1 Şubat 2019 Yeni Başlayanlar 0 4160 1642 kelime - 11 dakika109

Bu yazıya puan ver

(No Ratings Yet)

Nelder Mead Algorithm and Constrained Optimization in R

Nelder Mead Algoritması, simplex yöntemine dayalı, birkaç doğrudan aramayı sağlayan optimizasyon algoritmalarından biridir. Bu algoritmalar, “en iyi noktayı arayan” algoritma olarak özetlenebilir.

Nelder Mead Algoritması, tek bir simplex güncellemesine dayanır. Aşağıdaki algoritmalar Nelder Mead Algoritması çeşitleridir:

Spendley,
Hext,
Himsworth’un sabit şekil simpleks yöntemi.

Bu algoritma, Nelder ve Mead tarafından oluşturulan birkaç değişken içeren fonksiyonun yerel minimum noktasını/noktalarını bulmak için kullanılan bir simplex yöntemdir. Nelder Mead yöntemi, iki değişken için simplex bir üçgen oluşturur ve bu üçgenin, köşe noktalarındaki fonksiyon değerlerini karşılaştırır. Böylece optimum nokta bulunmuş olur. (Taylan, H.)

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/büyültülür ve minimum noktanın koordinatları bulunur. Algoritma, simplex terimini kullanarak oluşturulmuştur ve N tane değişkenli (N boyutta genelleştirilmiş bir üçgen) fonksiyonun minimum noktalarını buldurur. Bu şekilde bir hesaplamayla oluşturulmuş etkili bir çözümdür. (Taylan, H.)

Geniş bir tanım aralığı içerisinde tesadüfi olarak atanan değişken değerleriyle hatalı sonuçlar elde etme ihtimali artacağından, bu çalışmada tesadüfi atanan değişken değerleri Nelder-Mead algoritması ile lokal en iyi komşuya doğru yaklaşacak şekilde değişmektedir.

Fonksiyon değerinin en büyük olduğu, en kötü köşe reddedilir ve başka bir köşeyle yer değiştirilir. Yeni üçgen biçimlendirilir ve tekrar arama devam eder. Köşelerdeki fonksiyon değerleri ve üçgenin alanı gittikçe küçülür.

Kaynak: T. Cura / İstanbul Üniversitesi İşletme Fakültesi Dergisi 37, 1, (2008) 22-38

Bu şekilde en iyi nokta belirlenmiş olur ve optimizasyon tamamlanır. Her değişken için tanım aralığı içerisinde yer alacak şekilde üç farklı tesadüfi nokta seçilir. Değişken çiftleri Nelder-Mead metodu için başlangıç üçgenini oluşturmuş olacaktır.

Her yenilemede, noktalar bir polytope (bir dizinin boyutunun artması, iki boyut için çokgen, üç boyut için polihedron(çok yüzlü)) oluşturur. Noktalar, en kötü noktayı değiştirmek için yeni bir nokta üretilecek şekilde atanır.

En iyi noktalardan oluşan doğrular, çokgenin merkezini oluşturur. Bu merkez, en kötü noktaların merkez noktası üzerinden yansıtılmasıyla üretilir. Yani gelen her nokta ile merkez değişiyor, kötü noktalar eleniyor ve yeni nokta aranıyor.

Yeni gelen nokta, mevcut en iyi noktadan daha iyi ise, yansıma çok başarılıdır. Genişleme de başarılı olursa, nokta yerini alır. Aksi halde genişleme başarısız olursa, aynı yansıma farklı noktalar üstünden denenir.

Yeni ve eski polytope’deki en iyi fonksiyon değerleri arasındaki fark ve yeni en iyi nokta ile eski en iyi nokta arasındaki mesafe minimuma indiğinde yapılan işlemlerin doğru ilerlediğini ve optimum sonuca ulaştığını söylemek mümkündür.

Kaynak: http://www.palamedestoolbox.org

Nelder Mead Algoritması ve Sınırlandırılmış Optimizasyon Uygulamaları

Doğrusal Olmayan Programlama, Nelder Mead Algoritması – Örnek 1-

Bir şirket aynı iki kaynağı kullanarak iki farklı ürün üretmektedir. 1. ürünü (X1) üretmek için gerekli olan 1. kaynağın maliyeti 8 TL ve 2. kaynağın maliyeti 7 TL’dir. 2. ürünü(X2) üretmek için gerekli olan 1. kaynağın maliyeti 3 TL ve 2. kaynağın maliyeti 6 TL’dir. Tedarikçiler haftada 1. ürün için 1200 TL ve 2. ürün için 2100 TL kaynak sağlamaktadır. Şirket üretilen tüm ürünleri satabilir ancak bu satış fiyatı her iki ürüne de bağlı olduğu belirtilmiştir. 1.ürünün kar fonksiyonu 800-X1-X2 (üretilmiş birim başına fiyat), 2.ürünün kar fonksiyonu 2000-X1-3X2(üretilmiş birim başına fiyat) ise Şirketin karını maksimum yapmak için her hafta ne kadar ürün üretilmelidir ?

Not: Bu örnek Mathematica programı üzerinden çözülmüştür.

Öncelikle kısıtlarımızı belirleyelim. Kısıtlarımız;

8*X1 + 3*X2 ≤ 1200

7*X1 + 6*X2 ≤ 2100

X1 ≥ 0 ve X2 ≥ 0 olacak şekilde kısıtlarımız belirlenir.

Amaç fonksiyonumuz;

Z = (800-X1-X2)*X1 + (2000-X1-X2)*X2 şeklinde olmalıdır.

Çıktımıza göre optimum değer için X1’i 102, X2’nin değerini ise 126 seçtiğimizde problemi NelderMead Kısıtlı Lineer Olmayan Optimizasyon yöntemi ile çözmüş oluruz. Optimum değerimizin ise 249 864 olmuş olduğunu görmüş olduk.

Genel eğilimi görmek için kritik noktalardan daha büyük değerlerle çözüm grafiğine bakalım. Böylelikle büyük resmi görmüş olacağız.

İlk grafiğe bakıldığında eğimli-kıvrılmış bir yapı görüyoruz. Bizim bulduğumuz 102 ve 126 noktaları grafiğin zirve yaptığı değerlerdir. Alttaki grafikte ise bizim amaç fonksiyonumuzun maksimum olduğu yere kadar aldığı değerleri görüyoruz ve bu zirveden sonra amaç fonksiyonumuzun değeri gittikçe azaldığını ilk grafikten öğrenmiş oluyoruz.

Doğrusal Programlama, Sınırlandırılmış Optimizasyon – Örnek 2-

Kendimiz bir problem oluşturacağız bu örneklerde. Problemin hikaye kısmını siz değerli ve pek kıymetli okuyucularıma bırakıyorum. Bir problemimiz olsun. Kısıtlarımız ve minimize edilecek amaç fonksiyonumuz aşağıdaki gibi olmuş olsun. Şimdi bu problemi çözmeye başlayalım.

Çözümü R programında “lpSolveAPI” kütüphanesi yardımıyla yapalım. Bu kütüphanede istediğiniz kısıtı “add.constraint()” fonksiyonu ile modele belirtiyoruz. “make.lp()” fonksiyonu ile programa oluşturacağımız modelde 3 farklı değişken olduğunu belirtiyoruz (x,y,z ya da 1. kaynak, 2. kaynak, 3. kaynak gibi). “set.objfn()” fonksiyonunun içine ise amaç fonksiyonun katsayıları yazılır. Gerisini R programı bize veriyor.

Çıktılarda görüldüğü üzere, kısıtımızı sağlayan değerler C1=11.66, C2=0, C3=0 değerlerinde problemimiz minimum noktaya ulaşacaktır.

Doğrusal Programlama, Sınırlandırılmış Optimizasyon – Örnek 3-

Bu sefer oluşturacağımız örneği farklı bir yolla çözelim ve kısıtımızda eşitlik olsun.

Kısıtlı optimizasyonumuzu “Rsolnp” kütüphanesi yardımıyla çözelim. Bunun için öncelikle amaç fonksiyonunu yazıyoruz, ardından kısıt fonksiyonu yazılır ve bir değere eşitlenir. Ardından model oluşturulur.

Çıktımızda görüldüğü üzere X=X[1] değerini 23.9 ve Y=X[2] değerini -9.778 seçtiğimizde amaç fonksiyonu minimize edilmiş olur ve elde edilen minimum değer (kısıtın izin verdiği alanda) ise -10.8586 olmuş olur.

Doğrusal Olmayan Programlama, Sınırlandırılmış Optimizasyon – Örnek 4-

Problemimizin kısıtı bu sefer bir aralık olsun. Kısıtımız 11 ile 40 değerleri arasında olmuş olsun.

Amaç fonksiyonuna bakıldığında doğrusal olmadığı (Non-Linear Programming Optimization) görülür.

Çıktı incelendiğinde 6 denemede programımız sonucu buldu. X değerine 3.15, Y değerine ise 1.02 verildiğinde hem kısıtımız sağlanıyor hem de amaç fonksiyonu minimum oluyor. Amaç fonksiyonumuzun minimum değeri ise 66.23 olarak bulmuş olduk.

Siz değerli ve pek kıymetli okuyucularıma ve optimizasyon konularına ilgi duyanlar için R programında kullanabilecekleri fonksiyonları – kütüphaneleri – yöntemleri belirtmek isterim. Literatür taraması yaparken bu görsel ile karşılaştım, işinize yarayacağını ve faydalı olacağına inanıyorum.

Optimizasyon problemlerinin günümüzde çok önemli bir yeri vardır. Aslında bir nevi her şey optimizasyondur. Akşam ne yiyeceğimizden, eve giderken kaç tane ekmek alacağımıza kadar. Algoritmaları nasıl hızlandırabilirizden askeri teknolojilere kadar. Aslında temel soru; elimde neler var, neleri yapabilirim(neleri yapmama izin var-kısıtlarım neler) ve yapmak istediğim şeyin amacı ne ? Tüm bu sorular optimizasyondur. Verilen şartlar altında en iyi-doğru sonucu elde etme yoludur. Optimizasyon bir nevi model kalibrasyonudur. Yöneylem araştırmalarında, yazılımda, şirketlerin satış-üretim-lojistik-AR-GE birimlerinde ve bu gibi daha birçok alanda istatistikle beraber kullanılır.

Not: Nelder Mead algoritmasını ya da Sınırlandırılmış Optimizasyonu, Yıldız Teknik Üniversitesi’nde Lisans ve Yüksek Lisans derslerim olan Optimizasyon-Lineer Olmayan Programlama-Yöneylem Araştırmaları ve özellikle Uygulumalı Optimizasyon derslerinde işlemiştik. Uygulamalı Optimizasyon dersinde kıymetli hocam bu konunun önemli olduğunu söylemişti ve optimizasyon üzerine uzun bir konuşma yapmıştık. Bu konuşma, optimizasyonun önemini anlamam konusunda epey işime yaradı. Gerek ödevlerimde, gerek iş yerimde karşılaştığım sorunların çözümünde bakış açımı değiştirdi. Zamanla optimizasyon becerilerimi ve kodlamalarımı geliştirerek bu içeriği sizlere sunuyorum. İşbu sebeplerden dolayı, özetin özeti düzeyinde diyebileceğim kendi çalışma içerik bilgilerimi sizlerle paylaşmak istedim.

Bu yazı sayesinde birçok öğrencinin ödevlerine de yardımcı olacağıma inanıyorum. 🙂

Varsayımlarınızın sağlanması dileğiyle,

Veri ile kalın, Hoşça kalın..