KONUK YAZAR

Yayın Tarihi: 1 Haz 2012 | Konuk Yazarlar

0

KARINCA SÜRÜSÜ OPTİMİZASYONU

Bir karınca için yuvadan ayrılmak devler ülkesine girmek demektir ama yiyecek bulmanın da başka hiçbir yolu yoktur. Doğal olarak, karınca bu tehlikeli devler ülkesinde en kısa sürede yiyeceği bulmak ve hemen yuvaya dönmek ister ve bunun için iyi bir yol bulma stratejisine ihtiyaç duyar.

Benzer bir sorunla karşılaşan insansı topluluklar, bu sorunu evrim süreçleri içinde karmaşık bir sinir sistemi geliştirerek çözdüler. Bu da bazı bilim adamlarına göre modern insanın yolunu açtı. Oysa, sinir sistemi oldukça basit olan karıncanın insandaki kadar karmaşık stratejiler geliştirmesine olanak yoktu. Bununla beraber, karıncanın evrimi böceklerin zaten oldukça gelişmiş olan koku sistemlerini oldukça basit bir algoritma(1) ile birleştirdi, ve karınca ve benzeri böceklerin yol bulma sorununu müthiş bir şekilde çözdü.

Karıncaların yol bulma stratejileri, bu sürüleri inceleyen bilim insanlarına ilgi çekici gelmiştir. Çünkü karıncalar oldukça basit bir yöntem kullanmalarına rağmen, yol bulmakta insansılarla yarışacak kadar başarılı olabiliyorlar. Matematikçi ve mühendisler karınca davranışlarını taklit ederek oldukça karmaşık optimizasyon problemlerini çözebiliyorlar.

Optimizasyon, belirli matematiksel bir fonksiyonun en yüksek veya en düşük olduğu değerini bulmaya çalıştığımız matematik problemlerinin genel adıdır. Devler ülkesine adım atan karıncanın en büyük problemi şudur: yiyeceği yuvasına taşımalı ama devler ülkesinde olabildiğince az kalıp dönmelidir. Ayrıca strateji, bir sürü üyesinden yardım alınmadan ve farklı yer şekillerinde de uygulanabilmelidir.

Bu problem insanların da çözmek zorunda olduğu birçok probleme benzer. Örneğin Ankara’da basılan gazeteleri Türkiye’nin her iline dağıtmakla yükümlü bir gazete dağıtımcısının, ekonominin gereği olarak dağıtım yaparken en az benzin harcamak istemesi gibi, devler ülkesindeki karınca da aynı sorunla karşı karşıyadır. Öyleyse, bu tür problemlerde neden karıncaların izlediği stratejiyi kullanmayalım ki?

Karıncaların Yol Bulma Stratejisi

Karıncalar, insan dahil birçok canlının cinsel eşini bulabilmek için kullandığı koku yayma ve yayılan kokuları takip etme yönteminin benzerini kullanırlar. Karıncaların koku yayma ve koku alma yetenekleri oldukça güçlüdür ama yol bulma stratejisinde takip edilen koku, koku yayıcı karıncanın cinsiyetine bağlı değildir.

Karıncaların yol bulma stratejisi (Wikimedia Commons)

  1. Yuvadan çıkan karıncalar, bulundukları yerde diğer karıncalardan kaynaklanan baskın bir koku yoksa tamamen rastgele hareket ederler.
  2. Eğer herhangi bir yönden diğer karıncaların yaydığı bir kokuyu alabilmişse, karınca o tarafa yönelir. Birden çok yönden koku alıyorsa kokunun geldiği en baskın tarafa yönelir.
  3. Karıncanın yaydığı koku bir süre o bölgede kalabilir. Bu sayede bir yolu birden çok karınca tercih etmişse aradan belirli bir süre geçmiş olsa bile daha çok tercih edilen bölgeden daha baskın bir koku gelir.

Sürüdeki bütün karıncalar bu stratejiyi izlediğinde, başlangıçta rastgele başlayan sürü hareketi zamanla belli bir yol üstünde sabitlenir ki bu yol, yuva ile yiyecek arasındaki en kısa yoldur.

Yukarıdaki video, antsim programına ait bir animasyon. Görüldüğü gibi, karınca yuvası ile yiyecek arasında herhangi bir engel yok. Bu tür durumlarda karınca yuvası algoritması çok avantajlı değildir. Ama yine de karıncaların konumu hakkında hiçbir bilgisi olmadığı yiyeceğe nasıl ulaştığını görebilirsiniz. (Model, karıncaların tek algısının feromon olduğunu ve yiyeceğin kokusuz olduğunu varsayıyor).

Karıncıların Koku Alma Sistemleri

Karıncalar bir süre sonra sürekli geçtikleri yolda belirgin patikalar oluşturabiliyorlar. (Wikimedia Commons)

Yukarıda da incelediğimiz gibi karıncalar yol bulmak için ait olduğu sürüyle iletişim kurmalıdır ve bu iletişimi böcekler de oldukça gelişmiş olan koku yoluyla yapar. Birçok canlı çevresindeki kokuları algılar ve bu kokuları güzel ve kötü olarak sınıflar. Bu davranış, canlının ihtiyacı olan maddelere ulaşmasını ve ona zarar verebilecek olanlardan uzak durmasını sağlar. Ama, kendi türünden olan canlılarla iletişim kurmak için bunun yanında canlının koku üretebilmesi de gerekir. Bir canlının diğer canlılarla kokusal yolla sosyal ilişki kurmak için havaya yaydığı kimyasallara feromon diyoruz. Bilim insanları feromonların temelde  hayvanların hemen tamamında cinsel partner bulmak amacıyla evrimleştiğini düşünüyorlar.  Feromonların, karınca ve arılarda ana işlevleri olan cinsel eş bulma amacı dışında, sürü iletişimi için kullanılması Darwin’in fark ettiği, bir amaç için evrimleşmiş bir yapının evrim süreci içinde başka amaç için kullanılmasının iyi bir örneği.

Her ne kadar feromonların yapay taklitleri olan parfümlerle bu koku sistemini aldatıyor olsak da, insanlarda da cinsel sinyal vermek için koku kullanımı geçerli.

Doğadan Aldığımız Diğer Algoritmalar

Karınca Takip Algoritması bilim insanlarının doğayı gözlemleyerek keşfettikleri tek algoritma değil.  Kuş Sürüsü Optimizasyonları, yani kuşların, karıncalara benzer şekilde çok uzun mesafeleri kat ederken kullandıkları algoritmalar da bilim insanlarına ve mühendislere esin kaynağı oldu. Bunun yanında evrim teorisini temel alan çok sayıda algoritma kullanıyoruz. Bu algoritmaların bütününe Sezgisel Algoritmalar diyoruz. Karınca Kolonisi dışında en yaygın kullanılan sezgisel optimizasyon algoritmalarını şöyle sıralayabiliriz:

  1. Tavlama Taklit Algoritması (Simulated Annealing): Özellikle kristal atomlarının ardı sıra ısıtma ve soğutmalarla kristalin içindeki kusurların giderilmesi yöntemini taklit eder.
  2. Kuş Kolonisi Algoritması: (Particle Swarm Optimization Algorithm): Kuş sürülerinin uzun mesafeleri kat ederken kullandıkları takip yöntemini kullanır.
  3. Arı Sürüsü Algoritması: Karınca yerine arı davranışını taklit eden algoritmalardır.
  4. Genetik Algoritma: Evrimsel algoritmaların en ünlüsü, kusurları olan ve optimize edilmesi gereken veri bir DNA olarak kabul edilir ve üreme, mutasyon ve Darvinci doğal ayıklama sürekli uygulanır.

Kullanım Alanları

Karınca Sürüsü Algoritmasının ve diğer sezgisel algoritmaların kullanım alanları en kısa zaman problemleriyle sınırlı değildir. Karıncalar yalnızca bu amaç için kullansa da matematiksel formüller değiştirilerek aynı yapı en az kaynak (para veya enerji) veya başka optimizasyonlar için kullanılabilir. Örneğin yukarıda bahsettiğimiz gibi bir kargo şirketinin dağıtım rotasını belirlemek için kullanabilir -ki kargo şirketleri için sezgisel algoritmalar kullanan bu tür yazılımlar vardır. Bunun yanında en kısa zaman yerine maksimum sözcük ilişkisi koyarsak, rahatlıkla Google benzeri bir metin tarama ve arama sistemi elde ederiz. Google ve benzeri arama motorları arka planda sözcük ilişkisi ve sayfa değerini maksimize etmekte optimizasyon algoritmalarını kullanırlar (2). Google optimizasyon için kullandığı algoritmayı (ve bu algoritmanın bu yazıda bahsedilen sezgisel algoritmalardan biri olup olmadığını) açıklamamaktadır. Bununla beraber örneğin Karınca Optimizasyonu Algoritması bir arama motoru tarafından bu amaçla kullanılabilir (3).

Sonuç

Şu anda optimizasyon amacıyla yazılmış birçok programda yukarıda bahsedilen “Karınca Sürüsü Optimizasyonu” algoritması kullanılıyor. Bununla beraber, bu yöntem, optimizasyonla uğraşan mühendislerin doğadan esinlendikleri tek yöntem değildir. Bu bakımdan insan için hala doğa, bulunabilecek en iyi öğretmendir.

 Notlar:

(1) İsmini İslam Rönesansı matematikçilerinin en ünlüsü Harezmi’nin batı dillerindeki söylenişinden (Al- Khwarizm) alan algoritma, bir problemi çözmek veya bir veriyi işlemek için kullanılan yönergeler bütünüdür. Akla hemen bilgisayar yazılımlarını getirse de çok daha geniş bir kavramdır. Örneğin yemek tarifi veya bu yazıda bahsettiğimiz gibi bazı hayvanların bilişsel olmayan ama kurallı refleksleri de algoritmalardır.

(2) http://www.sirgroane.net/google-page-rank/
(3) http://www.hindawi.com/archive/2008/316145/ref/

Kaynaklar:

  • http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
  • http://iridia.ulb.ac.be/~mdorigo/ACO/index.html
  • Maniezzo, Gambardella, de Luigi (2004) “Ant Colony Optimization”
  • Kapak resmi kaynağı: Avustralya Müzesi

[box type=”shadow”] Konuk Yazar Hakkında

Ceyhun Çakar

1979 İstanbul doğumlu. 2002 yılında Orta Doğu Üniversitesinde Elektrik ve Elektronik Mühendisliği Lisansını tamamladı. Şu anda Gömülü Yazılım ARGE Yöneticisi olarak çalışıyor. Aynı zamanda Başkent Üniversitesi
Elektrik ve Elektronik Mühendisliği Ana Bilim Dalında yapay zeka ile tanıma sistemleri üzerine Yüksek Lisans yapıyor.

[/box]

Etiketler: , , , , , , , , , , , ,


Yazar

Açık Bilim Çevrimiçi Dergisi'ne konuk yazar olarak katkıda bulunmak ve destek vermek isteyebilirsiniz.






Yorum yapın (Facebook, Twitter gibi hesaplarınız geçerlidir.)

Back to Top ↑
  • Patreon’dayız

  • Bizi Takip Edin

  • iTunes Bağlantısı

  • Reklam Alanı

  • Destekçiler

  • E-POSTA LİSTESİ

    Yeni bir yayınımız yayımlandığında e-posta yoluyla haberdar olmak için adresinizi bu alana girin.

    Diğer 99.809 aboneye katılın

  • Hızlı Takvim

    Haziran 2012
    P S Ç P C C P
    « May   Tem »
     123
    45678910
    11121314151617
    18192021222324
    252627282930