بخشی از پاورپوینت
اسلاید 1 :
جستجوی ممنوع
Tabu Search
اسلاید 2 :
مقدمه و تاریخچه
جستجوی موضعی (Local Search)
ترفند TS : لیست ممنوع
معیارهای آزادسازی از Tabu List
معیارهای توقف
الگوریتم اولیه
Intensification و Diversification در TS
مقایسه SA و TS
مساله k-Tree
نرم افزار طراحی شده
نتایج حاصل از حل
اسلاید 3 :
مقدمه و تاریخچه :
عبارت Tabu(Taboo) از یک زبان پولنیزیایی ریشه می گیرد که توسط مردم بومی جزیره tonga برای مشخص کردن چیزهایی بکار می رود که مقدس و غیرقابل لمس و یا (بخاطر خطر داشتن ) ممنوع شده هستند. ارتباط این کلمه با حافظه ی مردم آن منطقه از این جهت که تجربیات گذشته باعث شده است تا چنین تلقی امروزی در مورد یک مفهوم خاص بوجود آید، کلید اصلی ارتباط این کلمه با مفهوم ممنوعیت در Tabu Search است.
عناصر ممنوع در Tabu Search با ارجاع به حافظه مشخص می شوند.
چنانکه می دانید، الگوریتم های فرا ابتکاری بسیاری برای دستیابی به حـداقل یک جـواب خـوب ( نه لــزوما بهترین ) برای یک مسـالـه NP-Hard بوجود آمده است.
بسیاری از این روشها از یک مکانیزم Local Search بهره می گیرند.
اسلاید 4 :
LS را می توان یک روال جستجوی تکرارشونده دانست که از یک جواب شدنی شروع می کند و با انجام اصلاحات جزیی (همان Move)، آنرا تا رسیدن به یک بهینه ی موضعی ادامه می دهد. با در نظر داشتن این نکته که در حالت معمول این بهینه ی موضعی، چیزی بیش از یک جواب متوسط نیست.
در LS معمولا کیفیت جواب بدست آمده به حد زیادی بستگی به غنای move های تعریف شده مان دارد. و این مساله اساسی در رویکرد های مبتنی بر LS است.
Tabu Search در سال 1986توسط Fred Glover برای غلبه بر این مشکل ارایه شد. اصل اولیه در TS ، مجاز دانستن move هایی که بهبودی به همراه ندارند، برای ادامه دادن جستجو در LS است، وقتی که به یک بهینه موضعی برمی خوریم.
البته در این روش برای اجتناب از دور زدن و رسیدن به جوابهایی که پیش از این بدست آمده، از حافظه ای بنام Tabu List استفاده می کنیم.
این حافظه جوابهای اخیر و یا move های اخیر را در خود ضبط می کند. در واقع یک TS ساده را می توان ترکیبی از یک حافظه کوتاه مدت با LS دانست.
اسلاید 5 :
همسایگی :
از اولین مفاهیمی که در TS می باید بدان پرداخت، مفهوم همسایگی است.
در هر تکرار، انتقالی (move) که بر روی جواب S اعمال می شود، مجموعه ای از جوابها را در فضای جستجو تعریف می کند که جوابهای همسایه گفته می شوند (N(S))
پس همسایگی، زیرمجموعه ای از فضای جواب است که به شکل زیر تعریف می شود :
N(S) : مجموعه ی جوابهایی که با استفاده از یک انتقال، از جواب S بدست می آیند.
چنانچه از تعریف بر می آید، ساختار همسایه، می تواند حتی شامل تمامی فضای جواب نیز باشد. برای یک مساله خاص، نوع انتقال یا move تعریف شده،
نقشی اساسی در وسعت همسایگی ی بوجود آمده دارد.
اسلاید 6 :
گفتیم که مفهوم اساسی در TS مجاز دانستن جوابهایی است که در تابع هدف بهبود ایجاد نمی کنند، اما ممکن است ما را به سمت جواب سراسری راهنمایی کنند، با این شــرط که در لیست جوابهای مـمنوع قرار نداشته باشند .
اما TS برای استفاده از چنین راه حلی، نیازمند آن است که از پدیده دور، که ناشی از بازگشت به جوابهای پیشین است، جلوگیری کند. این، وظیفه Tabu ها ست:
مجموعه ای از انتقال های ممنوع که به حافظه سپرده می شوند تا چنین بازگشتهایی رخ ندهد.
این انتقال های ممنوع، در حافظه ای کوتاه مدت (Short Term Memory) ذخیره می شوند تا (برای مدتی معین) انجام مجموعه ای معین از انتقال ها را ممنوع سازند. این مدت معین، یا اصطلاحا Tabu Tenure بنا بر الگوریتم حل و نوع مساله و ماهیت انتقال ها متغیر است.
حافظه مورد استفاده برای نگهداری Tabu ها معمولا گردشی و دارای طول ثابت است.
: Tabu List
اسلاید 7 :
جداسازی عملگر های مشابه از لیست عملگر های مجاز
نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع
اسلاید 8 :
نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع
اسلاید 9 :
نمایش موارد عملکرد یکسان روش تعویض و حذف و انتقال در تعریف همسایگی در الگوریتم جستجو ممنوع
اسلاید 10 :
تابو ها
نمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله اول
اسلاید 11 :
نمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله دوم
اسلاید 12 :
نمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله سوم
اسلاید 13 :
نمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله چهام
اسلاید 14 :
فلوچارت الگوریتم:
برای رسیدن به جواب بهینه در یک مسئله بهینهسازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت میکند. سپس الگوریتم بهترین جواب همسایه را از میان همسایههای جواب فعلی انتخاب میکند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت میکند؛ در غیراینصورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی میشود؛ به این معنا که حرکت قبل که بوسیلهی آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده میشود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود.
در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعهاست که توسط آن از قرار گرفتن الگوریتم در بهینهی محلی جلوگیری میشود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکتهایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج میشوند. مدت زمانی که حرکتها در فهرست ممنوعه قرار میگیرند توسط یک پارامتر که زمان ممنوعه (tabu tenure) نام دارد تعیین میشود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه مییابد که شرط خاتمه دیده شود. شرطهای خاتمه متفاوتی میتوان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه میتواند یک شرط خاتمه باشد.
اسلاید 16 :
معيارآزاد سازی از لیست : (Aspiration Criteria)
Tabu Search
تحت شرایطی، بعضي از ليستهاي ممنوع بسيار قوي هستند و از حركتهاي جذاب و خوب جلوگيري می كنند و اين درحالي است كه ممكن است هيچ خطري جهت افتادن در دور وجود نداشته باشد و يا ممكن است اين حركات باعث بهبود كلي جستجو شوند.
از اين رو لازم است كه از الگوريتمي استفاده كنيم تا ممنوع بودن را براي آن مورد خاص لغو كنند و اجازه دهند آن متغير وارد جستجو شود. اين وسيلهها معيار رضايت نام دارند.
سادهترين و پراستفادهترين معیار آزاد سازی كه تقريباً در تمامي TS ها استفاده ميشود، به اين صورت است كه يك حركت ممنوع، اگر به جوابي بهتر از جواب بهينه فعلی منجر گردد، بايد آن حركت انجام شود یعنی ممنوعيت آن لغو گردد (زيرا قبلاً چنين جوابي مشاهده نشده است).
معيار 1 : يک جواب باید از لیست ممنوع خارج شود، اگر از هر جوابي که قبلا به دست آمده بر اساس مقدار تابع هدف بهتر باشد .
معيار 2 : هرگاه ساختار روش و ليستهاي ممنوع در مرحله اي از فرايند تکرار به گونه اي باشد که امکان هيچ گونه حرکت وجود نداشته باشد در اين صورت حرکتي که در صف خارج شدن از ليست ممنوع از همه به خروج نزديک تر است انتخاب و ممنوعيت آن برداشته مي شود.
اسلاید 17 :
Stopping Conditions
شروط پاياني پركاربرد در TS عبارتنداز:
1. توقف بعد از تعداد تكرار مشخص
( مثلاً پس از کارکرد CPU به اندازة يك مدت زمان مشخص).
2. پس از تعدادي تكرار بدون اينكه جواب تابع هدف تغييركند (اين مورد، بيشترين استفاده را تا به حال داشته است).
3. وقتي كه جواب به يك حد آستانهاي و مقدار از پيش تعيين شده برسد.
اسلاید 18 :
Intensification & Diversification
عبارت Intensification در TS به مکانیسمی اطلاق می شود که بر اساس آن جوابها و move هایی که باعث رسیدن به جوابهای خوب شده اند، تقویت می شوند. بعبارت بهتر، این استراتژی، به بازگشت به جوابهای نخبه و جستجوی بیشتر در محدوده ی آنها، اشاره دارد. از آنجا که جوابهای نخبه برای مقایسه های بعدی مورد نیاز هستند، نحوه ی پیاده سازی ی این مفهوم شامل در نظر گرفتن یک حافظه ی مشخص برای این مجموعه از جوابها است.
استراتژی های Intensification به ابزاری برای مشخص کردن مجموعه ای از جوابهای نخبه نیاز دارند، تا پایه ای برای ترکیب خصوصیات خوب جهت ساخت جوابهای تازه، در دست داشته باشند. عضویت در این مجموعه از جوابها اغلب با در نظر گرفتن یک آستانه برای مقدار تابع هدف انجام می پذیرد.
يكي از مهمترين مشكلات روشهاي مبتني بر جستجوي محلي، گرايش اين روشها به محليبودن است. آنها تمايل دارند تا بيشتر در يك منطقة محدود به جستجو بپردازند. از نكات منفي كه ميتوان در اين روشها به آن رسيد اين است كه هر چند ممكن است جوابهاي خوبي پيدا شوند، اما ممكن است تمامي ناحية جواب بررسي نشود و ممكن است بهينهاي پيدا شود كه از جواب بهينة فعلي پيدا شده بسيار بهتر باشد. Diversification در TS يك مكانيسم است كه كوشش مي كند اين مشكل را با انتقال جستجو به ناحيه هاي كمتر مورد بررسي قرار گرفته و يا قرار نگرفته حل كند. دو روش عمده براي Diversification وجود دارد:
شروع دوباره : جستجو را از نقاطي كه كمتر مورد استفاده قرار گرفتهاند و يا از جواب بهينهاي که پيدا كرده است، دوباره شروع می كند ( نقاط ديگر را در داخل ليست ممنوع قرار می دهد).
هدایت جستجو: قرار دادن مکانیسمی در فرآیند جستجو كه كار رعایت پراکندگی را ازهمان ابتدا در دستور كار قرار مي دهد.
اسلاید 19 :
حافظه ها در TS
ShortTerm memory
ساختار حافظه ی کوتاه مدت در رویکرد Tabu Search بطور معمول به بخشی از حافظه اطلاق می شود که یا برای پیاده سازی Intensification بکار برده می شود و یا برای انجام LS مورد نیاز است. از آن جمله می توان حافظه ی اختصاص یافته به لیست ممنوع (Tabu List) را، بعنوان حافظه ای که برای عدم تکرار بکار برده می شود، در این دسته قرار داد.
LongTerm Memory:
حافظه ی بلند مدت، در TS با هدف جهت دادن به روند جستجو پیاده سازی می شود. بعبارت بهتر، معمولا این حافظه پیاده سازی معیار Diversification است. تذکر این نکته لازم است که در TS برای افزایش پراکندگی جستجو و هدایت آن، معمولا راه حل ها از یک مساله به مساله ی دیگر تفاوت می کند. یک روش، استفاده از متدی مشابه GLS (Guided Local Search) است.
اسلاید 20 :
TS vs. SA
پراکندگی بیشتر
سرعت همگرایی کمتر
معمولا سریعتر به جواب بهینه همگرا می شود
امکان قرار گرفتن در یک بهینه موضعی
