Karınca Kolonisi Optimizasyonu Nedir?

Karınca kolonisi optimizasyonu (Ant Colony Optimization, ACO), gerçek karıncaların yuvayla yiyecek kaynağı arasında kısa yolları nasıl bulduğunu taklit eden bir optimizasyon yöntemidir. 1990'ların başında Marco Dorigo'nun çalışmalarıyla ortaya çıktı ve sürü zekâsı yöntemleri arasında yer alır.

Karınca kolonisi optimizasyonu nedir?

Doğada karıncalar yürürken feromon adlı kimyasal bir iz bırakır. Diğer karıncalar feromonun yoğun olduğu yolları tercih etme eğilimindedir. Kısa yol daha hızlı tamamlandığı için o yolda iz daha çabuk birikir ve zamanla koloninin çoğu kısa yolu kullanır. Feromon zamanla buharlaştığı için az kullanılan yollar unutulur.

Algoritma nasıl çalışır?

1. Yapay karıncalar, olası çözümleri adım adım inşa eder; her adımda bir sonraki noktayı, feromon miktarına ve mesafe gibi sezgisel bilgilere göre olasılıkla seçer.
2. Tüm karıncalar turunu tamamlayınca çözümlerin kalitesi ölçülür.
3. İyi çözümlerin geçtiği yollara daha fazla feromon eklenir.
4. Tüm yollardaki feromonun bir kısmı "buharlaştırılır" ki algoritma tek bir yola erken kilitlenmesin.
5. Döngü belirli bir sayıda tekrarlanır.

Nerelerde kullanılır ve sınırları neler?

ACO özellikle gezgin satıcı problemi, araç rotalama, ağ yönlendirme ve çizelgeleme gibi grafik üzerinde yol arama problemlerinde etkilidir. Varsayımsal bir örnekle, bir dağıtım şirketinin araçlarını onlarca durağa yönlendirmesi bu tür bir problemdir.

Diğer metasezgisel algoritmalar gibi ACO da en iyi çözümü garanti etmez. Feromon buharlaşma oranı ve karınca sayısı gibi parametrelerin probleme göre ayarlanması gerekir; kötü ayar, ya çok yavaş ilerlemeye ya da erken takılmaya yol açar.