Genetik Algoritma ile Seyahat Eden Satıcı Problemi Çözümü

Genetik Algoritmalar Nedir?

Genetik algoritmalar, doğal evrim süreçlerinden ilham alan ve özellikle optimizasyon problemlerini çözmek için kullanılan bir yapay zeka tekniğidir. Bu algoritmalar, genetik varyasyon ve doğal seçim prensiplerine dayanarak belirli bir problemi çözmek için potansiyel çözümleri ‘genetik bireyler’ olarak temsil eder. Bir genetik algoritma, bir popülasyon oluşturur, bu popülasyondaki bireyleri değerlendirir, en iyi bireyleri seçer ve sonra onları nesil nesil geliştirerek daha iyi çözümler elde etmeye çalışır.

Genetik algoritmalar, birçok alanda kullanılmasına rağmen, en yaygın uygulamalarından biri optimizasyon problemleridir. Örneğin, Seyahat Eden Satıcı Problemi (TSP), bir dizi şehir arasında en kısa rotayı bulmayı amaçlayan klasik bir optimizasyon problemidir. Bu tür problemler genellikle büyük çözüm uzayına sahip olduklarından, geleneksel yöntemlerle çözülmesi zordur. İşte burada genetik algoritmalar devreye girer. Çeşitli çözümler arasında mükemmel bir denge bularak optimal rotayı belirlemek için etkili bir yol sunar.

Genetik algoritmalar, başlangıçta rastgele oluşturulmuş çözümlerle başlarlar. Her bir çözüm, bir temsil veya kromozom olarak tanımlanır. Daha sonra, bu çözümler üzerinde çeşitli genetik işlemler uygulanarak yeni çözümler üretilir. Bu işlemler, çaprazlama, mutasyon ve seçim gibi temel bileşenlere dayanır. Bu sayede, bir sonraki nesilde daha iyi çözüm adaylarının ortaya çıkması hedeflenir.

Seyahat Eden Satıcı Problemi Nedir?

Seyahat Eden Satıcı Problemi (TSP), bir satıcının belirli bir dizi şehir arasında en kısa yolculuğu yapmasını sağlamayı amaçlar. Her şehir arasında bir mesafe veya maliyet vardır ve satıcının tüm şehirleri ziyaret edip tekrar başlangıç noktasına geri dönmesi gerekmektedir. Bu problem, birçok alanda uygulanmakta ve önemli bir araştırma konusu haline gelmiştir.

TSP’nin zorluklarından biri, şehir sayısı arttıkça olası yol kombinasyonlarının üssel bir şekilde artmasıdır. Örneğin, 5 şehri olan bir TSP problemi için 12 olası yol vardır, ancak 10 şehir için bu sayı 3628800’e kadar çıkmaktadır. Bu, büyük TSP problemlerinin çözümünü son derece zor ve zaman alıcı hale getirir. Yüzlerce, binlerce hatta on binlerce şehir barındıran TSP problemleri için, geleneksel optimizasyon yöntemleri genellikle yetersiz kalır.

Bu sorun nedeniyle, genetik algoritmalar gibi sezgisel ve evrimsel yöntemler, TSP’nin etkili bir biçimde çözülmesi için sıklıkla tercih edilir. Genetik algoritmalar, geniş çözüm uzayını tarayarak, en iyi çözüm adaylarını belirlemekte ve zaman tasarrufu sağlamaktadır. Grafik teorisi ve kombinatorik optimizasyon alanındaki bu problemin araştırılması, genetik algoritmaların potansiyelinin daha da genişlemesine olanak tanır.

Python ile Genetik Algoritma Uygulaması

Python, genetik algoritmaların uygulanması için mükemmel bir dildir. Zengin kütüphane desteği sayesinde, algoritmaların hızlı bir şekilde geliştirilmesini ve test edilmesini sağlar. Bu bölümde, Python ile basit bir genetik algoritma kullanarak Seyahat Eden Satıcı Problemi’ni çözecek bir örnek uygulaması gerçekleştireceğiz.

Öncelikle gerekli kütüphaneleri yükleyelim:

import numpy as np
import random
import matplotlib.pyplot as plt

Bu kütüphaneler, rastgele sayılar oluşturmak, matematiksel işlemler yapmak ve sonuçlarımızı görselleştirmek için kullanılır. Sonra, şehirlerin koordinatlarını tanımlayarak başlayalım. Aşağıdaki örnek kodda başlangıç noktalarını belirleyeceğiz:

def create_city_coordinates(num_cities):
    return np.random.rand(num_cities, 2)

Bu fonksiyon, belirtilen sayıda şehir için rastgele koordinatlar oluşturacaktır.

Kromozom Tanımı ve Uygulama

Seyahat Eden Satıcı Problemi’nin çözümlerini temsil etmek için kromozomları tanımlamamız gerekiyor. Kromozomlar, şehir sıralarını temsil eden dizilerdir. Şimdi bir kromozom sınıfı oluşturalım:

class Chromosome:
    def __init__(self, genes):
        self.genes = genes
        self.fitness = None

    def calculate_fitness(self, city_coordinates):
        total_distance = 0
        for i in range(len(self.genes) - 1):
            start_city = city_coordinates[self.genes[i]]
            end_city = city_coordinates[self.genes[i + 1]]
            distance = np.linalg.norm(start_city - end_city)
            total_distance += distance
        self.fitness = 1 / total_distance  # Fitness as inverse of distance

Bu sınıf, genleri ve uygunluk değerlerini saklar. Uygunluk hesaplaması, genlerin sıralandığı şehirler arasındaki toplam mesafeyi bulur ve bu mesafeyi tersine çevirerek uygunluk değerini belirler.

Seçim, Çaprazlama ve Mutasyon

Şimdi genetik algoritmamızın temel bileşenlerini uygulayalım: seçim, çaprazlama ve mutasyon. Bu işlemler ile popülasyondaki en iyi bireyleri seçip, yeni bireyler ve mutasyonlar oluşturacağız. İlk olarak, popülasyondaki en iyi bireyleri seçelim:

def selection(population):
    return sorted(population, key=lambda x: x.fitness, reverse=True)[:int(len(population) / 2)]

Bu seçim fonksiyonu, popülasyondaki bireylerin uygunluk değerlerine göre sıralanmasını sağlar ve en yüksek uygunluğa sahip bireylerin bir alt kümesini döndürür.

Ardından, çaprazlama işlemi ile yeni bireyler üretelim:

def crossover(parent1, parent2):
    start, end = sorted(random.sample(range(len(parent1.genes)), 2))
    child_genes = parent1.genes[start:end] + [gene for gene in parent2.genes if gene not in parent1.genes[start:end]]
    return Chromosome(child_genes)

Bu çaprazlama fonksiyonu, iki ebeveynden genlerin bir kısmını alarak yeni bir birey oluşturur.

Sonuçların Görselleştirilmesi

Yukarıda oluşturduğumuz fonksiyonlarla çalışarak, genetik algoritmanın sonuçlarını görselleştirebiliriz. Toplam birkaç nesil oluşturduktan sonra en iyi çözümü elde edebiliriz. Sonuçları görselleştirmek için aşağıdaki kodu kullanabiliriz:

def plot_route(route, city_coordinates):
    plt.figure(figsize=(10, 6))
    plt.plot(city_coordinates[route + [route[0]], 0], city_coordinates[route + [route[0]], 1], 'o-')
    plt.xlabel('X Koordinatı')
    plt.ylabel('Y Koordinatı')
    plt.title('En İyi Rotanın Görselleştirilmesi')
    plt.grid(True)
    plt.show()

Bu grafik, en iyi çözüm rotasını görsel olarak sunar. Şehirler arasında geçişlerden ve alınan yolu gösterir.

Sonuç ve Değerlendirme

Genetik algoritmalar, Seyahat Eden Satıcı Problemi gibi karmaşık optimizasyon problemlerinin çözümünde etkili bir araçtır. Python ile uygulanan genetik algoritma, hem kolay anlaşılır hem de genişletilebilir bir yapıya sahiptir. Yapılan denemeler sonucunda, daha büyük şehir grupları ile çalışıldığında elde edilen sonuçlar tatmin edici düzeyde olabilir.

Gelecekte, genetik algoritmaların çeşitli parametrelerini optimize ederek ve farklı evrimsel stratejiler deneyerek bu tür problemlerde daha iyi sonuçlar elde etmek mümkündür. Yenilikçi yaklaşım ve sürekli öğrenme, yazılım geliştiricilere ve veri bilimcilere daha sofistike yöntemler sunabilir.

Sonuç olarak, genetik algoritmalar sadece Seyahat Eden Satıcı Problemi için değil, birçok optimizasyon problemi için esnek ve etkili bir çözüm yolu sunmaktadır. Python dilinin sağladığı kolaylıklarla birlikte, bu algoritmaların eğitim ve uygulama süreci, her seviyeden yazılımcı için keyifli bir deneyim olabilir.