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

مقید و نامقید: متغیرها اغلب دارای محدودیت ها یا قیود هستند. در بهینه سازی غیر مقید، متغیرها مجاز هستند تا هر مقداری را دارا باشند. اما در بهینه سازی مقید، متغیرها فقط مجاز به دارا بودن مقادیری هستند که منافاتی با قیود نداشته باشند. یک متغیر مقید اغلب به یک متغیر غیر مقید تبدیل می شود . بیشتر روشهای بهینه سازی عدد بهترین جواب را برای متغیرهای غیر مقید ارائه می دهند. یک مثال ساده بهینه سازی همراه با قید بصورت زیر می باشد :
کمینه سازی تابع f(x) روی بازه را در نظر بگیرید .متغیر x با تغییر متغیر x = sin(u) تبدیل به متغیر غیر مقید u می گردد . و حل مسأله با کمینه سازی f(sin(u)) برای هر مقدار از u بدست می آید .
Widget not in any sidebars

گسسته و پیوسته: بهینه سازی همچنین می تواند بصورت متغیرهای مجزا (گسسته) یا پیوسته، تفکیک گردد. متغیرهای مجزا تنها شامل یک عدد محدود از مقادیر ممکن می باشند، در حالی که متغیرهای پیوسته دارای اعداد نامحدودی از مقادیر ممکن هستند. اگر ما قصد داشته باشیم که به مجموعهای از اهداف دست یابیم، بهینه سازی مجزا به کار گرفته خواهد شد. در حالی که اگر ما بخواهیم مقدار کمینه f(x) را بر روی دامنهای از اعداد حقیقی بیابیم با یک مسأله پیوسته روبهرو هستیم.
خطی و غیرخطی : هنگامی که معادلات و قیود بصورت خطی باشند مسأله ، مسألهی بهینه سازی خطی است و چنانچه معادلات و قیود غیر خطی باشند با مسألهی غیر خطی سر و کار داریم.
تصادفی و غیر تصادفی: در یک مسئله بهینه سازی، بسته به آنکه متغیرهای مسأله مقادیر حقیقی، صحیح، باینری و یا تصادفی، اتخاذ شوند، مسألهی بهینه سازی به دستههای مختلف حقیقی صحیح، باینری و تصادفی تقسیم بندی می شوند. برخی از الگوریتمها سعی در بهینه ساختن تابع با شروع از یک سری مقادیر برای متغیرها دارند. این الگوریتمها به آسانی در دام بهینههای محلی دچار میشوند؛ اما سریع به جواب میرسند . تعدادی روشهای تصادفی محاسباتی را برای یافتن احتمال مقادیر متغیرها بهکار می برند که سرعت پایین تری دارند، اما توفیق بیشتری در یافتن بهینهی مطلق دارند .
تک هدفه و چند هدفه: یک مسألهی بهینـه‌سازی تک هدفه، دارای تنها یک تابع هدف می باشد. اما در یک مســألهی چند هدفه، تعداد تابع هدفهایی که بهطور همزمان بهینه میشوند؛ بیش از یکی است. معمولاً در یک مسألهی بهینه‌سازی چند هدفه، با دادن اهمیت (وزن) به هر یک از توابع هدف و جمع بستن آنها، مسأله را تبدیل به یک مسألهی تک هدفه میکنند. حل مسائل بهینه‌سازی چند هدفه، به تنهایی مبحث مستقل و مهمی از حوزه بهینه‌سازی است.
یک بعدی و چند بعدی: اگر تنها یک متغیر وجود دارد، بهینه سازی یک بعدی است . یک مسأله که دارای متغیرهای بیشتر از واحد باشد، نیاز به انجام بهینهسازی چند بعدی است. بدیهی است که هرقدر تعداد متغیرها بیشتر باشد، بهینه سازی مشکل تر است. بهینه سازی چند بعدی عموماً با تقریب زدن به یک سری بهینهسازی یک بعدی انجام می شوند .
3-3-روشهای حل مسائل بهینهسازی
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم‌های دقیق و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند[39]. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد.
شکل 3-2 روشهای حل مسایل بهینه سازی.
روش ریاضی که زیر شاخه ای از این روش است، به دو دسته مبتنی بر مشتق (بردار گرادیان و ماتریـس هسیان تابع هدف) و مبـتنی بر جســتجو (در حقیقت از مشــتق در آن استفاده نمیشود) تقسیم میشود. در این روش اغلب گرادیان تابع هدف مورد استفاده قرار میگیرد. بنابراین، در جایی که تابع دارای عدم پیوستگی باشد دستیابی به این روش عملاً دچار مشکل میگردد. متأسفانه روشهای کلاسیک ریاضی دارای دو اشکال پایهای می باشند؛ نخست اینکه برای هر مسأله بایستی روش حل مخصوص آن بهکار گرفته شود. همچنین، اغلب نقطهی بهینهی محلی بهعنوان نقطهی بهینهی کلی در نظر گرفته میشود. دستهبندی این روش در شکل 3-2 نمایش داده شده است.
شکل 3-3 تقسیم بندی روش محاسباتی.
بر خلاف الگوریتم‌های دقیق، الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به دو دسته الگوریتم‌های ابتکاری و فرا ابتکاری تقسیم‌بندی می شوند.
در روشهای ابتکاری و فرا ابتکاری بر خلاف روشهای ریاضی، که دارای پایه و اساس ریاضی بوده و همگرایی الگوریتمهای آن اثبات میگردد، ممکن است همگرایی مستندی نداشته باشند. در حل مسایل بهینهسازی اگر تابع هدفی که قرار است نقطهی بهینه آن یافت شود، محدب یا مقعر نباشد (یعنی ماتریس هسیان تابع مذکور نامعین باشد)، در این صورت تقریباً هیچ الگوریتم ریاضی وجود ندارد که تضمین کند جواب بهینه سراسری مسأله همگراست. به این دلیل، همواره بر ایجاد روشهای مؤثرتر و کاراتر تأکید شده است. لذا، در طی 20 سال اخیر نوع جدیدی از الگوریتم تخمینی، با دستیابی به هدفی قابل استفادهتر، با عنوان الگوریتمهای ابتکاری و فرابتکاری، پایهریزی گردیده است. در این روش در زمان محدود، جوابی نزدیک به جواب بهینه بهدست میآید. باید در نظر داشت که اساس این روش جدید بر پایه روش شمارشی بنا نهاده شده است؛ با این تفاوت که از اطلاعات اضافی برای هدایت کردن مسیر جستجو استفاده می‌گردد. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آنها در بهینه‌های محلی و عدم قابلیت آنها برای کاربرد در مسائل مختلف است. الگوریتم‌های فرا ابتکاری یا متاهیوریستیک‌ها برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای مکانیزم‌های خروج از بهینه محلی می‌باشند و قابل کاربرد در طیف وسیعی از مسائل هستند.
توانایی حل مسائل بسیار پیچیدهتر از قابلیتهای دیگر آن میباشد. به طور عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند. مطالعات نشان داده است الگوریتمهای مبتنی بر رفتار گروهی موجودات زنده در مقایسه با دیگر روشهای بهینه سازی بر روی برخی از مسائل کارایی بهتری دارند به همین دلیل گرایش زیادی برای استفاده از این الگوریتمها وجود دارد. به هر حال، علی رغم وجود کارایی خوب، این روشها هنوز از مشکلات و معایبی رنج می برند که باعث کاهش کارایی آنها در برخی مسائل می شود. همگرایی زودرس، سکون و سرعت همگرایی پایین برخی از مشکلات اصلی این الگوریتم ها است.
فرآیند طراحی و پیاده‌سازی الگوریتم‌های فرا ابتکاری دارای سه مرحله‌ی متوالی است که هر کدام از آن‌ها دارای گام‌های مختلفی هستند[40]. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحله‌ی یک آماده‌سازی است که در آن باید شناخت دقیقی از مسأله‌ای که می‌خواهیم حل کنیم بهدست آوریم و اهداف طراحی الگوریتم فرا ابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسأله، به طور واضح و شفاف مشخص شود. مرحله‌ی بعدی، ساخت نام دارد. مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه گیری عملکرد و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن تنظیم پارامترها، تحلیل عملکرد و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.
معیارهای مختلفی برای طبقه‌بندی این الگوریتم‌ها استفاده میشود که در ادامه چند نمونه ذکر میشود:
مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتم‌های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند. از الگوریتم‌های متداول فراابتکاری مبتنی بر جمعیت می‌توان الگوریتم‌های تکاملی (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، …)، بهینه‌سازی کلونی مورچگان،کلونی زنبورها، روش بهینه‌سازی ازدحام ذرات و الگوریتم رقابت استعماری و از الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعه و الگوریتم تبرید شبیه‌سازی شده را نام برد.
الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فراابتکاری از طبیعت الهام گرفته شده‌اند. مانند الگوریتم خفاش یا کلونی مورچه ها، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشدهاند.
با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند به این معنا که این نوع الگوریتم‌ها از اطلاعات به دست آمده در حین جستجو استفاده نمی کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فرا ابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
قطعی و احتمالی: یک الگوریتم فرا ابتکاری قطعی نظیر جستجوی ممنوعه، مسآله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فرا ابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.
الگوریتمهای فراابتکاری در حل بسیاری از مسائل بهینه‌سازی در حوزه‌های مختلف کاربرد دارند. در ادامه به طور اجمالی چند نمونه از این الگوریتمها به اختصار معرفی میگردد. پس از آن به تفصیل الگوریتــم خفاش که یک الگوریتم فراابتکاری میباشد و همچنین اساس کار این رساله بر آن بنا گردیده است، مورد بررسی قرار خواهد گرفت.
3-3-1- بهینه سازی تودهی ذرات
بهینه سازی تودهی ذرات به وسیلهی کندی و ابرهارت ارائه شده است [41] . این روش ، از رفتارهای هوشمند پرندگان در یافتن غذا الگو برداری شده است . مانند الگوریتمهای هوش جمعی دیگر، PSO از مجموعهای از جوابهای ممکن استفاده میکند و تا زمانی که از روی این جوابها یک جواب بهینه به دست آید یا معیار خاتمه برآورده شود ، الگوریتم ادامه مییابد. در این الگوریتم هر جواب ممکن به وسیلهی یک ذره نشان داده می شود و یک تودهی ذرات، مجموعهای از ذرات میباشد . مسوولیت تکامل توده به یک ناحیهی بهینه بر عهدهی تساوی سرعت میباشد. این تساوی دربرگیرندهی سه مؤلفه میباشد : مؤلفهی ضریب سرعت ، مؤلفهی فردی ((pi و مؤلفهی اجتماعی (Pg). کل روش را میتوان به صورت یک الگوریتم رفتاری توزیع شده در نظر گرفت که یک جستجوی چند بعدی را انجام میدهد.