الگوریتم مورچگان و رقابت‌پذیری


Widget not in any sidebars

شکل ‏42: شبه کد الگوریتم شبیه‌سازی تبرید
الگوریتم مورچگان اصلاح شده
در الگوریتم مورچگان اولیه ارائه شده، در هر تکرار به تعداد مورچه‌ها، جواب بر اساس قاعده تغییر حالت ایجاد می‌شود. سپس برای هر جواب قاعده‌ی به‌هنگام کردن محلی انجام می‌شود و بهترین جواب‌ به عنوان جواب برگزیده انتخاب شده و جواب‌هایی در همسایگی آنها تولید می‌گردد. در صورتی که کیفیت جواب همسایه ایجاد شده در اطراف جواب برگزیده بهتر از جواب برگزیده باشد، آن جواب جایگزین جواب برگزیده می‌شود و به‌هنگام کردن نهایی انجام می‌شود.
الگوریتم اولیه ارائه شده به خصوص در زمان استفاده از الگوریتم شبیه‌سازی تبرید به عنوان الگوریتم جستجوی محلی، دارای رقابت‌پذیری و کارایی کافی برای مسائل کوچک و متوسط بوده‌است. ولی در مسائل بزرگ از کارایی این الگوریتم کاسته می‌شد. به‌همین دلیل اصلاحاتی در الگوریتم ارائه‌شده داده شد که باعث افزایش کارایی و کیفیت جواب‌های این الگوریتم در مسائل بزرگ شد. بر خلاف الگوریتم اولیه ارائه شده، در الگوریتم اصلاح شده، تولید همسایگی بر روی تمامی جواب‌های تولید شده توسط مورچه‌ها انجام می‌گیرد. میزان تولید همسایگی برای همه جواب‌ها یکسان نمی‌باشد. بعد از تولید جواب توسط مورچه‌ها، جوابها با یکدیگر مقایسه شده و بر اساس کیفیت و میزان تابع هدف مرتب می‌شوند. برای هر جواب بر اساس رتبه آن، میزان همسایگی مشخص می‌گردد که از رابطه 4-7 بدست می‌آید:
4-7
در رابطه بالا، رتبه مورچه ام می‌باشد. میزان تولید همسایگی در اطراف جواب مورچه ام و پارامتر مسئله می‌باشد.
با توجه به رابطه بالا، همسایگی در اطراف جواب کل مورچه‌ها انجام می‌گیرد. تولید همسایگی در اطراف بهترین جواب بیشترین مقدار می‌باشد. در این الگوریتم، در اطراف بدترین جواب‌ها نیز همسایگی تولید می‌شود که باعث افزایش تنوع جواب‌ها و بررسی گسترده‌تری از فضای جستجو می‌شود. در این الگوریتم برای تولید همسایگی از الگوریتم جستجوی محلی همانند الگوریتم اولیه استفاده شده است.
شبه کد الگوریتم جستجوی محلی در الگوریتم اصلاح شده
شبه کد الگوریتم جستجوی محلی در الگوریتم اصلاح شده به صورت زیر می‌باشد.
Step 1
Initialization
Step 1.2
Use ant solution, Sk, and set Sk* =Sk.
Step 1.3
Set counter=0, temp=0.
Step 2
While,(U Step 2.1
If that v is a random number between 0 and 1, do the following:
Step 2.1.1
Do insert neighborhood. Select a neighbor Snewk of Sk.
Step 2.1.2
Compute ∆=Obj (Snewk) – Obj (Sk). If ∆≤0, set Sk =Snewk; tmp=tmp+1.
Step 2.1.3
Compute ∆=Obj (Snewk) – Obj (Sk*); If ∆≤0; set Sk* =Snewk

Share this post

Post navigation

You might be interested in...