دانلود فایل پاورپوینت جستجوی ممنوع

PowerPoint قابل ویرایش
34 صفحه
11900 تومان

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

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت جستجوی ممنوع قرار داده شده است

2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

4-در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

مقدمه و تاریخچه :

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

عناصر ممنوع در Tabu Search با ارجاع به حافظه مشخص می شوند.

چنانکه می دانید، الگوریتم های فرا ابتکاری بسیاری برای دستیابی به حـداقل یک جـواب خـوب ( نه لــزوما بهترین ) برای یک مسـالـه       NP-Hard بوجود آمده است.

بسیاری از این روشها از یک مکانیزم Local Search بهره می گیرند.

اسلاید ۲ :

LS را می توان یک روال جستجوی تکرارشونده دانست که از یک جواب شدنی شروع می کند و با انجام اصلاحات جزیی (همان Move)، آنرا تا رسیدن به یک بهینه ی موضعی ادامه می دهد. با در نظر داشتن این نکته که در حالت معمول این بهینه ی موضعی، چیزی بیش از یک جواب متوسط نیست.

در LS معمولا کیفیت جواب بدست آمده به حد زیادی بستگی به غنای  move های تعریف شده مان دارد. و این مساله  اساسی در رویکرد های مبتنی بر LS است.

Tabu Search در سال ۱۹۸۶توسط  Fred Glover  برای غلبه بر این مشکل ارایه شد. اصل اولیه در TS ، مجاز دانستن move هایی که بهبودی به همراه ندارند، برای ادامه دادن جستجو در LS است، وقتی که به یک بهینه  موضعی برمی خوریم.

البته در این روش برای اجتناب از دور زدن و رسیدن به جوابهایی که پیش از این بدست آمده، از حافظه ای بنام Tabu List استفاده می کنیم.

این حافظه جوابهای اخیر و یا move های اخیر را در خود ضبط می کند.  در واقع یک TS ساده را می توان                                            ترکیبی از یک حافظه  کوتاه مدت با    LS  دانست.

اسلاید ۳ :

همسایگی :

از اولین مفاهیمی که در TS می باید بدان پرداخت، مفهوم همسایگی است.

در هر تکرار، انتقالی (move) که بر روی جواب S اعمال می شود، مجموعه ای از جوابها را در فضای جستجو تعریف می کند که جوابهای همسایه گفته می شوند (N(S))

پس همسایگی، زیرمجموعه ای از فضای جواب است که به شکل زیر تعریف می شود :

N(S) : مجموعه ی جوابهایی که با استفاده از یک انتقال، از جواب           S بدست می آیند.

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

نقشی اساسی در وسعت همسایگی ی بوجود آمده دارد.

اسلاید ۴ :

 : Tabu List

گفتیم که مفهوم اساسی در TS مجاز دانستن جوابهایی است که در تابع هدف بهبود ایجاد نمی کنند، اما ممکن است ما را به سمت جواب سراسری راهنمایی کنند، با این شــرط که در لیست جوابهای مـمنوع قرار نداشته باشند .

اما TS برای استفاده از چنین راه حلی، نیازمند آن است که از پدیده دور، که ناشی از بازگشت به جوابهای پیشین است، جلوگیری کند. این، وظیفه  Tabu ها ست:

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

این انتقال های ممنوع، در حافظه ای کوتاه مدت (Short Term Memory) ذخیره می شوند تا (برای مدتی معین) انجام مجموعه ای معین از انتقال ها را ممنوع سازند. این مدت معین، یا اصطلاحا Tabu Tenure بنا بر       الگوریتم حل و نوع مساله و ماهیت انتقال ها متغیر است.

 حافظه مورد استفاده برای نگهداری Tabu ها معمولا                         گردشی و دارای طول ثابت است.

اسلاید ۵ :

جداسازی عملگر های مشابه از لیست عملگر های مجاز

نمایش موارد عملکرد یکسان روش تعویض و معکوس سازی در تعریف همسایگی در الگوریتم جستجو ممنوع

اسلاید ۶ :

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

اسلاید ۷ :

Basic Tabu Search Algorithm

شروع :

جواب اولیه امکان‌پذیر مانند S0 را پیدا کنید و قراردهید:

Set S := S0 , f* := f( S0 )S* := S0 , T := Ø.

جستجو

 تا زمانی‌که شرط پایانی برآورده نشده است، تکرار کن:

**  یک S   که           Ñ(S)انتخاب کن

**  اگر   F(S)<F*  آنگاه قرار بده :   F*:=F(S) و S*:=S

**  این حرکت را در لیست ممنوع قرار بده و قدیمی‌ترین ورودی لیست را اگر( لازم است ) حذف کن.

اسلاید ۸ :

معیارآزاد سازی از لیست :
(Aspiration Criteria)

معیار ۱ : یک جواب باید از لیست ممنوع خارج شود، اگر از هر جوابی که قبلا به دست آمده بر اساس مقدار تابع هدف بهتر باشد .

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

اسلاید ۹ :

Stopping Conditions

شروط پایانی پرکاربرد در TS عبارتنداز:

  1. توقف بعد از تعداد تکرار مشخص

( مثلاً پس از کارکرد CPU  به اندازه یک مدت زمان مشخص).

  1. پس از تعدادی تکرار بدون اینکه جواب تابع هدف تغییرکند (این مورد، بیشترین استفاده را تا به حال داشته است).
  2. وقتی که جواب به یک حد آستانه‌ای و مقدار از پیش تعیین ‌شده برسد.

اسلاید ۱۰ :

Intensification & Diversification

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

  • شروع دوباره : جستجو را از نقاطی که کمتر مورد استفاده قرار گرفته‌اند و یا از جواب بهینه‌ای که پیدا کرده‌ است، دوباره شروع می کند ( نقاط دیگر را در داخل لیست ممنوع قرار می دهد).
  • هدایت جستجو: قرار دادن مکانیسمی در فرآیند جستجو که  کار رعایت پراکندگی را ازهمان ابتدا در دستور کار قرار می دهد.
مطالب فوق فقط متون اسلاید های ابتدایی پاورپوینت بوده اند . جهت دریافت کل ان ، لطفا خریداری نمایید .
PowerPoint قابل ویرایش - قیمت 11900 تومان در 34 صفحه
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد