Python ile Genetik Algoritma

Evrime dayalı algoritmalardan biri olan ve insan kromozomundan esinlenilerek geliştirilen genetik algoritma; genellikle çizelgeleme, rota bulma, yapay öğrenme vb. alanlarda kullanılan bir sezgisel metottur. Bu yazıda, bir Knapsack problemi örneğinin genetik algoritmayla çözümünü Python üzerinden inceleyeceğiz.

Kaynak : Tech-Quantum

Genetik algoritmanın mantığı, iyi genlere sahip bireylerin bir sonraki jenerasyonda daha iyi bireylerin oluşmasına sebep olması düşüncesidir. Böylece, her jenerasyonda daha da iyiye giderek “en uygun” bireyler oluşacaktır.

Genetik algoritmayı 5 temel terim üzerinden anlatabiliriz: başlangıç popülasyonu (population), uygunluk fonksiyonu (fitness function), seleksiyon (selection), çaprazlama (crossover) ve mutasyon (mutation).

Şimdi de bir örnek üzerinden genetik algoritmanın kodunu inceleyelim.

Tatile giderken yanımıza alacağımız eşyaların seçilmesi konusunda zorluk yaşadığımızı farz edelim. Bir çantamız var ve bu çantaya eşyalarımızı koyup tatile gitmek istiyoruz ancak bütün eşyaları koymak istersek çantaya sığmayacağı için bazılarını alamayacağız. Çantanın hacmini geçmeden toplam değeri en fazla eden eşyaları yanımıza alarak seyahate başlamayı hedefliyoruz. Klasik bir Knapsack problemi…

Elimizde 10 adet eşya var. Her eşyanın bizim için bir değeri ve eşyaların kendi hacmi mevcut. Bu eşyaları, toplam hacmi 200 olan bir çantaya koymaya çalışıyoruz.

Item = namedtuple("Item", ["name", "value", "volume"])
book = Item('Book', 50, 80)
phone = Item('Phone', 100, 10)
flip_flop = Item('Flip Flop', 30, 30)
towel = Item('Towel', 30, 40)
umbrella = Item('Umbrella', 15, 90)
swimsuit = Item('Swimsuit', 90, 50)
jacket = Item('Jacket', 10, 150)
sunglasses = Item('Sunglasses', 70, 40)
laptop = Item('Laptop', 50, 100)
city_map = Item('City Map', 10, 5)

Genetik algoritma modelini kurmak için öncelikle bir sınıf oluşturmak gerekir. Algoritmanın çalışabilmesi için lazım olan; bir genomdaki gen sayısı (eşya sayısı), popülasyonun nüfusu (genom sayısı), jenerasyon sayısı (iterasyonun devam edeceği tur sayısı), çanta hacmi ve değerlendirilecek olan eşyaların bilgileri girdi olarak verilir. Eğer herhangi bir eşya listesi girdi olarak sağlanmazsa algoritmanın çalışması bir anlam ifade etmeyeceği için bir uyarı çıkar.

class GeneticAlgorithm:

    def __init__(self, items, len_genome=10, len_population=100,   n_generations=50, volume_limit=200):
        
        self.len_genome = len_genome
        self.len_population = len_population
        self.n_generations = n_generations
        self.volume_limit = volume_limit

        if not items:
            raise Exception("No item in list!")
        else:
            self.items = items

Genom, genlerden oluşan bir listedir ve indeks sayısı, değerlendirilecek olan eşya sayısı kadardır. Bu problem özelinde genler “0” veya “1” olarak ifade edilir. “1”, o eşyanın çantaya konulduğunu, “0” ise konulmadığını temsil eder. Genomun indeks sayısı kadar bir liste yaratılır ve indekslere rastgele bir şekilde “1” veya “0” atanır. Bir genom “çözüm” olarak da adlandırılabilir.

Popülasyon ve genom

def generate_genome(self):
    return random.choices([0, 1], k=self.len_genome)

Başlangıç popülasyonu, oluşturulan bütün genomların bir arada bulunduğu listedir. Bu popülasyon üzerinden ilk işlemler gerçekleşir.

def generate_population(self):
    return [self.generate_genome() for i in range(self.len_population)]

Uygunluk fonksiyonu, popülasyon içindeki bütün genomların uygunluk değerlerini hesaplar. Bütün genomların indeksleri üzerinden teker teker geçerek çantaya atılan eşyaların toplam değerini ve hacmini hesaplar. Eğer, toplam hacim çanta hacminden büyükse uygunluk skoru “0” olur. Toplam hacmin çanta hacminden küçük veya çanta hacmine eşit olması durumunda ise genomun uygunluk skoru hesaplanmış olur.

def fitness(self, genome):
    fitness_score = 0
    total_volume = 0
    for ind, gene in enumerate(genome):
        if gene == 0:
            continue
        fitness_score += self.items[ind].value
        total_volume += self.items[ind].volume
        if total_volume > self.volume_limit:
            fitness_score = 0
            break
    return fitness_score

Seleksiyon, popülasyon havuzundaki iki genomun çaprazlanmak üzere birbiriyle eşlenmesini sağlar. Bu seçimi yaparken dikkat edilmesi gereken kısım, uygunluk değeri yüksek olan genomların bu eşleşmelere katılma olasılığının daha fazla olmasıdır. Böylece iyi sonuçların birbiriyle çaprazlanarak daha iyi bir sonuca yol açması hedeflenmiştir.

def selection(self, fit_population):
    return random.choices(fit_population, weights=[p[1] for p in fit_population], k=2)

Not: “fit_population” değişkeni iki indeksten oluşan listelerin bir arada olduğu bir listedir. Birinci indeks, genomun popülasyon listesindeki indeksini, ikinci indeks ise o indeksteki genomun uygunluk skorunu gösterir. “fit_population” listesindeki elemanlar uygunluk skorlarına göre büyükten küçüğe sıralandığı için genomların popülasyondaki indekslerinin kaybolmaması ve böylece genomlara doğru bir şekilde ulaşılması için buna gerek duyulmuştur.

Tek noktalı çaprazlama, seçilen iki genomun belirli genlerini -bu örnek özelinde son üç genini- birbiriyle değiştirmesidir. Böylece iki ata genomdan iki yeni çocuk genom oluşturulmuş olur.

Tek noktalı çaprazlama ile son 3 genin değişimi

def single_point_crossover(self, selections, n_genes_swap=3):
    parent_1 = selections[0]
    parent_2 = selections[1]
    child_1 = parent_1[:-n_genes_swap] + parent_2[-n_genes_swap:]
    child_2 = parent_2[:-n_genes_swap] + parent_1[-n_genes_swap:]
    return [child_1, child_2]

Mutasyon, genomda bulunan bir genin rastgele belirlenip değiştirilmesidir. “0”sa “1”e veya “1”se “0”a dönüştürülen gen ile genom güncellenmiş olur. Bunun için indeksteki değerden 1'i çıkarıp mutlak değerini almak gerekir.

Mutasyon örneği: |0–1| = 1

def mutation(self, genome):
    index = random.randint(0, self.len_genome - 1)
    genome[index] = abs(genome[index] - 1)
    return genome

Elitizm, mevcut jenerasyonda en iyi sonuç veren genomların (çözümlerin) kaybedilmemesi için diğer jenerasyona doğrudan aktarılmasıdır. Bu örnekteki sınıf metodu, en iyi sonuca sahip beş genomun bir sonraki jenerasyona gönderilmesini sağlar.

def elitism(self, population, fit_population, n_transfer=5):
    next_gen = []
    for i in range(n_transfer):
        next_gen.append(population[fit_population[i][0]])
    return next_gen

Genetik algoritmanın uygulanması için yukarıda bahsedilen metotların istenilen sırayla birbirlerine entegre edilmesi gerekir. Bunun için de bütün süreç bir metotta toplanır.

Genetik algoritmaya başlarken önce genomlardan oluşan bir başlangıç popülasyonu oluşturmak gerekir. Bu popülasyondaki her genoma bir uygunluk fonksiyonu uygulanır ve bunun sonucunda her genom bir uygunluk skoruna sahip olur. Uygunluk skoru yüksek olan genomların birbiriyle eşleşme ihtimalini arttıran seleksiyon uygulanır. Seçilen iki ata genom arasında çaprazlama uygulanır ve böylece iki yeni çocuk genom elde edilir. Oluşan iki yeni genoma bir geni değiştirecek olan mutasyon uygulanarak bir sonraki jenerasyon listesine eklenirler ve bir jenerasyon tamamlanmış olur. Bir sonraki jenerasyona geçerken en iyi sonuçları kaybetmemek için de elitizm ile en iyi sonuçlar bir sonraki jenerasyona aktarılır. Girdi olarak verilen jenerasyon sayısı kadar bu süreç tekrar eder.

def run(self):
    population = self.generate_population()

    for generation in range(self.n_generations):
        fit_population = []
        for pop_index, genome in enumerate(population):
            fit_population.append([pop_index, self.fitness(genome)])

        fit_population = sorted(fit_population, key=lambda x: x[1], reverse=True)
        next_generation = self.elitism(population, fit_population)
        while len(next_generation) <= self.len_population:
            selected = self.selection(fit_population)
            selected = [population[selected[0][0]], population[selected[1][0]]]
            children = self.single_point_crossover(selected)

            for c in range(len(children)): 
                children[c] = self.mutation(children[c])

            next_generation += children

        if not generation == self.n_generations - 1:
            population = next_generation

    return population[fit_population[0][0]]

Algoritmayı başlatmak için GeneticAlgorithm sınıfını çağırmak ve girdi olarak eşyaların listesini iletmek gerekir. Daha sonra run() komutu kullanılarak algoritmanın bulduğu en uygun sonuca sahip genom (çözüm) elde edilir.

items = [book, phone, flip_flop, towel, umbrella, swimsuit, jacket, sunglasses, laptop, city_map]

model = GeneticAlgorithm(items=items)
solution = model.run()
model.print_result(solution)

Sonuçlar, mevcut 10 eşyadan aşağıdaki 6'sını yanımıza almamız gerektiğini gösteriyor. Bu 6 eşyanın toplam hacmi 175 ile 200'ün altındayken toplam değeri de 330 ile diğer seçeneklerden daha yüksek.

Algoritma sonucu

Bu örnek, genetik algoritmanın yazılabileceği en basit uygulamalarından biri. Algoritmayı manuel girdilerden kurtararak bir pakete çevirmek, mutasyon fonksiyonunu olasılık üzerinden daha akıllı hâle getirmek, tek noktalı çaprazlama yerine farklı çaprazlama yöntemleri denemek, jenerasyon veya popülasyon sayısını optimize etmek gibi daha ileri yöntemler denenebilir ve karşılaşılan problemin ihtiyacına/eksiğine göre yeni yaklaşımlar geliştirilebilir.

*Kodun tamamı için: GitHub