دانلود مقاله الگوریتم های دقیق و حافظه کوتاه مدت

دانلود پایان نامه

فضای جستجوی LS یا TS در واقع تمام پاسخ هایشدنی است که میتوان در جریان جستجو به آنها برخورد کرد. نزدیک ترین مفهوم پس از تعریف فضای جستجو، مفهوم ساختار همسایگی است که نشان دهنده تمام پاسخهایی است که میتوان با یک حرکت از پاسخ فعلی به آنها رسید. اگر مجموعه تمام تغییراتی را که برروی پاسخ فعلی میتوان انجام داد با نشان دهیم، و نشان دهنده تمام پاسخ های همسایهای باشد که میتوان به این طریق ساخت، خواهیم داشت :
با این اوصاف میتوان گفت که برای یک مسئله خاص این قابلیت وجود دارد که چندین ساختار همسایگی داشته باشیم (هر ساختار همسایگی متناظر با یک نوع حرکت یا تغییر برروی پاسخ های شدنی است). معروف ترین حرکاتی که در TS به کار می رود و به کمک آن ها ساختار همسایگی تعریف می شود شامل «قرار دادن» و «جابجایی» است. در حرکت قرار دادن، یکی از عناصر پاسخ انتخاب و در جایی بین باقی عناصر قرار می گیرد و به این شکل یک پاسخ جدید ساخته می شود. در جابه جایی، مکان قرار گرفتن دو عنصر در پاسخ فعلی با یکدیگر تعویض می شود.
یکی دیگر از نکاتی که TS را از LS متمایز میکند، «لیست حرکت های غیر مجاز» (TL) است. TL در واقع یک آرایه با طول مشخص است که در آن تمام حرکت اخیری که در جریان جستجو انجام شده اند ذخیره شده است و در صورت تکراری بودن یک حرکت (وجود آن در TL) از انجام آن جلوگیری میشود. در صورتی که حرکت تکراری نباشد، پس از انجام آن، حرکت انجام شده وارد TL میشود و اولین حرکتی که در TL وجود دارد از لیست خارج میشود. از TL با عنوان «حافظه کوتاه مدت» نیز یاد میشود. عناصر یا حرکت هایی که در TL ذخیره شده اند تا انجام تعداد مشخصی از حرکات (طول TL) قابلیت بازیابی و انجام مجدد ندارند مگر اینکه انجام آنها به مقدار قابل توجهی و به اندازه یک معیار از پیش تعیین شده تابع هدف را بهبود دهد. در واقع ما تنها در صورتی که معیار پیش گفته دیده شد میتوانیم یکی از عناصر TL را مورد استفاده قرار دهیم. این معیار با عنوان Aspiration Criteria شناخته میشود.
علاوه بر حافظه کوتاه مدت، دو نوع حافظه «میان مدت» و «بلند مدت» نیز در TS کاربرد دارد. این دو نوع حافظه در جریان جستجو این امکان را فراهم میآورند که پاسخهای بهتر امکان بیشتری جهت بروز داشته باشند و به همین نسبت پاسخهای بدتر تاثیر کمتری در فرآیند جستجو داشته باشند.
به طور کلی چهار چوب TS را به شکل زیر می وان نشان داد. ( مقدار فعلی، بهترین پاسخ شناخته شده، مقدار تابع هدف به ازای ، همسایگی و مقدار غیر تابو یا اجازه داده شده توسط Aspiration Criteria است.)
– یک پاسخ اولیه انتخاب کنید.
– قرار دهید
– جستجو را آغاز کنید و تا زمانی که معیار توقف حاصل نشده گامهای زیر را انجام دهید:
– را به گونه ای انتخاب کنید که .
– اگر ، قرار دهید و
– حرکت انجام شده و پاسخ ارزیابی شده را تابو قرار دهید. (مقادیر کهنه را در صورت لزوم پاک کنید.)
2-5-4-4. الگوریتم جستجوی پرندگان (PSO)
روش بهینه سازی جستجوی پرندگان (PSO) بر مبنای الگوی رفتار جمعی حیوانات کار میکند. این الگوریتم برای اولین بار در سال 1995 توسط کندی و ابرهارت معرفی شد. هر پاسخ شدنی در این الگوریتم به مثابه یک عضو از جامعه پرندگان (حیوانات) است که اطلاعات محدودی مانند سرعت نزدیکترین همسایه اش و وضعیت خود دارد و مجموعه این اعضا رفتار مشخصی را در شرایط مختلف مانند، هنگامیکه یک خطر آنها را تهدید میکند از خود بروز میدهد. به طور مثال، هنگام حمله یک کوسه به دستهای از ماهیها میتوان مشاهده کرد که آنها به دو دسته تقسیم میشوند و پس از رفع خطر به حالت اولیه باز میگردند.
شکل 2-1 نحوه رفتار دسته جانوران هنگام برخورد با خطر و الگو گیری الگوریتم PSO از این مطلب
به طور خلاصه هر کدام از افراد، اطلاعات محلی که شامل جایابی نزدیکترین همسایه اش است و توسط او قابل دسترسی است را برای تصمیم گیری در مورد مکان خودش بکار میبرد.
در این الگوریتم هر ذره توسط پارامتر وضعیتش که با و یک بردار ، که بردار سرعت آن است، نشان داده می شود. در هر گام حرکت ذره به کمک معادله زیر :
تبیین میشود. هسته اصلی روش شامل روشی است که طبق آن vi بعد از هر گام انتخاب میشود. به روز رسانی موقعیت ذرات بستگی به جهت حرکت، سرعت، بهترین پاسخ بدست آمده در مرحله قبل و مناسب ترین موقعیت میان همسایگان دارد.
2-6. مروری بر الگوریتم حل
هدف اصلی روش‌های هوشمند به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم های دقیق و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آنها در بهینه‌های محلی، و ناتوانی آنها برای کاربرد در مسائل گوناگون است. الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برون رفت از بهینه محلی می‌باشند و قابل کاربرد در طیف گسترده ای از مسائل هستند.
روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسأله خاصی کاربرد دارند. این دو نکته با استفاده از شکل (2-2) روشن خواهد شد.
شکل 2-2 بهینه محلی و بهینه کلی
با توجه به شکل بالا، این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند، به ویژه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی را خواهیم داشت.
نکته دوم این است که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله می‌شوند. در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسئله‌ای به کار گرفته شوند. بنابراین برای حل مسائل سخت، جهت یافتن جواب های نزدیک بهینه الگوریتم های هوش مصنوعی مانند الگوریتم های ابتکاری و فرا ابتکاری مناسب می باشند.