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

Tek Değişkenli Marjinal Dağılım Algoritması (Univariate Marginal Distribution Algorithm - UMDA)


Doğuhan ELMA

280 views

Tek Değişkenli Marjinal Dağılım Algoritması (Univariate Marginal Distribution Algorithm - UMDA), Olasılık Model Tabanlı Genetik Algoritmaların (PMGA) bir türüdür ve bir popülasyondaki çözümler üzerinden olasılık dağılımı modelini öğrenir.

UMDA, genetik algoritma döngüsüne benzer şekilde çalışır: bir popülasyon oluşturulur, bu popülasyon değerlendirilir ve ardından bir sonraki nesil için seçim yapılır. Ancak, seçim yapıldıktan sonra, kalan bireylerden bir olasılık modeli öğrenilir ve bu model, yeni bireyler oluşturmak için kullanılır.

Ayrıntılı olarak adımlar:

1. Başlangıçta, bir popülasyon oluşturulur. Bireyler genellikle rastgele oluşturulur.
2. Her bir bireyin uygunluk değeri hesaplanır. Uygunluk, bireyin problemi ne kadar iyi çözdüğünü belirleyen bir metriktir.
3. En iyi uygunluğa sahip bireyler seçilir. Bu, genellikle bir rulet çarkı seçimi veya turnuva seçimi ile yapılır.
4. Seçilen bireylerden bir olasılık modeli öğrenilir. UMDA'da, bu model genellikle tek değişkenli marjinal dağılımlardan oluşur, bu da her bit pozisyonunun bağımsız olarak değerlendirildiği anlamına gelir.
5. Bu olasılık modeli kullanılarak yeni bireyler oluşturulur.
6. Bu yeni popülasyon, bir sonraki iterasyonda kullanılır. Süreç, belirli bir durdurma kriteri karşılanana kadar tekrarlanır.

UMDA'nın en önemli özelliği, olasılık modelinin öğrenilmesi ve yeni bireylerin bu modelden örneklenmesidir. Bu, genetik çeşitliliği korurken, aynı zamanda arama alanını etkili bir şekilde daraltmayı sağlar. Bununla birlikte, UMDA'nın tek değişkenli (bağımsız) olasılık modeli, bireyler arasındaki karmaşık etkileşimleri modelleyemez, bu da algoritmanın karmaşık problemlerdeki performansını sınırlayabilir.

import numpy as np

# parametreler
n_pop = 50  # Popülasyon büyüklüğü
n_gen = 100  # Jenerasyon sayısı
n_bits = 10  # Her bireyin bit sayısı
p_s = 0.5  # Seçim oranı

# uygunluk fonksiyonu: daha büyük toplam daha iyi
def fitness(individual):
    return sum(individual)

# popülasyonu başlat
pop = np.random.randint(2, size=(n_pop, n_bits))

for gen in range(n_gen):
    # uygunlukları hesapla
    fit = np.array([fitness(ind) for ind in pop])

    # en uygun bireyleri seç
    chosen = pop[fit > np.percentile(fit, (1-p_s)*100)]
    
    # eğer hiçbir birey seçilmediyse, en uygun olanı seç
    if len(chosen) == 0:
        chosen = np.array([pop[np.argmax(fit)]]) # np.array ile diziye çevirilir

    # olasılık modelini öğren ve yeni popülasyon oluştur
    p = chosen.mean(axis=0)
    for i in range(n_pop):
        for j in range(n_bits):
            pop[i,j] = np.random.choice([0, 1], p=[1-p[j], p[j]])

print("Final population:")
print(pop)

Bu kod, Tek Değişkenli Marjinal Dağılım Algoritması (UMDA) kullanılarak bir popülasyonun evrimini simüle eder. İlk olarak, belirli bir bit sayısı (n_bits) ile rastgele bir popülasyon oluşturulur. Her bir "birey" bu popülasyon içinde bir dizi olup, bu dizi 0 ve 1'lerden oluşur.

Daha sonra, her jenerasyon için aşağıdaki adımlar tekrarlanır:

1. Uygunlukları hesaplar: Her bir bireyin uygunluk değerini, bireyin elemanlarının (0'lar ve 1'ler) toplamı olarak belirler. Yani, bu örnekte daha fazla 1'e sahip olan bireyler daha uygun kabul edilir.
2. En uygun bireyleri seçer: Uygunluk değeri belirli bir eşiği (bu durumda, uygunluk değerlerinin belirli bir yüzdelik dilimini) geçen bireyleri seçer. Bu bireyler, bir sonraki jenerasyonun oluşturulmasına yardımcı olacaklardır.
3. Olasılık modelini öğrenir ve yeni popülasyon oluşturur: Seçilen bireylerden her bir bitin ortalama değerini hesaplar ve bu değerleri kullanarak yeni bireyler oluşturur.

Son çıktı, bu evrimsel sürecin sonunda elde edilen popülasyonu gösterir. Bu nedenle, her jenerasyonun sonunda, popülasyondaki bireylerin genellikle daha fazla 1'ye sahip olduklarını ve bu nedenle başlangıçtaki rastgele popülasyona göre daha "uygun" olduklarını görmeyi bekleriz. Bu, UMDA'nın temel amacıdır: Belirli bir uygunluk fonksiyonunu optimize etmek için popülasyonun evrimini simüle etmek. Bu durumda, uygunluk fonksiyonu, bir bireyin elemanlarının toplamıdır.

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