Karınca Kolonisi Optimizasyonu (ACO)

Karınca kolonisi optimizasyonu nedir?

Karınca kolonisi optimizasyonu (ACO), gerçek karıncaların yiyecek ararken izledikleri davranıştan esinlenen bir metasezgisel (metaheuristic) optimizasyon yöntemi. Marco Dorigo'nun 1990'ların başında ortaya attığı yaklaşım, tek tek denenemeyecek kadar büyük problemlere "yeterince iyi" çözümler bulmak için kullanılır.

Karıncalar yürürken feromon denen kimyasal bir iz bırakır. Diğer karıncalar bu izi takip etme eğilimindedir; kısa yollar daha hızlı kat edildiği için üzerlerinde daha çok feromon birikir ve zamanla koloni en kısa yolda birleşir. Bu dolaylı haberleşme biçimine stigmerji denir — karıncalar birbiriyle doğrudan konuşmaz, ortamı değiştirerek iletişim kurar.

Nasıl çalışır?

ACO bu fikri yapay karıncalara taşır. Her yapay karınca çözümü adım adım kurar ve her adımda nereye gideceğine iki şeye bakarak olasılıksal karar verir: o yoldaki feromon miktarı ve problemin kendi sezgisel bilgisi (örneğin iki şehir arası mesafe).

Bütün karıncalar birer çözüm ürettikten sonra iki şey olur:

• Feromon bırakma — daha iyi çözümlerin kullandığı yollara daha çok feromon eklenir, böylece o yollar bir sonraki turda daha cazip olur.
• Buharlaşma — tüm feromon zamanla azalır. Bu, kolonin kötü bir yola erkenden saplanıp kalmasını engeller ve yeni yolları keşfetmeye alan açar.

Bu döngü tekrarlandıkça çözümler giderek iyileşir. İlk ve en bilinen versiyonu olan Ant System, Gezgin Satıcı Problemi (TSP) üzerinde denenmiştir.

Neden önemli?

ACO, bütün olasılıkları tek tek denemenin imkânsız olduğu dev arama uzaylarında işe yarar. Merkezî bir kontrol yok; basit kuralları izleyen çok sayıda ajanın ortak davranışından akıllı bir sonuç çıkar. Bu dağıtık yapı onu özellikle sürekli değişen problemlerde (örneğin ağ trafiği) dayanıklı kılar.

Genetic algorithm ve simulated annealing gibi doğadan esinlenen diğer yöntemlerle aynı aileden; hiçbiri en iyi çözümü garanti etmez ama pratikte çok hızlı biçimde kaliteli çözümlere ulaşır.

Kullanım alanları

En klasik örneği rota ve lojistik: teslimat araçlarının güzergâhını planlamak, telekom ağlarında paket yönlendirmek. Üretim planlama (scheduling), görev atama, baz istasyonu yerleşimi ve özellik seçimi (feature selection) gibi alanlarda da sık görülür. Türkiye'deki mühendislik literatüründe metasezgisel yöntemler arasında en çok çalışılanlardan biri.