Jump to content
  • entries
    55
  • comments
    2
  • views
    59,207

Karınca Kolonisi Sistemi (Ant Colony System - ACS)


Doğuhan ELMA

253 views

Karınca Kolonisi Sistemi (Ant Colony System - ACS), Karınca Kolonisi Optimizasyonu algoritmasının (ACO) bir türüdür. ACS, 1997 yılında Dorigo ve Gambardella tarafından önerilmiştir. Bu algoritma, gerçek karıncaların yiyecek arama davranışından esinlenerek karmaşık optimizasyon problemlarını çözmek için kullanılır. 

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

ACS algoritması, bu feromon bırakma ve takip etme sürecini modelleyerek optimizasyon problemlarını çözer. 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ı araştırır ve bu sırada feromon bırakır. 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 yönlendirilir.

Özellikle, ACS algoritması, seyahat eden satış elemanı problemları (TSP) gibi çeşitli yol bulma ve optimizasyon problemlarında çok etkilidir. TSP, bir satış elemanının bir dizi şehri ziyaret edip başlangıç noktasına dönmesi gereken bir durumda, toplam yolun en kısa olmasını sağlayacak en iyi rotayı bulmayı içerir.

Bu algoritma, gerçek dünyadaki karınca kolonilerinin çözüm bulma stratejilerini kullanarak genel amaçlı bir optimizasyon algoritması oluşturmuştur. Ancak, algoritmanın parametrelerinin dikkatlice seçilmesi gerekiyor. Bu parametreler, feromonların buharlaşma hızını, feromon güncellemesinin ağırlığını ve karıncaların rastgele seçim ve feromon izleme arasında nasıl bir denge kurduğunu belirler. Bu parametrelerin doğru şekilde ayarlanması, algoritmanın performansını büyük ölçüde etkileyebilir.

Karınca Kolonisi Sistemi (Ant Colony System - ACS) ö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
Q = 1
rho = 0.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] += Q / distances[i, j]  # Feromon bırakma

    # Lokal feromon güncellemesi
    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 - rho) * pheromones[i, j] + rho * Q

# 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}")

Bu basit ACS ö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: daha iyi çözümler daha fazla feromon bırakır, böylece diğer karıncalar bu çözümlere yönlendirilir. Her iterasyon sonunda, feromon matrisi belirli bir oranda decay (buharlaşma) uygulanır. Ayrıca, her karınca feromon güncellemesi sırasında, daha önce ziyaret ettiği rotalar üzerinde lokal bir feromon güncellemesi yapar. 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.

Bu parametrelerin her biri, Karınca Kolonisi Sistemi (ACS) algoritmasının nasıl çalıştığını kontrol eder:

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.

7. Q: Feromon bırakma miktarı. Her karınca, yolunu tamamladığında feromon matrisine bu miktarı ekler.

8. rho: Lokal feromon güncelleme oranı. Her karınca, feromon bıraktığı rotalarda, bu oranda lokal bir feromon güncellemesi yapar.

Bu parametrelerin her birinin doğru şekilde ayarlanması, algoritmanın performansını büyük ölçüde etkileyebilir. Genellikle, bu parametreler, problem tipine ve kullanılan özel ACS versiyonuna bağlı olarak farklılık gösterir.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...