آموزش الگوریتم جستجوی ممنوعه TS به همراه مثال

مقدمه و تاریخچه الگوریتم جستجوی ممنوعه TS

الگوریتم جستجوی تابو (Tabu) یا ممنوعه یک استراتژی جستجوی حافظه می‌باشد که توسط آقای گلور (Glover) در سال ۱۹۸۶ پیشنهاد شد. در دهه ۱۹۹۰ این الگوریتم محبوبیت بالایی در حل مسائل بهینه‌سازی داشت.

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

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

برای این روش از لیستی به نام لیست ممنوعه یا لیست تابو استفاده می‌کند که هر انتخابی که الآن انجام داد در آن لیست قرار می‌گیرد و برای دفعه بعد قابل انتخاب نخواهد بود که در ادامه بیشتر در مورد روند کار الگوریتم توضیح خواهیم داد.

یک مفهوم اساسی در TS این است که جستجوی هوشمند باید مبتنی بر یادگیری باشد. استفاده از حافظه انعطاف‌پذیر فراتر از بهینه بودن را بررسی می‌کند و از حالت اولیه جستجو برای تأثیرگذاری بر وضعیت‌های آینده آن استفاده می‌کند.

مفاهیم اصلی در الگوریتم جستجوی ممنوعه TS

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

لیست ممنوعه

لیست ممنوعه (Tabu list) یا لیست تابو جابه‌جایی های اخیر را نگهداری می‌کند و وظیفه آن این است که از همگرایی به سمت جواب‌های بهینه محلی جلوگیری کند. درواقع طوری می‌شود که جواب‌هایی که اخیراً جستجو شده‌اند در این لیست قرار می‌گیرند و ممنوع می‌شوند.

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

پاورپوینت الگوریتم جستجوی ممنوعه TS

کلیک کنید

لیست تنفس

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

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

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

حل مسئله کوله پشتی با الگوریتم جستجوی ممنوعه TS در متلب

کلیک کنید

عملکرد الگوریتم ممنوعه TS

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

دلیل این انتخاب می‌تواند این باشد که شاید دیگر لازم نشود محاسبات را از اول انجام دهیم. برای این انتخاب از تابع سازگاری استفاده می‌شود. حالا اگر زمان پردازش مسئله باشد، همسایه‌ای که با انتخاب آن زمان پردازش بهتر می‌شود انتخاب خواهد شد یا اگر مسافت مدنظر باشد، همسایه‌ای انتخاب می‌شود که در کل روی مسیر تأثیر مثبت در جهت کوتاه کردن مسافت بگذارد.

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

لیست ممنوعه از گیرکردن در بهینه محلی جلوگیری می‌کند. حالا بعدازاینکه تعدادی از حرکات در لیست ممنوعه قرار گرفتند تعدادی از آن‌ها از لیست خارج می‌شوند. تعداد زمانی که جواب‌ها یا حرکات در لیست ممنوعه قرار می‌گیرند بر اساس پارامتری به نام tabu tenure مشخص می‌شود. حرکت از جواب کنونی به همسایه تا جایی ادامه پیدا می‌کند که شرایط خاتمه الگوریتم برقرار شود. حالا این شرط می‌تواند تعداد حرکت به جواب همسایه در نظر گرفته شود یعنی بعد از تعداد مشخصی دیگر حرکت به سمت همسایه انجام نشود و الگوریتم پایان یابد.

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

Set x=x0;
Set length (L) =z;
Set L={};
Repeat
    Generate a random neighbor x’;
     If x’ ∉  L then 
         If length (L) > z then
             Remove oldest solution from L;
             Set x’∈ L;
         End if
    End if

    If x’< x then
        x=x’;
    end if
until (stopping criteria satisfies)
return x;

فلوچارت الگوریتم جستجوی ممنوعه TS

مثالی از عملکرد الگوریتم جستجوی ممنوعه TS

خوب در این قسمت اجازه بدید با یک مثال الگوریتم جستجوی ممنوعه TS را بیشتر توضیح دهیم. فرض کنید با مسئله فروشنده دوره گرد مواجه هستیم. ۶ تا شهر داریم به نام‌های A، B،C،D،E،F که قرار است از این شهرها به ترتیب عبور کنیم و از اولین انتخاب به سمت آخرین شهر برویم و از همه شهرها عبور کنیم. هدف این است که در کوتاه‌ترین زمان ممکن این مسیر را طی کنیم و مهم هم نیست که از کدام شهر اول عبور کنیم یا کدام شهر دومین انتخاب ما باشد و به همین ترتیب تا آخر ادامه دارد.

به‌عنوان نمونه فرض کنید که اگر شهر D قبل از شهر C ملاقات شود در طول مسیر ۱ ساعت تفاوت خواهد کرد پس مسیر دوم بهینه‌تر خواهد بود. حالا در شکل‌های زیر به نوع انتخاب و زمان‌بندی و لیست ممنوعه و تنفس توجه کنید.

در شکل ۱ نمونه اولیه از ترتیب شهرها را داریم و فرض می‌کنیم که در شکل ۱ مدت‌زمان طی شده بین شهرها برابر ۹ ساعت است اگر حرکت را از سمت چپ به سمت راست به ترتیب ادامه دهیم. حالا باید یک جواب همسایه انتخاب کنیم و همان‌طور که قبلاً توضیح دادیم وضعیت همسایه انتخابی طوری است که به وضعیت فعلی بسیار نزدیک می‌باشد. در ادامه پاورپوینت الگوریتم جستجوی ممنوعه TS در ۱۸ صفحه در قالب ppt. یا pptx. با قابلیت ویرایش و توضیحات اضافی برای برخی صفحات در قالب Note آماده دانلود می باشد.

اگر طبق شکل ۲ برای پیدا کردن جواب همسایه جاهای دو شهر F و C را عوض کنیم. البته اگر تمام شهرها را دو به دو عوض کنیم چندین حالت مختلف خواهیم داشت ما در مثال ۳ حالت برتر را در نظر می‌گیریم. حالت‌هایی که C و F را جابه‌جا کنیم ۲ ساعت از زمان طی شده کم می‌شود یا حالتی که D و F را جابه‌جا کنیم، ۱ ساعت از زمان طی شده کاسته می‌شود و حالتی که A و C را جابه‌جا کنیم، ۲ ساعت به زمان طی شده اضافه می‌شود به همین ترتیب زمان‌ها محاسبه می‌شوند.

با این کار همان تابع سازگاری یا فیتنس را محاسبه می‌کنیم که در اینجا مدت‌زمان طی شده است. پس بین این حالات جابه‌جایی C و F بهینه‌ترین است. که بعد از جابه‌جایی زمان طی شده ۷ ساعت خواهد بود.

همان‌طور که در شکل ۳ مشاهده می‌کنید F و C را جابه‌جا کردیم. گفتیم در الگوریتم جستجوی ممنوعه لیستی به نام تابو داریم که حرکات انجام‌شده قبلی را در آن ذخیره می‌کنیم تا به تعداد مشخصی چرخه، از آن استفاده نشود. پس جابه‌جایی F و C در لیست ممنوعه (در سمت راست آن) در خانه سوم ذخیره شد یعنی تا ۳ چرخه اجازه استفاده از آن را نداریم البته مگر اینکه مثل مثال بالا در مورد مشتری به‌خصوص فکر کنیم که استفاده از آن موجب اتفاق چشم‌گیری خواهد شد.

تا اینجای کار یک دور مراحل را انجام دادیم و به زمان ۷ ساعت رسیدیم. حالا در دور دوم هستیم مثل دور اول باز جابه‌جایی‌ها را برای همسایه‌ها باید انجام دهیم تا به بهترین جابه‌جایی برسیم. شکل ۴ را مشاهده می‌کنیم.

همان‌طور که در شکل ۴ مشاهده می‌کنید با این جابه‌جایی ها درواقع بهبودی حاصل نمی‌شود. بااین‌حال جابه‌جایی B و E را انتخاب می‌کنیم به امید اینکه این انتخاب در آینده منجر به انتخاب‌های بهتر شود یعنی یک انتخاب کمی بد را انجام می‌دهیم تا نتایج بهتری را بگیریم. جابه‌جایی B و E نیز وارد لیست ممنوعه می‌شود و همان‌طور که در شکل ۵ می‌بینیم، زمان طی شده به ۸ ساعت تغییر می‌کند.

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

خوب طبق شکل ۶ مشاهده می‌کنیم که با تغییر C و F نتیجه یک واحد بهتر می‌شود ولی این جابه‌جایی در لیست ممنوعه قرار دارد و این دور و دور بعد نمی‌توانیم از آن استفاده کنیم. پس به‌جای آن جابه‌جایی D و A را انجام می‌دهیم. چراکه تنها بهترین حالت ممکن است. حالا این جابه‌جایی را هم به لیست ممنوعه اضافه می‌کنیم و لیست را بروز می‌نماییم. با این جابه‌جایی تغییری در زمان اجرا رخ نمی‌دهد. حالا طبق شکل ۷ یک بار دیگر جابه‌جایی را انجام می‌دهیم.

همان‌طور که در شکل ۷ مشاهده می‌کنید حالت جابه‌جایی C و F باوجود اینکه در لیست ممنوعه قرار دارد ولی با کاستن ۴ ساعت از زمان طی شده تا اینجا بهترین عملکرد را با اختلاف نشان می‌دهد و بعدازآن انتخاب B و E است که آن‌هم در لیست ممنوعه قرار دارد ولی خوب جابه‌جایی C و F یک بهبودی است که واقعاً خوب عمل می‌کند اینجا است که شرایط تنفس مطرح می‌شود.

این را می‌توان در اول الگوریتم به‌صورت شرطی بیان کرد که اگر حالتی موجب بهبودی بیشتر از ۲ واحد شد قانون لیست ممنوعه را در نظر نگیرد. حالا با انجام این جابه‌جایی زمان ما به ۴ ساعت کاهش یافت. تا اینجای کار ۴ دور را انجام دادیم حالا می‌توان تعداد دورهای بیشتری را به امید اینکه نتیجه بهتری را پیدا کنیم ادامه دهیم ولی ما فرض می‌کنیم تا همین‌جا کافی است و جواب بهینه را یافتیم.

در سورس کد حل مسئله فروشنده دوره گرد با الگوریتم TS، مسئله TSP را با استفاده از الگوریتم جستجوی ممنوعه حل می کنیم. به جرأت می توان گفت الگوریتم جستجوی ممنوعه بهترین الگوریتم در بین الگوریتم های فرا ابتکاری است که می شود برای حل مسئله فروشنده دوره گرد از آن استفاده کرد.

روش های پیشرفته الگوریتم جستجوی ممنوعه TS

ممکن است ساختار این الگوریتم در مسائل بزرگ جوابگو نباشد. به همین منظور برای بالا بردن قدرت این الگوریتم از یک سری روش‌ها که معروف به روش‌های پیشرفته TS هستند استفاده می‌شود در ادامه این روش‌ها را نام‌برده و در مورد هرکدام توضیح مختصری بیان می‌کنیم.

۱- فهرست کاندید

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

۲- روش تقویت

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

۳- روش تنوع دادن

در جستجوهای محلی از آنجایی ممکن است جستجو در منطقه محدودی انجام گیرد بنابراین ممکن است از یافتن جواب‌های بهتر در مناطق دیگر بازبماند که در این روش تلاش می‌شود جستجو به مناطقی که تاکنون کشف نکرده هم سر بزند.

۴- دادن مجوز به جواب های غیر شدنی

بعضی مواقع محدودیت‌های مسئله به‌قدری است که الگوریتم از جستجوی مؤثر بازمی‌ماند در این مواقع مقداری محدودیت‌های مسئله در نظر گرفته نمی‌شوند و به‌جای آن جریمه‌ای برای تابع هدف در نظر گرفته می‌شود.

سخن آخر در مورد الگوریتم جستجوی ممنوعه TS

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