Karınca Kolonisi Optimizasyonu (Ant Colony Optimization - ACO), ilk olarak Marco Dorigo ve arkadaşları tarafından 1990'ların sonunda geliştirilmiş bir optimizasyon algoritmasıdır. Bu algoritma, karınca kolonilerinin yiyecek kaynaklarına en kısa yolun nerede olduğunu bulma şeklini taklit eder.

Gerçek karınca kolonileri, yiyecek kaynaklarına en kısa yolu bulmak için feromon denilen bir kimyasal madde kullanır. Yiyeceğe giden her karınca, geri dönerken feromon bırakır. Diğer karıncalar bu feromonu algılar ve feromon yoğunluğu en yüksek olan yolu takip etmeye eğilimlidirler. Zaman içinde, en kısa yol en yüksek feromon yoğunluğuna sahip olacak ve karıncaların çoğu bu yolu takip edecektir.

ACO algoritması, bu feromon bırakma ve takip etme sürecini taklit ederek en kısa yolu (veya en uygun çözümü) bulur. Algoritma, her biri bir çözümü temsil eden "sanal karıncalar"dan oluşan bir koloni kullanır. Her iterasyonda, karıncalar rastgele bir şekilde çözüm alanını ararlar ve bu sırada feromon bırakırlar. Daha sonra, feromon yoğunluğuna göre çözümleri güncellerler: daha iyi çözümler daha fazla feromon bırakır, böylece diğer karıncalar bu çözümlere doğru yönlendirilir.

ACO algoritması genellikle seyahat satıcısı problemi gibi rotalama problemlarında kullanılır, ancak başka optimizasyon problemlarında da kullanılabilir. ACO'nun avantajlarından biri, algoritmanın karmaşık çözüm alanlarını etkili bir şekilde arayabilmesidir. Bununla birlikte, algoritmanın parametrelerinin (feromonun buharlaşma hızı, feromonun yoğunluğu vb.) dikkatlice ayarlanması gerekir ve bu, belirli bir problem için en iyi ayarları bulmayı zorlaştırabilir.

Ant Colony Optimization (ACO) örneği verilmiştir. Bu örnekte, bir karınca kolonisini kullanarak en kısa yol problemini çözeceğiz.

import numpy as np

# Parametreler
n_ants = 10
n_cities = 5
n_iterations = 100
decay = 0.1
alpha = 1
beta = 1

# Şehirler arası mesafe matrisi (rastgele oluşturulmuştur)
distances = np.random.rand(n_cities, n_cities)
distances = (distances + distances.T) / 2  # Simetrik matris oluşturuluyor

# Feromon matrisi
pheromones = np.ones((n_cities, n_cities))

# Karıncaların gezinti yolları
paths = np.zeros((n_ants, n_cities)).astype(int)

for iteration in range(n_iterations):
    # Yol oluşturma
    for ant in range(n_ants):
        visit = np.random.choice(n_cities)  # İlk şehiri seç
        paths[ant, 0] = visit

        for step in range(1, n_cities):
            not_visited = np.delete(np.arange(n_cities), paths[ant, :step])
            probabilities = pheromones[visit, not_visited] ** alpha / distances[visit, not_visited] ** beta
            probabilities /= probabilities.sum()
            
            visit = np.random.choice(not_visited, p=probabilities)  # Sonraki şehiri seç
            paths[ant, step] = visit

    # Feromon güncelleme
    pheromones *= (1 - decay)  # Buharlaşma
    for ant in range(n_ants):
        for step in range(n_cities - 1):
            i, j = paths[ant, step], paths[ant, step + 1]
            pheromones[i, j] += 1 / distances[i, j]  # Feromon bırakma

# En iyi yolun çıktısı
best_path_index = np.argmin([distances[path[:-1], path[1:]].sum() for path in paths])
best_path = paths[best_path_index]
print(f"En iyi yol: {best_path}")

örnek çıktı:

En iyi yol: [0 3 2 4 1]

Bu basit ACO örneği, belirli bir sayıda şehir arasındaki en kısa yol problemini çözmeye çalışır. Her iterasyonda, her karınca rastgele bir şehirden başlar ve daha sonra bir sonraki şehiri, o şehire olan mesafe ve o şehirdeki feromon yoğunluğuna bağlı olarak belirler. Daha sonra, karıncalar yollarını tamamladığında, feromon matrisi güncellenir: her karınca, ziyaret ettiği şehirler arasında feromon bırakır ve aynı zamanda tüm feromonlar bir miktar buharlaşır. Bu süreç, belirli bir sayıda iterasyon boyunca tekrarlanır. En sonunda, en kısa yol, tüm karıncaların oluşturduğu yollar arasında en kısa olanı olarak seçilir.

1. n_ants: Karınca sayısı. Bu parametre, algoritmanın her iterasyonda kaç tane çözüm arayacağını belirler. Daha fazla karınca, daha fazla çözüm araması ve potansiyel olarak daha iyi sonuçlar anlamına gelir, ancak bu aynı zamanda daha fazla hesaplama süresi gerektirir.

2. n_cities: Şehir sayısı. Bu, algoritmanın çözmeye çalıştığı problemin boyutunu belirler.

3. n_iterations: İterasyon sayısı. Algoritmanın kaç kez çalışacağını belirler. Daha fazla iterasyon, potansiyel olarak daha iyi sonuçlar anlamına gelir, ancak bu da daha fazla hesaplama süresi gerektirir.

4. decay: Feromon buharlaşma oranı. Her iterasyonun sonunda, feromon matrisi bu oranda azaltılır. Bu, eski çözümlerin zamanla önemsiz hale gelmesini sağlar ve algoritmanın yeni çözümleri keşfetmesine olanak sağlar.

5. alpha: Feromonun önemini belirler. Alpha, feromonların karıncaların bir sonraki şehiri seçerken ne kadar önemli olduğunu belirler.

6. beta: Mesafenin önemini belirler. Beta, mesafenin karıncaların bir sonraki şehiri seçerken ne kadar önemli olduğunu belirler.