» SOSYAL ZEKA TABANLI OPTİMİZASYON YAKLAŞIMI - 4

Yayinlanma Zamani: 2011-12-16 01:24:00





Eğer yalnızca tamsayılar ile ilgilenecek olursak bu durumda 0 ile 15 aralığındaki 16 nokta çözüm kümemizi ve 16 ile 30 arasındaki 15 nokta ise kısıta uymayan noktaları temsil eder. Dolayısıyla bu noktalar arasında kısıta uyan noktaların yakalanma olasılığı oldukça yüksektir. Tabi noktalarla birlikte kısıtlarında tamsayıya yuvarlanmış olmaları gerekir. Tüm bu hususlar dikkate alındığında hassasiyeti ilk iterasyonlarda düşük tutmak, daha sonra gittikçe arttırmak SZTO’nun bu yöntemde verimliliğini arttıracaktır. İlk iterasyonlarda tamsayılar arasından en iyisi seçilecek, daha sonra onlar mertebesine nilerek diğer noktalar araştırılacak ve bu süreç son iterasyonlara gelindiğinde arzu edilen hassasiyete ulaşacaktır. Böylelikle ilk iterasyonda en iyi noktaların saptana bilme olasılığı yükselecek ve parçacık sayısının aşırı arttırılmasına ve dolayısı ile çözüm süresinin uzatılmasına ihtiyaç duyulmayacaktır.
Bu teknik yazılımımızın genel model çözme algoritmasına uygulanmış ve olumlu  sonuçlar elde edilmiştir.
3.4.2. Penaltı Yöntemi
SZTO’nun kısıtlı modelleri çözebilmesi için geliştirdiğimiz tekniklerden bir tanesi de
penaltı model çözüm yöntemidir.
Ana hatlarıyla yöntem, belirtilen kısıtlar doğrultusunda çözüm kümesinde kalmalarını
sağlayacak cezalarla parçacıkları yönlendirmek ve karar verebilmelerini sağlamaktır. Bu
etki, amaç fonksiyonuna kısıtları sağlama becerisine göre minimum bir model ise
ekleme yaparak, maksimum ise de eksiltme yaparak gerçekleşir.
Çözüm uzayında rastsal dağılan parçacıklar, amaç fonksiyonlarını modelin içeriğine
göre minimum ya da maximum yapma eğilimindedirler. Bunun sağlanabilmesi için
normal SZTO mantığında olduğu gibi, herbir parçacığın hızı grubun en iyisi ve bireysel
en iyinin pozisyonundan etkilenerek değişir. Bu değişim ölçüsü ise az önce de
bahsettiğimiz gibi, amaç fonksiyoununun amaca ne kadar yakın olduğuna bağlıdır.

Penaltı yönteminin uygulandığı algoritmanın başlangıcında herbir parçacığın belirlenen
kısıtları ne ölçüde sağladığı belirlenerek amaç fonksiyonuna yansıtılır.
Aşağıdaki örnek üzerinden gidecek olursak:
Min X1 + X2 + X3 ;
X1 + X2 > 5
X2 + X3 = 4
‘ X1 + X2 + X3 minimum yapılmaya çalışılmaktadır. Bunu yaparken sağlanması
gerekli iki kısıtımız mevcuttur.
İterasyonlara geçmeden önce rastsal olarak çözüm uzayı üzerinde konumlandırılarak
yaratılmış parçacıklar, kısıtları sağlayıp sağlamamalarına göre araştırılmaktadır. Bunun
yapılması simplex algoritmasındakine benzer bir dönüştürme işlemi ile gerçekleştirilir.
Min X1 + X2 + X3 ;
X1 + X2 + S1 = 5
X2 + X3 + S2 = 4
Noktanın koordinatları kısıtları sağlamıyorsa ne kadar sağlamadığının tanımlanabilmesi
için bir bolluk değişkeni (S) kısıtlara eklenerek eşitlik sağlanır. Çünkü parçacıkların
hızlarının değişiminde bir etken olan rastsallık, kısıtların dışında hareket etmelerine
olanak sağlamıştır. Bunun önlenebilmesi ise eklenen değişkenlerin amaç fonksiyonunda
da değerlendirilmesine bağlıdır. Böylece parçacıklar kısıtlardan etkilenir.
Böylelikle, süreç içerisinde uyulması zorunlu kısıtları sağlamayan parçacıklar,
sağlamama değerlerine göre daha büyük bir amaç fonksiyonu değerine (amaç
minimuma ulaşmak olduğu için) sahip olacaklardır.

Min X1 + X2 + X3 + S1 + S2 ;
X1 + X2 + S1 = 5
X2 + X3+ S2 = 4
Dönüştürme işleminin ardından iterasyonlara geçilir. Bir iterasyon boyunca normal
sürü SZTO dışında, süreçte bazı farklılıklar mevcuttur. Bunlardan ilki, hesapanan amaç
fonksiyonu değerinin bir geçici değişkene aktarılarak, bu değişkenin kısıtları sağlama
ölçüsü oranında arttırılması suretiyle, herbir parçacığın grupsal en iyi ve bireysel en iyi
değerlerinin bu değişken üzerinden yapılmasına gidilmesiyken, bir diğeri ise, kısıtlara
ve amaç fonksiyonuna eklenen değişkenlerin çözüm uzayında bir başka boyut olarak
tanımlanmasıdır. Yani örneğimizde, 3 boyut varken , boyut sayısı 5 e çıkartılarak çözüm
aranır.
Boyutsal değişiklik yapıldıktan sonra, iterasyonlar başlatılarak her iterasyonda
algoritma, mevcut amaç fonksiyonu değerini kısıtların sağlanamamasına göre belli bir
oranda arttırır. Böylece kısıtların sağlanması bir zorunluluk haline getirilebilmiştir.
Algoritmanın temel mantığını açıklayacak olursak:
Dummy= f(X1,X2,X3)
İf X1 + X2 < 5 then dummy = dummy + dummy * S1 / S1başlangıç
İf X2 + X3 <> then dummy = dummy + dummy * S2 / S2Başlangıç .

İf dummy < GrupsalEniyiDeğeri then .....

GrupsalEniyiDeğeri=dummy

End if
İf dummy< bireyselEniyiDeğeri then......

BireyselEniyiDeğeri = dummy


End if,
şeklindedir.
Bu şekilde en iyi nokta seçimi için kısıtları sağlamaya zorlanan parçacıklar, verilen
fonksiyonu ilgili kısıtlar doğrultusunda çözüme ulaştırabilir. Bulunan sonuçlardaki
hatalar ise yaklaşık 10000 de 1 ler seviyesinde olup bu hatanın da iterasyon sayısı ve
grup sayısının arttırılması ile azaltılabileceği düşünülebilir.
Penaltı yöntemi ile SZTO algoritmasındaki zorluk çekilen bir husus ise, kısıtlara verilen
cezalar ile amaç fonksiyonunda katsayıları düşük olan (minimum problemi olduğunu
düşünürsek), yani atanması kuvvetle muhtemel değişkenler arasında bir ödünleşmenin
gerçekleşerek sonucu etkilemesidir. Bu ödünleşmenin engellenmesi, amaç fonksiyonuna
yüklenen bolluk değişkenlerin katsayılarının arttırılması ile mümkün olabilir. Böylece
kısıtların sağlanabilmesi daha olası bir durum olacaktır.
3.4.3. Huni Etkisi
Çözüm kümesinin çok küçük olduğu durumlarda bu uygulanabilecek bir diğer yöntem
bu çözüm kümesini komşu noktaların bir kısmını daha kapsayacak şekilde
genişletmektir. Ancak bu genişlik iterasyon sayısı ilerledikçe daralmalıdır ki kısıtlardan
sapma olabildiğince küçülsün. Yine Bölüm 3.3’deki örneği ele alacak olursak, amaç
fonksiyonumuz
3 * X1 - 2 * X2
ve kısıtımız ise
X1 + X2 < 15
iken, çözüm kümesi şekil 1’de görülmektedir.

 

Bu durumda klasik algoritmayı, kısıtı sağlamayan noktaların en iyi nokta olarak
atanmasına engel olacak şekilde değiştirerek gri bölge ile temsil edilen çözüm kümesi
içerisinde sonuç bulunabilir. Ancak eğer kısıt
X1+X2 < 15
yerine
X1+X2 = 15
olarak değiştirilir ise, bu durumda gri bölgedeki noktalar çözüm kümesinden çıkar ve
yalnızca kısıtı oluşturan denklem üzerindeki noktalar çözüm kümesi olur. Bu durumda
klasik algoritmanın kısıta uyan noktaları yakalama olasılığı çok düşük olduğundan
uygun noktalar ve dolayısı ile en iyi noktalar saptanamaz ve algoritma işlevselliğini
yitirir

Sonraki Konu :


Duyuru

Facebook sayfamiza üye olun


Duyuru
Sitemizde güncelleme çalismalari devam etmektedir.
Görüs ve önerilerinizi bizimle paylasabilirsiniz ! mail adresimiz : endustrimuhendisligi@hotmail.com