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,

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