جستجوی متغیر همسایگی (Variable Neighborhood Search - VNS)، در ریاضیات (Mathematics)

انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :

جستجوی متغیر همسایگی (Variable Neighborhood Search - VNS) :

📌 معرفی

جستجوی متغیر همسایگی (Variable Neighborhood Search - VNS) توسط ملادنوویچ و هانسن (Mladenović & Hansen) در سال ۱۹۹۷ معرفی شد. ایده اصلی VNS این است که با تغییر سیستماتیک ساختارهای همسایگی (Neighborhoods) در طول جستجو، از بهینه های محلی فرار کند و جواب های بهتری بیابد.

🔄 اصول VNS

یک بهینه محلی برای یک ساختار همسایگی، لزوما برای ساختار دیگر بهینه محلی نیست.

با تغییر همسایگی ها، می توان از بهینه های محلی خارج شد.

بهینه سراسری در همه ساختارهای همسایگی بهینه محلی است.

📐 مراحل اصلی VNS

انتخاب مجموعه ای از ساختارهای همسایگی

\[ N_k \]

برای

\[ k = 1,...,k_{max} \]

.

یافتن یک جواب اولیه

\[ x \]

.

تا شرط توقف:

\[ k = 1 \]

را تنظیم کن.

تا

\[ k \leq k_{max} \]

:

تکان (Shaking): یک جواب

\[ x' \]

به طور تصادفی از همسایگی

\[ N_k(x) \]

انتخاب کن.

جستجوی محلی: یک جستجوی محلی روی

\[ x' \]

انجام بده تا به

\[ x'' \]

برسیم.

حرکت یا نه (Move or not): اگر

\[ x'' \]

بهتر از

\[ x \]

بود،

\[ x = x'' \]

قرار بده و

\[ k=1 \]

تنظیم کن. در غیر این صورت،

\[ k = k+1 \]

.