Dağılım Araması (Scatter Search), optimizasyon algoritmalarından biridir ve birden çok çözüm oluşturmak ve bu çözümleri birleştirerek daha iyi çözümler elde etmek için özellikle tasarlanmıştır. Scatter Search, çözüm kümesini sürekli olarak genişletir ve iyileştirir.

Scatter Search'de çözüm adayları, önceden belirlenmiş bir dağılım kullanılarak belirlenen çeşitlilik kriterlerine göre seçilir. Çözüm adayları genellikle "referans seti" adı verilen bir kümede saklanır ve bu set daha sonra yeni çözüm adaylarını oluşturmak için kullanılır.

Scatter Search, optimizasyon problemleri için oldukça etkili olabilir, özellikle genetik algoritmalar gibi başka evrimsel algoritmalarla birleştirildiğinde. Bu tür algoritmalar genellikle geniş ve karmaşık arama alanlarında yüksek kaliteli çözümler bulmak için kullanılır. Scatter Search, ayrıca çok hedefli optimizasyon problemlerini çözmek için de kullanılabilir. 

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

1. Başlangıç popülasyonunun oluşturulması: Başlangıçta, çeşitli çözümler oluşturulur. Bu çözümler genellikle rastgele seçilir veya belirli bir heuristik kullanılarak oluşturulur.

2. Referans setinin oluşturulması: Başlangıç popülasyonundan, belirli bir çeşitlilik kriterine göre çözümler seçilir ve referans setine eklenir.

3. Yeni çözümlerin oluşturulması: Referans setindeki çözümler, yeni çözümler oluşturmak için birleştirilir. Bu genellikle, iki veya daha fazla çözümün belirli bölümlerini alarak ve bunları yeni bir çözümde birleştirerek gerçekleştirilir.

4. Referans setinin güncellenmesi: Oluşturulan yeni çözümler, belirli bir kalite kriterine göre değerlendirilir ve eğer daha iyilerse, referans setine eklenir.

5. Durma kriterinin kontrol edilmesi: Algoritma, belirli bir durma kriteri karşılanana kadar 3. ve 4. adımları tekrarlar. Bu durma kriteri genellikle belirli bir zaman sınırına, iterasyon sayısına veya başka bir kriterlere ulaşıldığında gerçekleşir.

Bu adımlar, belirli bir optimizasyon problemine uygun hale getirilebilir ve gerektiği şekilde uyarlanabilir. Her ne kadar Scatter Search algoritması karmaşık görünebilir olsa da, birçok farklı problem türüne uygulanabilme yeteneği ve geniş çözüm arama yetenekleri nedeniyle, oldukça popüler ve etkili bir optimizasyon yöntemi olarak kabul edilir.

0-1 knapsack problemi, belirli bir ağırlık sınırlaması altında en yüksek toplam değeri elde etmek için hangi öğelerin alınacağını belirlemek için kullanılan bir optimizasyon problemidir.

import random

def generate_solution(num_items):
    """Rastgele bir çözüm oluşturur."""
    return [random.randint(0, 1) for _ in range(num_items)]

def evaluate_solution(solution, values, weights, max_weight):
    """Bir çözümün kalitesini (toplam değeri) ve geçerliliğini (ağırlık sınırlaması) belirler."""
    total_value = sum(val * sol for val, sol in zip(values, solution))
    total_weight = sum(wgt * sol for wgt, sol in zip(weights, solution))

    if total_weight > max_weight:
        return 0  # geçerli olmayan çözüm
    else:
        return total_value

def combine_solutions(sol1, sol2):
    """İki çözümü birleştirir."""
    return [(s1+s2)//2 for s1, s2 in zip(sol1, sol2)]

# problem parametreleri
num_items = 10
values = [random.randint(1, 50) for _ in range(num_items)]
weights = [random.randint(1, 50) for _ in range(num_items)]
max_weight = sum(weights) // 2

# başlangıç popülasyonu
population = [generate_solution(num_items) for _ in range(20)]
population.sort(key=lambda sol: evaluate_solution(sol, values, weights, max_weight), reverse=True)

# algoritma
for _ in range(1000):
    # yeni çözümler oluştur
    new_solutions = [combine_solutions(random.choice(population), random.choice(population)) for _ in range(10)]

    # popülasyonu güncelle
    population += new_solutions
    population.sort(key=lambda sol: evaluate_solution(sol, values, weights, max_weight), reverse=True)
    population = population[:20]  # en iyi 20 çözümü koru

# en iyi çözüm
best_solution = population[0]
print("Best solution:", best_solution)
print("Value:", evaluate_solution(best_solution, values, weights, max_weight))

Bu kod, bir Scatter Search algoritmasının temel bir uygulamasını göstermektedir ve birçok farklı şekilde uyarlanabilir ve geliştirilebilir. Örneğin, çözümler oluşturmak ve birleştirmek için farklı yöntemler kullanılabilir, ve popülasyonun güncellenmesi ve çözüm adaylarının değerlendirilmesi için farklı kriterler belirlenebilir.

Scatter Search algoritmasının genel bir işleyişine dair bir örnek verebiliriz. Ancak, belirtmekte fayda var ki bu algoritma karmaşıktır ve genellikle daha büyük, daha karmaşık veri setlerinde kullanılır. 

Scatter Search, bir grup çözüm oluşturarak ve bu çözümleri birbirleriyle karşılaştırarak çalışır. Her bir çözüm, bir "mahalle" veya "çözüm uzayı" oluşturur ve algoritma, en iyi çözümü bulmak için bu uzayda arama yapar.

Örneğin, bir şehirdeki en kısa yol problemini ele alalım. Şehirler listesini permutasyonlarının tümünü oluşturarak başlarız. Her bir permutasyon, bir çözüm temsil eder. Bu ilk çözüm kümesi rastgele seçilebilir veya heuristik bir yöntemle oluşturulabilir. 

Ardından, bu çözümleri karşılaştırarak ve en iyi çözümleri seçerek bir "referans set" oluştururuz. Referans setindeki çözümler, çözüm uzayımızın farklı bölgelerini temsil eder.

Daha sonra, çeşitli çözümleri birleştiren ve yeni çözümler oluşturan bir "kombinasyon yöntemi" uygularız. Bu yeni çözümler, referans setine eklenir ve işlem, bir durma koşulu karşılanana kadar tekrar eder. Durma koşulu genellikle bir zaman sınırlaması veya belirli bir sayıda iterasyon olabilir.

Bu sürecin sonunda, referans setindeki en iyi çözüm, genel problem için en iyi çözüm olarak kabul edilir. Bu çözüm, şehirler arasındaki en kısa yol olacaktır.

Unutmayın ki bu basit bir örnektir. Gerçek dünyada, Scatter Search genellikle çok daha karmaşık problemlerde kullanılır ve daha sofistike heuristikler ve kombinasyon yöntemleri gerektirebilir. Ayrıca, bu örnekte olduğu gibi her çözümün açık bir şekilde belirlenmesi yerine, genellikle çözümler bir dizi parametre veya değişken tarafından tanımlanır.

Bir örnek:

Scatter Search algoritmasının daha karmaşık bir uygulamasını, örneğin bir havaalanı personel zaman çizelgesi planlamasında düşünebiliriz. 

Havaalanı personel zaman çizelgeleri, birçok farklı kısıtlamalar ve hedefler arasında dengelerken ideal bir çözüm bulmak için karmaşık bir optimizasyon problemi oluşturur. Çalışanların belirli saatlerde ve belirli günlerde çalışma gereklilikleri, belirli pozisyonlar için gereken minimum personel sayısı, çalışanların mevcudiyeti ve istekleri, yasal ve sendika kısıtlamaları vb. gibi çeşitli faktörler göz önüne alınmalıdır.

İlk başta, bir dizi rastgele zaman çizelgesi oluşturabiliriz. Bu çizelgeler, belirli bir değerlendirme fonksiyonu kullanılarak derecelendirilir ve en iyi olanlar bir referans setine eklenir.

Ardından, bir dizi zaman çizelgesi birleştirilir ve yeni zaman çizelgeleri oluşturmak için genetik algoritma benzeri bir işlem uygulanır (örneğin, çaprazlama ve mutasyon).

Bu yeni çizelgeler, değerlendirme fonksiyonuna göre derecelendirilir ve yeterince iyi olanlar referans setine eklenir. 

Bu süreç, belirli bir durma koşulu karşılanana kadar tekrarlanır. Sonuçta, en iyi zaman çizelgesi (veya çizelgeler), işgücü maliyetlerini minimize etmek ve çalışan memnuniyetini maksimize etmek gibi belirli hedeflere ulaşmamızı sağlar.

Bu tür bir problemde, Scatter Search algoritması genellikle bir dizi heuristik ve özel kombinasyon yöntemi kullanılarak uyarlanır ve büyük ölçüde paralelleştirilebilir, bu da büyük ölçekli problemler için idealdir.