مجموعه آموزشی پی استور - https://programstore.ir

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

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

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

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

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

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

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

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

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

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

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

لیست ممنوعه

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

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

لیست تنفس

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

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

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

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

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

عملکرد الگوریتم ممنوعه 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

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

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

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

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

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

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

پاورپوینت الگوریتم جستجوی ممنوعه TS در 18 صفحه در قالب ppt. یا pptx. با قابلیت ویرایش و توضیحات اضافی برای برخی صفحات در قالب Note آماده دانلود می باشد.

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

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

مثال برای الگوریتم TS

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

مثال برای الگوریتم TS

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

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

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

مثال الگوریتم TS

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

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

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

مثال برای الگوریتم TS

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

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

مثال الگوریتم TS

الگوریتم جستجوی ممنوعه TS برای حل مسئله فروشنده دوره گرد TSP در متلب [5]

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

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

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

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

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

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

2- روش تقویت

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

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

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

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

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

حل مسئله 8 وزیر با الگوریتم جستجوی ممنوعه TS در متلب [6]

حل مسئله 8 وزیر با الگوریتم جستجوی ممنوعه TS در متلب

سورس کد حل مسئله 8 وزیر با الگوریتم جستجوی ممنوعه TS در متلب عنوان محصولی است که در این بخش قرار داده شده است. در این سورس کد دو نمونه از حل مسئله، 8 وزیر هوش مصنوعی و n وزیر با الگوریتم TS در متلب ارائه شده است.

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

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