صفحه محصول - پاورپوینت جست و جوی ممنوع

پاورپوینت جست و جوی ممنوع (pptx) 34 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 34 اسلاید

قسمتی از متن PowerPoint (.pptx) :

جستجوی ممنوع Tabu Search مقدمه و تاریخچه جستجوی موضعی (Local Search) ترفند TS : لیست ممنوع معیارهای آزادسازی از Tabu List معیارهای توقف الگوریتم اولیه Intensification و Diversification در TS مقایسه SA و TS مساله k-Tree نرم افزار طراحی شده نتایج حاصل از حل Tabu Search مقدمه و تاریخچه : عبارت Tabu(Taboo) از یک زبان پولنیزیایی ریشه می گیرد که توسط مردم بومی جزیره tonga برای مشخص کردن چیزهایی بکار می رود که مقدس و غیرقابل لمس و یا (بخاطر خطر داشتن ) ممنوع شده هستند. ارتباط این کلمه با حافظه ی مردم آن منطقه از این جهت که تجربیات گذشته باعث شده است تا چنین تلقی امروزی در مورد یک مفهوم خاص بوجود آید، کلید اصلی ارتباط این کلمه با مفهوم ممنوعیت در Tabu Search است. عناصر ممنوع در Tabu Search با ارجاع به حافظه مشخص می شوند. چنانکه می دانید، الگوریتم های فرا ابتکاری بسیاری برای دستیابی به حـداقل یک جـواب خـوب ( نه لــزوما بهترین ) برای یک مسـالـه NP-Hard بوجود آمده است. بسیاری از این روشها از یک مکانیزم Local Search بهره می گیرند. Tabu Search Tabu Search LS را می توان یک روال جستجوی تکرارشونده دانست که از یک جواب شدنی شروع می کند و با انجام اصلاحات جزیی (همان Move)، آنرا تا رسیدن به یک بهینه ی موضعی ادامه می دهد. با در نظر داشتن این نکته که در حالت معمول این بهینه ی موضعی، چیزی بیش از یک جواب متوسط نیست. در LS معمولا کیفیت جواب بدست آمده به حد زیادی بستگی به غنای move های تعریف شده مان دارد. و این مساله اساسی در رویکرد های مبتنی بر LS است. Tabu Search در سال 1986توسط Fred Glover برای غلبه بر این مشکل ارایه شد. اصل اولیه در TS ، مجاز دانستن move هایی که بهبودی به همراه ندارند، برای ادامه دادن جستجو در LS است، وقتی که به یک بهینه موضعی برمی خوریم. البته در این روش برای اجتناب از دور زدن و رسیدن به جوابهایی که پیش از این بدست آمده، از حافظه ای بنام Tabu List استفاده می کنیم. این حافظه جوابهای اخیر و یا move های اخیر را در خود ضبط می کند. در واقع یک TS ساده را می توان ترکیبی از یک حافظه کوتاه مدت با LS دانست. همسایگی : Tabu Search از اولین مفاهیمی که در TS می باید بدان پرداخت، مفهوم همسایگی است. در هر تکرار، انتقالی (move) که بر روی جواب S اعمال می شود، مجموعه ای از جوابها را در فضای جستجو تعریف می کند که جوابهای همسایه گفته می شوند (N(S)) پس همسایگی، زیرمجموعه ای از فضای جواب است که به شکل زیر تعریف می شود : N(S) : مجموعه ی جوابهایی که با استفاده از یک انتقال، از جواب S بدست می آیند. چنانچه از تعریف بر می آید، ساختار همسایه، می تواند حتی شامل تمامی فضای جواب نیز باشد. برای یک مساله خاص، نوع انتقال یا move تعریف شده، نقشی اساسی در وسعت همسایگی ی بوجود آمده دارد. Tabu Search گفتیم که مفهوم اساسی در TS مجاز دانستن جوابهایی است که در تابع هدف بهبود ایجاد نمی کنند، اما ممکن است ما را به سمت جواب سراسری راهنمایی کنند، با این شــرط که در لیست جوابهای مـمنوع قرار نداشته باشند . اما TS برای استفاده از چنین راه حلی، نیازمند آن است که از پدیده دور، که ناشی از بازگشت به جوابهای پیشین است، جلوگیری کند. این، وظیفه Tabu ها ست: مجموعه ای از انتقال های ممنوع که به حافظه سپرده می شوند تا چنین بازگشتهایی رخ ندهد. این انتقال های ممنوع، در حافظه ای کوتاه مدت (Short Term Memory) ذخیره می شوند تا (برای مدتی معین) انجام مجموعه ای معین از انتقال ها را ممنوع سازند. این مدت معین، یا اصطلاحا Tabu Tenure بنا بر الگوریتم حل و نوع مساله و ماهیت انتقال ها متغیر است. حافظه مورد استفاده برای نگهداری Tabu ها معمولا گردشی و دارای طول ثابت است. : Tabu List Tabu Search Reversion (3,4) Is equal to Swap (3,4) جداسازی عملگر های مشابه از لیست عملگر های مجاز نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع Tabu Search Reversion (2,4) Is equal to Swap (2,4) نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع Tabu Search Insertion(2,3) Is equal to Swap (3,4) نمایش موارد عملکرد یکسان روش تعویض و حذف و انتقال در تعریف همسایگی در الگوریتم جستجو ممنوع