DALL•E ile oluşturulan resim
 

Bu yazımızda bilgisayar bilimlerinde bir klasik olan sırt çantası problemine bakacağız. Geleneksel hesaplama yöntemlerini kullanarak çözmenin neden zor olduğunu ve genetik programlamanın "yeterince iyi" bir çözüm bulmaya nasıl yardımcı olabileceğini açıklayacağız. Daha sonra, kendimizi test etmek için böyle bir çözümün Python uygulamasına bakacağız.

 
Sırt çantası problemi, karmaşık hesaplama problemlerini çözmenin zorluğunu göstermek için kullanılabilir. En basit haliyle, kişiye belli bir kapasitede bir sırt çantası, boyutları ve değerleri olan bir dizi eşya verilir ve sırt çantasına konulan eşyaların kapasitesini aşmadan değerini en üst düzeye çıkarması istenir. Sırt çantası problemi birçok şekilde formüle edilebilir, ancak genellikle geleneksel algoritmalar kullanıldığında çözülmesi zor bir problem olarak kabul edilir.

Sırt çantası probleminin zorluğu, bunun NP-tam bir problem olması gerçeğinde yatmaktadır, bu da küresel olarak optimal bir çözümü garanti edebilecek bilinen bir çözümün olmadığı anlamına gelmektedir. Bu nedenle, sorun inatçıdır ve geleneksel yöntemlerle hızlı bir şekilde çözülemez. Sırt çantası problemini çözmek için en iyi bilinen algoritmalar, uzun çalışma sürelerine sahip olabilen ve optimal bir çözümü garanti etmeyebilen kaba kuvvet arama veya buluşsal yöntemleri kullanmayı içerir.

 
Bununla birlikte, genetik programlama, sırt çantası sorununa bir çözüm bulmak için alternatif bir yöntem sağlayabilir. Genetik programlama, karmaşık sorunlara çözüm aramak için evrimsel algoritmaları kullanan bir tekniktir. Genetik programlamayı kullanarak, verilen problem için “yeterince iyi” olan bir çözümü hızlı bir şekilde bulmak mümkündür. Çözümleri optimize etmek ve iyileştirmek için de kullanılabilir.

Genetik programlamada, bir dizi olası çözüm (veya ilk nesil) rastgele üretilir ve ardından bir dizi kritere göre değerlendirilir. Kriterlere en uygun çözümler daha sonra seçilir ve yeni çözüm varyantları (veya sonraki nesiller) oluşturmak için genetik mutasyonlar uygulanır. Bu yeni nesil varyantlar daha sonra değerlendirilir ve tatmin edici bir çözüm bulunana kadar süreç tekrarlanır. Süreç, optimal veya en iyi “yeterince iyi” çözüm bulunana kadar tekrarlanır.

Sırt çantası problemini çözmek için genetik programlama kullanmanın avantajı, yeterince iyi bir çözümün, olası tüm çözümleri kapsamlı bir şekilde araştırmak zorunda kalmadan hızlı bir şekilde bulunabilmesidir. Bu, onu geleneksel algoritmalardan çok daha verimli bir yaklaşım haline getirir ve çok daha hızlı bir çözüm bulunmasına olanak tanır.

 
Artık sırt çantası probleminin ne olduğu, genetik programlamanın ne olduğu ve ikincisini neden birincisini denemek ve çözmek için kullanacağımız hakkında bir fikrimiz olduğuna göre, yukarıda tanımladığımız şeyin Python uygulamasına bir göz atalım.

Önemli fonksiyonları tek tek inceleyeceğiz ve ardından bütünsel programa bakacağız.

Program, üçüncü taraf kitaplıkları kullanılmadan Python'da uygulanmaktadır.

Rastgele popülasyon oluştur

 
Bu işlev, belirli bir boyutta rastgele bir popülasyon oluşturur. Verilen boyutu yinelemek için bir for döngüsü kullanır ve her yineleme için bir kromozom oluşturur. Bu kromozom, random.choice() işlevi kullanılarak oluşturulan 0'lar ve 1'lerin bir listesidir. Kromozom daha sonra popülasyon listesine eklenir. Son olarak, işlev bir mesaj yazdırır ve nüfus listesini döndürür. Bu işlev, genetik algoritmalar için bir birey popülasyonu oluşturmak için kullanışlıdır.

def generate_population(size): population = [] for _ in range(size): genes = [0, 1] chromosome = [] for _ in range(len(items)): chromosome.append(random.choice(genes)) population.append(chromosome) print("Generated a random population of size", size) return population

Kromozom uygunluğunu hesapla

 
Bu fonksiyon, bir kromozomun uygunluğunu hesaplamak için kullanılır. Argüman olarak bir kromozom alır ve onu yineler. Belirli bir indeksteki kromozomun değeri 1 ise, karşılık gelen öğenin ağırlığını ve değerini sırasıyla toplam ağırlığa ve toplam değere ekler. Toplam ağırlık maksimum ağırlığı aşarsa uygunluk 0'a ayarlanır. Aksi takdirde uygunluk toplam değere ayarlanır. Bu işlev, belirli bir kromozomun uygunluğunu belirlemek için genetik algoritmalarda kullanılır.

def calculate_fitness(chromosome): total_weight = 0 total_value = 0 for i in range(len(chromosome)): if chromosome[i] == 1: total_weight += items[i][0] total_value += items[i][1] if total_weight > max_weight: return 0 else: return total_value

kromozomları seçin

 
Bu fonksiyon, çaprazlama için bir popülasyondan iki kromozom seçmek için kullanılır. İlk olarak, hesapla_uygunluk() işlevini kullanarak popülasyondaki her bir kromozomun uygunluk değerlerini hesaplar. Daha sonra her değeri tüm uygunluk değerlerinin toplamına bölerek uygunluk değerlerini normalleştirir. Son olarak, normalleştirilmiş uygunluk değerlerine dayalı olarak popülasyondan rastgele iki kromozom seçmek için random.choices() işlevini kullanır. Seçilen iki kromozom daha sonra çaprazlama için ana kromozomlar olarak döndürülür.

def select_chromosomes(population): fitness_values = [] for chromosome in population: fitness_values.append(calculate_fitness(chromosome)) fitness_values = [float(i)/sum(fitness_values) for i in fitness_values] parent1 = random.choices(population, weights=fitness_values, k=1)[0] parent2 = random.choices(population, weights=fitness_values, k=1)[0] print("Selected two chromosomes for crossover") return parent1, parent2

Geçiş gerçekleştir

 
Bu fonksiyon iki kromozom arasında çaprazlama gerçekleştirir. Girdi olarak iki ebeveyn kromozomu alır ve rastgele bir geçiş noktası seçer. Daha sonra iki ana kromozomu çaprazlama noktasında birleştirerek iki çocuk kromozomu oluşturur. Birinci ebeveyn kromozomunun birinci kısmı ve ikinci ebeveyn kromozomunun ikinci kısmı alınarak birinci çocuk kromozomu oluşturulur. İkinci çocuk kromozomu, ikinci ebeveyn kromozomunun birinci kısmı ve birinci ebeveyn kromozomunun ikinci kısmı alınarak oluşturulur. Son olarak, iki çocuk kromozomu çıktı olarak döndürülür.

def crossover(parent1, parent2): crossover_point = random.randint(0, len(items)-1) child1 = parent1[0:crossover_point] + parent2[crossover_point:] child2 = parent2[0:crossover_point] + parent1[crossover_point:] print("Performed crossover between two chromosomes") return child1, child2

Mutasyon gerçekleştir

 
Bu işlev, bir kromozom üzerinde bir mutasyon gerçekleştirir. Bir kromozomu argüman olarak alır ve 0 ile kromozomun uzunluğu arasında rastgele bir sayı üretmek için rastgele modülünü kullanır. Mutasyon noktasındaki değer 0 ise 1, 1 ise 0 olarak değiştirilir. Fonksiyon daha sonra bir mesaj yazdırır ve mutasyona uğramış kromozomu döndürür. Bu işlev, bir organizma popülasyonundaki genetik mutasyonları simüle etmek için kullanılabilir.

def mutate(chromosome): mutation_point = random.randint(0, len(items)-1) if chromosome[mutation_point] == 0: chromosome[mutation_point] = 1 else: chromosome[mutation_point] = 0 print("Performed mutation on a chromosome") return chromosome

En iyi kromozomu al

 
Bu işlev, bir kromozom popülasyonunu alır ve popülasyondan en iyi kromozomu döndürür. Bunu, önce popülasyondaki her bir kromozom için bir uygunluk değerleri listesi oluşturarak yapar. Daha sonra listede maksimum uygunluk değerini ve buna karşılık gelen indeksi bulur. Son olarak, kromozomu maksimum uygunluk değerinin indeksinde döndürür. Bu işlev, sonraki işlemlerde kullanmak üzere bir kromozom popülasyonundan en iyi kromozomu bulmak için kullanışlıdır.

def get_best(population): fitness_values = [] for chromosome in population: fitness_values.append(calculate_fitness(chromosome)) max_value = max(fitness_values) max_index = fitness_values.index(max_value) return population[max_index]

Kontrol döngüsü

 
Bu kod, bir kromozom popülasyonunu geliştirmek için evrimsel bir algoritma gerçekleştiriyor. Belirtilen nesil sayısı boyunca döngü yaparak başlar. Her nesil için, popülasyondan iki kromozom seçilir ve daha sonra iki yeni kromozom oluşturmak için bunlar üzerinde çaprazlama yapılır. Daha sonra, iki yeni kromozom belirli bir olasılıkla mutasyona tabi tutulur. Rastgele oluşturulmuş olasılık önceden belirlenmiş eşiğin üzerindeyse, yeni kromozomlar bireysel olarak rastgele bir genetik mutasyona tabi tutulur. Son olarak, eski popülasyon, iki yeni kromozomdan ve eski popülasyondan kalan kromozomlardan oluşan yeni popülasyonla değiştirilir.

for _ in range(generations): # select two chromosomes for crossover parent1, parent2 = select_chromosomes(population) # perform crossover to generate two new chromosomes child1, child2 = crossover(parent1, parent2) # perform mutation on the two new chromosomes if random.uniform(0, 1) mutation_probability: child1 = mutate(child1) if random.uniform(0, 1) mutation_probability: child2 = mutate(child2) # replace the old population with the new population population = [child1, child2] + population[2:]

 
Yukarıdaki işlevleri ve kontrol döngüsünü alırsak, konsola birkaç parametre ve bazı çıktılarla birlikte bir öğe listesi eklersek, aşağıdaki tam Python uygulamasını elde ederiz.

Basit olması için tüm parametrelerin kodlanmış olduğunu unutmayın; ancak, çok az sorunla bunun yerine komut satırı bağımsız değişkenleri kabul edilebilir veya kullanılabilir öğelerin sayısı, değeri ve ağırlığı da dahil olmak üzere bunlardan herhangi biri için kullanıcı girdisi istenebilir.

import random # function to generate a random population
def generate_population(size): population = [] for _ in range(size): genes = [0, 1] chromosome = [] for _ in range(len(items)): chromosome.append(random.choice(genes)) population.append(chromosome) print("Generated a random population of size", size) return population # function to calculate the fitness of a chromosome
def calculate_fitness(chromosome): total_weight = 0 total_value = 0 for i in range(len(chromosome)): if chromosome[i] == 1: total_weight += items[i][0] total_value += items[i][1] if total_weight > max_weight: return 0 else: return total_value # function to select two chromosomes for crossover
def select_chromosomes(population): fitness_values = [] for chromosome in population: fitness_values.append(calculate_fitness(chromosome)) fitness_values = [float(i)/sum(fitness_values) for i in fitness_values] parent1 = random.choices(population, weights=fitness_values, k=1)[0] parent2 = random.choices(population, weights=fitness_values, k=1)[0] print("Selected two chromosomes for crossover") return parent1, parent2 # function to perform crossover between two chromosomes
def crossover(parent1, parent2): crossover_point = random.randint(0, len(items)-1) child1 = parent1[0:crossover_point] + parent2[crossover_point:] child2 = parent2[0:crossover_point] + parent1[crossover_point:] print("Performed crossover between two chromosomes") return child1, child2 # function to perform mutation on a chromosome
def mutate(chromosome): mutation_point = random.randint(0, len(items)-1) if chromosome[mutation_point] == 0: chromosome[mutation_point] = 1 else: chromosome[mutation_point] = 0 print("Performed mutation on a chromosome") return chromosome # function to get the best chromosome from the population
def get_best(population): fitness_values = [] for chromosome in population: fitness_values.append(calculate_fitness(chromosome)) max_value = max(fitness_values) max_index = fitness_values.index(max_value) return population[max_index] # items that can be put in the knapsack
items = [ [1, 2], [2, 4], [3, 4], [4, 5], [5, 7], [6, 9] ] # print available items
print("Available items:n", items) # parameters for genetic algorithm
max_weight = 10
population_size = 10
mutation_probability = 0.2
generations = 10 print("nGenetic algorithm parameters:")
print("Max weight:", max_weight)
print("Population:", population_size)
print("Mutation probability:", mutation_probability)
print("Generations:", generations, "n")
print("Performing genetic evolution:") # generate a random population
population = generate_population(population_size) # evolve the population for specified number of generations
for _ in range(generations): # select two chromosomes for crossover parent1, parent2 = select_chromosomes(population) # perform crossover to generate two new chromosomes child1, child2 = crossover(parent1, parent2) # perform mutation on the two new chromosomes if random.uniform(0, 1) mutation_probability: child1 = mutate(child1) if random.uniform(0, 1) mutation_probability: child2 = mutate(child2) # replace the old population with the new population population = [child1, child2] + population[2:] # get the best chromosome from the population
best = get_best(population) # get the weight and value of the best solution
total_weight = 0
total_value = 0
for i in range(len(best)): if best[i] == 1: total_weight += items[i][0] total_value += items[i][1] # print the best solution
print("nThe best solution:")
print("Weight:", total_weight)
print("Value:", total_value)

Yukarıdaki kodu dosyaya kaydedin knapsack_ga.pyve ardından yazarak çalıştırın python knapsack_ga.py.

Örnek bir çıktı aşağıdaki gibidir:

Available items:
[[1, 2], [2, 4], [3, 4], [4, 5], [5, 7], [6, 9]] Genetic algorithm parameters:
Max weight: 10
Population: 10
Mutation probability: 0.2
Generations: 10 Performing genetic evolution:
Generated a random population of size 10
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome The best solution:
Weight: 10
Value: 14

Ve işte gidiyorsun. Artık sırt çantası problemini çözmek için genetik programlamayı nasıl kullanacağınızı biliyorsunuz. Biraz ustalıkla, yukarıdaki komut dosyası, en iyi "yeterince iyi" çözümleri için her türlü hesaplama açısından karmaşık sorunu çözmek için değiştirilebilir.

Okuduğunuz için teşekkür ederim!

 
Bu makalenin bazı bölümleri GPT-3'ün yardımıyla çizildi ve/veya yazıldı.

 
 
Matthew Mayo (@mattmayo13) bir Veri Bilimcisi ve çığır açıcı çevrimiçi Veri Bilimi ve Makine Öğrenimi kaynağı olan KDnuggets'ın Genel Yayın Yönetmenidir. İlgi alanları doğal dil işleme, algoritma tasarımı ve optimizasyonu, denetimsiz öğrenme, sinir ağları ve makine öğrenimine yönelik otomatik yaklaşımlardır. Matthew, bilgisayar bilimi alanında yüksek lisans derecesine ve veri madenciliği alanında yüksek lisans diplomasına sahiptir. Editör1'e kdnuggets[dot]com adresinden ulaşılabilir.
 

• SEO Destekli İçerik ve Halkla İlişkiler Dağıtımı. Bugün Gücünüzü Artırın.
• Plato blok zinciri. Web3 Metaverse Zekası. Bilgi Güçlendirildi. Buradan Erişin.
• Kaynak: https://www.kdnuggets.com/2023/01/knapsack-problem-genetic-programming-python.html?utm_source=rss&utm_medium=rss&utm_campaign=genetic-programming-in-python-the-knapsack-problem