:::: MENU ::::
İncelemeler

XOR-based artifi cial bee colony algorithm for binary optimization

“XOR-based arti ficial bee colony algorithm for binary optimization” başlıklı çalışma Mustafa Servet KIRAN ve Mesut GÜNDÜZ tarafından yapılmış olup “Turkish Journal of Electrical Engineering & Computer Sciences” dergisinde 2013 yılında basılan 21.sayısının 2307-2328.sayfalarında basılmıştır.

Zhu ve Kwong [G. Zhu, S. Kwong, “Gbest-guided artifi cial bee colony algorithm for numerical function algorithm”, Applied Mathematics and Computation, Vol. 217, pp. 3166{3173, 2010.] PSO’dan esinlenerek ABC algoritmasına gbest parametresini ekleyerek exploitation(sömürü) kapasitesini artırmışlardır.

Kashan ve arkadaşları [M.H. Kashan, N. Nahavandi, A.H. Kashan, “DisABC: a new arti cial bee colony algorithm for binary optimization”, Applied Soft Computing, Vol. 12, pp. 342{352, 2011.] discrete arti cial bee colony (DisABC) ismini verdikleri ikili bir algoritma önermişlerdir.

Kapasitesiz tesis yeri seçimi problemi (KTYP), üzerinde en çok çalışılan tesis yeri seçimi problemlerinden birisidir. KTYP, aday tesisler arasından tesis açma sabit maliyeti ve açılan tesislerden müşteri taleplerini karşılama maliyeti toplamını en azlayacak şekilde açılacak olan tesislerin bir kümesinin belirlenmesi problemidir. KTYP, NP-zor problemler sınıfında yer aldığından dolayı bu problemin çözümü için literatürde genel amaçlı sezgisellere dayalı çeşitli algoritmalar geliştirilmiştir.

ABC algoritmasının temel adımları:

abc-1

Belirlenen aralıkta rastgele değerler üretilerek popülasyon oluşturulur. R=0-1 aralığında rastgele bir sayıdır.

abc-2

Her işçi arı(çözüm) için fitness hesabı yukarıdaki formüle göre yapılır. Amaç fonksiyona göre f değişmektedir. Eğer f değeri sıfırdan küçükse mutlak değer alınarak 1 eklenmektedir. f, 0’a eşit veya büyükse 1/1+f formülüyle sonuç hesaplanır.

abc-3

Her işçi arı kendi çözümünü iyileştirmeye çalışmaktadır. Yukarıdaki formüle göre üretilen aday çözüm mevcut çözümden daha iyiyse yer değişimi yapılır. Her iterasyonda popülasyondan rastgele seçilen komşu çözümün ilgili tek boyutuyla mevcut ilgili tek boyut üzerinden işlemler yapılır. Aday çözüm daha iyi çıkmaz ise terk sayacı(abandonment counter) bir artırılır.

abc-4

Gözcü arılar kovana gelen işçi arılardan yukarıdaki formül sayesinde kaynakların durumu hakkında bilgi almaktadır. Burada bir olasılık hesabı yapılmaktadır. Bir arının olasılık değeri kendi fitness değeri ile 0,9’un çarpımının en iyi fitnesa bölümü sonucu elde edilen değere 0,1 eklenmesiyle bulunur.

Terk sayacı limit değere ulaşmış bir işçi arı kaşif(scout) arıya dönüştürülür. Mevcut işçi arı sistemden çıkar kaşif arı rastgele bir çözümle sisteme dahil olarak yeniden işçi arı olur. Terk sayacı sıfırlanır. Her iterasyonda sadece 1 kaşif arı oluşabilir.

ABC algoritmasının çerçevesi:

abc-algorithm

binABC Algoritması

Problemin çözüm uzayı ikili yapılandırılmış şekilde ise binABC algoritması kullanılabilir.

Burada fabrikanın açık olma durumunu 1 kapalı olma durumunu 0 olarak düşünebiliriz.

binabc-1

Üretilen rastgele bir sayı 0,5’ten küçükse 0, büyükse 1 değeri döndürülür.

ABC’nin aday çözüm üretme formülü aşağıdaki şekilde yeniden yapılandırılır.

binabc-2

Logic operator olarak AND, OR ve XOR kullanılabileceği belirtildikten sonra çalışmada neden XOR kullanıldığı aşağıdaki şekilde açıklanmıştır.

binabc-3

Tablolar incelendiğinde görülecektir OR kullanıldığı zaman %75 1 sonucu AND kullanıldığı zaman %75 0 sonucu üretilmektedir. XOR kullanımında ise 0 ve 1 sonuçları yarı yarıyadır. XOR değişme olasılığı daha uygundur.

BPSO(Binary PSO) Algoritması

Parçacıkların hızları temel algoritmadaki formülle hesaplandıktan sonra:
bpso-1

Üretilen rastgele sayı, parçacığın hızının Sigmoid fonksiyonunun sonuç değerinden küçükse 1 diğer durumlarda 0 üretilir.

PSO’ya Shi and Eberhart [Shi, Yuhui, and Russell Eberhart. “A modified particle swarm optimizer.” Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on. IEEE, 1998.APA] tarafından inertia weight (w) parametresi eklenmiştir.

DisABC Algoritması
KASHAN, Mina Husseinzadeh; NAHAVANDI, Nasim; KASHAN, Ali Husseinzadeh. DisABC: a new artificial bee colony algorithm for binary optimization. Applied Soft Computing, 2012, 12.1: 342-352.

Mevcut arı ile komşu arı arasındaki farklılığı esas alarak bir hesaplama yapar.

disabc-1

m01 Xij = 0 ve Xkj = 1 olduğu durumların sayısını verir.
m10 Xij = 1 ve Xkj = 0 olduğu durumların sayısını verir.
m11 Xij = 1 ve Xkj = 1 olduğu durumların sayısını verir.

Aynı şekilde aday çözüm içinde gerekli hesaplamalar yapılır.

M01 Vij = 0 ve Xij = 1 olduğu durumların sayısını verir.
M10 Vij = 1 ve Xij = 0 olduğu durumların sayısını verir.
M11 Vij = 1 ve Xij = 1 olduğu durumların sayısını verir.

dissimilarity

disabc-2

Yukarıdaki model kurulduktan sonra ilgili çalışmadan direk alınmış olan new binary solution generator (NBSG) ile çözüm aşağıdaki şekilde üretilir.

nbsg

NBSG algoritması aşağıdaki şekilde çalışmaktadır.

disabc-3

disabc-4

IBPSO Algoritması

BPSO ile temel farkı sürekli değerler almadan direk ikili değerler çözüm olarak alınmaktadır. Kısaca PSO sürekli uzayda, BPSO’nun hız değerleri sürekli uzayda, IBPSO’nun ise parçacık ve hız vektörü ikili uzayda hareket etmektedir.

ibpso

Çalışmada önerilen binABC algoritmasını kıyaslamak için UFLP probleminin kullanılma sebepleri şu şekilde izah edilmiştir.
1-UFLP saf binary bir problemdir ve içinde sürekli veya integer tipi değişkenler bulunmamaktadır.
2-Üretilen uygun olmayan çözümleri elemine etmeye ihtiyaç duymaz.
3-Test seti için optimal değerler mevcuttur.
4-Kıyaslanarak diğer algoritmalar bu problemi çözmüştür.

Çalışmada;

uncapacitated facility location test suit (15 test problems)
Kaynak: OR-Library [BEASLEY, John E. OR-Library: distributing test problems by electronic mail. Journal of the operational research society, 1990, 41.11: 1069-1072.]
4 problems Cap71-74 are small-sized,
8 problems Cap101-104 ve Cap131-134 are medium-sized,
CapA,CapB, ve CapC are large-sized

test-suite

Sonuçların analizi için kullanılan GAP parametresi aşağıdaki şekilde hesaplanmıştır.

gap

Yapılan araştırmalar sonucunda önerilen binABC için ideal popülasyon sayısının 40, limit değerinin ise D*N/4 olduğu açıklanmıştır.

BPSO algoritmasında kullanılan Sigmoid fonksiyonunun 6- ve 6 arasında değerler alabilen parçacıklara karşılık üretmiş olduğu 0-1 arasındaki değerler aşağıdaki gibidir.

sigmoid

İterasyona bağlı olarak inertia weight değeride aşağıdaki formüle göre düzenlenmiştir.

inertia-weight

Çalışmayı indirmek için:

xor-based-artificial-bee-colony-algorithm-for-binary-optimization


GEZGİN SATICI PROBLEMİ İÇİN SEZGİSEL METOTLARIN PERFORMANS ANALİZİ

“GEZGİN SATICI PROBLEMİ İÇİN SEZGİSEL METOTLARIN PERFORMANS ANALİZİ” başlıklı çalışma Mustafa GERŞİL ve Asil ALKAYA tarafından yapılmış ve XI. Üretim Araştırmaları Sempozyumunda 23-24 Haziran 2011’de sunulmuştur.

Çalışmada GSP; Evrimsel Algoritma, Benzetim Tavlaması ve Genetik Algoritma, Benzetim Tavlaması ve Rastgele Arama Algoritması çözülmüş, en iyi sonucu Evrimsel Algoritmanın verdiği belirlenmiştir.

Çalışmayı indirmek için:
gezgin-satici-problemi-icin-sezgisel-metotlarin-performans-analizi



Dynamic Diversity Control by Injecting Artificial Chromosomes for Solving TSP Problems

“Dynamic Diversity Control by Injecting Artificial Chromosomes for Solving TSP Problems” başlıklı çalışma Chang, P. C., Huang, W. H., Liu, J. Y. C., Chen, C., & Ting, C. J 2008 yılındaki IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence) kongrede sunulmuş ve çalışma 542-549. sayfalarda basılmıştır.

Lokal optimuma takıldığı noktalarda belirli bir eşik değer belirlenerek o değere ulaşıldığında popülasyonun ortalama değerlerine sahip yapay ajanlar eklenerek çözümün takıldığı noktadan kurtulmasını amaçlamaktadır.

Genetik algoritma komşuluk bazlı aramayı kullanan sezgisel yöntemlere göre daha geniş bir şekilde arama uzayını taramaktadır. Bunun yani sıra GA lokal optimumlarda takılmaya daha elverişlidir.

dlow ve dhigh olarak düşük ve yüksek çeşitlilik ortalamaları(diversity measure) belirlenmiştir. dlow’a düşüldüğünde dhigh’a yükselinceye kadar yapay ajan eklemesi yapılır. dhigh’a gelen sistem araştırma sürecine devam eder.

Popülasyon çeşitliliği evrimsel hesaplamanın performansı için esas noktadır.

ddcga

Population Diversity değeri belirtilen eşik değerinden büyükse klasik GA çalışır, küçük ve eşit olursa yapılan modifikasyon uygulanır.

Üretilecek yeni kromozomların seçimi için çiftleşme havuzundaki fitness değeri kabul edilebilir durumda olan en iyi 100 kromozon seçilir. Bu 100 kromozom temel alınarak oluşturulan kromozomlar üreme havuzuna enjekte edilir.

DDCGA algoritmasının sözde kodu:

ddcga-algorithm

Seçim işlemi rulet tekerleği prensibine göre yapılmaktadır.

Dominance matrix aşağıdaki şekilde oluşturulmuştur.

dominance-matrix

Olasılık matrisi:

probability-matrix

Çiftleşme havuzunda bulunan ana kromozom ile yapay kromozom arasında seçim yapılır. İyi olan kalır, diğeri silinir.

Diversity Measure aşağıdaki şekilde hesaplanmıştır:

diversity-measure

Literatürde 5 farklı çeşitlilik ölçme yaklaşımı(diversity measure approach) bulunmaktadır.

1-By Hamming Distance(Hamming Uzaklığı)
2-Euclidean Distance
3-Connection Matrix
4-Information Entropy
5-…

Düşük fitness ve diversity değeri olanlar süreçte elenmektedir. Böylelikle yüksek diversity ve fitness değerlerine sahip ana bireylerden oluşan yapay bireyler daha kaliteli sonuçlar üretmektedir.

KroA100 isimli GSP’ne uygulanan metodun sonuçları incelendiğinde düşük diversity değeri olanlar elendiği zaman daha başarılı olunduğu ortadadır.

archive-size

Archive size artırıldığı zamanda başarı artmaktadır.

Makaleyi indirmek için:

DynamicDiversityControlbyInjectingArtificialChromosomesforSolvingTSPProblems


Sayfalar:1...1213141516171819