Değişken Komşuluk Araması (VNS)
Variable Neighborhood Search (VNS) · Ayrıca şöyle bilinir: VNS, Değişken Komşuluk Araması (VNS), variable neighbourhood search
Değişken Komşuluk Araması (VNS), 1997 yılında Mladenović ve Hansen tarafından tanıtılan bir meta-sezgisel optimizasyon çerçevesidir. Sistematik olarak önceden tanımlanmış bir komşuluk yapıları kümesi arasında geçiş yaparak yerel optimumlardan kaçar — önce mevcut çözümü (sallama) arama uzayının farklı bir bölgesine ulaşmak için bozarak, ardından o bölge içinde bir yerel arama uygulayarak ve son olarak yalnızca mevcut çözümü iyileştirirse yeni çözümü kabul ederek. Yöntem, birleştirilmiş problemler (rotalama, çizelgeleme, grafik problemleri) ve sürekli optimizasyon için yeterince esnektir, bu da onu operasyon araştırmalarında en yaygın kullanılan komşuluk tabanlı meta-sezgisellerden biri haline getirir.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
VNS, doğal olarak birden fazla komşuluk yapısının tanımlanabileceği her türlü optimizasyon problemi için uygundur — örneğin, bir rotalama probleminde farklı takas, ekleme veya yer değiştirme hamleleri veya bir çizelgeleme probleminde farklı değişim operatörleri. Hem birleştirilmiş hem de sürekli değişkenler üzerinde çalışır, normalite varsayımı gerektirmez ve algoritma istatistiksel örnekler yerine çözümler üzerinde çalıştığı için minimum veri kümesi boyutu dayatmaz. VNS, arama manzarasının engebeli olduğu ve tek bir yerel aramanın tutarlı bir şekilde iyi çözümler bulamadığı durumlarda özellikle etkilidir. Temel ön koşul, her biri yerel bir arama prosedürü tarafından keşfedilebilen en az iki farklı komşuluk yapısını tanımlama yeteneğidir.
Güçlü yönler & sınırlılıklar
- Birden fazla komşuluk yapısı kullanarak arama uzayını sistematik olarak kapsar, tek bir yerel optimumda tuzağa düşme riskini büyük ölçüde azaltır.
- Üretilebilirlik önemli olduğunda, deterministik Değişken Komşuluk İnişi (VND) varyantı mevcuttur.
- Çekirdek çerçevede herhangi bir değişiklik yapmadan hem birleştirilmiş (rotalama, çizelgeleme, grafik problemleri) hem de sürekli optimizasyona uygulanabilir.
- Normalite varsayımı ve minimum örneklem boyutu yok — yöntem, istatistiksel verilere değil, çözümlere dayanır.
- Modüler tasarım: komşuluk yapıları ve iç yerel arama bağımsız olarak değiştirilebilir, bu da algoritmanın yeni problem türlerine uyarlanmasını kolaylaştırır.
- Performans, seçilen komşuluk yapılarının kalitesine kritik derecede bağlıdır; kötü tasarlanmış komşuluklar yavaş veya etkisiz aramaya yol açar.
- Komşulukların sayısı ve sıralaması (k_max) uygulayıcı tarafından ayarlanmalıdır — evrensel bir kural yoktur ve kötü bir seçim çözüm kalitesini iyileştirmeden çalışma süresini artırır.
- Popülasyon tabanlı meta-sezgisellerin (genetik algoritmalar, parçacık sürüleri) aksine, VNS yalnızca tek bir mevcut çözümü korur, bu da yüksek derecede çok modlu manzaralarda çeşitliliği sınırlayabilir.
- Hesaplama maliyeti, iç yerel aramanın maliyetiyle doğru orantılıdır; pahalı değerlendirme fonksiyonları, her VNS yinelemesini yavaş hale getirebilir.
SSS
VNS, benzetilmiş tavlama veya tabu aramadan nasıl farklıdır?
Her üçü de yerel optimumlardan kaçan tek çözümlü meta-sezgisellerdir, ancak farklı mekanizmalar kullanırlar. Benzetilmiş tavlama, zamanla azalan bir olasılıkla daha kötü çözümleri kabul eder; tabu arama, bir bellek listesi kullanarak yakın zamanda ziyaret edilen hamleleri yasaklar. VNS kesinlikle iyileştirme tabanlıdır — asla daha kötü bir çözümü kabul etmez — ve bunun yerine farklı arama uzayı bölgelerini keşfetmek için artan büyüklükteki yapılandırılmış bir komşuluk ailesine güvenir. Bu, VNS'yi benzetilmiş tavlamadan daha deterministik ve ayarlanması daha kolay hale getirir.
Değişken Komşuluk İnişi (VND) nedir ve VNS ile nasıl ilişkilidir?
VND, VNS'nin deterministik iç arama bileşenidir. Bir dizi komşuluk yapısı arasında sıralı olarak döner: N_k komşuluğundaki bir hamle çözümü iyileştirirse, N_1'den yeniden başlar; aksi takdirde N_{k+1}'e geçer. VND kendi başına bir yerel arama prosedürüdür. VND, sallama-yerel arama-kabul döngüsü içinde yerel arama olarak kullanıldığında, birleşik algoritmaya Genel VNS (GVNS) denir. Saf deterministik bir iniş kabul edilebilir olduğunda VND ayrıca bağımsız olarak çalıştırılabilir.
Kaç komşuluk yapısına ihtiyacım var?
VNS'nin basit bir tekrarlanan yerel aramaya göre herhangi bir avantaj sunması için minimum iki farklı komşuluk yapısı gereklidir. Uygulamada, üç ila beş iyi seçilmiş komşuluk çoğu birleştirilmiş problemi etkili bir şekilde kapsar. Komşuluklar en küçükten (en az bozucu) en büyüğe doğru sıralanmalı ve her biri iç yerel arama tarafından verimli bir şekilde keşfedilebilmelidir. Kalite, miktardan çok daha önemlidir: iki iyi tasarlanmış komşuluk, on kötü tasarlanmış komşuluktan daha iyi performans gösterir.
VNS sürekli (gerçek değerli) optimizasyon problemlerini ele alabilir mi?
Evet. Sürekli problemler için komşuluklar tipik olarak ayrık hamle operatörleri yerine pertürbasyon yarıçapı veya adım boyutu ile tanımlanır. Çekirdek VNS döngüsü — sallama, yerel arama, daha iyiyse kabul — aynı şekilde çalışır. Sürekli VNS, parametre kalibrasyonu, regresyon ve mühendislik tasarımı problemlerine uygulanmıştır.
Kaynaklar
- Mladenović, N. & Hansen, P. (1997). Variable Neighborhood Search. Computers & Operations Research, 24(11), 1097–1100. DOI: 10.1016/S0305-0548(97)00031-2 ↗
- Hansen, P., Mladenović, N., Brimberg, J. & Pérez, J.A.M. (2019). Variable Neighborhood Search: Basics and Variants. EURO Journal on Computational Optimization, 7(1), 3–56. DOI: 10.1007/978-3-319-91086-4_3 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 1). Variable Neighborhood Search (VNS). ScholarGate. https://scholargate.app/tr/optimization/variable-neighborhood-search
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Genetik AlgoritmaOptimizasyon↔ karşılaştır
- Harmony SearchOptimizasyon↔ karşılaştır
- Simulated AnnealingOptimizasyon↔ karşılaştır
- Tabu SearchOptimizasyon↔ karşılaştır