Değişken Mahalle Araması (Variable Neighborhood Search, VNS), bir meta-sezgisel optimizasyon algoritmasıdır. Birçok reel dünya optimizasyon sorununda, yerel optimumlara takılmaktan kaçınmak için genellikle birden çok arama stratejisi kullanılır. VNS, yerel arama stratejilerinin bu olasılıklarını genişletmeye yardımcı olacak bir yaklaşım sunar.

VNS'nin temel fikri, bir dizi farklı mahalle yapısını sistematik olarak kullanmaktır. Her bir mahalle yapısı, çözüm alanının farklı bir bölgesine karşılık gelir. Bu durum, VNS'nin farklı yerel optimumlardan kaçmasına ve genel bir optimuma ulaşmasına yardımcı olur.

VNS'nin genel adımları aşağıdaki gibidir:

1. Başlangıç çözümü seçilir.

2. Farklı bir mahalle yapısı seçilir ve mevcut çözümün bu mahalledeki en iyi komşusu bulunur.

3. Bu yeni çözüm, mevcut çözümden daha iyi ise, bu yeni çözüm mevcut çözüm olarak kabul edilir ve mahalle yapısı değiştirilir.

4. Eğer bu yeni çözüm mevcut çözümden daha iyi değilse, farklı bir mahalle yapısı seçilir.

5. Bu adımlar, belirli bir durdurma kriteri karşılanana kadar tekrar edilir (örneğin, belirli bir zaman sınırı geçilmiştir veya belirli bir sayıda iterasyon tamamlanmıştır).

VNS, yerel arama yöntemlerini kullanan birçok reel dünya optimizasyon sorununda etkilidir. Ayrıca, farklı mahalle yapıları kolayca uyarlanabilir ve genellenebilir, bu da VNS'yi çeşitli uygulamalar için esnek bir araç haline getirir.

import random

# Rastgele bir sayı listesi oluşturuyoruz
numbers = [random.randint(-10, 10) for _ in range(20)]

def neighborhood(seq, k):
    """seq listesindeki 'k' elemanlı tüm altkümeleri oluşturur"""
    return [seq[i:i+k] for i in range(len(seq)-k+1)]

def vns(seq, k_max):
    """Verilen bir 'seq' listesi üzerinde VNS uygular"""
    current_solution = seq[:1]
    k = 1
    while k <= k_max:
        # 'k' elemanlı altkümeleri oluşturuyoruz
        neighbors = neighborhood(seq, k)
        # En iyi komşuyu buluyoruz (toplamı en yüksek olanı)
        best_neighbor = max(neighbors, key=sum)
        if sum(best_neighbor) > sum(current_solution):
            # Daha iyi bir çözüm bulduysak, mevcut çözümü güncelleriz
            current_solution = best_neighbor
            k = 1
        else:
            # Aksi takdirde, bir sonraki mahalleye geçeriz
            k += 1
    return current_solution

# VNS'yi uygulayalım
best_subset = vns(numbers, 3)
print("En iyi altküme: ", best_subset)

Bu kod, numbers listesindeki sayıların toplamını maksimize eden altkümeyi bulmaya çalışır. vns fonksiyonu, farklı büyüklükteki mahallelerde (altkümelerde) arama yapar (her bir 'k' için). Her adımda, en iyi komşuyu (yani toplamı en yüksek olan altkümeyi) bulur. Eğer bu komşu mevcut çözümden daha iyiyse, mevcut çözümü bu komşuyla değiştirir ve 'k' değerini 1'e sıfırlar. Eğer bu komşu mevcut çözümden daha iyi değilse, bir sonraki mahalleye (yani bir sonraki 'k' değerine) geçer. Bu işlem, belirli bir 'k_max' değerine kadar devam eder. Bu basit örnekte 'k_max' değeri 3 olarak belirlenmiştir.

Değişken Mahalle Araması (Variable Neighborhood Search - VNS) algoritmasının temel kavramlarına aşağıda yer verilmiştir:

Mahalle (Neighborhood): Optimizasyon problemlerinde, bir çözümün "mahallesi" genellikle o çözüme benzer çözümlerin bir kümesidir. Bu benzerlik genellikle küçük, yerel değişikliklerle elde edilir. Örneğin, bir yol planlama probleminde bir çözümün mahallesi, mevcut yoldaki iki şehir arasındaki sıralamanın değiştirilmesiyle elde edilebilecek tüm yollar olabilir.

Değişken Mahalle (Variable Neighborhood): VNS, bir dizi farklı mahalle yapılarını kullanan bir arama algoritmasıdır. Bu, algoritmanın çözüm alanının farklı bölgelerini keşfetmesini sağlar ve yerel optimumlara takılı kalmasını önler.

Mahalle Yapıları (Neighborhood Structures): VNS algoritması, genellikle bir dizi mahalle yapısı tanımlar. Her mahalle yapısı, bir çözümün mahallesini farklı bir şekilde tanımlar. Algoritma, bu mahalle yapılarını döngüsel olarak kullanarak arama yapar.

Yerel Arama (Local Search): VNS, her mahalle yapısı için bir yerel arama algoritması uygular. Yerel arama, bir çözümün mahallesindeki en iyi komşuyu (yani en düşük maliyetli veya en yüksek getirili çözümü) bulmayı amaçlar.

Kabul Kriteri (Acceptance Criterion): VNS genellikle bir kabul kriteri kullanır. Bu, bir çözümün mahallesindeki bir komşunun mevcut çözümden daha iyi olup olmadığını belirler. Eğer komşu çözüm daha iyiyse, o çözüm yeni mevcut çözüm olur ve algoritma yeni mevcut çözümün mahallesinde arama yapmaya devam eder.

Dış döngü ve İç döngü (Outer Loop and Inner Loop): VNS algoritmasının tipik bir uygulaması, iki döngü içerir. İç döngü, bir mahalle yapısında yerel arama yapar. Dış döngü ise, mahalle yapıları arasında geçiş yapar.

Dahada açarsak;

Mahalle Yapıları: Bir "mahalle", çözümünüzün etrafındaki çözümleri ifade eder. Mahalle yapısı, neyin "yakın" olduğunu belirler. Örneğin, çikolata mağazalarını ziyaret etmeye karar verdiyseniz, bir mahalle yapısı yürüme mesafesindeki mağazaları içerebilir. Başka bir mahalle yapısı, belirli bir otobüs hattı boyunca olan mağazaları içerebilir.

Değişken Mahalle Arama (VNS): Bu, farklı mahalle yapıları arasında geçiş yapan bir arama stratejisi türüdür. Bu, süpermarkete giderken farklı yolları denemek gibi düşünülebilir. Belki bir yol daha hızlıdır, ama diğer yolda daha fazla çikolata mağazası vardır.

Yerel Arama: VNS, çözüm alanında gezinmek için yerel arama stratejileri kullanır. Yerel arama, çözümünüzün etrafındaki çözümleri arar ve en iyisini seçer. Bu, en iyi çikolata mağazasını bulmak için bölgenizdeki tüm mağazaları denemeye benzer.

Sarsma: VNS, bir çözümü "sallar" ve yeni bir çözüm bulmak için farklı bir alana atlar. Bu, bir otobüs alıp başka bir şehirdeki çikolata mağazalarını denemek gibidir.

Bu terimlerin hepsi, çözümünüzü geliştirmek için nasıl araştırma yapacağınıza dair stratejilerle ilgilidir. VNS, farklı "mahallelerde" dolaşarak ve çözümünüzü "sallayarak" daha iyi bir çözüm bulmanıza yardımcı olur.

Başka Şekilde örneklendirirsek;

Mahalle Yapıları: Mahalle yapıları, çözümünüzün etrafındaki çözümlerin bir dökümüdür. Mahalle yapısı, neyin "yakın" olduğunu belirler ve bir çözüm seti sunar. Örneğin, eğer bir yemek tarifi üzerinde çalışıyorsanız, bir mahalle yapısı belki bir malzemeyi değiştirme, bir diğeri belki de pişirme süresini ayarlama olabilir.

Değişken Mahalle Arama (VNS): Farklı mahalle yapıları arasında geçiş yaparak çeşitliliği arttırmayı amaçlar. Diyelim ki, bir yemek tarifindeki malzemeyi değiştirdiğinizde tatmin edici bir sonuç elde edemiyorsunuz, o zaman belki pişirme süresini ayarlamak daha iyi bir sonuç verir. VNS, çeşitli mahalle yapıları arasında böyle bir geçiş sağlar.

Yerel Arama: VNS yerel arama stratejilerini kullanır. Yerel arama, çözümünüzün etrafındaki çözümleri arar ve en iyisini seçer. Bu, yemek tarifinizi geliştirmek için farklı malzemeler denemek veya pişirme süresini ayarlamak gibidir.

Sarsma: VNS, yeni bir çözüm bulmak için mevcut çözümü "sarsar". Bu, tarifinizi tamamen değiştirip yeni bir tarif denemeye benzer. Belki tamamen farklı bir tarif, beklediğiniz lezzeti daha iyi yakalar.

Bu terimlerin hepsi, bir çözümü nasıl iyileştirebileceğinize dair stratejilerle ilgilidir. VNS, farklı mahallelerde (stratejilerle) dolaşmayı, çözümünüzü "sarsmayı" (tamamen farklı bir yöntem denemeyi) ve en iyi çözümü bulmak için yerel arama (mevcut çözümünüzün etrafında dolaşmayı) içerir. Bu, bir problemi çözme veya bir hedefe ulaşma sürecinde karşılaşılan zorlukları aşmanın bir yolu olabilir.