شبکه های سنسوری[۳۸]، زمانبندی پروژه، خوشه بندی و دسته بندی، بهینه سازی ترکیبی، سیستم های فازی، پردازش سیگنال، تصویر، آنتن، زیست پزشکی، شبکه های مخابراتی، کنترل، طراحی، الکترونیک و الکترومغناطیس، ماشین و موتور، شناسایی خطا، فلزکاری، شبکه های عصبی، سیستم های قدرت، رباتیک، امنیت، ارتش، مدلسازی و پیش بینی.
از این رو، در این فصل ابتدا مبحث بهینـهسازی مورد بررسی اجمالی قرار گرفته و سپس تعدادی از روشهای بهینه سازی مرتبط با اهداف این پایان نامه ارائه میگردد. سپس از آن جا که هدف ما استفاده از الگوریتم خفاش به منظور انجام عمل خوشهبندی میباشد؛ به تشریح و بررسی این الگوریتم اقدام شده است.
۳-۲- شرح مسأله بهینهسازی
بهینهسازی یکی از زمینه های تحقیقاتی مهم در دهههای اخیر بوده است که نتیجه آن طراحی انواع مختلفی از الگوریتمها بوده است. بهینهسازی، تغییر دادن ورودیها و خصوصیات یک دستگاه به نحوی است که بهترین خروجی یا نتیجه به دست آید. ورودیها، متغیرهای فرایند با تابع مورد بررسی هستند که با نامهای تابع هدف [۳۴]، تابع هزینه[۳۵] و یا تابع برازندگی[۳۶] نامیده میشود. خروجی نیز به صورت هزینه، سود و یا برازندگی تعریف میشود. غالب مسائل بهینهسازی به صورت کمینهسازی مقدار یک تابع هزینه در نظر گرفته شدهاند. به راحتی میتوان نشان داد که هر نوع مسألهی بهینهسازی را میتوان در قالب یک مسألهی کمینهسازی تعریف نمود .شکل استاندارد مسأله بهینه سازی به صورت زیر است:
به طوری که:
-
- ، تابع مورد نظر ما است که می خواهیم بر روی کمینه شود.
-
- محدودیت نابرابری نامیده می شود.
-
- محدودیت تساوی نامیده می شود.
طبق قرارداد، شکل استاندارد، یک مسأله به حداقل رساندن را توصیف می کند. یک مسأله به حداکثر رساندن می تواند با منفی کردن تابع هدف به دست آید.
به طور کلی توابع هدف به سه دسته تقسیم میشوند:
-
- تابع هدف تفکیکناپذیر[۳۷]: یک تابع را تفکیکناپذیر گویند اگر نتوان آن را به صورت جمع چند تابع جداگانه نوشت. پیدا کردن نقطهی بهینهی سراسری توابع هدف غیرقابل تفکیک بسیار مشکل است.
-
- تابع هدف چند وجهی[۳۸] : یک تابع چند وجهی است اگر ۲ یا بیشتر از ۲ نقطه بهینهی محلی داشته باشد. پیداکردن نقطهی بهینهی سراسری این توابع بسیار سخت است و این پیچیدگی زمانی افزایش مییابد که نقاط بهینه در کل فضای جستجو پخش شده باشند.
-
- تابع هدف مشتقناپذیر[۳۹]: تابع هدفی مشتقناپذیر است اگر در هر کدام از نقاط فضای جواب خود مشتقناپذیر باشد.
مسائل بهینهسازی از دیدگاههای مختلف، به دســـتههای متفاوتی تقسیم میگردند. در شکل ۳-۱، برخی از این دستهبندیها نشان داده شده است. هیچکدام از این شاخهها به طور کامل مستقل از هم نیستند. برای مثال، یک مسأله بهینه سازی دینامیک می تواند مقید یا غیر مقید باشد . به علاوه، تعدادی از متغیرها ممکن است گسسته و تعدادی دیگر پیوسته باشند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در ادامه به توضیح مختصر راجع به این روشها میپردازیم.
شکل ۳-۱ دسته بندیهای متفاوت در مسایل بهینه سازی.
ایستا و پویا: بهینه سازی دینامیک به این معنی است که خروجی تابعی از زمان می باشد در حالی که استاتیک به معنی مستقل بودن بهینه سازی از تأثیر زمان می باشد. هنگامی که شما در نواحی شهر سکونت دارید، راههای مختلفی وجود دارد تا شما به مرکز برسید.
اما بهترین مسیر کدام است ؟ در نگاه اول ، ما با یک مسأله بهینه سازی استاتیک سر و کار داریم و مسأله می تواند با بهره گرفتن از یک نقشه یا کیلومتر شمار یک اتومبیل حل شود. اما در واقع، این مسأله ساده نیست! زیرا کوتاهترین مسیر الزاماً سریع ترین مسیر نیست. یافتن سریعترین مسیر یک مسأله دینامیکی است که جواب به زمان روز، آب و هوا، حوادث و … بستگی دارد. برای یافتن بهترین جواب حل مسأله به صورت استاتیکی مشکل است اما با اضافه شدن بعد زمان امکان حل مسأله (به صورت دینامیکی) افزایش می یابد .
مقید و نامقید: متغیرها اغلب دارای محدودیت ها یا قیود هستند. در بهینه سازی غیر مقید، متغیرها مجاز هستند تا هر مقداری را دارا باشند. اما در بهینه سازی مقید، متغیرها فقط مجاز به دارا بودن مقادیری هستند که منافاتی با قیود نداشته باشند. یک متغیر مقید اغلب به یک متغیر غیر مقید تبدیل می شود . بیشتر روشهای بهینه سازی عدد[۴۰] بهترین جواب را برای متغیرهای غیر مقید ارائه می دهند. یک مثال ساده بهینه سازی همراه با قید بصورت زیر می باشد :
کمینه سازی تابع f(x) روی بازه را در نظر بگیرید .متغیر x با تغییر متغیر x = sin(u) تبدیل به متغیر غیر مقید u می گردد . و حل مسأله با کمینه سازی f(sin(u)) برای هر مقدار از u بدست می آید .
گسسته و پیوسته: بهینه سازی همچنین می تواند بصورت متغیرهای مجزا (گسسته) یا پیوسته، تفکیک گردد. متغیرهای مجزا تنها شامل یک عدد محدود از مقادیر ممکن می باشند، در حالی که متغیرهای پیوسته دارای اعداد نامحدودی از مقادیر ممکن هستند. اگر ما قصد داشته باشیم که به مجموعه ای از اهداف دست یابیم، بهینه سازی مجزا به کار گرفته خواهد شد. در حالی که اگر ما بخواهیم مقدار کمینه f(x) را بر روی دامنهای از اعداد حقیقی بیابیم با یک مسأله پیوسته روبهرو هستیم.
خطی[۴۱] و غیرخطی[۴۲] : هنگامی که معادلات و قیود بصورت خطی باشند مسأله ، مسأله بهینه سازی خطی است و چنانچه معادلات و قیود غیر خطی باشند با مسأله غیر خطی سر و کار داریم.
تصادفی و غیر تصادفی: در یک مسئله بهینه سازی، بسته به آنکه متغیرهای مسأله مقادیر حقیقی، صحیح، باینری و یا تصادفی، اتخاذ شوند، مسأله بهینه سازی به دستههای مختلف حقیقی صحیح، باینری و تصادفی تقسیم بندی می شوند. برخی از الگوریتمها سعی در بهینه ساختن تابع با شروع از یک سری مقادیر برای متغیرها دارند. این الگوریتمها به آسانی در دام بهینههای محلی دچار میشوند؛ اما سریع به جواب میرسند . تعدادی روشهای تصادفی محاسباتی را برای یافتن احتمال مقادیر متغیرها بهکار می برند که سرعت پایین تری دارند، اما توفیق بیشتری در یافتن بهینه مطلق دارند .
تک هدفه و چند هدفه: یک مسأله بهینـهسازی تک هدفه، دارای تنها یک تابع هدف می باشد. اما در یک مســألهی چند هدفه، تعداد تابع هدفهایی که به طور همزمان بهینه میشوند؛ بیش از یکی است. معمولاً در یک مسأله بهینهسازی چند هدفه، با دادن اهمیت (وزن) به هر یک از توابع هدف و جمع بستن آنها، مسأله را تبدیل به یک مسأله تک هدفه می کنند. حل مسائل بهینهسازی چند هدفه، به تنهایی مبحث مستقل و مهمی از حوزه بهینهسازی است.
یک بعدی و چند بعدی: اگر تنها یک متغیر وجود دارد، بهینه سازی یک بعدی است . یک مسأله که دارای متغیرهای بیشتر از واحد باشد، نیاز به انجام بهینهسازی چند بعدی است. بدیهی است که هرقدر تعداد متغیرها بیشتر باشد، بهینه سازی مشکل تر است. بهینه سازی چند بعدی عموماً با تقریب زدن به یک سری بهینهسازی یک بعدی انجام می شوند .
۳-۳-روشهای حل مسائل بهینهسازی
روشها و الگوریتمهای بهینهسازی به دو دسته الگوریتمهای دقیق[۴۳] و الگوریتمهای تقریبی[۴۴] تقسیمبندی میشوند[۳۹]. الگوریتمهای دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش مییابد.
شکل ۳-۲ روشهای حل مسایل بهینه سازی.
روش ریاضی که زیر شاخه ای از این روش است، به دو دسته مبتنی بر مشتق (بردار گرادیان و ماتریـس هسیان تابع هدف) و مبـتنی بر جســتجو (در حقیقت از مشــتق در آن استفاده نمی شود) تقسیم می شود. در این روش اغلب گرادیان تابع هدف مورد استفاده قرار میگیرد. بنابراین، در جایی که تابع دارای عدم پیوستگی باشد دستیابی به این روش عملاً دچار مشکل میگردد. متأسفانه روشهای کلاسیک ریاضی دارای دو اشکال پایهای می باشند؛ نخست اینکه برای هر مسأله بایستی روش حل مخصوص آن بهکار گرفته شود. همچنین، اغلب نقطهی بهینه محلی بهعنوان نقطهی بهینه کلی در نظر گرفته می شود. دستهبندی این روش در شکل ۳-۲ نمایش داده شده است.
شکل ۳-۳ تقسیم بندی روش محاسباتی.
بر خلاف الگوریتمهای دقیق، الگوریتمهای تقریبی قادر به یافتن جوابهای خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینهسازی سخت هستند. الگوریتمهای تقریبی نیز به دو دسته الگوریتمهای ابتکاری[۴۵] و فرا ابتکاری[۴۶] تقسیمبندی می شوند.
در روشهای ابتکاری و فرا ابتکاری بر خلاف روشهای ریاضی، که دارای پایه و اساس ریاضی بوده و همگرایی الگوریتمهای آن اثبات میگردد، ممکن است همگرایی مستندی نداشته باشند. در حل مسایل بهینهسازی اگر تابع هدفی که قرار است نقطهی بهینه آن یافت شود، محدب یا مقعر نباشد (یعنی ماتریس هسیان تابع مذکور نامعین باشد)، در این صورت تقریباً هیچ الگوریتم ریاضی وجود ندارد که تضمین کند جواب بهینه سراسری مسأله همگراست. به این دلیل، همواره بر ایجاد روشهای مؤثرتر و کاراتر تأکید شده است. لذا، در طی ۲۰ سال اخیر نوع جدیدی از الگوریتم تخمینی، با دستیابی به هدفی قابل استفادهتر، با عنوان الگوریتمهای ابتکاری و فرابتکاری، پایهریزی گردیده است. در این روش در زمان محدود، جوابی نزدیک به جواب بهینه بهدست می آید. باید در نظر داشت که اساس این روش جدید بر پایه روش شمارشی بنا نهاده شده است؛ با این تفاوت که از اطلاعات اضافی برای هدایت کردن مسیر جستجو استفاده میگردد. دو مشکل اصلی الگوریتمهای ابتکاری، قرار گرفتن آنها در بهینههای محلی و عدم قابلیت آنها برای کاربرد در مسائل مختلف است. الگوریتمهای فرا ابتکاری یا متاهیوریستیکها برای حل این مشکلات الگوریتمهای ابتکاری ارائه شدهاند. در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتمهای بهینهسازی تقریبی هستند که دارای مکانیزمهای خروج از بهینه محلی میباشند و قابل کاربرد در طیف وسیعی از مسائل هستند.
[دوشنبه 1400-09-29] [ 06:00:00 ق.ظ ]
|