Etiket arşivi: algoritma

Parçacık Sürüsü Optimizasyon Algoritması (Particle Swarm Optimization Algorithm)

Parçacık Sürüsü Optimizasyon Algoritması(PSO), kuş sürülerinin davranışlarından esinlenilerek ortaya çıkarılmış bir algoritmadır. Popülasyon tabanlıdır ve skotastik bir yapıya sahiptir. Sosyal sistemler bireyin çevresiyle ve diğer bireylerle olan etkileşimini ve davranışını incelemektedir. Bu davranışlara sürü zekası denmektedir. Sürülerden esinlenilerek ortaya çıkarılan iki popüler optimizasyon yöntemi vardır. Bunlar; Karınca Koloni Optimizasyonu ve Parçacık Sürü Optimizasyonudur.PSO sürünün besin kaynağı ararken ortaya koyduğu davranış üzerine kuruludur. PSO, evrimsel algoritmalarla bir çok benzerlik göstermektedir. PSO’nun adımları aşağıdaki gibidir. taşıma şirketi

Algoritmada bahsedilen parçacıklar sürüdeki bireylere işaret etmektedir.

PSO KONTROL PARAMETRELERİ

  • Parçacık Sayısı : Problemin çeşidine göre ayarlanmalıdır. Bazı problemlerde 10 parçacık yeterliyken, bazılarında 20-40, bazılarında ise 100-200 değerleri gerekmektedir.
  • Parçacık Boyutu : Optimize edilecek probleme göre değişir.
  • Parçacık Aralığı :Probleme göre farklı boyut ve aralıklarda ayarlanabilir.
  • Vmax : Bir iterasyonda bir parçacıkta meydana gelecek maksimum hızı belirler. Genellikle parçacık aralığına göre ayarlanır.
  • Öğrenme Faktörleri : Denklemde görülen c değerleridir. Genellikle 2 olarak seçilirler. Fakat farklı değerler de alabilirler. Yaygın olarak [0,4] aralığında alınır.
  • Durdurma Kriteri : İki şekilde yapılabilir; Birincisi başlangıçta maksimum iterasyon sayısı belirlenir ve algoritma bu sayıya ulaştığında sonlandırılır. İkincisi ise değerlendirme fonksiyonu istenilen değere ulaştığından algoritma sonlandırılır.

Algoritmanın Pseudo Code’u aşağıdaki gibidir.

Begin
   While Durdurma kriteri sağlanmıyorsa do
      Begin
      for i = 1 to parçacık sayısı 
         Uygunluk Değeri := f(Xi); 
         Pi ve gi’yi güncelle;
         I denklemini kullanarak hızı güncelle;
         Parçacığın koordinatını güncelle;
         i= i+1;
   end while
end

Parçacık Sürüsü Algoritması bir başlangıç popülasyonuyla başlatılır ve algoritmanın çalışmasıyla, çözümler güncellenir ve optimum çözüm bulunmaya çalışılır. Her döngüde parçacıkların konumları, iki en iyi(best) değere göre güncellenir. Bu değerlerden ilki pbest, o ana kadar parçacığın elde ettiği en iyi çözümü sağlayan konum koordinatlarıdır. Diğer değer ise popülasyon tarafından elde edilen en iyi çözümü sağlayan konum koordinatlarıdır. Diğer değeri local en iyi(best) olarak kabul edersek, bu değer ise global en iyi olarak kabul edilir.

Aşağıda D adet parametrede oluşmuş, n adet parçacığın oluşturduğu popülasyon görülmektedir.

Popülasyon matrisine göre i. parçacık   Xi = [ Xi1,Xi2,…,…,X1D] şeklinde ifade edilir. En iyi değeri veren parçacığın pozisyonu için de pbest  şeklinde bir matris oluşturulur. Yine aynı şekilde yukarıdaki denklemde verilen hız parametresi de vektörle ifade edilir.

Denklemler de geçen C değerleri öğrenme faktörleridir. Bu değerler her parçacığı en iyi konuma çeken stokastik hızlanma terimlerini ifade eden sabitlerdir. İlk c değeri parçacığın kendi tecrübesine göre hareket etmesini, diğeri ise sürüdeki diğer parçacıkların tecrübelerine göre hareket etmesini sağlar. Bu sabitlerin değerleri belirlenirken dikkat edilmelidir. Düşük değerler seçilmesi durumunda hedefe doğru dolaşarak gider, böylelikle farklı yerler gezilerek, farklı kaynak bulma imkanı doğabilir. Fakat bu durum hedefe ulaşma süresini uzatır. Bu değerlerin yüksek seçilmesinde ise hedefe doğru hızla gidilir fakat bu durumun, hedefin atlanıp geçilmesine de sebep olabileceği unutulmamalıdır. Yapılan çalışmalar sonrasında elde edilen verilere göre en uygun c değerleri 2 olarak bulunmuştur. Ayrıca denklemde bulunan rand değerleri [0,1] arasında düzgün dağılımı rastgele değerlerdir. Denklemlerde geçen k değerleri ise iterasyon sayısını bildirmektedir.

PARÇACIKLARIN HIZ VE KOORDİNATI

Parçacıkların hız ve koordinat hesaplamaları yukarıda verdiğim I ve II numaralı denklemler ile yapılmaktadır. Yeni konum yeni hız ve bir önceki koordinat bilgisiyle hesaplanmaktadır. İkinci denklem bunu göstermektedir. x(k+1) bir sonraki koordinat bilgisi, mevcut koordinat bilgisi x(k) ile parçacığın o andaki hızı ile toplanarak bulunmakta.

İlk denklem ise mevcut hızı hesaplamaktadır. c1 ve c2 değerleri global en iyiye gidiş için önem arz etmektedir. Bu yüzden dikkatli seçilmelidir. Daha önce bahsettiğim gibi bu değerler genelde 2 seçilirler.

Yukarıda görüldüğü üzere verilen hız denklemi pbest ve gbest  değerlerine bağımlıdır. Bu yüzden tüm elemanlar hesaba katılmamaktadır. Bu yüzden formülü aşağıdaki şekildeki gibi de kullanabiliriz. Bu şekildeki kulanım sayesinde yeni  hız bulunurken sadece en iyilerin kullanımından kurtarılmış olacaktır. Formüldeki x değeri orantı sabiti, qi değeri ise pbest değerlerinin ağırlıklı toplamı olarak kullanılmaktadır.

Parçacık Sürüsü Optimizasyonu Algoritması’nda bir diğer önemli nokta da komşuluk seçimidir. Üzerinde çalıştığımız probleme göre komşuluk seçimi stratejisi belirlenir. Komşuluk seçimi için genel olarak kullanılan birkaç metod vardır.

KAYNAKLAR

  • Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis, Applications and Hybridization Perspectives
  • Parçacık Sürüsü Optimizasyon Algoritması ve Benzetim Örnekleri – Seçkin Tamer-Cihan Karakuzu
  • Parçacık Sürü Optimizasyonunda Yeni Bir Birey Davranış Biçimi Önerisi – Ö.Tolga Altınöz-A.Egemen Yılmaz
  • http://www.swarmintelligence.org
  • http://wikipedia.org

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm)

Bir Cevap Yazın

Diferansiyel Gelişim Algoritması (DGA), popülasyon tabanlı sezgisel bir optimizasyon tekniğidir. Global optimizasyon için basit ama güçlü bir tekniktir. Özellikle sürekli verilerin söz konusu olduğu problemlere yönelik olarak geliştirilmiştir ve rastlantısal bir yapıya sahiptir. Temeli genetik algoritmaya dayanır. Benzer operatörleri kullansalar da bu operatörlerin yapısı ve kullanım şekilleri birbirinden farklıdır. Genel anlamda algoritmanın adımları aşağıdaki gibidir.

Algoritmanın adımlarını sırasıyla inceleyelim;

1. Kontrol Parametrelerinin Değerlerini ve Sınırlarını Atama

Temel anlamda parametrelerimiz aşağıdaki gibidir;

  • Değişken Sayısı (D) : minimum 1 olmak üzere istenilen sayı verilebilir. Kromozomdaki gen sayısı olarak düşünülebilir. (1,2,…….,j)
  • Maksimum Jenerasyon Sayısı (Gmax) : Oluşturulacak olan popülasyonun kaç jenerasyon boyunca mutasyon, rekombinasyon ve seleksiyona tabî tutulacağını belirtir. (1,2,…….Gmax)
  • Popülasyon büyüklüğü (NP) : Popülasyonun büyüklüğünün ne kadar olacağını belirtir. Bu da kromozom sayısı olarak düşünülebilir.
  • Ölçekleme Faktörü (F) : Ölçekleme faktörüdür, kullanıcı belirleyecektir.
  • Çaprazlama Oranı (CR) : Olasılığı temsil eder bu yüzden 0 ile 1 arasında değer alır.
  • Xlo ve Xhi  değerleri ise parametre sınırlarını belirtmektedir.

Kontrol parametrelerinin  değerlerinin atanması işlemi şu şekilde temsil edilir;

NP üçten büyük olmalıdır, çünkü Diferansiyel Gelişim Algoritması’nda yeni kromozomların üretilebilmesi için mevcut kromozon dışında üç adet kromozom gerekmektedir. NP adet D boyutlu kromozomdan meydana gelen başlangıç popülasyonun oluşturulma şekli aşağıdaki gibidir.

2. Başlangıç Popülasyonunun Oluşturulması

Mevcut popülasyon gelecek jenerasyonu oluşturmak için kullanılacağından dolayı başlangıç popülasyonu  iyi tanımlanmış sınırlamalara sahip bir araştırma uzayından uniform dağılımla rastgele elemanlar seçilerek oluşturulur.

3. Değerlendirme Fonksiyonu

Yeni bir birey üretildiğinde popülasyona girip girmeyeceğine değerlendirme fonksiyonuyla karar verilir. Hedef kromozomumuzun uygunluk değeri bilinmektedir. Yeni birey onunla karşılaştırılır ve popülasyona girip girmeyeceğine karar verilir. Böylelikle yeterince uygun olmayan bireyler popülasyona eklenmeyerek popülasyonun bozulmaması sağlanır.

4. Mutasyon İşlemi

Mutasyon işlemi parametre optimizasyonu açısından büyük önem  taşır. Kromozomun genleri üzerinde rasgele değişiklikler yapmaktır. Mutasyon sayesinde çözüm noktası çözüm uzayında hareket etmektedir. Bir anlamda mutasyon arama uzayını genişletmektedir. Böylelikle daha çok bölgeye ulaşılıp farklı çözümlere ulaşılabilme ihtimali ortaya çıkar. Mutasyondan beklenen çözümün, çözüm uzayında doğru yönde ve  doğru miktarda hareket etmesidir. Bu sayede bir yerde takılıp kalınmaz. Fakat bu hareketin beklenen şekilde doğru yönde ve doğru miktarda olması garanti edilemez. Mutasyona tabî tutulacak kromozom dışında birbirinden farklı üç kromozom seçilir. () İlk ikisinin farkı alınır ve ölçekleme faktörüyle çarpılır. F genellikle 0 ile 2 arasında değerler almaktadır. Ağırlıklandırılmış fark kromozomu ile üçüncü kromozom toplanır. Amacı amaç vektörleri doğru yönde hareket ettirecek artışları üretmektir.

5. Rekombinasyon İşlemi

Mutasyon işlemi temel olarak yeni araştırma bölgelerinin araştırılmasından sorumludur. Rekombinasyon ya da çaprazlama işleminin amacı ise var olan amaç vektör parametrelerinden yararlanarak yeni vektörler oluşturmak suretiyle araştırmanın başarılı olması için yardımcı olmaktır. Rekombinasyon önceki jenerasyonla başarılı çözümleri birleştirir. Daha iyi bireyler üretmek için eldeki bireyler çaprazlanır.  Mutasyon işlemini gerçekleştirirken elde ettiğimiz fark kromozomu ve Xi,g kromozomu kullanılarak yeni deneme kromozomu (Ui,G+1) üretilir. Deneme kromozomuna genler CR olasılıkla fark kromozomundan 1-CR olasılıkla mevcut kromozomdan seçilir. j=jrand koşulu, en az bir tane genin üretilen yeni kromozomdan alınmasının garanti olması için kullanılır.

6. Seleksiyon İşlemi

Yeni üretilen bireylerin hangi şartlar altında popülasyona girebileceğini tanımlayan kriterdir. Buradaki seleksiyon yöntemi aç gözlü olarak seçilmiştir. Bilindiği üzere diğer evrimsel algoritmalarda kullanılan Deterministik, Rulet Tekerleği, Rasgele ve Turnuva gibi seleksiyon metodları bulunmaktadır. Çalışılan probleme göre bu metodlarda biri de burada tercih edilebilir. Deterministik te belirli sayıdaki en iyi bireyler ile yeni popülasyon oluşturulur, kötü bireyler popülasyona katılmaz. Rulet tekerleğinde, her bireyin çözüme uygunluk derecesi arttıkça yeni popülasyona aktarılma şansı artar. Rasgele seçimde bireylerin uygunluk dereceleri seçilme şanslarını etkilemez. Turnuva metodunda, rasgele seçilen iki birey arasında uygunluk derecesi yüksek olan popülasyona katılırken diğer birey popülasyona kabul edilmez.

Mutasyon, rekombinasyon ve seleksiyon işlemleri durdurma kriteri sağlanana kadar tekrar sırasıyla devam ettirilir. Diferansiyel gelişim algoritmasını maksimum jenerasyon sayısına ulaşana denk çalışır ve ulaştığında algoritma durdurulur. Buna ek algoritmanın çalışması maksimum jenerasyon sayısı ile değil belirlenen durdurma kriterine göre de belirlenebilir. Bu durumda en iyi ve en kötü bireylerin arasındaki farkın belirlenen miktara kadar düşmesi durumunda algoritma sonlandırılır.

Diferansiyel Gelişim Algoritması sürekli parametreleri söz konusu olduğu durumlarda oldukça başarılı sonuçlar veren bir algoritmadır.

KAYNAKLAR

  • Particle Swarm Optimization and Differential Evolution Algorithms : Technical Analysis, Applications and Hybridization Perspectives
  • Yapay Zeka Optimizasyon Algoritmaları – Derviş Karaboğa
  • Diferansiyel Gelişim Algoritması – Timur Keskintürk
  • http://tr.wikipedia.org
  • Diferansiyel Gelişim Algoritması Kullanılarak Sinyal Kesimine Yönelik Adaptik SDY Süzgeç Tasarımı
  • An Introduction to Differential Evolution – Kelly Fleetwood
  • Differential Evolution : A Simple Evolution Strategy for Fast Optimization – Napapan Piyasatian

Yapay Arı Koloni Algoritması (Artificial Bee Colony – ABC Algorithm)

Bir Cevap Yazın

Giriş

Bu yazıda önce Yapay Arı Koloni Algoritmasının (Artificial Bee Colony – ABC) temelini teşkil eden gerçek arıların yiyecek arama davranışı açıklanacaktır. Sonra yapay arı algoritması ve bu algoritmanın örnek bir problem için uygulamada kullanılması gösterilecektir.

Gerçek Arıların Davranışları

Doğal bir arı kolonisinde yapılacak işler o iş için özelleşmiş arılar tarafından yapılır. Yani yapılacak işlere göre arılar arasında bir iş bölümü vardır ve kendi kendilerine organize olabilmektedirler. İş bölümü yapabilme ve kendi kendine organize sürü zekâsının iki önemli bileşenidir. Arıların minimal yiyecek arama modelinde temel üç bileşen vardır. Bunlar; yiyecek kaynakları, görevli işçi arılar ve görevsiz işçi arılar.

Yiyecek kaynakları

Arıların nektar, polen veya bal elde etmek için gittikleri kaynaklardır. Kaynağın değeri, çeşidi, yuvaya yakınlığı, nektar konsantrasyonu veya nektarın çıkarılmasının kolaylığı birçok etkene bağlı olabilir. Ama kaynağın zenginliği tek ölçüt olarak alınabilir.

Görevli İşçi Arılar

Daha önceden keşfedilen belli kaynaklara ait nektarın kovana getirilmesinden sorumludur. Ayrıca ziyaret ettikleri kaynağın kalitesi ve yeri ile ilgili bilgiyi kovanda bekleyen diğer arılarla da paylaşırlar.

Görevsiz İşçi Arılar

Nektarın toplanacağı kaynak arayışı içerisindeki arılardır. Görevi belirsiz iki çeşit işçi arı bulunmaktadır. Bunlar; rastgele kaynak arayışında olan kâşif arılar ve kovanda bekleyen ve görevli arıları izleyerek bu arılar tarafından paylaşılan bilgiyi kullanarak yeni kaynağa yönelen gözcü arılardır.

Görevli arıların yiyecek kalitesi ve yeri ile ilgili bilgi paylaşımı dans alanında olmaktadır. Bir arı dans ederken diğer arılar ona antenleri ile dokunur ve bulduğu kaynağın tadı ve kokusu ile ilgili bilgiyi alır.

Danslar

Kaynağın kovana olan mesafesine göre çeşitli danslar mevcuttur: dairesel dans, kuyruk dansı ve titreme dansı gibi.

Daire Dansı Belirlenen yiyecek kaynağının kovana olan uzaklığı maksimum 50-100 metre civarında olduğundan bu dans yön ve uzaklık bilgisi içermez.

Titreme Dansı Arıların petek üzerinde düzensiz tarzda ve yavaş tempoda bacaklarını titreterek ileri, geri, sağa ve sola hareketleri söz konusudur. Arı zengin bir nektar kaynağı bulduğunu ancak kovana işlenebileceğinden fazla nektar geldiğini ve bundan dolayı nektar işleme görevine geçmek istediğini belirtmektedir. Bu dansın amacı kovan kapasitesi ve yiyecek getirme aktivitesi arasındaki dengeyi sağlamaktır.

Kuyruk Dansı 100 metreden 10 kilometreye kadar olan geniş bir alan içerisinde bulunan kaynaklarla ilgili bilgi aktarımında kullanılır. Bu dans 8 rakamına benzeyen figürlerin yapıldığı dans çeşididir. Dansı izleyen arıların bir titreşim oluşturması ile dansa son verilir. Dansın her 15 saniyede tekrarlanma sayısı, nektar kaynağının uzaklığı hakkında bilgi vermektedir. Daha az tekrarlanma sayısı daha uzak bölgeleri ifade etmektedir.

Yön bilgisi Şekil-1’deki gibi 8 rakamı şeklindeki dansın açı bilgisinden elde edilir. Şekilde verilen örnekte dansı izleyen arılar, danstan güneşle yiyecek arasındaki açının 45o olduğunu anlamaktadırlar.

Şekil-1 Arılarda Dans

Tüm zengin kaynaklarla ilgili bilgiler dans alanında gözcü arılara iletildiğinden, gözcü arılar birkaç dansı izledikten sonra hangisini tercih edeceğine karar verir. Yiyecek arayıcı arıların daha iyi anlaşılabilmesi için Şekil-2’deki verilen modelin incelenmesi faydalı olacaktır.

A ve B ile gösterilen iki keşfedilmiş kayna bölgesi olduğunu varsayılım. Araştırma başlangıcında potansiyel yiyecek arayıcı, görevi belirsiz bir işçi arı olarak araştırmaya başlayacak ve bu arı kovan etrafındaki kaynakların yerinden haberdar degildir. Bu durumdaki arı için iki olası durum söz konusudur.

  1. Bu arı kaşif arı olabilir ve içsel ve dışsal etkilere bağlı olarak yiyecek aramaya başlayabilir (Şekil-2’de S ile gösterilmiştir).
  2. Bu arı kuyruk dansını izleyen gözcü arı olabilir ve izlediği dansla anlatılan kaynağa gidebilir (Şekil-2’de R ile gösterilmektedir). Bir kaynak keşfedildikten sonra arı imkanları dahilinde bu kaynağın yerini hafızaya alır ve hemen nektar toplamaya başlar. Bu arı artık nektarın zenginliğine göre görevli arı haline gelmiş olur. İşçi arı nektarı aldıktan sonra kovana döner ve bunu yiyecek depolayıcılara aktarır. Nektar aktarıldıktan sonra arı için üç seçenek ortaya çıkmaktadır:
  • Gittiği kaynağı bırakarak bağımsız işçi olabilir (Şekil-2’de UF ile gösterilmiştir).
  • Gittiği kaynağa dönmeden önce dans eder ve kovandaki arkadaşlarını da aynı kaynağa yönlendirebilir ( Şekil-2’de EF1 ile gösterilmiştir).
  • Diger arıları yönlendirmeden direkt kaynağa gidebilir (Şekil-2’de EF2 ile gösterilmiştir).

Şekil-2 Yiyecek Arama Çevrimi

Yapay Arı Kolonisi Algoritması

Doğada var olan zeki davranışlar içeren süreçlerin incelenmesi araştırmacıları yeni optimizasyon metotları geliştirmeye sevk etmiştir. Derviş Karaboğa, arıların yiyecek arama davranışını modelleyerek Yapay Arı Kolonisi(ABC) algoritması geliştirilmiştir.

Derviş Karaboğa’nın ABC algoritmasının temel aldığı modelde bazı kabuller yapılmaktadır. Bunlardan birincisi her bir kaynağın nektarının sadece bir görevli arı tarafından alınıyor olmasıdır. Yani görevli arıların sayısı toplam yiyecek kaynağı sayısına eşittir. İşçi arıların sayısı aynı zamanda gözcü arıların sayısına eşittir. Nektarı tükenmiş kaynağın görevli arısı artık kâşif arı haline dönüşmektedir. Yiyecek kaynaklarının yerleri optimizasyon problemine ait olası çözümlere ve kaynakların nektar miktarları ise o kaynaklarla ilgili çözümlerin kalitesine (uygunluk) karşılık gelmektedir. Dolayısıyla ABC optimizasyon algoritması en fazla nektara sahip kaynağın yerini bulmaya çalışarak uzaydaki çözümlerden problemin minimumu yada maksimumunu veren noktayı bulmaya çalışmaktadır.

Bu Modele ait süreç adımları aşağıdaki gibi verilebilir.

  1. Yiyecek Arama surecinin başlangıcında, kaşif arılar çevrede rastgele arama yaparak yiyecek aramaya başlarlar.
  2. Yiyecek kaynakları bulunduktan sonra, kaşif arılar artık görevli arı olurlar ve buldukları kaynaklardan kovana nektar taşımaya başlarlar. Her bir görevli arı kovana donup getirdiği nektarı boşaltır ve bu noktadan sonra ya bulduğu kaynağa geri döner ya da kaynakla ilgili bilgiyi dans alanında sergilediği dans aracılığıyla kovanda bekleyen gözcü arılara iletir. Eğer faydalandığı kaynak tükenmiş ise görevli kaşif arı haline gelir ve yeni kaynak arayışına yönelir.
  3. Kovanda Bekleyen gözcü arılar zengin kaynakları işaret eden dansları izlerler ve yiyeceğin kalitesi ile orantılı olan dans frekansına bağlı olarak bir kaynağı tercih ederler.

ABC algoritmasının bu süreçleri ve temel adımları ise şu şekilde sıralanabilir;

  1. Başlangıç yiyecek kaynağı bölgelerinin üretilmesi
  2. Repeat
  3. İçi arıların yiyecek kaynağı bölgelerine gönderilmesi
  4. Olasılıksal seleksiyonda kullanılacak olasılık değerlerinin görevli arılardan gelen bilgiye göre hesaplanması
  5. Gözcü arıların olasılık değerlerine göre yiyecek kaynağı bölgesi seçmeleri
  6. Kaynağı bırakma kriteri:limit ve kaşif arı üretimi
  7. Until çevrim sayısı=Maksimum çevrim sayısı

Yiyecek arayan arılarda görülen zeki davranış ile bu davranışı simule eden ABC algoritmasının temel birimleri aşağıda açıklanmaktadır.

1.Başlangıç Yiyecek Kaynağı Bölgelerinin Üretilmesi

Arama uzayını yiyecek kaynaklarını içeren kovan çevresi olarak düşünürsek algoritma arama uzayındaki çözümlere karşılık gelen rastgele yiyecek kaynağı yerleri üreterek çalışmaya başlamaktadır. Rastgele yer üretme sureci her bir parametrelerinin alt ve üst sınırları arasında rastgele değer üreterek gerçeklenir (Eşitlik-1).

Burada i=1… SN, J=1…D ve SN yiyecek kaynağı sayısı ve D is optimize edilecek parametre sayısıdır. Xmin j parametrelerin alt sınırıdır.

2. İsçi Arıların Yiyecek Kaynağı Bölgelerine Gönderilmesi

Daha öncede belirtildiği gibi her bir kaynağın bir görevli arısı vardır. Dolayısıyla yiyecek kaynakların sayısı görevli arıların sayısına eşittir. İşçi arı çalıştığı yiyecek kaynağı komşuluğunda yeni bir yiyecek kaynağı belirler ve bunun kalitesini değerlendirir. Yeni kaynak daha iyi ise bu yeni kaynağı hafızasına alır. Yeni kaynağın mevcut kaynak komşuluğunda belirlenmesinin benzetimi Eşitlilik-2 tanımlanmaktadır.

xi ile gösterilen her bir kaynak için bu kaynağın yani çözümünün tek bir parametresi (rastgele seçilen parametresi, j) değiştirilerek xi komşuluğunda vi kaynağı bulunur. Eşitlik 2 de j,[1,D] aralığında rastgele üretilen bir tamsayıdır. Rastgele seçilen j parametresi değiştirilirken, yine rastgele seçilen xk komsu çözümünün ( k E {1,2,SN} ) j. parametresi ile mevcut kaynağın j parametresinin farkları alınıp [-1 1 ] arasında rastgele değer alan  sayısı ile ağırlandırıldıktan sonra mevcut kaynağın j parametresine eklenmektedir.

Eşitlik-2’den de görüldüğü gibi  xi,j ve xk,j arasındaki fark azaldıkça yani çözümler birbirine benzedikçe xi,j parametresindeki değişim miktarı da azalacaktır. Böylece bölgesel optimal çözüme yaklaştıkça değişim miktarı da adaptif olarak azalacaktır.

Bu işlem sonucunda üretilen vi,j‘nin daha önceden belli olan parametre sınırları asması durumunda j. parametreye ait olan alt veya üst sınır değerlerine ötelenmektedir (Eşitlik-3).

Sınırlar dâhilinde üretilen vi parametre vektörü yeni bir kaynağa temsil etmekte ve bunun kalitesi hesaplanarak bir uygunluk değeri atanmaktadır (Eşitlik-4).

Burada fi ve vi kaynağının yani çözümünün maliyet değeridir. xi ve vi arasında nektar miktarlarına yani uygunluk değerlerine göre bir açgözlü (greddy) semce işlemi uygulanır. Yeni Bulunan vi çözümü daha iyi ise görevli arı hafızasından eski kaynağın yerini silerek vi kaynağının yerini hafızaya alır. Aksi takdirde görevli arı xi kaynağına gitmeye devam eder ve xi çözümü geliştirilemediği için xi kaynağı ile ilgili geliştirememe sayacı (failure) bir artar, geliştirdiği durumda ise sayaç sıfırlanır.

3. Gözcü Arıların Seleksiyonda Kullanacakları Olasılık Değerlerinin Hesaplanması (Dans Benzetimi)

Tüm görevli arılar bir çevrimde araştırmalarını tamamladıktan sonra kovana donup buldukları kaynakların nektar miktarları ile ilgili gözcü arılara bilgi aktarırlar. Bir gözcü arı dans aracılıyla paylaşılan bilgiden faydalanılarak yiyecek kaynaklarının nektar miktarları ile orantılı bir olasılıkla bir bölge(kaynak) seçer. Bu ABC‘nin altında çoklu etkileşim sergilendiğinin bir örneğidir. Olasılıksal seçme işlemi, algoritmada nektar miktarlarına karşılık gelen uygunluk değerleri uygulanarak yapılmaktadır. Uygunluk değerine bağlı seçme işlemi rulet tekerliği,sıralamaya dayalı, stokastik ,örnekleme, turnuva yöntemi yada diğer seleksiyon şemalarından herhangi biri ile gerçeklenir.Temel ABC algoritmasında bu seleksiyon işlemi rulet tekerliği kullanılarak yapılmıştır. Tekerlekteki her bir dilimin açısı uygunluk değeri toplamına oranı o kaynağın diğer kaynaklara göre nispi seçilme olasılığı olduğunu vermektedir (Eşitlik-5).

Burada  kaynağın kalitesini SN görevli arı sayısını göstermektedir. Bu olasılık hesaplama işlemine göre bir kaynağın nektar miktarı arttıkça (uygunluk değeri arttıkça) bu kaynak bölgesini seçecek gözcü arı sayısı da artacaktır. Bu özellik ABC’ nin pozitif geri besleme özelliğine karşılık gelmektedir.

4. Gözcü Arıların Yiyecek Kaynağı Bölgesi Seçmeleri

Algoritma da olasılık değerleri hesaplandıktan sonra be değerler kullanılarak rulet tekerleğine göre secim işleminde her bir kaynak için [0.1] aralığında rastgele sayı üretilen ve pi değeri bu üretilen sayıdan büyükse görevli arılar gibi gözcü arı da Eşitlik-2’yi kullanarak bu kaynak bölgesinde yeni bir çözüm üretir. Yeni çözüm değerlendirilir ve kalitesi hesaplanır. Sonra yeni çözümle eski çözümün uygunluklarının karşılaştırıldığı en iyi olanın seçildiği açgözlü seleksiyon işlemine tabi tutulur. Yeni çözüm daha iyi ise eski çözüm yerine bu çözüm alınır ve çözüm geliştirememe sayacı (failure) sıfırlanır. Eski çözümün uygunluğu daha iyi ise bu çözüm muhafaza edilir ve geliştirememe sayacı (failure) bir artırılır. Bu süreç,tüm gözcü arılar yiyecek kaynağı bölgelerine dağılana kadar devam eder.

5. Kaynağı Bırakma Kriteri: Limit ve Kaşif Arı Üretimi

Bir çevrim sonunda tüm görevli ve gözcü arılar arama süreçlerini tamamladıktan sonra çözüm geliştirememe sayaçları (failure) kontrol edilir. Bir arının bir kayaktan faydalanıp faydalanmadığı, yani gidip geldiği kaynağın nektarının tükenip tükenmediği çözüm geliştirememe sayaçları aracılığıyla bilinir. Bir kaynak için çözüm geliştirememe sayacı belli bir eşik değerinin üzerindeyse, artık bu kaynağın görevli arısının tükenmiş olan o çözümü bırakıp kendisi için başka bir çözüm araması gerekir. Bu da biten kaynakla ilişkili olan görevli arının kâşif arı olması anlamına gelmektedir. Kâşif arı haline geldikten sonra, bu arı için rastgele çözüm arama sureci başlar (Eşitlik-1). Kaynağın terk ettiğinin belirlenmesi için kullanılan eşik değeri ABC algoritmasının önemli bir kontrol parametresidir ve “limit” olarak adlandırılmaktadır. Temel ABC algoritmasında her çevrimde sadece kâşif arının çıkmasına izin verilir.

Tüm bu birimler arasındaki ilişki ve döngü Şekil-3’deki gibi bir akış diyagramı ile şematize edilebilir.

6. Seleksiyon Mekanizmaları

ABC algoritması 4 farklı seleksiyon işlemi kullanmaktadır.Bunlar ;

  1. Potansiyel iyi kaynaklarının belirlenmesine yönelik eşitlik 5 olasılık değerlerinin hesaplandığı global olasılık temelli seleksiyon sureci.
  2. Görevli ve gözcü arıların renk,şekil,koku gibi nektar kaynağının turunu belirlenmesi sağlayan görsel bilgiyi kullanarak bir bölgede kaynağın bulunmasına vesile olan bölgesel olasılık tabanlı seleksiyon işlemi (Eşitlik-2).
  3. İşçi ve gözcü arıların daha iyi olan kaynağı belirlemek amacıyla kullandıkları açgözlü seleksiyon.
  4. Kâşif Arılar tarafından eşitlik 1 aracılıyla gerçekleştirilen rastgele seleksiyon.

Bütün bu seleksiyon metotların bir arada kullanılmasıyla ABC algoritması hem iyi bir global araştırma hem de bölgesel araştırma yapabilmektedir.

ABC Algoritması Akış Şeması

7. ABC Algoritmasının Adımları

Önceki bölümlerde genel hatları ile ABC algoritmasının adımları ve her bir adımda yapılan işlemler tarif edilmişti ancak bu adımları sözde kod seklinde baştan aşağı yazmak faydalı olacaktır.

  1. Eşitlik 1 aracılıyla tüm xi,j i=1…SN,j =1…D, çözümlerine başlangıç değerlerinin atanması ve çözüm geliştirememe sayaçlarının  sıfırlanması failurei=0
  2. fi=f(xi) fonksiyon değerlerinin ve bu değerlere karşılık gelen uygunluk değerlerin  hesaplaması
  3. Repeat
  4. for i=1 to Sn do
  5. Eşitlik 2 kullanarak xi çözümünün görevli arısı için yeni bir kaynak üret vi ve f(vi)’yi (4) eşitliğinde yerine koyarak bu çözümün uygunluk değerini hesapla
  6. xi ve vi arasında açgözlü seleksiyon işlemi uygula ve daha iyi olanı seç
  7. xi çözümü gelişememişse çözüm geliştireme sayacını bir artır failurei= failurei+1, gelişmemişse sıfırla, failurei=0
  8. End For
  9. Eşitlik 5 ile gözcü arıların seçim yaparken kullanacakları uygunluk değerine dayalı olasılık değerlerini pi hesapla
  10. t=0 i=1
  11. Repeat
  12. if random<pi then
  13. Eşitlik 2 ‘i kullanarak gözcü arı için yeni bir kaynak, vi üret
  14. xi ve vi arasında açgözlü seleksiyon işlemi uygula ve daha iyi olanı seç.
  15. xi çözümü gelişememişse çözüm geliştirememe sayacını bir artır failurei= failurei+1, gelişmemişse sıfırla, failurei=0
  16. t=t1
  17. End İf
  18. Until t=SN
  19. if max (failurei) > limit then
  20. xi eşitlik 1 ile üretilen rastgele bir çözümle değiştir.
  21. End İf
  22. En İyi Çözümü hafıza da tut
  23. Until Durma kriteri

ABC’nin Temel Özellikleri

ABC algoritmasının temel özellikleri şu şekilde sıralanabilir;

  1. Oldukça esnek ve basittir.
  2. Gerçek yiyecek arayıcı arıların davranışlarına oldukça yakın şekilde simule eder.
  3. Sürü zekâsına dayalı bir algoritmadır.
  4. Nümerik problemler için geliştirilmiştir ama ayrık problemler içinde kullanılabilir.
  5. Oldukça az kontrol parametresine sahiptir
  6. Kâşif Arılar tarafından gerçekleştirmen küresel ve görevli ve gözcü arılar tarafından gerçekleştirilen bölgesel araştırma kabiliyetine sahiptir ve ikisi paralel yürütülmektedir.

UYGULAMA VE DENEY SONUÇLARI

Algoritmanın performansını Rastrigin Problemi üzerinde görmeye çalıştık. Bu anlamda bu fonksiyonu çözmeye çalıştık. Deney sonuç ve performanslarına geçmeden önce Rastrigin Problemi ve Fonksiyonu nedir ve ne işe yarar bundan bahsetmek istiyorum. Rastrigin fonksiyonu içerisinde birçok lokal minimumu içeren ve bu yüzden de optimizasyon tekniklerinin performansını ölçmek için ideal olan bir test fonksiyonudur. Fonksiyonun global minimumu iki boyutlu uzay için [0,0] noktası, üç boyutlu bir uzay için ise [0,0,0] noktasıdır. Fonksiyonun grafik üzerindeki görünümü aşağıdaki şekildeki gibidir.

Kullandığım demo uygulama http://mf.erciyes.edu.tr/abc/ web sitesinden alınmıştır. Çeşitli optimizasyon problemleri üzerinde ABC Algoritması’ nın performansını gözlemektedir. Biz yukarıda da bahsettiğimiz üzere bu fonksiyonlardan Rastrigin Fonksiyonunu kullandık. Demo uygulamanın genel görünümü aşağıdaki gibidir.

Öncelikle uygulamanın parametrelerine bakalım. Demo üzerinde parametreler ve açıklamaları aşağıda sırasıyla verilmiştir.

  • # of parameter: Üzerinde çalışılan uzayın boyutu. Biz uygulamamızda anlaşılması ve gözlemi kolay olması maksadıyla 2 boyutlu uzayda çalışmayı tercih ettik.
  • Colony Size: Kolonide bulunan arı miktarı.
  • Parameter Range: Algoritmanın çalışmasını istediğimiz aralık. Yukarıdaki görülen şekilde aralık [-5,5] olarak seçilmiştir. Böylelikle alan daraltılarak arıların hareketi daha rahat görülmektedir.
  • # of Cycle: Algoritmanın durdurma kriteri olarak çalışma sayısı belirtilmiştir.
  • Limit: Her döngüde görevli ve gözcü arılar arama süreçlerini tamamladıktan sonra çözüm geliştirememe sayaçlarına bakarlar eğer ki limit değeri aşılmışsa yani algoritma belli bir süre boyunca artık iyi değer vermemeye başlamışsa bu bölgeden vazgeçilir. Limit değeri bu sayacı belirtmektedir.
  • # of Runs: Algoritmanın baştan itibaren kaç defa çalışacağı. Biz her defasında varsayılan değer kabul edilen bir kez çalıştırdık.

Ayrıca demo şekil üzerinde görülen Obtained kısmı algoritmanın bulduğu en iyi değerleri, Desired kısmı fonksiyonun beklenilen değerlerini, üst soldaki grafik Rastrigin Fonksiyonu’nun grafiksel olarak üç boyutlu görünümünü, üst sağdaki grafik fonksiyon grafiğinin üstten görünümünü, sol alttaki grafik en iyi değerin kaçıncı döngüde bulunduğunu ve bulunan değerlerin ortalama iyiliğini göstermektedir. Sağ alttaki grafik ise arıların hareketini her döngüde izleme imkânı sunmaktadır. Buradaki mavi noktalar, görevli işçi arılar;  yeşil noktalar, kaşif; kırmızı noktalar, beklenen değer; ve son olarak da mor noktalar, o ana kadar ki bulunan en iyi çözüm noktasını göstermektedir.

Deney Sonuçları: Yaptığımız deneylerde Colony Size, Cycle Sayısı ve Limit Sayısı parametrelerinin algoritmanın performansı üzerindeki etkilerine baktık. Her deney çeşidi için en az 5’er adet deney yapılmıştır.

Colony Size Deneyi

            Sabit Değerler: Parameter Range (-5,5), Cycle (100), Limit (20)

  1. Deney Colony Size Değeri: 30
  2. Deney Colony Size Değeri: 50
  3. Deney Colony Size Değeri: 60
  4. Deney Colony Size Değeri: 75
  5. Deney Colony Size Değeri: 100

Deney Değerlendirmesi: Bulunan en iyi değerlere bakıldığında yaptığımız deney için Colony Size değişimi çok etki etmemiştir fakat Colony Size’ın artışı algoritmanın daha az döngüde en iyi değerlere ulaşmasını sağlamıştır. Yani koloni büyüklüğü problemin daha kısa sürede çözülmesini sağlamaktadır. Bu durumda eğer ki Colony Size’ı artırma imkânımız yoksa döngü (cycle) sayısının yüksek tutulması gerekir. Aksi takdirde en iyi çözüme çok yakın olan çözümlere ulaşamayabiliriz.

# of Cycle Deneyi (Döngü Sayısı)

            Sabit Değerler: Colony Size(50), Parameter Range (-5,5), Limit (20)

  1. Deney Cycle Değeri: 10
  2. Deney Cycle Değeri: 20
  3. Deney Cycle Değeri: 50
  4. Deney Cycle Değeri: 70
  5. Deney Cycle Değeri: 100

Deney Değerlendirmesi: Colony Size deneyinde 10 ile 100 döngü arasında deneyler yaptık. 10 beklenen değerler için çok bir sayı oldu ve hata oranı çok fazla çıktı. Belirlenen parametrelerde için bu deneyde cycle değerini artırmaya başladık ilk anlamlı sonuç 20’de çıkmıştır ve beklenen değere yüzde bir oranında hataya sahip değerler bulunmuştur. Bundan sonraki artışlar hata oranını giderek düşürmeye başlamış fakat yaklaşık 70 cycle’dan sonra hata oranında çok fazla bir değişim olmamaya başlamıştır. Belirlenen sabit parametrelere göre bu deney için yaklaşık 70 cycle değeri uygun bir değer olarak belirlenmiştir. Cycle değeri belli bir yere kadar olumlu etki etmekte, belli bir yerden sonra ise etmemektedir.

# Limit Deneyi

            Sabit Değerler: Colony Size(50), Parameter Range (-5,5), Cycle(80)

  1. Deney Limit Değeri: 5
  2. Deney Limit Değeri: 10
  3. Deney Limit Değeri: 20
  4. Deney Limit Değeri: 40
  5. Deney Limit Değeri: 50
  6. Deney Limit Değeri: 60
  7. Deney Limit Değeri: 70

Deney Değerlendirmesi: Limit deneyinde diğer parametreler sabit kalmak koşuluyla limit değeri olarak 5’ten 70’e kadar deneyler yaptık. 5 değerinde yüksek cycle değerlerinde beklenen değere yakın değerler elde ettik. Limit değerini artırmaya başladık ve yavaş yavaş daha az cycle’da beklenen değerlere çok yakın değerler elde etmeye başladık. Fakat sabit değerlerle birlikte yaklaşık 20 limit değerinden sonraki değerlerde çok tutarlı sonuçlar elde edemedir. Yani 20 için daha az iken, 40 ta cycle değeri arttı, ama 50’de yine azaldı. Bu deneyler sonucunda limit değerinin cycle sayısına göre ayarlanması gerektiğiniz düşünüyoruz. Çünkü bu deneyde cycle 80 iken limit değerini 70’e kadar artırdık. Belli bir noktadan sonra anlamsız sonuçlar elde ettik. Bu sebeple limit için bizim düşüncemiz cycle sayısının yaklaşık yüzde 10’u ile %25’i arasında bir değer alması ideal olacaktır.

KAYNAKLAR

Fikstür Oluşturma Algoritması – Fikstür Hazırlama (tek ve çift sayıda takım ile)

3 Yanıt

Lisans döneminde algoritma ödevlerimizden bir tanesi girilen takım sayısına göre fikstür oluşturan bir programdı. Aklıma gelince paylaşayım istedim.

ÇİFT SAYIDA TAKIM İLE FİKSTÜR OLUŞTURMA

Fikstür algoritmalarında mantık; n adet takım varsa, ligde n-1 adet hafta müsabaka olmalıdır. (Rövanşlar hesaba katılırsa hafta sayısı 2 x (n-1) olacaktır.) İlk haftanın fikstürü çekilir, diğer haftalar ise ilk hafta referans alınarak belirlenir. Bizim kullandığımız algoritmayı örnekle açıklayayım. Örneğin 6 takımlı bir lig oluşturalım. Bu takımları 1, 2, 3, 4, 5, 6 şeklinde ifade edelim. İlk hafta maçları şu şekilde olsun;

image2

Birinci haftayı oluşturduktan sonra ilk takımı sabit tutarak diğer takımları saat yönünün tersinde ilerletelim. Bu durumda ikinci hafta aşağıdaki şekilde olacaktır;

image3

İlk takımı sabit tutup diğer haftaları bu şekilde hesaplamaya devam ettiğimiz taktirde 6 takımlı ligin 5 hafta sürecek müsabakalarının fikstürü aşağıdaki gibi olacaktır.

image

Fikstür bu şekilde belirlendikten sonra ev – deplasman ayarları da yapılabilir.

TEK SAYIDA TAKIM İLE FİKSTÜR OLUŞTURMA

Farklı bir durum da tek sayıda takım olması durumudur. Bu durumda ilk hafta oluşturulurken bir takımın karşısına X yazılabilir. Böylelikle fikstür çekimi sonucunda karşısına X gelen takım o haftayı bay geçecektir.

Her iki durum için de fikstür ayarlaması yukarıdaki gibi yapıldıktan sonra rasgele her takım için bir sayı çekilir. Örneğin Galatasaray geldi kura çekti ve 2 çıktı, Fenerbahçe’ye 3 çıktı vs. Bu durumda her sayıya karşılık gelen takım belirlenmiş olur.

ALGORİTMA

Bazı talepler üzerine algoritmanın kabakoduyla alakalı biraz daha bilgi vermek istedim.

N adet takım olsun. Öncelikle takımları bir diziye attım. N-1 hafta maç olmalı (deplasmanları saymazsak, sayacaksak eğer fikstürün tam tersi olacak zaten).
Örnekte olduğu gibi 6 tane takım olsun (mantığını kavrayınca istenirse 500 olsun sorun yok). Tüm takımları bir diziye atalım. Daha sonra random olarak bir indis seçip sabit tutacağımız takımı belirleyelim ve o indisi diziden silelim. Bu durumda bir takım seçtik ve 5 adet takım dizide kaldı. Takım isimleri de 1, 2, 3, 4, 5 ve 6 olsun. Biz 1’i sabit seçmiş olalım. Bu durumda;
sabit takım – 1
takım_dizisi = [2, 3, 5, 6, 4]
sabit takım ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler (bu örnek için dizinin ikinci elemanı (3) ile beşinci (6), üçüncü elemanı (4) ile dördüncü elemanı (5)). Yani;
1-2, 3-4, 5-6
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiz şöyle olacak;
takım_dizisi = [4, 2, 3, 5, 6]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-4, 2-6, 3,5
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [6, 4, 2, 3, 5]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-6, 4-5, 2-3
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [5, 6, 4, 2, 3]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-5, 6-3, 4-2
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [3, 5, 6, 4, 2]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-3, 5-2, 6-4
Böylelikle 6 takım olduğu için 5 haftalık fikstür tamamlanmış oluyor.
Kısaca algoritma şu;
n tane takım için takımların hepsini diziye at. Bir tane random takım belirle ve sabit takım olarak seç. Bu takımı diziden sil.
indis = random (1,n)
sabit_takim = dizi(indis)
dizi.pop(indis)
 
for i = 1 to (n-1)
          i. hafta fikstur = 
          1. maç = sabit_takim:dizi(0)
          for j=1 to (n-2)/2:
                 j. maç = dizi(j+1):dizi(n-j)

 

Fikstür çekme ile ilgili sorunuz olursa bu yazıya yorum yazarak sorabilir veya mail atabilirsiniz. Bu yazı işinize yaramışsa veya hoşunuza gitmişse sayfadaki reklamlara tıklayarak teşekkür edebilirsiniz. 🙂

Johnson Algoritması–En Kısa Yol Problemi (The Shortest Path Problem)

Bir Cevap Yazın

En Kısa Yol Problemi’nden (The Shortest Path Problem) daha önce bahsetmiştim. Bu yazımda bu problemi çözmek için kullanılan algoritmalardan kısaca bahsedip, Johnson Algoritması’nın üzerinde duracağım. En Kısa Yol Problemi için üretilen algoritmaların bazıları şunlardır;

  • Djikstra Algoritması
  • Bellman Ford Algoritması
  • Floyd – Warshall Algoritması
  • Johnson Algoritması
  • A* Search Algoritması
  • Dinitz Algoritması
  • Tarjan Algoritması
  • GOR Algoritması
  • Dial Algoritması

Algoritmalardan bazılarına kısaca göz atacak olursak;

  • Dijkstra Algoritması: Single Source, Single Pair ve Single Destination problemlerini çözmek için kullanılır. Döngüye girme ihtimalinden dolayı negatif ağırlıklı bağlantıları kabul etmez. Basit bir algoritmadır. Buna karşı performansı yüksektir.
  • Bellman Ford Algoritması: Single Source problemlerini kenar ağırlıkları negatif olduğu durumlarda da çözebilmektedir.
  • A* Search Algoritması: İki nokta arasındaki en kısa yolu aramayı hızlandırmak için sezgisel yöntemler kullanarak çözüm arar.
  • Floyd – Warshall Algoritması : All pairs probleminin çözümünde kullanılır.
  • Johnson Algoritması : Floyd Warshall Algoritması’ndaki gibi all pairs problemini çözmeye yarar. Sparse(dağınık) ve yönlü graflar için kullanılan bir algoritmadır. Sparse graflarda Floyd-Warshall’dan daha hızlı çalışır. Daha yoğun grafiklerde daha hızlı çalışabilir.En önemli özelliği negatif kenarlar içeren graflar için çözüm sunar.

Johnson Algoritması (Johnson’s Algorithm)

1977 yılında Donald B. Johnson tarafından geliştirilmiştir. Bellman Ford, Reweighting ve Dijkstra Algoritması tabanlı, All pairs problemini çözmek için kullanılan bir algoritmadır. Sparse(dağınık) ve directed(yönlü) graflar için kullanılan güzel bir çözüm yoludur. Bağlantıların negatif olmasına izin vermektedir ve bu en önemli özelliğidir. Negatif bağlantıları reweighting yöntemiyle işlem sırasında ağırlıkları yeniden hesaplayarak pozitif ağırlıklara güncellemektedir. Bu yönüyle Floyd Warshall’a benzemektedir fakat O(V3) olan çalışma süresi Johnson Algoritması’nın tercih edilmesine neden olur. Ayrıca Floyd Marshall daha sık graflarda tercih edilirken, Johnson seyrek graflarda daha iyidir. Ağırlıkların pozitif olması durumunda Dijkstra’nın kullanılması daha iyi performans sağlar. Algoritmanın adımlarını aşağıdaki graf üzerinde açıklayalım.

1

  • Adım 1: Öncelikle grafa aşağıda görüldüğü üzere yeni bir düğüm ve bu düğümden grafta bulunan tüm düğümlere bağlantılar eklenir. Bu düğümün ve bağlantılarının ağırlığı sıfır olarak belirlenir.

2

  • Adım 2: Her düğüm için Bellman–Ford Algoritması bir kez çalıştırılır ve düğümlerin ağırlıkları belirlenir. Aşağıda görüldüğü üzere her düğümün ağırlığı içerisine yazıldı.

image

  • Adım 3 : Adım 4’te Dijkstra Algoritması kullanılacaktır. Bilindiği üzere Dijkstra Algoritması negatif bağlantı uzunluklarını kabul etmemektedir. Bu yüzden bu adımda ağırlıklar tekrar hesaplama yöntemiyle yenilecek ve negatif bağlantı kalmayacaktır. Yeniden hesaplama yöntemi şu şekildedir;  ŵ(u, v) = w(u, v) + d(s, u) – d(s, v)

4 x

Ağırlıkların yeniden hesaplanması Reweighting Teorem ile yapılır. Formülde yeni kenar ağırlığı eski kenar ağırlığı ile düğümün, algoritmanın birinci adımında eklenen yeni düğümüne olan ağırlığı ile toplanır. Bu değerden gidilecek olan düğümün S düğümüne olan ağırlığı çıkarılır ve yeni ağırlık bulunur. Reweightin işlemi sonucunda shortest path değişmezken, ağırlıkların hepsi nonnegative olur. Burada akla şu soru gelebilir; ağırlıkları bu şekilde hesaplayacağımıza tüm düğümlere minimum bağlantı uzunluğunu eklesek olmazmı? Olmaz çünkü bu en kısa yolun değişmesine sebep olabilir. Aşağıda ağırlıkların güncellenmiş hali bulunmaktadır. Kenarların yeni ağırlıklarının bulunma işlemine örnek verecek olursak ; eski ağırlığı 8 olan kenarın yeni ağırlığı yukarıda bahsettiğimiz yöntemle 8 + 0 – (-5) = 13 ‘e olarak hesaplanır.

3

Aşağıdaki grafikta tüm düğümlere minimum düğüm ağırlığının eklenmesi durumunda ortaya çıkacak bozulma görülmektedir. Birinci durumda kısa yol alttaki iken, ikinci durumda üstteki oluyor. Bu metod görüldüğü üzere kısa yolun değişmesine sebep oluyor.
5

  • Adım 4 : Birinci adımda eklenen düğüm graftan silinir ve geri kalan tüm düğümler için Dijkstra Algoritması uygulanır. Tüm çiftler arası en kısa yol bulunur. Aşağıda tüm düğümler için ağırlıkların Dijkstra Algoritması’yla yeniden hesaplanması görülmektedir.

8 9 10

ALGORİTMANIN KARMAŞIKLIĞI

Algoritmanın karmaşıklığına bakalım. Algoritmanın adımlarını kontrol edelim.

  • İlk adımda yeni düğüm ekleniyor ve her düğümün ağırlığı Bellman Ford ile hesaplanıyor. Bu durumun getirdiği karmaşıklık O(VE)’dir.
  • Daha sonra negatif kenarlardan kurtarmak için reweighting işlemi yapılıyor. Bu durumun getirdiği karmaşıklık O(E)’dir.
  • Her düğüm için Djikstra Algoritması’nın getirdiği karmaşıklık O(V2 logV + VE logV )’dir.

Bu durumda Johnson Algoritması’nın karmaşıklığı O(V2 logV + VE logV) olarak hesaplanır.

(V: Düğümler Kümesi , E: Bağlantılar Kümesi )

Kaynaklar

Shortest Path Problem – En Kısa Yol Problemi

Bir Cevap Yazın

Shortest Path Problem yani En Kısa Yol Problemi’nden önce bu konuyla ilgili olan Graph Theory’den bahsetmek istiyorum.

Graph Theory

Graf Teori yani Çizge Kuramı, çizgeleri yani grafları inceleyen matematik dalıdır. Graflar node (yada vertice) yani düğümler ve edge yani bağlantılardan oluşan bir çeşit ağ yapısıdır. Bağlantıların her birinin değeri vardır ve tek yada çift yönlü olabilirler. Bir G grafı, G = (V,E) şeklinde ifade edilir. Burada V düğümler kümesi , E ise bağlantılar kümesini ifade eder.

Shortest Path Problem

Shortest Path Problem, Graph Theory içerisinde önemli bir problemdir. Graf içerisinde belirtilen node’lar arasındaki en kısa yolu bulmayı amaçlar. Bu özelliğiyle Gezgin Satıcı Problemi’ne de (Travelling Salesman) benzer. Ancak Gezgin Satıcı’dan iki noktada ayrılır. Birincisi, hedef düğüme giderken tüm düğümlere uğramak zorunda değiliz. İkincisi de hedefe vardıktan sonra başlangıca dönmüyoruz.

En kısa yollar döngüler içeremez, ancak negatif bağlantı değerleri bulundurabilirler. Bununla birlikte n tane düğümün olduğu bir grafta en kısa yol n-1 kenardan daha fazla kenara sahip olamaz.

Kaynak nodun diğer tüm node’lara olan en kısa yollarını bularak Graph Theory içerisinde yer alan En Kısa Yol Ağacı’nı da (Shortest Path Tree) oluşturabiliriz.

Shortest Path Problemleri

· Single-Source (Single – Destination) : Verilen bir node’dan diğer tüm node’lara olan en kısa yolun bulunması problemidir.

  • Single-Pair: Verilen iki node arası en kısa yolun bulunması problemidir.
  • All-Pairs : Grafta bulunan tüm ikililer arası en kısa yolun bulunması problemidir.

En Kısa Yol Problemi’nin Görüldüğü Yerler

En Kısa Yol Problemi’ni çözen çeşitli algoritmalardan daha sonra bahsedeceğiz, ancak daha önce bu problem nerelerde görülür onlardan bahsetmek istiyorum.

  • Navigasyon cihazlarında güzergah ayarlaması sırasında
  • Dynamic Routing kullanan Network’lerde En ucuz yada hızlı hat ayarlaması yaparken
  • Limancılık, havacılık, postacılık güzergah ayarlaması esnasında
  • Hatta Rubik Cube’ü en az hamlede çözmek için dahi kullanılabilir.
  • Robot hareket planlaması

Kaynaklar

Quad Tree (Dörtlü Ağaç)

Bir Cevap Yazın

Quad dörtlü, tree ağaç demektir. QuadTree adı üstünde bir ağaç yapısıdır. Her nodun (node) dört adet çocuğu (child) vardır. İki boyutlu uzayda kullanılmaktadır. Üzerinde çalışılan bölge dörtlü alanlara bölünerek uygulanır.

Örnek verecek olursak; İlgilendiğimiz alan aşağıdaki gibi olsun. Alanı iki boyutlu bir uzay gibi  düşünelim. Bu bölgeye her hangi bir eleman geldiğinde bölge dörde bölünür. Ağacın şekli üçüncü resimdeki gibi olur. Root’un sadece ilk elemanı doludur.

1  3 2

Bölgeye eleman gelmeye devam etsin. İkinci eleman ilk elemandan farklı bir bölgede olduğu için alan bölme işlemine gerek kalmadı. Ağaçta ise root’un ikinci elemanı B nodu oldu.

quadtree1 5

Yeni elemanımız B ile aynı bölgede olsun. Bu durumda B’nin bulunduğu bölge dörde bölünecek ve ağacın yapısı değişecektir.

6 7

Bölgeye birkaç eleman daha ekleyelim ve ağacın durumuna bakalım.

8 9

E elemanı bölgeye eklendiğinde B’nin bulunduğu alan tekrar dörde bölünür. Ağaçta B bir alta geçerek E ile kardeş olur.

10 11

Bölgeye F elemanı eklendiğinde ise durum aşağıdaki ağaçtaki gibi olur.12 13

Sorularınız olursa yardımcı olmaya çalışırım. Konuyla ilgili buradan da bilgiye ulaşabilirsiniz.