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ı:

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

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.

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.

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:

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.

Ü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.

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.

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:

Ü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.

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.

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 algoritması aşağıdaki şekilde çalışmaktadır.

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.

Ç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

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

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.

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

Çalışmayı indirmek için:

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