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

لینک دانلود و خرید پایین توضیحات

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

نوع فایل : 

.ppt ( قابل ويرايش و آماده پرينت )

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

---

 قسمتی از متن .ppt : 

 

جستجوی ممنوع

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

دانست.