دانلود مقاله الگوریتم های فراابتکاری و روش های فرا ابتکاری

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

تجزیه


تجزیه
جستجوی همسایه
جستجوی همسایه
تولید ستون
تولید ستون
تکرار
تکرار
نمودار 2-1 طبقه‌بندی انواع روش‌های بهینه‌سازی
2-5-1. روش‌های شمارشی
در روش‌های شمارشی، در هر تکرار فقط یک نقطه متعلق به فضای دامنه تابع هدف بررسی می‌شود. این روش‌ها برای پیاده‌سازی، ساده‌تر از روش‌های دیگر می‌باشند؛ اما به محاسبات قابل توجهی نیاز دارند. در این روش‌ها سازوکاری برای کاستن دامنه جستجو وجود ندارد و دامنه فضای جستجو شده با این روش خیلی بزرگ است. برنامه‌ریزی پویا مثال خوبی از روش‌های شمارشی می‌باشد. این روش کاملاً غیرهوشمند است و به همین دلیل امروزه بندرت به تنهایی مورد استفاده قرار می‌گیرد.
2-5-2. روش‌های محاسباتی (جستجوی ریاضی)
این روش‌ها از مجموعه شرایط لازم و کافی که در جواب مسأله بهینه‌سازی صدق می‌کند، استفاده می‌کنند. وجود یا عدم وجود محدودیت‌های بهینه‌سازی در این روش‌ها نقش اساسی دارد. به همین علت، این روش‌ها به دو دسته روش‌های با محدودیت و بی‌محدودیت تقسیم می‌شوند.
روش‌های بهینه‌سازی بی‌محدودیت با توجه به تعداد متغیرها شامل بهینه‌سازی توابع یک متغیره و چند متغیره می ‌باشند. روش‌های بهینه‌سازی توابع یک متغیره، به سه دسته روش‌های مرتبه صفر، مرتبه اول و مرتبه دوم تقسیم می‌شوند. روش‌های مرتبه صفر فقط به محاسبه تابع هدف در نقاط مختلف نیاز دارد؛ اما روش‌های مرتبه اول از تابع هدف و مشتق آن و روش‌های مرتبه دوم از تابع هدف و مشتق اول و دوم آن استفاده می‌کنند. در بهینه‌سازی توابع چند متغیره که کاربرد بسیار زیادی در مسائل مهندسی دارد، کمینه‌سازی یا بیشینه‌سازی یک کمیت با مقدار زیادی متغیر طراحی صورت می‌گیرد. یک تقسیم‌بندی، روش‌های بهینه‌سازی با محدودیت را به سه دسته برنامه‌ریزی خطی، روش‌های مستقیم و غیرمستقیم تقسیم می‌کند. مسائل با محدودیت که توابع هدف و محدودیت‌های آنها خطی باشند، جزو مسائل برنامه‌ریزی خطی قرار می‌گیرند. برنامه‌ریزی خطی شاخه‌ای از برنامه‌ریزی ریاضی است و کاربردهای فیزیکی، صنعتی و تجاری بسیاری دارد.
در روش‌های مستقیم، نقطه بهینه به طور مستقیم جستجو شده و از روش‌های بهینه‌یابی بی‌محدودیت استفاده نمی‌شود. هدف اصلی روش‌های غیرمستقیم استفاده از الگوریتم‌های بهینه‌سازی بی‌محدودیت برای حل عمومی مسائل بهینه‌سازی با محدودیت می‌باشد. در اکثر روش‌های محاسباتی بهینه‌یابی، از گرادیان تابع هدف برای هدایت جستجو استفاده می‌شود. اگر مثلاً به علت ناپیوستگی تابع هدف، مشتق آن قابل محاسبه نباشد، این روش‌ها اغلب با مشکل روبه‌رو می‌شوند.
2-5-3. روش‌های ابتکاری (جستجوی تصادفی)
یک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد. روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است. با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است. برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و کرانه کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت. به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری یا فرا ابتکاری یا جستجوی تصادفی صورت گرفته است. روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند. روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند. این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند. عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.
همان طور که گفته شد، با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده که مشهورترین آنها، الگوریتم سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کران برای حل برنامه‌های خطی با اعداد صحیح است. بنابراین در سال‌های اخیر توجه بیشتری بر روش‌های ابتکاری برگرفته از طبیعت که شباهت‌هایی با سیستم‌های اجتماعی یا طبیعی دارد، صورت گرفته است و نتایج بسیار خوبی در حل مسائل بهینه‌سازی ترکیبی NP-hard به دنبال داشته است. در این الگوریتم‌ها هیچ ضمانتی برای آنکه جواب به دست آمده بهینه باشد، وجود ندارد و تنها با صرف زمان بسیار می‌توان جواب نسبتاً دقیقی به دست آورد؛ در حقیقت با توجه به زمان صرف شده، دقت جواب تغییر می‌کند.
برای روش‌های ابتکاری نمی‌توان تعریفی جامع ارائه کرد. با وجود این، در اینجا کوشش می‌شود تعریفی تا حد امکان مناسب برای آن عنوان شود: روش جستجوی ابتکاری، روشی است که می‌تواند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کند. هیچ تضمینی برای بهینه بودن جواب وجود ندارد و متأسفانه نمی‌توان میزان نزدیکی جواب به دست آمده به جواب بهینه را تعیین کرد.
2-5-4. روش های فرا ابتکاری
یکی از روشهای حل مسائل بهینه سازی و به خصوص مسائل بهینه سازی ترکیبی، استفاده از الگوریتم های فراابتکاری است. به طور کلی الگوریتم های فراابتکاری را این گونه میتوان تعریف کرد:
«الگوریتمهای فراابتکاری، روشهای حلی هستند که بین- های بهبود محلی و استراتژیهای سطح بالاتر، جهت ایجاد فرآیندی که قابلیت فرار از بهینه محلی و اجرای یک جستجوی پایدار را داشته باشد، هماهنگی ایجاد میکنند». [49]
علیرغم تمامی پیشرفتهایی که در زمینه الگوریتمهای فراابتکاری شکل گرفته است، در طی دوران تکامل آنها، انتقاداتی نیز به آنها وارد بوده است. به عنوان مثال، منتقدان این زمینه مطرح کنند که میتوان تابع هدف را به گونه ای طراحی کرد که الگوریتم مزبور تمامی فضای مسئله را جستجو کند، و این در واقع معادل همان الگوریتمهای دقیق یا قطعی است. هم چنین هر کدام از این الگوریتمها در برخی از مسائل دارای قدرت هستند و در برخی دیگر میتوانند کاملا ضعیف عمل کنند.
در پاسخ به ایراد دوم این نکته نیز ذکر شده است که کارآیی دو الگوریتم، در یک مسئله خاص بیش از این که وابسته به نوع الگوریتم باشد، وابسته به پارامترهایی است که برای آن در نظر گرفته میشود. بنابراین باید گفت که نمیتوان در مورد کارآیی یک الگوریتم نسبت به دیگری اظهار نظر قطعی کرد.