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

Aşırı Optimizasyon (Extremal Optimization - EO)


Doğuhan ELMA

253 views

Extremal Optimization (EO) veya "Aşırı Optimizasyon", kısmi sıralamaları kullanarak genel olarak NP-zor problemlerin çözümünde uygulanan bir optimizasyon tekniğidir. Bu yaklaşım, sistemlerin dinamiklerini inceleyen istatistiksel fizikten ilham almıştır. Extremal Optimization, çok sayıda yerel minimum veya maksimuma sahip karmaşık optimizasyon problemlarının çözümü için genellikle kullanılır.

EO algoritması genellikle aşağıdaki adımları içerir:

1. İlk olarak, bir başlangıç çözümü rastgele seçilir ve çözümdeki her bir elemanın 'kalitesi' değerlendirilir. Kalite genellikle çözümdeki bir elemanın çözüm kalitesine olan katkısını ölçer.

2. Daha sonra, kalite değerine göre her bir elemanın sıralaması belirlenir. Burada, kalitesi düşük olan elemanların daha yüksek sıralamaya sahip olması beklenir. Yani, bir eleman ne kadar kötüyse, o elemanın değiştirilme olasılığı o kadar yüksektir.

3. Bir sonraki adımda, sıralamaya göre bir eleman seçilir ve bu eleman rastgele bir değerle değiştirilir. Bu adımda, genellikle bir olasılık dağılımı kullanılır.

4. Bu süreç, belirlenen bir durma kriterine kadar devam eder. Durma kriteri genellikle belirli bir iterasyon sayısına veya belirli bir çözüm kalitesine ulaşmayı içerir.

EO, yerel arama tekniği ve iteratif bir yaklaşıma dayanır ve genellikle genetik algoritmalardan veya diğer evrimsel hesaplama tekniklerinden daha basittir. Ancak, EO'nun diğer optimizasyon tekniklerine göre bazı avantajları vardır. Örneğin, EO genellikle yerel minimumlardan kaçmayı başarır ve bu, çoğu kez karmaşık optimizasyon problemlarının çözümünde oldukça yararlıdır.

Extremal Optimization (EO) algoritmasının en basit biçimini ele alalım. Örneğin, bir takas tabanlı optimizasyon problemi olan seyahat satış temsilcisi problemi (Travelling Salesman Problem - TSP) üzerinde çalışacağımızı düşünelim. Bu durumda, TSP'nin her bir çözümü şehirlerin bir sırasını temsil eder ve her bir şehir bir eleman olarak kabul edilir. İki şehir arasındaki mesafeyi optimize etmeye çalışacağız.

Ancak, bu tür bir problem karmaşıktır ve genellikle spesifik bir optimizasyon kitaplığı gerektirir. Aşağıda, temel EO algoritmasının Python'da nasıl uygulanabileceğine dair bir örneği bulabilirsiniz. Ancak, lütfen bu kodun bir basitleştirilmiş versiyon olduğunu ve genellikle gerçek dünya problemlarının çözümü için daha karmaşık ve uyarlanmış bir algoritma gerektireceğini unutmayın.

import numpy as np

# Problem ayarları
n = 100  # eleman sayısı
num_iter = 1000  # iterasyon sayısı

# Rastgele bir başlangıç çözümü oluşturalım
solution = np.random.rand(n)

for _ in range(num_iter):
    # Kaliteyi hesaplama (burada daha düşük kalite, daha yüksek sıralama anlamına gelir)
    quality = solution ** 2  # Burada, kalite olarak elemanların karelerini alıyoruz
    
    # Sıralamayı hesaplama
    ranks = np.argsort(np.argsort(quality))

    # Değiştirilecek elemanı seçme
    tau = 1.0  # tau, seçim olasılığının ölçeğini kontrol eder
    probabilities = ranks ** -tau
    probabilities /= probabilities.sum()  # Olasılıkları normalize ediyoruz
    index = np.random.choice(n, p=probabilities)

    # Seçilen elemanı rastgele bir değerle değiştirme
    solution[index] = np.random.rand()

print("Son çözüm: ", solution)

Bu kodda, kalite olarak elemanların karelerini kullanıyoruz, böylece daha büyük değerlerin (daha yüksek kalitedeki elemanların) değiştirilmesi daha olası olacaktır. Ayrıca, seçim olasılığının ölçeğini kontrol etmek için tau parametresini kullanıyoruz. Bu parametre, sıralamanın seçim olasılığı üzerindeki etkisini kontrol eder. Bu parametre daha yüksek olduğunda, kötü performans gösteren elemanların değiştirilmesi daha olası olur. Son olarak, seçilen elemanı rastgele bir değerle değiştiriyoruz.

Bu örnek oldukça basitleştirilmiştir ve gerçek dünya uygulamalarında genellikle daha karmaşık bir kalite fonksiyonu ve daha gelişmiş bir seçim ve değiştirme mekanizması gereklidir. Ayrıca, bu örnekte, çözüm kalitesini belirli bir problem çerçevesinde anlamlı bir şekilde değerlendirecek bir durma kriterimiz veya hedef fonksiyonumuz yoktur. Bunlar genellikle probleme özgüdür ve algoritmanın uygulandığı spesifik problemi çözmek için özenle seçilmelidir.

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