Ile gerçekleştirir. Birincisi, sadece en iyi karıncalara feromen bırakması izin verilmesi



Yüklə 445 b.
tarix06.05.2018
ölçüsü445 b.
#42242











ile gerçekleştirir. Birincisi, sadece en iyi karıncalara feromen bırakması izin verilmesi,

  • ile gerçekleştirir. Birincisi, sadece en iyi karıncalara feromen bırakması izin verilmesi,

  • diğeri ise bir şehirden diğer bir şehre gidilirken denge unsuru olarak bir pseudo-

  • random orantı kuralı kullanılmasıdır. 1997’ de ise Hoos ve Stutzle feromen izini

  • maximum ve minimum aralıklarda sınırlayan MIN-MAX Ant System adında bir

  • algoritma önermişler, 1999’ da Bullnheimer, Hartl ve Stauss ASRank adı altında

  • Elitist Strategy nin gelişmiş bir çeşidini sunmuşlardır. Bu algoritmaya göre her tur

  • sonunda karıncalar tur uzunluklarına göre sıralanmakta, sadece sıralamadaki belli

  • sayıda en iyi karıncaların ve o ana kadarki en iyi karıncanın belli bir miktara göre

  • feromen bırakmasına izin verilmektedir. Bu temel algoritmalardan başka daha bir

  • çok algoritma ACO alanında geliştirilmiş ve geliştirilmektedir. İşte AS den bu güne

  • kadar bu kadar gelişim gösteren ACO algoritmaları bugün NP-Hard (Zor)

  • problemlerin çözümünde genetik algoritmalar, tavlama benzetimi, tabu

  • araştırmaları gibi diğer meta-sezgisel yaklaşımlı rakiplerine rağmen en iyi

  • algoritmalar haline geldiler.



KARINCA SİSTEMİ

  • KARINCA SİSTEMİ

  • Karınca kolonileri meta sezgiseli, doğal karıncaların yuvaları ile besin kaynakları arasında izledikleri yolların

  • izlenmesi sonucu ortaya çıkan bilimsel gerçekler üzerine doğmuştur. Gerçek karıncalar ile ilgili deneyler

  • Goss ve arkadaşları [4] tarafından 1989 yılında laboratuar ortamında yetiştirilmiş karınca kolonileri üzerinde

  • yapılmıştır. Bu çalışmalarda elde edilen sonuçlar; Pek çok karınca türü neredeyse kördür, karıncalar

  • yuvalarından yiyecek kaynağına veya tersi yönde hareket ederlerken geçtikleri yollara feromen adı verilen bir

  • tür kimyasal madde bırakmaktadırlar, karıncalar bir yol seçmelerigerektiği zaman bu seçimi alternatif yollar

  • üzerine bırakılmış olan feromen madde yoğunluğuna göre belirlemektedirler ve karıncaların bu hareketleri

  • merkezi bir kontrol ile sağlanmamaktadır şeklinde özetlenmiştir. Karıncaların yuvaları ile yiyecek kaynağı

  • arasındaki hareketleri Şekil 1’degösterilmiştir[5]. Şekil1’de görüldüğü gibi,karıncalar yuvalarının etrafındaki

  • alanda yiyecek kaynaklarını rassal bir şekilde ararlar. Bir karınca bir yiyecek kaynağı bulduğu zaman kaynağın

  • kalitesini veya miktarını değerlendirir ve bir miktar yiyecek alarak yuvasına geri döner. Bu geri dönüş sırasında,

  • bulduğu yiyecek kaynağının kalitesi veya miktarıyla doğru orantılı olacak şekilde kullandığı yola feromen maddesi

  • koyar. Böylece diğer karıncalar bu yolun sonundaki yiyecek kaynağının kalitesi veya miktarı konusunda bilgi

  • sahibi olurlar. Yuvaya yakın kaynaklara ulaşmak daha kolay olacağı için bu bölgelerde feromen

  • maddesinin yoğunluğu daha fazla olacaktır. Karıncaların bu hareketlerinin sayısal bir örneği Şekil 2’de verilmiştir

  • [6]. Karıncaların bu önemli özellikleri Hewlett-Packard ve British Telecom’daki araştırmacılar tarafından

  • iletişim ağlarının dengelenmesi ve mesaj rotalaması problemlerinde kullanılmıştır [7]. Burada ağ üzerinde

  • yapay karıncaların feromen bırakma ve bu bilgiyi kullanma özellikleri simule edilmiş ve elde edilen

  • sonuçlara göre rotalama yapılmıştır. Doğal karıncaların bu davranış kalıplarının, özellikle en kısa yol problemleri

  • olmak üzere, pek çok kombinatoriyel optimizasyon probleminde kullanılabileceği ilk kez 1992 yılında Marco

  • Dorigo ve arkadaşları tarafından ortaya atılmıştır [8].Karıncaların doğal hareketleri ile kombinatoriyel

  • optimizasyon problemlerinin uyuşan karakteristik



Şekil 1. a) Karıncalar A-E arasındaki yolu izlemektedirler. b)Yolun bir yerine bir

  • Şekil 1. a) Karıncalar A-E arasındaki yolu izlemektedirler. b)Yolun bir yerine bir

  • engel konulmuştur ve karıncalar hangi yönü seçeceklerine rasgele karar verirler.

  • c)Kısa olan yolda daha fazla feromen birikir.



Şekil 2. A) Karıncalar bir karar noktasına gelirler. B) Bir kısım karınca yukarıdaki

  • Şekil 2. A) Karıncalar bir karar noktasına gelirler. B) Bir kısım karınca yukarıdaki

  • yolu bir kısmı ise aşağıdakini seçer. Seçim tümüyle rassaldır. C) Karıncalar

  • neredeyse sabit bir hızda yürüdükleri için aşağıdaki ve kısa olan yolu seçen

  • karıncalar turlarını daha çabuk bitirirler ve bir sonraki karar noktasına daha çabuk

  • ulaşırlar. D) Kısa olan yolda feromen birikmesi daha fazla olur.



özellikleri;Gerçek karıncaların arama alanı ile kombinatoriyel problemlerin mümkün

  • özellikleri;Gerçek karıncaların arama alanı ile kombinatoriyel problemlerin mümkün

  • sonuçlar kümesi, bir kaynaktaki yiyecek miktarı ile amaç fonksiyonu, feromen madde ile hafıza’dır [9].Karınca Kolonileri Meta sezgiselinden türetilmiş ve çeşitli problemlerin çözümünde kullanılan çok sayıda algoritma vardır. Bu algoritmalar formülasyon olarakbirbirinden ayrılmakta fakat hepsi karınca kolonileri metasezgiselinin ortak özelliklerini Kullanmaktadır.



Karınca Sisteminin İşleyişi

  • Karınca Sisteminin İşleyişi

  • Karınca sisteminin işleyişi, tüm mümkün komşu düğüm noktalarının gösterildiği bir

  • grafik üzerinde gösterilecektir. Bu grafikte, t=0 anında tüm karıncalar başlangıç

  • noktasındadırlar.Sistemin başlangıç konumu Şekil 3’de gösterilmiştir [2]. Şekil 3’de

  • gösterilen sistem, 3 iş ve 4 adet makineden oluşan bir atölye sistemi olarak

  • düşünülebilir.



Şekil 4’de karınca aynı düğüm noktasını bir kez daha seçememe kısıtı altında, tüm

  • Şekil 4’de karınca aynı düğüm noktasını bir kez daha seçememe kısıtı altında, tüm

  • düğüm noktalarını seçer ve bir tur böylece bitmiş olur. Karıncanın seçtiği tüm düğümler

  • Şekil 5’de gösterilmiştir.



Geliştirilmiş Karınca Sistemleri

  • Geliştirilmiş Karınca Sistemleri

  • Max-Min Karınca Sistemi: Max-Min karınca sistemi, karınca sistemiyle aynı olasılık

  • fonksiyonunu kullanmaktadır. İki algoritma arasındaki farklılık feromen

  • güncelleştirmesindedir [11]. Max-Min karınca sisteminde, bulunan iyi sonuçlardan

  • daha fazla faydalanabilmek için, her tur sonunda sadece bir ve en iyi sonucu bulan

  • karıncanın feromen eklemesine izin verilir. Ayrıca karıncaların sürekli aynı sonucu

  • bulmasını önlemek için max-min karınca sistemi algoritmasında feromen

  • güncelleştirmesine dair bir üst limit ve alt limit belirlenir. Son olarak, bu

  • algoritmada problemin başlangıcında tüm feromen miktarları belirlenen üst limite

  • eşitlenir [12].Mertebe Temelli Karınca Sistemi: Bu algoritma da karınca sistemi

  • formülasyonunu kullanmaktadır fakat farkı feromen madde güncelleştirmesinde

  • olmaktadır [13]. Bu algoritmada yalnızca en iyi çözümü bulan karınca ve o tur içerisinde

  • iyi çözümler bulan belli sayıda karıncanın feromen eklemesine izin verilmektedir.



3. ANT SYSTEM ALGORİTMASI

  • 3. ANT SYSTEM ALGORİTMASI

  • Karıncaların feromen bırakma ve takip etme mantığı üzerine kurulu olan ilk algoritmadır. Bu algoritmadan kastedilen yukarıda da bahsedildiği gibi Ant-Cycle algoritmasıdır. Bu algoritma ilk olarak Travelling Salesman Problem(TSP) problemi üzerinde

  • denenmiştir. TSP problemi bir kişinin, verilen şehirler üzerinden sadece bir kez geçmek şartıyla, tüm şehirleri dolaşarak en kısa turu bulması problemidir. Bu problem NP-Hard bir problemdir. Şekil 1’de de gösterildiği gibi bir çok tur ihtimali

  • bulunmaktadır ve normal algoritmik yöntemlerle zaman karmaşıklığı O(n!) dir.



ilk olarak TSP nin seçilmesinde ise;

  • ilk olarak TSP nin seçilmesinde ise;

  • Shortest path problemi olduğu için kolay

  • adapte edilebilir olması

  • NP-hard bir problem olması

  • Çokça kullanıldığı için başka algoritma

  • testleriyle kolayca karşılaştırılabilir olması Herkesin kolayca anlayabileceği bir problem

  • olması

  • rol oynamıştır.[4]

  • Ant System algoritmasında, karıncalar sonucu sırayla çizgedeki (graph) şehirleri gezerek paralel bir şekilde çözerler. Her karıncanın bir şehirden diğerine geçmesinde olasılığa dayalı bir kural uygulanır. Karınca k nın t. turunda i şehrinden j şehrine geçerken uygulanan olasılık fonksiyonu pkij (t) aşağıdakilere bağlıdır;

  • j şehrine gidilip gidilmediği ve ziyaret

  • edilmemiş şehirler: Her sanal karınca

  • gerçeğinden farklı olarak daha önce uğradığı

  • yerlerin listesini tutar (Tabu Listesi). Tur

  • sonunda liste tamamen dolarken yeni bir tur

  • için liste yenilenir.

  • Problem boyunca sabit kalan ve sezgisel

  • seçimliliği etkileyen sezgisel değer ηij : Bu

  • değer TSP için görünürlük (visibility) olup

  • iki şehrin arasındaki uzaklığın tersidir

  • (1/dij ).

  • İki şehir arasındaki feromen miktarı:

  • Karıncaların turları sonunda attıkları turun

  • uzunluğuna bağlı olarak bıraktıkları

  • feromen miktarıdır. Bu değer problem

  • devam ettikçe değişir ve öğrenilmiş yönleri

  • seçmede etkin rolü oynar.



Bu fonksiyon aşağıdaki gibi formülize edilir.

  • Bu fonksiyon aşağıdaki gibi formülize edilir.



Diğer önemli bir parametre ise sistemde var olan

  • Diğer önemli bir parametre ise sistemde var olan

  • karınca sayısıdır. Kullanılan karınca sayısı çok fazla olursa sub-optimal sonuçlara

  • neden olurken, bu sayının az olması feromen buharlaşması nedeniyle beklenen

  • kollektif çalışma özelliği kaldıracaktır. O yüzden Dorigo karınca sayısının şehirlere

  • eşit olmasını (m = n) ve karıncaların başlangıçta rasgele şehirlere dağıtılmalarını uygun

  • bulmuştur.Bu verilen bilgilere göre AS algoritması Şekil 2’deki gibidir.



Şekil 2. Ant System Algoritması

  • Şekil 2. Ant System Algoritması



Son olarak bu konuda yapılan araştırmalar ve testler sonucunda şunu söyleyebiliriz ki;

  • Son olarak bu konuda yapılan araştırmalar ve testler sonucunda şunu söyleyebiliriz ki;

  • Algoritma O(t.n2.m) (eğer n = m ise O(t.n3))

  • zamanda çözüm yapar.(t = NCMAX).

  • Problemin doğru çözülmesinde parametre

  • ayarlarının güzel yapılması etkilidir. Yanlış

  • verilen kararlarla çalışan algoritma iyi

  • sonuçlar vermez. Parametre değerlerinin

  • seçim kuralları ise yapılan bir çok deney

  • sonucunda anlaşılmıştır.

  • Bu algoritma yalnızca küçük ölçekli

  • TSP’lerde (75 şehirden az) optimal sonuçlar

  • üretirken daha büyük ölçeklilerde optimal

  • sonuçlardan uzaklaşılır. Bu ise bu algoritma

  • üzerinde düşünülüp yeni stratejilerin

  • bulunmasına (Örneğin Elitist Strategy)

  • olanak tanımıştır.



4. EĞİTİMDE GÖRSELLE ŞTİRME VE ALGORİTMA SİMÜLASYONU

  • 4. EĞİTİMDE GÖRSELLE ŞTİRME VE ALGORİTMA SİMÜLASYONU

  • Bir çok öğrenci, bazı algoritmaların anlaşılması ve analiz edilmesinin zor olduğunu

  • söylerken eğitmenler de yine bazı algoritmaların anlaşılmasının zorluğundan

  • bahsederler.Bunun en büyük sebeplerinden birisi de algoritmaların soyut verilerden

  • oluşması ve karmaşık bir yapıya sahip olmalarıdır. Algoritma simülasyonları ve

  • görselleştirilmesi, algoritmaları grafiksel olarak göstererek, öğrencilerin ve eğitmenlerin

  • bu problemine çözüm bulmak için geliştirilen yazılımlardır.[5]Kara tahtaya yapılan ve

  • kitaplardaki grafiksel gösterimler ve anlatımlar da öğrenmeyi sağlayabilir ama dinamik

  • ve sembolik resimlerle ifade edilmiş bir görselleştirme,algoritmanın mantığının

  • anlaşılmasında daha etkili olacaktır. Fakat bu bir gerçek olmasına rağmen bu

  • tip görselleştirme uygulamaları çok yaygınlık kazanmamıştır. Bunun sebepleri ise

  • eğitmenlerin;

  • Bu uygulamaları öğrenmek için yeterli

  • zamanlarının olmaması

  • Bunların diğer sınıf aktivitelerinin

  • zamanından çalacağı düşünmeleri

  • Bu tip uygulamaların çok zaman alıcı ve

  • güç olmasından dolayı çekinmeleri

  • Bu uygulamaları eğitimsel olarak faydalı

  • bulmamaları olarak söylenebilir.[5]



Bu dört sebep bir algoritma simülasyonu yaparken bir köşeye bırakılamaz.

  • Bu dört sebep bir algoritma simülasyonu yaparken bir köşeye bırakılamaz.

  • Çünkü yapılan test ve deneyler ne kadar da bu gösterme ve simülasyonların

  • öğrenmede etkili olduğunu gösterse de [5][6][7]var oluş amaçlarına (öğrenmeye

  • yardımcılık) ulaşamayan simülasyonların gerçekleştirilmesi, hem zaman kaybı

  • hem de hüsranla sonuçlanacaktır. Bu yüzden simülasyonu tasarlarken onu

  • etkin yapacak etkenler iyice düşünülüp ona göre karar verilmesi gereklidir.

  • Algoritma simülasyon ve görselleştirimlerinin bir başka kullanım sebebi ise

  • konuya ilgiyi arttırmak ve konuyu daha zevkli bir hale getirmektir. Özellikle

  • yukarıda bahsedilen Karınca Kolonisi Optimizasyonu algoritmaları gibi yeni

  • gelişmekte ve kullanımı gittikçe yaygınlaşmakta olan bu tip algoritmalara

  • dikkat çekebilmek ve bunlara ilgiyi arttırmak için simülasyonlar

  • gerçekleştirmek algoritmanın öğreniminden çok daha farklı kazanımları

  • sağlayabilir.



5. UYGULAMA

  • 5. UYGULAMA

  • Uygulamamızda ACO algoritmalarının önemini ve çıkış

  • Noktasını göz önüne alarak ACO

  • algoritmalarının ilki olan Ant Sistem algoritmasının uygulaması ve

  • görselleştirmesi gerçekleştirilmiştir. İnternet üzerinden de

  • işletilebilen bu Ant System Algoritması simülasyonu yoluyla;

  • Ant Colony Optimization algoritmalarını

  • öğrenciye daha iyi tanıtmak, öğretmek ve bu

  • konuya olan ilgilerini arttırmak

  • Ant System algoritması etkileyen

  • parametrelerin daha iyi anlaşılmasını

  • sağlamak

  • amaçlanmıştır. Daha önce de bahsettiğimiz gibi eğer etkin bir

  • simülasyon yapmak istiyorsak kararlarımızı amaca uygun

  • vermek zorundayız. Bu yüzden bu simülasyonu geliştirirken

  • amacımıza uygun olacak şekilde bazı kriterleri gerçekleştirdik.

  • Bunlar;

  • Ant System algoritmasının doğasına uygun olacak şekilde

  • simülasyonu gerçekleştirmek • Diğer ACO algoritmaları yerine Ant System algoritmasını ve

  • problem olarak TSP yi seçmek. Bu ACO algoritmalarının çıkış

  • noktasını anlatabilmek için önemlidir.



Şekil 3 ve şekil 4’de görüldüğü gibi kullanıcıların şehirleri istedikleri gibi

  • Şekil 3 ve şekil 4’de görüldüğü gibi kullanıcıların şehirleri istedikleri gibi

  • şehireklemelerine izin vererek farklı koşullarda çalışan algoritmanın çalışmasını

  • göz ile analiz edebilmeleri sağlamak.



Şekil 5’te de gösterildiği gibi algoritmada kritik rol oynayan parametreleri

  • Şekil 5’te de gösterildiği gibi algoritmada kritik rol oynayan parametreleri

  • değiştirmeolanağı sağlanarak parametre etkilerinin daha kolay anlaşılmasını

  • sağlamak. Çünkü görsel olmayan çözümlerde sadece sonuçla

  • incelenebildiğinden bu etkiler fazla anlaşılamayabilmektedir.



Şekil 6. Simülasyonun Adım Adım Çalışması (Kırmızı yollar o anki en iyi turu, açık

  • Şekil 6. Simülasyonun Adım Adım Çalışması (Kırmızı yollar o anki en iyi turu, açık

  • mavi Kesikli çizgili yollar ise o anki turunu tamamlayan karıncanın turunu

  • göstermekte)



6. SONUÇLAR

  • 6. SONUÇLAR

  • Sürü zekası uygulamaları yapay zeka ve yapay yaşam kapsamı altındaki

  • multi-agent sistem yaklaşımları olup optimizasyon problemleri,robotbilim,

  • telekomünikasyon, veri madenciliği gibi bir çok konuda başarı sonuçlar

  • veren uygulamalardır. Bunlardan biri olan Karınca Kolonisi Optimizasyonu

  • Algoritmaları da zamanla geliştikçe yapay zekanın önemli bir alanı olan TSP

  • gibi NP-Hard problemlerin çözümünde genetik algoritmalar gibi rakiplerine karşı

  • üstünlüğünü göstererek önemini daha da arttırmaktadır.Fakat bu konunun

  • bilgisayar bilimlerinden başka biyoloji ile ilintili olması ve tamamen

  • formülizasyona dayalı ve dağınık bir yapıda olan algoritmalardan oluşması

  • konuya adaptasyonu ve öğrenmeyi güçleştirmektedir. Algoritma simülasyonları

  • ise öğrenme sürecini kısaltan uygulamalardır. Geliştirdiğimiz uygulamada

  • bu kriterler göz önüne alınarak bir simülasyon gerçekleştirilmiştir. Bu

  • yöntemlerin çıkış noktası olan Ant System algoritmasını görselleştirmek

  • yoluyla kullanıcıların konuya hızlı uyum sağlaması

  • hedeflenmiştir. Kritik rol oynayan parametrelerin ve karınca davranışlarının

  • etkileri grafiksel olarak görselleştirilerek daha iyi verim alınmıştır. Karmaşık

  • görünmesi nedeniyle beklenenden az kişinin çalışma ve araştırmalar yapmakta

  • olduğu bu alan grafikler yardımı ile eğlenceli hale getirilmiştir.



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə