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

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir