:::: MENU ::::
exploration

The Ant Lion Optimizer

“The Ant Lion Optimizer” başlıklı çalışma Seyedali Mirjalili tarafından yapılmış olup Advances in Engineering Software 83 (2015): 80-98.sayfaları arasında yayınlanmıştır.

The Ant Lion Optimizer (ALO) Karınca Aslanı Optimizasyonu

Bu alanda makale yazarken kullanılması gereken sihirli kelimeler:
-exploration
-local optima avoidance
-exploitation
-convergence

Karınca aslanı böceği karıncaları avlayarak yaşamını sürdürmektedir. Bu algoritma karınca aslanı böceği’nin avlanma şeklini modellemiştir.

Algoritmada karıncalar random walk şeklinde bir yürüyüş yapar.

500 iterasyon boyunca 3 farklı random walk davranışı yukarıda görülmektedir. Birinde yükseliş, birinde alçalış, birinde ise karmaşık bir hareket vardır.

İterasyonlar devam ederken rastgele yürüyüşün menzili daraltılır.
Bir karınca, karınca aslanından daha iyi amaç fonksiyonu değerine sahip olduğu anda yakalanmış sayılır ve karınca aslanı avının yerini alır.

Random walk, alt ve üst sınırları belirli uzayda kullanılmadığından min-max normalizasyonu ile kullanılması gerekmektedir.

x, random walk ile elde ettiğimiz vektör olsun.

Yukarıdaki komut ile x vektörünü -100,+100 aralığına normalize ediyoruz.

Karınca aslanının kurduğu tuzaklardan etkilenme işini aşağıdaki şekilde yapmaktadır:

min(Karinca(i,t))=KarincaAslani(j,t)+Min(Karincalar ve KarincaAslanlari)
t.iterasyondaki i.karıncanın en küçük değeri = t.iterasyondaki j.karınca aslanının değeri + en küçük değer
max(Karinca(i,t))=KarincaAslani(j,t)+Max(Karincalar ve KarincaAslanlari)
t.iterasyondaki i.karıncanın en büyük değeri = t.iterasyondaki j.karınca aslanının değeri + en büyük değer

Daha sonra karınca aslanlarına rulet tekerleği seçimi uygulanarak bir tanesi seçilir.

Min(Karincalar ve KarincaAslanlari) ve Max(Karincalar ve KarincaAslanlari) değerleri belirli bir oranda giderek azaltılmaktadır.

oran=10^w*t/T
t=mevcut iterasyon
T=toplam iterasyon
w iterasyona bağlı sabit
(w = 2 when t > 0.1T, w = 3 when t > 0.5T, w = 4 when t > 0.75T, w = 5 when t > 0.9T, and w = 6 when t > 0.95T).

w sabiti sömürünün doğruluğunu ayarlayabilir.

İterasyonlar sürecinde sömürü için süreç yukarıdaki gibidir.

Bu aşamadan sonra eğer karınca, karıncaaslanından daha iyi bir konumdaysa ilgili karınca, karıncaaslanı olur.

Algoritmada elitizm, en iyi karıncaaslanının konumunun tutulmasıyla sağlanır.

Karınca(i)=(Random(KarıncaAslanı)+Random(Elit))/2

Karıncalar, her iterasyonda rulet ile seçilmiş bir karıncaaslanının random walk yapmış hali ile elit karıncaaslanının randomwalk yapmış halinin toplamının yarısını alarak konumlarını günceller.

ALO’nun sözde kodu aşağıdadır:

Çalışmada iddia edilen bazı kazanımlar:
Rulet seçimi keşfi artırmıştır.
Rastgele yürüyüş keşfi artırmıştır.
Popülasyon tabanlı algoritmalar doğal olarak lokal optimumlardan kaçma kabiliyetine sahiptir.
Rastgele yürüyüş ile popülasyonun çeşitlenmesi sağlanmıştır.
İterasyona bağlı olarak daraltma (Adaptive shrinking) ile sömürü güçlendirilmiştir.
Karıncaların hareketi uyarlanabilir bir şekilde azaltılarak yakınsama hızı artırılmıştır.
En iyi karıncaaslanının konumu iterasyonlar sürecinde kaydedilerek umut verici bölgelerin taranması sağlanmıştır.
En iyi karıncaaslanı diğer bireylerinde daha iyi konumlara hareket etmesini sağlar.

The-ant-lion-optimizer


Diversity Measures in Artificial Bee Colony

“Diversity Measures in Artificial Bee Colony” başlıklı çalışma Harish Sharma, Jagdish Chand Bansal ve K V Arya tarafından yapılmış olup Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2012) konferansında sunulmuştur.

Exploration(Keşfetme) ve exploitation(Sömürme) kapasiteleri bir sezgisel algoritmanın en önemli parametrelerindendir. Bir algoritmada exploration iyileşirken, exploitation kötüleşir, exploration kötüleşirken, exploitation iyileşir. O yüzden bu ikisi arasındaki denge önemlidir. Bu ikisinin ne olması ile ilgili belirlemeler için “diversity measures” çeşitlilik ölçümleri yapılır. Bu çalışmanın konusu çeşitlilik ölçümleridir.

Bir optimizasyon algoritmasından beklenen başlangıçta çeşitliliği yüksek tutup, iterasyonlar ilerledikçe bunu küçültmesidir.

Çalışmada 7 önemli çeşitlilik ölçümü anlatılmış, bunlar bilinen 5 benchmark ile test edilmiş ve sonuçlar açıklanmıştır.

ABC’de üretilen aday çözümde adım boyutu(step size):
step-size

ABC’de belirlenen limit değeri kadar kere iyileştirilemeyen kaynak yok edilerek, sisteme yeniden rastgele oluşturulmuş başka bir kaynak eklenir.

Çeşitlilik ölçekleri öklid uzaklığı esasına göre çalışmaktadır. Öklid uzaklığı iki nokta arasındaki doğrusal uzaklıktır.

Parametrelerin normalizasyonu için Swarm Diameter(Sürü Çapı) kullanılır.

1-Swarm Diameter(Sürü Çapı): Sürüdeki bütün eksenlerdeki en uzak iki birey arasındaki uzaklıktır.

swarm-diameter

Çap hesabı aşağıdaki şekilde yapılır:

diameter

2-Swarm Radius(Sürü Yarıçapı)

Sürünün ortalamasından en uzaktaki birey arasındaki mesafeye denir.

swarm-radius

Aşağıdaki şekilde hesaplanır:

radius

D ve R’nin büyük olması exploration’un iyiliğine delalet ederken, exploitation’un kötülüğüne delalet eder. Her iki parametrede outlier(aykırı) bireylerden kötü etkilenir.

3-Average Distance around Swarm Center(Sürü Merkezi çevresinde ortalama uzaklık)

da

Bütün bireylerin sürü merkezinden uzaklığını belirtir.

Düşük olması bireylerin sürü merkezinde toplandığını gösterirken, büyük olması bireylerin sürü merkezinden dağınık vaziyette olduğunu gösterir.

Bu ölçüm [T. Krink, J.S. VesterstrOm, and J. Riget. Particle swarm optimisation with spatial particle extension. In Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on, volume 2, pages 1474–1479. IEEE, 2002.] çalışmasında kullanılmıştır.

4-Geometric Average Distance around the Swarm Center(Sürü Merkezi çevresinde geometrik ortalama uzaklık)

Bu ölçüm aykırı bireylerden etkilenmez. Aşağıdaki formülle hesaplanır:

dgm

Geometrik ortalamayla ilgili olarak:

Gözlem sonuçlarının her biri bir önceki gözlem sonucuna bağlı olarak değişiyorsa ve bu değişmenin hızı saptanmak istenirse geometrik ortalama sağlıklı sonuçlar verir. Geometrik ortalama bulmak için veri değerlerinin pozitif olması gerekir. Eğer tek bir veri değeri sıfır ise geometrik ortalama anlamsız olur.

5-Normalized Average Distance around the Swarm Center(Sürü Merkezi çevresinde normalize edilmiş ortalama uzaklık)

Average Distance around Swarm Center(Sürü Merkezi çevresinde ortalama uzaklık) ile aynıdır fakat Swarm Diameter(Sürü Çapı) ile normalize edilmiştir. Bu normalizasyon Swarm Radius(Sürü Yarıçapı) ile de yapılabilir. Aşağıdaki şekilde hesaplanır:

dn

6-Average of the Average Distance around all Particles in the Swarm(Sürüdeki tüm bireylerin çevresinde ortalama uzaklığın ortalaması)

Bu ölçümde her birey tek tek sürü merkezi kabul edilerek ortalamaları alınır ve sonundaki tüm sonuçlarında ortalaması alınır. Aşağıdaki şekilde hesaplanır:

dall

Bu ölçüm her bireyin sürüdeki bir başka bireye göre ortalama dağılımını gösterir.

7-Swarm Coherence(Sürü Uyumu)
Aşağıdaki şekilde hesaplanır:
uyum

Bu ölçüm adım boyutlarının ortalamasını sürü merkezine göre hesaplar.

Tartışma

İterasyonlar boyunca popülasyon çeşitliliğinin azaltılması exploration’dan exploitation’a geçiş olarak açıklanmaktadır.

-swarm diameter ve swarm radius çözümler aynı noktada toplandığı zaman 0 çıkmaktadır. İkisi de aykırı bireylerden çok etkilenmektedir.

-Average Distance around Swarm Center(Sürü Merkezi çevresinde ortalama uzaklık), swarm diameter ve swarm radius’ten daha sağlam bir ölçümdür fakat aykırı bireyler ortalamayı bozarsa bunun da performans düşer. Ayrıca bu metod ile Average of the Average Distance around all Particles in the Swarm(Sürüdeki tüm bireylerin çevresinde ortalama uzaklığın ortalaması) metodunda farkın 0 olması durumunda ölçüm sonuçsuz kalmaktadır.

-Geometrik ortalama kullanarak yapılan ölçüm aykırı bireylerden en az etkilenen ölçümdür.

-Swarm Coherence(Sürü Uyumu)’nun büyük olması bireylerin aynı yönde hareket ettiğini belirtir, küçük olması ise zıt yönde hareket ettiklerini gösterir. Swarm Coherence(Sürü Uyumu)’nun büyük olması exploration yapıldığını küçük olması exploiting yapıldığını gösterir.

Yüksek sürü çeşitliliği ve düşük sürü uyumu durumu:

highparticlediversity-and-smallswarmcoherence

Bireyler arama uzayına dağılmış durumdadır ve sürü merkezinin adım boyutu nispeten daha az etkilidir.

Yüksek sürü çeşitliliği ve yüksek sürü uyumu durumu:

highparticlediversity-and-largeswarmcoherence

Bireyler arama uzayına dağılmış durumdadır ve sürü merkezinin adım boyutu daha etkilidir.

lowparticlediversity

Sürü uyumu doğrudan popülasyon çeşitliliğine bağlı değildir. ABC’de sürü uyumu, popülasyon çeşitliliği ile orantılı olarak değişmemektedir bu yüzden doğru bir ölçüm metodu değildir.

Genel olarak bakıldığında aykırı bireyler popülasyon çeşitliliği ölçüm metodlarını etkilemektedir ve etkisi tamamen yok edilememektedir.

Deneysel Sonuçlar

Aşağıdaki benchmark fonksiyonlarında deneme yapılmıştır.

test-problems

Çalışmayı indirmek için:

diversitymeasuresinartificialbeecolony