Gezgin Satıcı Probleminin Genetik Algoritma ile çözümü

Optimizasyon, günümüz iş dünyasının ve bilimsel araştırmaların kalbinde yer alan bir kavram. Kaynakların en verimli şekilde kullanılması, maliyetlerin düşürülmesi ve performansın en üst düzeye çıkarılması gibi hedefler, karmaşık problemlerin etkili çözümlerini gerektiriyor. Bu karmaşık problemlerden biri de ünlü “Gezgin Satıcı Problemi” (TSP – Traveling Salesperson Problem). Peki, doğadan ilham alan bir yaklaşımla bu zorlu probleme nasıl çözüm bulabiliriz? Cevap: Genetik Algoritmalar!

Bu yazımızda, önce Genetik Algoritmaların ne olduğunu ve nasıl çalıştığını inceleyecek, ardından gerçek dünya koordinatları üzerinde Gezgin Satıcı Problemi’ni adım adım nasıl çözdüğümüzü ve bu süreci animasyonla nasıl görselleştirdiğimizi anlatacağız.

Genetik Algoritmalar: Doğadan İlham Alan Çözüm Sanatı

Genetik Algoritmalar (GA), Charles Darwin’in evrim teorisinden esinlenerek geliştirilmiş, arama ve optimizasyon problemlerini çözmek için kullanılan güçlü bir hesaplamalı yöntemdir. Temel fikir, “en uygun olanın hayatta kalması” prensibine dayanır. Bir problem için potansiyel çözümlerden oluşan bir popülasyon oluşturulur ve bu popülasyon, genetik operatörler (seçilim, çaprazlama ve mutasyon) aracılığıyla nesiller boyunca evrimleştirilerek daha iyi çözümlere ulaşılmaya çalışılır.

Temel Kavramlar Nelerdir?

Genetik Algoritmaların temel yapı taşları şunlardır:

• Birey (Kromozom): Çözüm uzayındaki potansiyel bir çözümü temsil eder. TSP özelinde bu, şehirlerin ziyaret edilme sırasını gösteren bir rotadır.
• Popülasyon: Bir grup bireyden (potansiyel çözümden) oluşan kümedir.
• Uygunluk Fonksiyonu (Fitness Function): Bir bireyin (çözümün) ne kadar iyi olduğunu değerlendiren bir fonksiyondur. TSP için bu, rotanın toplam mesafesidir (daha kısa mesafe, daha yüksek uygunluk).
• Seçilim (Selection): Popülasyondaki daha iyi (daha uygun) bireylerin bir sonraki nesli oluşturmak üzere seçilme olasılığının daha yüksek olduğu süreçtir. Turnuva seçimi gibi çeşitli yöntemler kullanılır.
• Çaprazlama (Crossover): İki ebeveyn bireyden genetik bilgi alarak yeni yavru bireyler oluşturma işlemidir. Amaç, ebeveynlerin iyi özelliklerini yavrulara aktarmaktır. TSP için “Sıralı Çaprazlama (Ordered Crossover – OX1)” gibi özel yöntemler kullanılır.
• Mutasyon (Mutation): Bir bireyin genetik yapısında rastgele küçük değişiklikler yaparak çözüm uzayında çeşitliliği artırma ve yerel optimumlara takılıp kalmayı önleme işlemidir. TSP için “Takas Mutasyonu (Swap Mutation)” bir örnektir.
• Jenerasyon (Nesil): Algoritmanın bir iterasyonudur. Her jenerasyonda yeni bir popülasyon oluşturulur.
• Elitizm: En iyi birey veya bireylerin doğrudan bir sonraki nesle aktarılmasıdır, böylece en iyi çözümün kaybolması engellenir.

Genetik Algoritma Adımları

Tipik bir Genetik Algoritma süreci şu adımları izler:

1. Başlangıç Popülasyonu Oluşturma: Rastgele veya belirli bir yöntemle potansiyel çözümlerden oluşan bir başlangıç popülasyonu yaratılır.
2. Uygunluk Değerlendirmesi: Popülasyondaki her bireyin uygunluk değeri hesaplanır.
3. Seçilim: Uygunluk değerlerine göre bir sonraki neslin ebeveynleri seçilir.
4. Çaprazlama: Seçilen ebeveynler arasında belirli bir olasılıkla çaprazlama işlemi uygulanarak yeni yavrular oluşturulur.
5. Mutasyon: Yeni oluşturulan yavrulara belirli bir olasılıkla mutasyon uygulanır.
6. Yeni Popülasyon Oluşturma: Elit bireyler, çaprazlama ve mutasyon sonucu oluşan yavrularla yeni bir popülasyon oluşturulur.
7. Durdurma Kriteri: Algoritma, belirli bir jenerasyon sayısına ulaşıldığında, yeterince iyi bir çözüm bulunduğunda veya belirli bir süre geçtiğinde sonlanır.

Gezgin Satıcı Problemi’ni (TSP) Genetik Algoritma ile Çözmek: Adım Adım Uygulama

Belirli bir şehir koordinat seti için Gezgin Satıcı Problemi’ni Genetik Algoritma ile nasıl çözdüğük. Şimdi bu süreci nasıl görselleştirdiğimizi inceleyelim.

Çalışmanın kodları ve slaydın olduğu github reposu için tıklayınız.

1. Problem Tanımı ve Veri Hazırlığı

Elimizde, her biri X ve Y koordinatlarına sahip bir dizi şehir bulunuyordu. İlk adım olarak, bu koordinatları (örneğin, (78.0636611116238, 11.854112682699414)) daha okunabilir ve işlenebilir olması için noktadan sonra üç basamağa yuvarladık (örneğin, (78.064, 11.854)). Bu, hem hesaplama hassasiyetini kabul edilebilir bir seviyede tutar hem de verinin sunumunu kolaylaştırır.

2. Genetik Algoritma Parametrelerinin Belirlenmesi

Algoritmanın performansını etkileyen çeşitli parametreler belirledik:

• Popülasyon Boyutu: 100 (Her jenerasyonda değerlendirilecek rota sayısı)
• Jenerasyon Sayısı: 200 (Algoritmanın çalışacağı toplam iterasyon sayısı; animasyon için optimize edildi)
• Mutasyon Oranı: %10 (Bir rotanın mutasyona uğrama olasılığı)
• Çaprazlama Oranı: %80 (İki rotanın çaprazlanma olasılığı)
• Elitizm Sayısı: 5 (Her jenerasyonda en iyi 5 rotanın doğrudan bir sonraki nesle aktarılması)
• Turnuva Boyutu: 5 (Turnuva seçiminde kaç rotanın karşılaştırılacağı)

3. Temel Fonksiyonların Oluşturulması

Algoritmanın temelini oluşturan fonksiyonları tanımladık:

• Mesafe Hesaplama: İki şehir arasındaki Öklid mesafesini hesaplayan fonksiyon.
• Rota Mesafesi Hesaplama: Belirli bir rotadaki tüm şehirler arasındaki toplam mesafeyi hesaplayan fonksiyon (son şehirden ilk şehre dönüş dahil).
• Uygunluk Fonksiyonu: Rota mesafesinin tersi (1 / toplam_mesafe) olarak tanımlandı. Böylece daha kısa rotalar daha yüksek uygunluk değerine sahip oldu.

4. Genetik Operatörlerin Uygulanması

Evrim sürecini yönlendiren genetik operatörleri kullandık:

• Başlangıç Popülasyonu: Şehirlerin rastgele sıralamalarından oluşan rotalarla ilk popülasyon oluşturuldu.
• Seçilim: Turnuva Seçimi yöntemiyle, popülasyondan rastgele seçilen küçük bir grup rota (turnuva) içerisinden en iyisi ebeveyn olarak seçildi.
• Çaprazlama: Sıralı Çaprazlama (Ordered Crossover – OX1) yöntemi kullanıldı. Bu yöntem, TSP gibi sıralama problemlerinde geçerli (her şehrin bir kez ziyaret edildiği) yavrular üretmek için etkilidir.
• Mutasyon: Takas Mutasyonu (Swap Mutation) ile bir rotadaki iki şehrin pozisyonları rastgele değiştirilerek çeşitlilik sağlandı.

5. Evrim Süreci ve Sonuçların Görselleştirilmesi

Belirlenen jenerasyon sayısı boyunca algoritma çalıştırıldı. Her jenerasyonda:

1. Popülasyondaki tüm rotaların uygunlukları hesaplandı.
2. O jenerasyonun en iyi rotası ve mesafesi kaydedildi.
3. Seçilim, çaprazlama ve mutasyon işlemleriyle yeni bir popülasyon oluşturuldu.

Bu sürecin en heyecan verici kısımlarından biri, her jenerasyonda en iyi rotanın nasıl değiştiğini anlık olarak harita üzerinde animasyonla izlemekti. Bu görselleştirme, algoritmanın çözüm uzayında nasıl gezindiğini ve kademeli olarak daha iyi çözümlere nasıl yakınsadığını net bir şekilde görmemizi sağladı.

6. Elde Edilen Sonuç

Algoritma tamamlandığında, tüm jenerasyonlar boyunca bulunan en kısa rota ve bu rotanın toplam mesafesi elde edildi. Konsolda, en iyi rotanın şehir sıralaması ve toplam mesafesi net bir şekilde gösterildi. Örneğin, 500jenerasyon sonunda elde ettiğimiz en iyi rotanın toplam mesafesi 524.70 birim olarak bulundu.

Animasyonun Gücü: Çözümün Evrimini İzlemek

Bu projede sadece en iyi çözümü bulmakla kalmadık, aynı zamanda çözümün adım adım nasıl evrildiğini gösteren bir animasyon da oluşturduk. Bu animasyon:

• Genetik Algoritmanın dinamik doğasını anlamayı kolaylaştırır.
• Farklı rotaların nasıl denendiğini ve iyileştirildiğini görsel olarak takip etme imkanı sunar.
• Algoritmanın yakınsama davranışını sezgisel olarak gösterir.
• Karmaşık bir optimizasyon sürecini daha anlaşılır ve ilgi çekici hale getirir.

Müşterilerimize veya paydaşlarımıza bir çözüm sunduğumuzda, sadece sonucu değil, o sonuca nasıl ulaşıldığını da göstermek büyük önem taşır. Animasyonlu görselleştirmeler, bu iletişimi güçlendiren etkili araçlardır.

DeepmineAI ile Optimizasyonun Geleceğine Adım Atın!

Gezgin Satıcı Problemi gibi karmaşık optimizasyon görevleri, doğru araçlar ve uzmanlıkla ele alındığında etkili bir şekilde çözülebilir. DeepmineAI olarak, Genetik Algoritmalar, Makine Öğrenmesi ve diğer Yapay Zeka tekniklerini kullanarak işletmenizin en zorlu problemlerine özel çözümler sunuyoruz.

• Lojistik ve rota optimizasyonu,
• Tedarik zinciri yönetimi,
• Üretim planlama,
• Finansal modelleme,
• Ve daha birçok alanda verimliliği artırmak, maliyetleri düşürmek ve rekabet avantajı elde etmek için buradayız.

Sonuç

Gezgin Satıcı Problemi çözümü zor görünen sorunlara zarif ve güçlü yaklaşımlar sunar. Optimizasyon yolculuğunuzda size rehberlik etmekten mutluluk duyarız!

Projeleriniz hakkında görüşmek ve size özel optimizasyon çözümlerimizi keşfetmek için bizimle iletişime geçin!