Baskın Olmayan Sıralama Genetik Algoritması II (Non-dominated Sorting Genetic Algorithm II veya kısaca NSGA-II), çok amaçlı optimizasyon problemlerini çözmek için tasarlanmış bir evrimsel algoritmadır. Kalyanmoy Deb ve arkadaşları tarafından 2002 yılında geliştirilmiştir.

Çok amaçlı optimizasyon, birbiriyle çelişen birden çok hedefi optimize etme problemini ifade eder. Bu durumda, tek bir "en iyi" çözüm yerine, çeşitli "eşit derecede iyi" çözümler bulunabilir ve bunlar genellikle Pareto-optimal çözümler olarak bilinir.

NSGA-II, üç temel mekanizma üzerine kuruludur: baskın olmayan sıralama, kalabalık karşılaştırma ve elitizm. İşte nasıl çalıştığına genel bir bakış:

1. Baskın olmayan sıralama: Algoritma, her bireyin çözüm uzayındaki yerine göre bir "baskın olmayan" sıralama yapar. Bir bireyin başka bir birey tarafından "baskın edilmesi", ikinci bireyin tüm hedeflerde ilk bireyden en az eşit veya daha iyi olması ve en az bir hedefte daha iyi olması anlamına gelir. Baskın olmayan bireyler aynı "ön" veya seviyeye yerleştirilir. Algoritma daha sonra bu bireyleri çıkarır ve kalan bireyler üzerinde aynı süreci tekrarlar, her seferinde bir sonraki "ön" bireylerini bulur. Bu süreç, tüm bireyler bir ön seviyeye atanana kadar devam eder.

2. Kalabalık karşılaştırma operatörü: NSGA-II, aynı ön seviyedeki bireyler arasında seçim yapmak için bir kalabalık karşılaştırma operatörü kullanır. Bu operatör, her bireyin "kalabalık mesafesi"ni hesaplar, bu da bireyin komşularının hedef değerlerine ne kadar yakın olduğunu gösterir. Kalabalık mesafesi daha büyük olan bireyler, daha az kalabalık bölgelerde bulundukları ve bu nedenle daha fazla çeşitlilik sundukları için tercih edilir.

3. Elitizm: NSGA-II, bir nesilden diğerine en iyi bireylerin aktarılmasını sağlar. Bu, algoritmanın daha önce bulduğu iyi çözümleri korumasına ve daha hızlı bir şekilde yakınsamasına yardımcı olur.

NSGA-II, genetik algoritmaların kullanıldığı birçok alanda etkili ve popüler bir algoritmadır. Bunlar arasında mühendislik tasarımı, yapay sinir ağları, veri madenciliği ve daha pek çok alan bulunur. Özellikle çok sayıda hedefin olduğu ve/veya çözüm uzayının karmaşık olduğu problemler için uygundur.

Kod:

import numpy as np

# Hedef fonksiyonumuzu tanımlıyoruz.
# Bu örnekte, iki hedefimiz var: x[0] ** 2 ve (x[0] - 2) ** 2
def objective_function(x):
    return [x[0] ** 2, (x[0] - 2) ** 2]

# İlk nüfusu oluşturuyoruz. Her bireyin iki boyutlu olduğunu varsayıyoruz.
def generate_initial_population(size, dimensions):
    return np.random.uniform(-10, 10, (size, dimensions))

# Nüfustaki her birey için hedef değerlerini hesaplıyoruz.
def compute_objective_values(population):
    return np.array([objective_function(x) for x in population])

# Baskın olmayan sıralama fonksiyonu. Hedef değerlerine göre nüfustaki bireyleri sıralar.
def fast_non_dominated_sort(values):
    population_size = values.shape[0]
    domination_counts = np.zeros(population_size, dtype=int)
    dominated_sets = [set() for _ in range(population_size)]
    fronts = [[]]
    for i in range(population_size):
        for j in range(i + 1, population_size):
            if np.all(values[i] <= values[j]) and np.any(values[i] < values[j]):
                domination_counts[j] += 1
                dominated_sets[i].add(j)
            elif np.all(values[j] <= values[i]) and np.any(values[j] < values[i]):
                domination_counts[i] += 1
                dominated_sets[j].add(i)
        if domination_counts[i] == 0:
            fronts[0].append(i)
    i = 0
    while len(fronts[i]) != 0:
        next_front = []
        for individual in fronts[i]:
            for dominated_individual in dominated_sets[individual]:
                domination_counts[dominated_individual] -= 1
                if domination_counts[dominated_individual] == 0:
                    next_front.append(dominated_individual)
        i += 1
        fronts.append(next_front)
    return fronts[:-1]


# Seçim ve çaprazlama işlemleri gerçekleştirilir.
def crossover(parent1, parent2, crossover_rate=0.5):
    child = np.empty(parent1.shape)
    for i in range(len(parent1)):
        child[i] = parent1[i] if np.random.rand() < crossover_rate else parent2[i]
    return child

# Mutasyon işlemi gerçekleştirilir.
def mutate(individual, mutation_rate=0.1):
    for i in range(len(individual)):
        if np.random.rand() < mutation_rate:
            individual[i] += np.random.normal()
    return individual

# Çocukları oluşturmak için seçim, çaprazlama ve mutasyon işlemlerini gerçekleştiriyoruz.
def create_offspring(population, fronts, values):
    offspring = []
    for front in fronts:
        np.random.shuffle(front)  # for random selection
        for i in range(0, len(front) // 2 * 2, 2):  # for pairs of parents
            parent1 = population[front[i]]
            parent2 = population[front[i + 1]]
            child1 = crossover(parent1, parent2)
            child2 = crossover(parent1, parent2)
            child1 = mutate(child1)
            child2 = mutate(child2)
            offspring.extend([child1, child2])
    return np.array(offspring)

# Parametreler
population_size = 100
num_generations = 50
dimensions = 2

# İlk nüfusu oluşturuyoruz
population = generate_initial_population(population_size, dimensions)

# Nesiller boyunca iterasyon yaparak NSGA-II algoritmasını çalıştırıyoruz
for generation in range(num_generations):
    print(f"Nesil {generation}")

    # Nüfustaki her birey için hedef değerlerini hesaplıyoruz
    values = compute_objective_values(population)

    # Baskın olmayan sıralamayı gerçekleştiriyoruz
    fronts = fast_non_dominated_sort(values)

    # Çocukları oluşturuyoruz
    offspring = create_offspring(population, fronts, values)

    # Ebeveynler ve çocuklar birleştirilir
    population = np.concatenate((population, offspring))

    # Birleştirilmiş nüfusu sıralıyoruz
    values = compute_objective_values(population)
    fronts = fast_non_dominated_sort(values)

    # Bir sonraki nesil için en iyi bireyleri seçiyoruz
    next_population = []
    for front in fronts:
        if len(next_population) + len(front) <= population_size:
            for individual in front:
                next_population.append(population[individual])
        else:
            break
    population = np.array(next_population)

Bu kodda NSGA-II algoritması birçok nesil boyunca çalıştırılıyor. Her nesilin sonunda, popülasyondaki bireylerin hedef değerlerini hesaplıyor ve bunları baskın olmayan sıralama ile sıralıyor. Sıralama, çözümlerin birden fazla hedefi optimize etmeye çalıştığı çok hedefli optimizasyon problemlerinde kullanılır. Baskın olmayan sıralamada, bir çözüm ancak tüm hedeflerde diğer çözümden daha iyi olduğunda diğerini domine eder.

Bir sonraki adımda, çocukların oluşturulması için çaprazlama ve mutasyon işlemleri gerçekleştirilir. Ebeveynler ve çocuklar daha sonra birleştirilir ve bu birleştirilmiş popülasyon baskın olmayan sıralamayla tekrar sıralanır.

Bir sonraki nesil için en iyi bireyler seçilir. Bu seçim sürecinde, popülasyon boyutunun sabit kalmasını sağlamak için bireylerin belirli bir sayısı seçilir.

Kod çıktısını inceleyerek, her nesilde bireylerin hedef değerlerinin nasıl değiştiğini ve popülasyonun zamanla nasıl evrimleştiğini görebilirsiniz. İdeal olarak, hedef değerler nesiller boyunca azalır ve bu, algoritmanın çözümü geliştirdiğini gösterir. Ancak, NSGA-II'nin çok hedefli bir algoritma olduğunu unutmayın, yani çözüm hem tüm hedefleri optimize etmelidir ve ayrıca çeşitliliği (çözüm alanındaki farklı bölgeleri keşfetme) korumalıdır. Bu nedenle, hedef değerlerin birindeki bir azalma, diğerinde bir artışa yol açabilir. NSGA-II'nin genel amacı, bu çeşitli hedefler arasında bir denge bulmaktır.