Tabu Search (جستجوی ممنوع)

Tabu Search (جستجوی ممنوع)

اسلاید 1: جستجوی ممنوعTabu Search

اسلاید 2: مقدمه و تاریخچهجستجوی موضعی (Local Search)ترفند TS : لیست ممنوع معیارهای آزادسازی از Tabu Listمعیارهای توقف الگوریتم اولیه Intensification و Diversification در TSمقایسه SA و TSمساله k-Treeنرم افزار طراحی شدهنتایج حاصل از حلTabu Search

اسلاید 3: مقدمه و تاریخچه : عبارت Tabu(Taboo) از یک زبان پولنیزیایی ریشه می گیرد که توسط مردم بومی جزیره tonga برای مشخص کردن چیزهایی بکار می رود که مقدس و غیرقابل لمس و یا (بخاطر خطر داشتن ) ممنوع شده هستند. ارتباط این کلمه با حافظه ی مردم آن منطقه از این جهت که تجربیات گذشته باعث شده است تا چنین تلقی امروزی در مورد یک مفهوم خاص بوجود آید، کلید اصلی ارتباط این کلمه با مفهوم ممنوعیت در Tabu Search است.عناصر ممنوع در Tabu Search با ارجاع به حافظه مشخص می شوند. چنانکه می دانید، الگوریتم های فرا ابتکاری بسیاری برای دستیابی به حـداقل یک جـواب خـوب ( نه لــزوما بهترین ) برای یک مسـالـه NP-Hard بوجود آمده است. بسیاری از این روشها از یک مکانیزم Local Search بهره می گیرند. Tabu Search

اسلاید 4: Tabu SearchLS را می توان یک روال جستجوی تکرارشونده دانست که از یک جواب شدنی شروع می کند و با انجام اصلاحات جزیی (همان Move)، آنرا تا رسیدن به یک بهینه ی موضعی ادامه می دهد. با در نظر داشتن این نکته که در حالت معمول این بهینه ی موضعی، چیزی بیش از یک جواب متوسط نیست. در LS معمولا کیفیت جواب بدست آمده به حد زیادی بستگی به غنای move های تعریف شده مان دارد. و این مساله اساسی در رویکرد های مبتنی بر LS است.Tabu Search در سال 1986توسط Fred Glover برای غلبه بر این مشکل ارایه شد. اصل اولیه در TS ، مجاز دانستن move هایی که بهبودی به همراه ندارند، برای ادامه دادن جستجو در LS است، وقتی که به یک بهینه موضعی برمی خوریم. البته در این روش برای اجتناب از دور زدن و رسیدن به جوابهایی که پیش از این بدست آمده، از حافظه ای بنام Tabu List استفاده می کنیم.این حافظه جوابهای اخیر و یا move های اخیر را در خود ضبط می کند. در واقع یک TS ساده را می توان ترکیبی از یک حافظه کوتاه مدت با LS دانست.

اسلاید 5: همسایگی :Tabu Searchاز اولین مفاهیمی که در TS می باید بدان پرداخت، مفهوم همسایگی است. در هر تکرار، انتقالی (move) که بر روی جواب S اعمال می شود، مجموعه ای از جوابها را در فضای جستجو تعریف می کند که جوابهای همسایه گفته می شوند (N(S)) پس همسایگی، زیرمجموعه ای از فضای جواب است که به شکل زیر تعریف می شود :N(S) : مجموعه ی جوابهایی که با استفاده از یک انتقال، از جواب S بدست می آیند.چنانچه از تعریف بر می آید، ساختار همسایه، می تواند حتی شامل تمامی فضای جواب نیز باشد. برای یک مساله خاص، نوع انتقال یا move تعریف شده، نقشی اساسی در وسعت همسایگی ی بوجود آمده دارد.

اسلاید 6: Tabu Searchگفتیم که مفهوم اساسی در TS مجاز دانستن جوابهایی است که در تابع هدف بهبود ایجاد نمی کنند، اما ممکن است ما را به سمت جواب سراسری راهنمایی کنند، با این شــرط که در لیست جوابهای مـمنوع قرار نداشته باشند .اما TS برای استفاده از چنین راه حلی، نیازمند آن است که از پدیده دور، که ناشی از بازگشت به جوابهای پیشین است، جلوگیری کند. این، وظیفه Tabu ها ست: مجموعه ای از انتقال های ممنوع که به حافظه سپرده می شوند تا چنین بازگشتهایی رخ ندهد. این انتقال های ممنوع، در حافظه ای کوتاه مدت (Short Term Memory) ذخیره می شوند تا (برای مدتی معین) انجام مجموعه ای معین از انتقال ها را ممنوع سازند. این مدت معین، یا اصطلاحا Tabu Tenure بنا بر الگوریتم حل و نوع مساله و ماهیت انتقال ها متغیر است. حافظه مورد استفاده برای نگهداری Tabu ها معمولا گردشی و دارای طول ثابت است. : Tabu List

اسلاید 7: Tabu SearchReversion (3,4)45132Is equal to41532Swap (3,4)45132جداسازی عملگر های مشابه از لیست عملگر های مجازنمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع

اسلاید 8: Tabu SearchReversion (2,4)43512Is equal to41532Swap (2,4)43512نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع

اسلاید 9: Tabu SearchInsertion(2,3)41352Is equal to41532Swap (3,4)41352نمایش موارد عملکرد یکسان روش تعویض و حذف و انتقال در تعریف همسایگی در الگوریتم جستجو ممنوع

اسلاید 10: 12345234561502,41425,31636,21483,1Current solutionTabu tenureswapcostتابو هانمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله اول

اسلاید 11: 212345234561676,21403,41725,31384,1Current solutionTabu tenureswapcostنمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله دوم

اسلاید 12: 2112345234561851,51533,41372,61465,2Current solutionTabu tenureswapcostنمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله سوم

اسلاید 13: 12tabu12345234561676,21401,41725,31323,1Current solutionTabu tenureswapcostنمایش نحوه عملکرد لیست تابو بافرض اینکه طول لیست تابو برابر دو باشد مرحله چهام

اسلاید 14: فلوچارت الگوریتم:برای رسیدن به جواب بهینه در یک مسئله بهینه‌سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می‌کند. سپس الگوریتم بهترین جواب همسایه را از میان همسایه‌های جواب فعلی انتخاب می‌کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می‌کند؛ در غیراین‌صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می‌شود؛ به این معنا که حرکت قبل که بوسیله‌ی آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می‌شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود. در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه‌است که توسط آن از قرار گرفتن الگوریتم در بهینه‌ی محلی جلوگیری می‌شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت‌هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می‌شوند. مدت زمانی که حرکت‌ها در فهرست ممنوعه قرار می‌گیرند توسط یک پارامتر که زمان ممنوعه (tabu tenure) نام دارد تعیین می‌شود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می‌یابد که شرط خاتمه دیده شود. شرط‌های خاتمه متفاوتی می‌توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می‌تواند یک شرط خاتمه باشد.Tabu Search

اسلاید 15: Basic Tabu Search Algorithm Tabu Searchk := 1. generate initial solution WHILE the stopping condition is not met DO     -Identify N(s). (Neighbourhood set)     -Identify T(s,k). (Tabu set)     -Identify A(s,k). (Aspirant set)     -Choose the best s’ Є  N(s,k) = {N(s) - T(s,k)}+A(s,k).     -Memorize s’ if it improves the previous best known solution     -s := s’.     -k := k+1. END WHILETabu Search

اسلاید 16: معيارآزاد سازی از لیست : (Aspiration Criteria) Tabu Searchتحت شرایطی، بعضي از ليستهاي ممنوع بسيار قوي هستند و از حركت‌هاي جذاب و خوب جلوگيري می كنند و اين درحالي است كه ممكن است هيچ خطري جهت افتادن در دور وجود نداشته باشد و يا ممكن است اين حركات باعث بهبود كلي جستجو شوند. از اين رو لازم است كه از الگوريتمي استفاده كنيم تا ممنوع بودن را براي آن مورد خاص لغو كنند و اجازه دهند آن متغير وارد جستجو شود. اين وسيله‌ها معيار رضايت نام دارند.ساده‌ترين و پراستفاده‌ترين معیار آزاد سازی كه تقريباً در تمامي TS ها استفاده مي‌شود، به اين صورت است كه يك حركت ممنوع، اگر به جوابي بهتر از جواب بهينه فعلی منجر گردد، بايد آن حركت انجام شود یعنی ممنوعيت آن لغو گردد (زيرا قبلاً چنين جوابي مشاهده نشده است).

اسلاید 17: Stopping ConditionsTabu Searchشروط پاياني پركاربرد در TS عبارتنداز:1. توقف بعد از تعداد تكرار مشخص ( مثلاً پس از کارکرد CPU به اندازة يك مدت زمان مشخص).2. پس از تعدادي تكرار بدون اينكه جواب تابع هدف تغييركند (اين مورد، بيشترين استفاده را تا به حال داشته است).3. وقتي كه جواب به يك حد آستانه‌اي و مقدار از پيش تعيين ‌شده برسد.Tabu Search

اسلاید 18: Tabu SearchTabu SearchIntensification & Diversification عبارت Intensification در TS به مکانیسمی اطلاق می شود که بر اساس آن جوابها و move هایی که باعث رسیدن به جوابهای خوب شده اند، تقویت می شوند. بعبارت بهتر، این استراتژی، به بازگشت به جوابهای نخبه و جستجوی بیشتر در محدوده ی آنها، اشاره دارد. از آنجا که جوابهای نخبه برای مقایسه های بعدی مورد نیاز هستند، نحوه ی پیاده سازی ی این مفهوم شامل در نظر گرفتن یک حافظه ی مشخص برای این مجموعه از جوابها است. استراتژی های Intensification به ابزاری برای مشخص کردن مجموعه ای از جوابهای نخبه نیاز دارند، تا پایه ای برای ترکیب خصوصیات خوب جهت ساخت جوابهای تازه، در دست داشته باشند. عضویت در این مجموعه از جوابها اغلب با در نظر گرفتن یک آستانه برای مقدار تابع هدف انجام می پذیرد.

اسلاید 19: حافظه ها در TSShortTerm memoryساختار حافظه ی کوتاه مدت در رویکرد Tabu Search بطور معمول به بخشی از حافظه اطلاق می شود که یا برای پیاده سازی Intensification بکار برده می شود و یا برای انجام LS مورد نیاز است. از آن جمله می توان حافظه ی اختصاص یافته به لیست ممنوع (Tabu List) را، بعنوان حافظه ای که برای عدم تکرار بکار برده می شود، در این دسته قرار داد. LongTerm Memory: حافظه ی بلند مدت، در TS با هدف جهت دادن به روند جستجو پیاده سازی می شود. بعبارت بهتر، معمولا این حافظه پیاده سازی معیار Diversification است. تذکر این نکته لازم است که در TS برای افزایش پراکندگی جستجو و هدایت آن، معمولا راه حل ها از یک مساله به مساله ی دیگر تفاوت می کند. یک روش، استفاده از متدی مشابه GLS (Guided Local Search) است. Tabu Search

اسلاید 20: TS vs. SA پراکندگی بیشتر سرعت همگرایی کمتر معمولا سریعتر به جواب بهینه همگرا می شود امکان قرار گرفتن در یک بهینه موضعی

اسلاید 21: Tabu Search5121611134

اسلاید 22: Tabu SearchTabu Search512161113412161111125131344411121316Tree Nodes Array:511Static Swap

اسلاید 23: Tabu Search5121611134716Dynamic SwapTree Nodes Array:7

اسلاید 24: Tabu Searchگراف کامل وزن­دار و بدون جهت G با n گره (Node) داده شده است. مطلوبست پیدا کردن درختی با k یال، بطوریکه مجموع وزنهای روی یال ها، Minimum باشد. مساله درخت k (k-Tree) (n-complete graph) |V | = nT گراف همبند بدون دور باشدیافتن گراف (درخت) T به نحوی که:St:که در آن:w(ei) : وزن یال i ام روی درختVT : مجموعه گره های درخت ET : مجموعه یالهای درخت T

اسلاید 25: گراف G : ماتریس 2 بعدی متقارن، با n سطر و n ستون (با نام Graph). اگر ei = (p,q) یالی از گره p به q باشد، آنگاه :w(ei) = Graph(p,q) = Graph(q,p)Tabu Searchطراحی کروموزم:آرایه ای به طول k از جفت عددهای به فرم (x,y) که معرف یال ها هستند.5121611134

اسلاید 26: Tabu SearchTabu Search512161113412161111125131344411121316Tree Nodes Array:511Static Swap

اسلاید 27: Tabu Search5121611134716Dynamic SwapTree Nodes Array:7

اسلاید 28: شاخصه های برنامه

اسلاید 29: تحلیل نتایجTDrop SizeTAdd SizeRepeatInit Solution311100RandomObjective FunctionRepeatskn525

اسلاید 30: تحلیل نتایجTDrop List RangTAdd List RangeInit Function1-102-15Greedy

اسلاید 31: تحلیل نتایجAverage:11.18StD :1.33Optimum:7

اسلاید 32: تحلیل نتایجTAddList ≈ TDropListTAddList > 1.9 * TDropList%61میانگین درصد ها

اسلاید 33: کاربردهای TS (Fred Glover)Tabu Search

اسلاید 34: با تشکر از توجه شماTabu Search