Jump to content
Üyelik kaydınızı yaparak son yazılan içeriklerden haberdar olun! ×
  • entries
    55
  • comments
    2
  • views
    324,022

Kompakt Genetik Algoritma (Compact Genetic Algorithm - cGA)


Doğuhan ELMA

210 views

Compact Genetic Algorithm (cGA), bir çeşit Genetik Algoritma (GA) ve tahmini dağılımlı algoritmalardan biridir. Geleneksel genetik algoritmaların aksine, cGA bir popülasyonu açıkça tutmaz; bunun yerine, bir olasılık dağılımını (genlerin olasılıklarını içeren bir vektör) saklar ve bu dağılımdan çözümler oluşturur. 

cGA'nın temel adımları şunlardır:

1. Başlatma: Başlangıçta, cGA'nın çözüm vektörünün tüm elemanları 0.5 ile başlar. Bu, tüm bitlerin 0 veya 1 olma olasılığının eşit olduğunu gösterir.

2. Çözüm Oluşturma: Olasılık vektöründen iki çözüm oluşturulur. Her bit, bitin olasılığına göre rastgele seçilir.

3. Rekabet: İki çözüm, bir fitness fonksiyonuna dayalı olarak karşılaştırılır. Fitness fonksiyonu, bir çözümün ne kadar "iyi" olduğunu belirler.

4. Güncelleme: Kazanan çözüm, olasılık vektörünü günceller. Kazanan çözümdeki her 1 biti için ilgili olasılık değeri bir miktar artar, her 0 biti için ilgili olasılık değeri bir miktar azalır.

5. Terminasyon Kontrolü: Belirli bir durdurma kriteri (örneğin, maksimum iterasyon sayısı veya belirli bir fitness değeri) karşılanana kadar 2. adımdan 4. adıma dönülür.

cGA'nın avantajı, popülasyon büyüklüğünden bağımsız bir hesaplama maliyetine sahip olmasıdır, çünkü popülasyonu açıkça tutmaz. Bunun yerine, çözüm alanının genel olasılık dağılımını tahmin etmeye çalışır. Bu, genellikle büyük ölçekli optimizasyon problemları için kullanışlıdır. Ancak, bu yaklaşım, çözümün karmaşıklığına ve problemdeki genlerin etkileşimine bağlı olarak, bazı durumlarda performansı sınırlayabilir.

Bu örnekte, ikili dize çözümler üzerinde çalışan ve çözümün fitness'ini değerlendirmek için basit bir hedef fonksiyonu kullanan bir cGA uygulamasını sunuyorum.

import numpy as np

def fitness_function(solution):
    return np.sum(solution)

def run_cga(sol_len, num_iterations):
    # Başlangıç olasılık vektörünü oluşturun
    probabilities = np.full(sol_len, 0.5)

    for iteration in range(num_iterations):
        # Olasılık vektöründen iki çözüm oluşturun
        solution1 = np.random.binomial(1, probabilities)
        solution2 = np.random.binomial(1, probabilities)

        # Her iki çözümün fitness'ini hesaplayın
        fitness1 = fitness_function(solution1)
        fitness2 = fitness_function(solution2)

        # Kazananı belirleyin
        winner = solution1 if fitness1 > fitness2 else solution2

        # Olasılık vektörünü güncelleyin
        learning_rate = 1.0 / (iteration + 1)
        probabilities += learning_rate * (winner - probabilities)

    # En iyi çözümü döndür
    best_solution = np.random.binomial(1, probabilities)
    return best_solution

# Algoritmayı çalıştır
best_solution = run_cga(sol_len=50, num_iterations=100)
print("Best solution:", best_solution)

Bu kod, belirli bir çözüm uzunluğu ve iterasyon sayısı için cGA'yı çalıştırır. Fitness fonksiyonu, bir çözümün ne kadar iyi olduğunu belirlemek için kullanılır - bu örnekte, basitçe bir çözümdeki tüm bitlerin toplamını alıyoruz. Her iterasyon sırasında, olasılık vektöründen iki çözüm oluşturulur ve bu çözümler fitness değerlerine göre karşılaştırılır. Kazanan çözüm, olasılık vektörünü günceller.

Son olarak, kod en iyi çözümü döndürür. Bu örnekte, "en iyi" çözüm genellikle tüm bitleri 1 olan çözüm olacaktır, çünkü fitness fonksiyonumuz bitlerin toplamını maksimize etmeye çalışıyor.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  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...