Tabakalar halinde örgütlenen canlıların bazıları, sosyal ilişkilerini doğal seçilim yoluyla geliştirirler. Bu seçilim sürecinde bazı bireyler, diğerlerine göre daha üstün özelliklere sahip olarak hayatta kalıp, üremeye devam ederler. Bu sayede bir sonraki nesle daha avantajlı özellikler aktarılır. Bu yaklaşım, birçok problemi çözmek için kullanılan doğal algoritmalara ilham vermiştir. Baskın küme problemi (Dominance Cluster Problem) de bu algoritmalar kullanılarak çözülebilen bir problemdir. Bu yazıda, discrete grey wolf optimizasyon algoritması kullanılarak baskın küme problemi çözülecektir. İlk olarak, baskın küme probleminin ne olduğuna bakalım.
Baskın Küme Problemi
Baskın küme problemi, bir ağın düğümlerinin birbirleriyle olan ilişkileriyle ilgili bir problemdir. Ağdaki bir düğümün baskınlığı, o düğümle doğrudan ya da dolaylı olarak bağlantısı olan diğer düğümlerin sayısıyla ölçülür. Baskın küme problemi, ağı oluşturan düğümlerin baskınlık sayılarına göre ağın en küçük sayıda küme halinde ifade edilebilmesi sorunudur.
Baskın küme problemi, verilen bir graf üzerinde en büyük ve en kompakt kümeyi bulmaya çalışmaktır. Bu problemi çözmek için, her bir düğümü bir küme olarak düşünebiliriz ve her küme, düğümler arasındaki ağırlıklı bağlantıları temsil eder.
Discrete Grey Wolf Optimizasyon Algoritması
Discrete Grey Wolf Optimization (DGWO) algoritması, birçok optimizasyon problemi çözmek için kullanılan bir yöntemdir. DGWO, klasik Grey Wolf Optimization (GWO) algoritmasının bir modifikasyonudur ve kategorik değerler için uygulanabilir.
DGWO algoritması, bir popülasyon içinde üç tip lobo temsil eder: Alpha lobosu, beta lobosu ve delta lobosu. Bu lobolar arasındaki etkileşim, en iyi çözümü bulmak için kullanılır.
Algoritma şöyle çalışır:
- İlk olarak, rastgele bir popülasyonda alpha, beta ve delta loboları oluşturulur. Her lobo, problem için geçerli olan değer aralığındaki bir kategori değerini temsil eder.
- Daha sonra, alpha, beta ve delta lobolarının yerleri güncellenir. Her lobonun yerini, diğer lobolarla olan etkileşimi kullanarak hesaplar.
- Güncellenen loboların değerleri, problem için tanımlanmış olan değerlendirme fonksiyonu ile değerlendirilir ve en iyi lobo seçilir.
- Bu işlem, belli bir iterasyon sayısı kadar tekrar edilir.
- Son iterasyonda en iyi lobo, en iyi çözüm olarak seçilir.
DGWO algoritması, klasik GWO algoritmasına benzer şekilde çalışır ve klasik GWO algoritmasının avantajlarını korur. Ancak, DGWO, kategorik değerler için uygulanabilir olması nedeniyle daha geniş bir uygulama alanına sahiptir. Örneğin, baskın küme problemi, sayısal değerler değil, kategori değerleri kullanarak çözülebilir.
Baskın Küme Problemi Çözümü için DGWO Algoritması
İlk olarak, numpy kütüphanesini çağıralım.
import numpy as np
Ardından, solve_dominance_cluster_DGWO() adında bir fonksiyon tanımlayalım.
def solve_dominance_cluster_DGWO():
Fonksiyon içinde, bir doğrusal grafik olarak temsil edilen örnek ağırlıklı bir matris oluşturalım.
Ardından, matris boyutunu belirlemek için n değişkenini tanımlayalım.
n = len(adj_mat)
Popülasyonu oluşturmak için alfa, beta ve delta kurdu pozisyonlandıralım.
alpha = np.random.randint(0, 2, n)
beta = np.random.randint(0, 2, n)
delta = np.random.randint(0, 2, n)
DGWO algoritması için parametreleri de tanımlayalım.
a = 2
A = 0
C = 2
Baskın küme problemi için bir fitness fonksiyonu tanımlayalım.
def eval_dominance_cluster(x):
return sum([adj_mat[i][j] for i in range(n) for j in range(i, n) if x[i] and x[j]])
Burada, eval_dominance_cluster fonksiyonu, x vektörü ile temsil edilen bir çözümün uygunluğunu hesaplamak için kullanılır. Bu uygunluk fonksiyonu, ağ matrisindeki bağlantılar arasında x vektöründeki düğümler tarafından oluşturulan bir hakim küme içeren bağlantı sayısını hesaplar.
Bu döngü, DGWO algoritmasının ana döngüsüdür. Her adımda, alfa, beta ve delta kurtların pozisyonu güncellenir ve bu pozisyonlar bir sınır kontrolüne tabi tutulur. Daha sonra, her kurdun yeni pozisyonundaki uygunluk hesaplanır ve en iyi çözüm güncellenir. Son olarak, DGWO algoritması için parametreler güncellenir.
En iyi çözümü döndürelim.
# return best solution
return best_solution
solve_dominance_cluster_DGWO() fonksiyonunu çağırarak en iyi çözümü hesaplayalım ve bu çözümü ekrana yazdıralım.
solution = solve_dominance_cluster_DGWO()
print(solution)
Bu yazıda Discrete Grey Wolf Optimizasyon algoritmasını kullanarak baskın küme problemini çözdük. Algoritma, doğal seçilimden ilham alarak, üç farklı kurt sürüsü (alpha, beta ve delta) kullanarak arama yapar. Her iterasyonda bu kurt sürüleri yeni pozisyonlarını belirler ve fitness değerleri hesaplanarak en iyi çözüm belirlenir. Algoritma son derece etkili bir şekilde çalışır ve genel olarak nispeten az sayıda iterasyonda çözüm üretir. DGWO algoritması, bu özellikleri nedeniyle birçok farklı optimizasyon problemi için kullanılabilir.