آموزش الگوریتم جستجوی متغیر محلی VNS

مقدمه آموزش الگوریتم جستجوی متغیر محلی VNS

تاکنون پیشرفت‌های زیادی در طراحی و کاربرد الگوریتم‌های اکتشافی در مورد مسائل بهینه‌سازی انجام شده است. الگوریتم‌های ابتکاری عمومی (یا فرا ابتکاری، به عنوان مثال، باز پخت شبیه‌سازی شده، جستجوی تابو، جستجوی ژنتیکی) که از گیر افتادن در اولین بهینه محلی یافت شده اجتناب می‌کنند، منجر به نتایج بسیار بهبود‌یافته در بسیاری از زمینه‌های عملی شده‌اند.

روش‌های جستجوی محلی برای بهینه‌سازی ترکیبی با انجام دنباله‌ای از تغییرات محلی که در یک راه‌حل اولیه اتفاق می‌افتد و هر بار مقدار تابع هدف را بهبود می‌بخشد، انجام می‌گیرد. این کار تا زمانی که یک بهینه محلی پیدا شود، ادامه می‌یابد. یعنی در هر تکرار یک راه‌حل بهبود‌یافته ‘x در همسایگی راه‌حل فعلی x به دست می‌آید، تا زمانی که هیچ پیشرفت دیگری در جهت بهبود یافت نشود.

پاورپوینت الگوریتم های ژنتیک

کلیک کنید

به این ترتیب اغلب ویژگی‌های مطلوب راه‌حل فعلی، (به عنوان مثال، اکثر متغیرها در‌حال حاضر در مقدار بهینه خود هستند) نگه داشته می‌شوند و برای به دست آوردن راه‌حل‌های همسایه امیدوار‌کننده استفاده می‌شوند. علاوه بر این، یک روال جستجوی محلی به‌طور مکرر برای رسیدن از این راه‌حل‌های همسایه به بهینه محلی اعمال می‌شود.

هدف این است که نشان دهیم یک روش فرا ابتکاری ساده و موثر ممکن است با تغییر سیستماتیک همسایگی در یک الگوریتم جستجوی محلی به دست آید. این رویکرد را جستجوی متغیر محلی VNS می نامیم. این الگوریتم توسط آقایان Mladenović و Hansen در سال ۱۹۹۷ در مقاله Variable Neighborhood Search پیشنهاد شده است.

الگوریتم جستجوی متغیر محلی VNS

در توضیح این الگوریتم در مرحله اول اجازه دهید یک مجموعه متناهی از همسایگان را از قبل انتخاب کنیم که با N_K مشخص می‌کنیم و (k=1 ,… , k_max) و N_k(x) را مجموعه‌ای از راه‌حل‌ها در kامین همسایگی x در‌نظر بگیریم.

الگوریتم ابتکاری جستجوی متغیر محلی VNS معمولاً از یک ساختار همسایه استفاده می‌کند. برای مثال k_max = 1. ولی اگر از بیش از یک ساختار استفاده کند باید به سوالات زیر پاسخ دهد.

• کدام N_k و به چه تعدادی از آن باید استفاده شود؟
•  ترتیب این N_k‌ها در جستجو به چه شکلی باید باشد؟
• چه استراتژی جستجویی در تغییر همسایه باید استفاده شود؟

پاسخ ساده و صریح به این سؤالات از طریق قوانین الگوریتم اصلی الگوریتم VNS که در ادامه آورده شده است ارائه می‌شود.

الگوریتم جستجوی متغیر محلی VNS به طور سیستماتیک بیان‌گر مشاهدات زیر است:

• حداقل محلی مربوط به یک ساختار همسایه لزومی ندارد برای بقیه هم حداقل محسوب شود.
• یک حداقل سراسری با توجه به تمام ساختارهای همسایه ممکن، یک حداقل محلی محسوب می‌شود.
• در مورد بسیاری از مسائل، حداقل‌های محلی با توجه به یک یا چند همسایه نسبتاً به یکدیگر نزدیک هستند.

طبق آخرین مشاهده تجربی، مشخص می‌شود که یک بهینه محلی اغلب اطلاعاتی در مورد بهینه سراسری ارائه می‌دهد. برای مثال ممکن است چندین متغیر با مقدار یکسان در هر دو مورد قرار گرفته باشند. با این حال، معمولاً مشخص نیست که کدام یک از آن‌ها این شرایط را دارد. بنابراین، تا زمانی که مورد بهتری پیدا شود، باید مطالعه سازماندهی شده در حیطه همسایگی این بهینه محلی انجام گیرد.

• پاورپوینت الگوریتم های فراابتکاری — کلیک کنید

بر‌خلاف بسیاری از الگوریتم‌های فرا ابتکاری، طرح‌های اساسی VNS و مولفه‌های آن ساده هستند و به پارامترهای کمی نیاز دارند و حتی گاهی اوقات هیچ پارامتری ندارند. بنابراین علاوه بر ارائه راه‌حل‌های بسیار خوب، که اغلب نسبت به روش‌های دیگر ساده‌تر هستند، الگوریتم جستجوی متغیر محلی VNS بینشی در مورد دلایل چنین عملکردی ارائه می‌دهد که به نوبه خود می‌تواند منجر به پیاده‌سازی کارآمدتر و پیچیده‌تری شود.

شبه کد الگوریتم جستجوی متغیر محلی VNS

در الگوریتم جستجوی متغیر محلی VNS برای شروع کار مجموعه‌ای از همسایه‌ها انتخاب می‌شوند، همان‌طور که قبلا نیز اشاره شد این مجموعه را با N_K مشخص می‌کنیم و (k=1 ,… , k_max)، که در جستجو از آن استفاده خواهد شد. در گام بعدی راه حل اول x پیدا می‌شود تا وقتی که k=k_max نشده، نقطه ‘x را بصورت تصادفی از kامین همسایه x تولید می‌کند.

جستجوی محلی را روی ‘x به عنوان راه‌حل اولیه اعمال می‌کند. بهینه محلی بدست آمده را برابر “x قرار می‌دهد. اگر راه‌حل بدست آمده از راه‌حل قبلی بهتر باشد در اینصورت “x=x قرار داده و جستجو را با N_۱(k=1) ادامه می‌دهد، در غیر اینصورت k=k+1 شده و عملیات تکرار می‌شود.

Select the set of neighborhood structures Nk, k= 1 ..... kmax
initial solution x
set k:=1
repeat
generate x' ( x یک نقطه در همسایگی ) 
apply some local search method with x' as initial solution
denote x" as obtained local optimum
if x" is better than x then
x:=x"
else
k:=k+1
until k = kmax

مرحله اصلی می‌تواند تا زمانی که شرایط توقف دیگری برآورده شود (مثلاً حداکثر تعداد تکرار، حداکثر زمان مجاز CPU یا حداکثر تعداد تکرار بین دو مورد بهبودی) تکرار شود. اغلب همسایه‌های موفق در الگوریتم جستجو N_k تودر‌تو خواهند بود. توجه داشته باشید که به منظور جلوگیری از گیر‌افتادن در چرخه (که ممکن است در صورت استفاده از هر قانون قطعی رخ دهد)، ‘x در مرحله دوم بصورت تصادفی تولید می‌شود. در ادامه بحث به مولفه‌های این الگوریتم می‌پردازیم.

مولفه‌های الگوریتم جستجوی متغیر محلی VNS

• Variable Neighborhood Descent (VND)
• Reduced VNS (RVNS)
• skewed VNS (SVNS)
• (VNDS) Variable Neighborhood Decomposition Search

متغیر محلی نزولی (VND)

متغیر محلی نزولی VND (که به عنوان بهترین جستجوی محلی بهبود نیز شناخته می شود) در صورتی بدست می‌آید که تغییر محله‌ها به روش قطعی انجام شود. در توضیح الگوریتم آن فرض می‌کنیم که یک راه‌حل اولیه x داده شده است. اکثر روش‌های اکتشافی‌ جستجوی محلی در مرحله نزول خود از تعداد همسایه‌های بسیار کمی استفاده می‌کنند. راه‌حل نهایی باید یک حداقل محلی با در نظر گرفتن تمامی همسایه‌های  k_max باشد. بنابراین شانس دستیابی به یک حداقل جهانی با استفاده از VND بیشتر از یک ساختار تک همسایگی است.

این روش به عنوان مؤلفه‌ای از الگوریتم جستجوی متغیر محلی VNS شامل انتخاب یک راه حل اولیه x، یافتن جهتی که بیشترین شیب نزول از x را در همسایگی N(x) دارد و حرکت به سمت حداقل f(x) در N(x) در امتداد آن جهت، بوده و اگر هیچ جهت نزولی وجود نداشته باشد، اکتشاف متوقف می شود و در غیر این صورت این مراحل تکرار می شود. این قوانین بصورت زیر خلاصه شده است.

Initialization.
Choose f, X, neighborhood structure N(x), initial solution x;
Current step (Repeat).
(۱) Find x' = argmin x∈N(x) f(x);
(۲) If f(x') < f(x) set x' ← x" and iterate; otherwise, stop.

مشاهده می‌کنید که یک ساختار همسایگی N(x) برای تمامی x ∈ X تعریف شده است. مسائل بهینه‌سازی گسسته معمولاً از بردارهایی تشکیل می‌شوند که با برخی اصلاحات ساده از x بدست می‌آیند. (برای مثال تکمیل یک یا دو جزء از یک بردار ۰-۱). سپس در هر مرحله، همسایگی x به طور کامل بررسی می‌شود که این کار می‌تواند زمان‌بر باشد. در اینصورت استفاده از اکتشاف نزول اول (first descent heuristic) می‌تواند یک جایگزین برای آن باشد. سپس بردارهای x’ ∈ N(x) به طور سیستماتیک شمارش می‌شوند و به محض یافتن جهت نزول، حرکت انجام می‌شود. خلاصه این موارد را در ادامه مشاهده می‌کنید.

Initialization.
Choose f, X, neighborhood structure N(x), initial solution x;
Current step (Repeat).
(۱) Find first solution x' is a member of N(x);
(۲) If f(x') > f(x), find next solution x" is a member of N(x); set x' ← x" and iterate
(۲); otherwise, set x ← x' and iterate (1);
(۳) If all solutions of N(x) have been considered, stop

در VDN یک بهینه محلی برای یک نوع حرکت ‘x ← x ( در داخل محوطه همسایگی N1(x))  برای نوع دیگر حرکت ضروری نیست ”’x ← x (در داخل محوطه همسایگی N2(x)). بنابراین می‌توان از مزایای ترکیب روش‌های اکتشافی نزولی استفاده کرد که موجب ایجاد VDN پایه، همان‌طور که در ادامه نشان داده شده است، می‌شود.

Initialization. Select the set of neighborhood structures NL, for L= 1,...,Lmax,
that will be used in the descent; find an initial solution x (or apply the rules to
a given x);
Repeat the following sequence until no improvement is obtained:
(۱) Set L ← ۱;
(۲) Repeat the following steps until L = Lmax:
(a) Exploration of neighborhood. Find the best neighbor x' of x (x' is a member of NL(x));
(b) Move or not. If the solution x' thus obtained is better than x, set
x ← x' and L ← ۱; otherwise, set L ← L + 1;

البته توجه داشته باشید که یکسری موارد در اعمال این الگوریتم باید در نظر گرفته شوند.

جستجوی متغیر محلی VNS کاهش یافته (RVNS)

فرض کنید یک حداقل محلی x از f بدست آمده است. در این حالت ترجیح می‌دهیم که جستجو از این حداقل خارج شده و دره عمیق‌تر دیگری را بیابد. در نسخه‌های استاندارد جستجوی متغیر محلی VNS، هیچ دانش قبلی از چشم انداز فرض نمی‌شود یا مورد بهره‌برداری قرار نمی‌گیرد. بنابراین بهتر است موارد زیر مورد سوال قرار گیرد:

• به چه سمتی باید حرکت انجام شود؟
• چه مسافتی باید طی شود؟
• چگونه باید حرکت‌ها را در صورت عدم موفقیت تغییر داد؟

این اهداف در طرح متغیر محلی VNS کاهش یافته‌، که در ادامه ارائه شده، دنبال می شوند.

Initialization. Select the set of neighborhood structures Nk, for k = 1,...,kmax,
that will be used in the search; find an initial solution x; choose a stopping
condition;
Repeat the following sequence until the stopping condition is met:
(۱) Set k ← ۱;
(۲) Repeat the following steps until k = kmax:
(a) Shaking. Generate a point x' at random from the kth neighborhood
of x (x' is a member of Nk(x));
(b) Move or not. If this point is better than the incumbent, move
there (x ← x'), and continue the search with N1 (k ← ۱); otherwise, set
k ← k + 1;

جستجوی متغیر محلی VNS اریب (SVNS)

روش جستجوی متغیر محلی اریب به مسئله جستجوی دره‌ها یا حداقل‌های دور از راه‌حل فعلی می‌پردازد. در حقیقت به این شکل است که هنگامی که بهترین راه‌حل در یک منطقه بزرگ پیدا شد، لازم است که راهی برای پیدا کردن راه‌حل بهتر یا بهبودیافته‌تر طی شود.

راه‌حل‌هایی که به‌طور تصادفی در همسایگی‌های دور پیدا می‌شوند، ممکن است به‌طور قابل‌توجهی با راه‌حل فعلی متفاوت باشند و VNS می‌تواند تا حدی به روش اکتشاف MultiStart نزدیک شود (که در آن پایین رفت‌ها یا نزول‌ها به طور تکراری از راه‌حل‌های تولید شده تولید می‌شوند، که البته روش خیلی کارآمدی نیست.)در نتیجه، مقداری جبران فاصله از راه حل قبلی باید انجام شود.

ولی با این حال VNS معمولاً راه‌حل‌های بهتر یا خوب را نسبت به MultiStart ارائه می‌دهد و به خصوص زمانی که بهینه‌های محلی زیادی وجود دارد، راه‌حل‌های بسیار بهتری ارائه می‌دهد.

با این حال ممکن است برخی از نمونه‌ها چندین دره جدا از هم و احتمالاً دور از هم داشته باشند که حاوی راه‌حل‌های تقریباً بهینه هستند. اگر همسایگی‌های بزرگ‌تری را در نظر بگیریم، اطلاعات مربوط به بهترین بهینه محلی فعلی از بین می رود و VNS به MultiStart تبدیل می شود. بنابراین، اصلاح VNS به منظور کاوش کاملتر دره‌هایی که از راه‌حل فعلی دور هستند، بسیار جالب است.

زمانی که راه حلی البته نه لزوما راه‌حل خوب نزدیک به بهترین راه حلی تا به حال شناخته شده یافت می شود، به شرطی که این راه‌حل جدید از آخرین راه‌حل یافت شده فاصله داشته باشد، اصلاح بر روی جستجوی متغیر محلی VNS با پذیرش مجدد جستجو انجام می‌شود. طرح VNS اصلاح شده برای این نوع، به نام Skewed Variable Neighborhood Search نامیده می‌شود.

Initialization. Select the set of neighborhood structures Nk, for k = 1,...,kmax, that will
be used in the search; find an initial solution x and its value f(x); set xopt ← x, fopt ← f(x):
choose a stopping condition and a parameter value α;
Repeat the following until the stopping condition is met:
(۱) Set k ← ۱;
(۲) Repeat the following steps until k = kmax:
(a)Shaking. Generate a point x at random from the kth neighborhood of x;
(b)Local search. Apply some local search method with x as initial solution; denote
with x the so obtained local optimum;
(c) Improvement or not. If f(x) < fopt set fopt ← f(x) and xopt ← x;
(d) Move or not. If f(x) − αρ(x, x) < f(x) set x ← x and k ← ۱; otherwise set
k ← k + 1.

جستجوی تجزیه متغیر محلی  (VNDS)

روش VNDS که در سال ۲۰۰۱ توسط هانسن پیشنهاد شد. VNS پایه را به یک طرح دو سطحی براساس تجزیه مسئله گسترش می‌دهد. برای سهولت ارائه، اما بدون از دست دادن کلیت، فرض می شود که راه‌حل x مجموعه ای از عناصر را نشان می دهد. برای فهم بهتر این روش به شبه کد زیر توجه کنید.

Initialization. Select the set of neighborhood structures Nk, for k = 1,...,kmax, that will
be used in the search; find an initial solution x; choose a stopping condition;
Repeat the following sequence until the stopping condition is met:
(۱) Set k ← ۱;
(۲) Repeat the following steps until k = kmax:
(a) Shaking. Generate a point x' at random from the kth neighborhood of x (x' is a member of Nk(x)); in other words, let y be a set of k solution attributes present in x' but not in x (y = x' \ x).
(b) Local search. Find a local optimum in the space of y either by inspection or by
some heuristic; denote the best solution found with y' and with x" the corresponding
solution in the whole space S (x" = (x' \ y) ∪ y'
);
(c) Move or not. If the solution thus obtained is better than the incumbent, move
there (x ← x"), and continue the search with N1 (k ← ۱); otherwise, set k ← k + 1;

توجه داشته باشید که تنها تفاوت بین VNS اولیه و VNDS در مرحله 2b است. به‌جای استفاده از روش جستجوی محلی در کل فضای راه‌حل S ( از x’ ∈ Nk(x) شروع می‌شود) در VNDS در هر تکرار یک مسئله فرعی را در فضای فرعی حل می‌کنیم که Vk ⊆ Nk(x) بوده و x’ ∈ Vk باشد. هنگامی که جستجوی محلی مورد استفاده در این مرحله نیز VNS باشد، طرح VNS دو سطحی ایجاد می‌شود.

سخن آخر در مورد الگوریتم جستجوی متغیر محلی VNS

در این مقاله در مورد الگوریتم جستجوی متغیر محلی VNS از جمله الگوریتم‌های فرا ابتکاری مورد بحث قرار گرفت. کلیاتی در مورد این الگوریتم و نحوه کار آن در پیدا کردن حداقل بهینه بیان شد. همچنین سعی کردیم دیگر مشتقات این الگوریتم را نیز در حد امکان همراه با شبه کدهایی در جهت فهم بهتر ارائه دهیم. در نهایت از اینکه تا انتهای مقاله ما را همراهی کردید سپاسگزاریم.