شبکه های سنسوری[۳۸]، زمان­بندی پروژه، خوشه بندی و دسته بندی، بهینه سازی ترکیبی، سیستم های فازی، پردازش سیگنال، تصویر، آنتن، زیست پزشکی، شبکه های مخابراتی، کنترل، طراحی، الکترونیک و الکترومغناطیس، ماشین و موتور، شناسایی خطا، فلزکاری، شبکه های عصبی، سیستم های قدرت، رباتیک، امنیت، ارتش، مدل­سازی و پیش بینی.
از این رو، در این فصل ابتدا مبحث بهینـه­سازی مورد بررسی اجمالی قرار گرفته و سپس تعدادی از روش­های بهینه سازی مرتبط با اهداف این پایان نامه ارائه می­گردد. سپس از آن جا که هدف ما استفاده از الگوریتم خفاش به ­منظور انجام عمل خوشه­بندی می­باشد؛ به تشریح و بررسی این الگوریتم اقدام شده است.
۳-۲- شرح مسأله بهینه­سازی
بهینه­سازی یکی از زمینه ­های تحقیقاتی مهم در دهه­های اخیر بوده است که نتیجه آن طراحی انواع مختلفی از الگوریتم­ها بوده است. بهینه‌سازی، تغییر دادن ورودی‌ها و خصوصیات یک دستگاه به نحوی است که بهترین خروجی یا نتیجه به دست آید. ورودی‌ها، متغیرهای فرایند با تابع مورد بررسی هستند که با نام‌های تابع هدف ^[۳۴]، تابع هزینه^[۳۵] و یا تابع برازندگی^[۳۶] نامیده می‌شود. خروجی‌ نیز به صورت هزینه، سود و یا برازندگی تعریف می‌شود. غالب مسائل بهینه‌سازی به صورت کمینه‌سازی مقدار یک تابع هزینه در نظر گرفته شده‌اند. به راحتی می‌توان نشان داد که هر نوع مسأله‌ی بهینه‌سازی را می‌توان در قالب یک مسأله‌ی کمینه‌سازی تعریف نمود .شکل استاندارد مسأله­ بهینه سازی به صورت زیر است:

به طوری که:

• •  ، تابع مورد نظر ما است که می خواهیم بر روی  کمینه شود.

• •  محدودیت نابرابری نامیده می شود.

• •  محدودیت تساوی نامیده می شود.

طبق قرارداد، شکل استاندارد، یک مسأله به حداقل رساندن را توصیف می کند. یک مسأله به حداکثر رساندن می تواند با منفی کردن تابع هدف به دست آید.
به طور کلی توابع هدف به سه دسته تقسیم می­شوند:

1. 1. تابع هدف تفکیک‌ناپذیر^[۳۷]: یک تابع را تفکیک‌ناپذیر گویند اگر نتوان آن را به صورت جمع چند تابع جداگانه نوشت. پیدا کردن نقطه­ی بهینه‌ی سراسری توابع هدف غیرقابل تفکیک بسیار مشکل است.

1. 1. تابع هدف چند ­وجهی^[۳۸] : یک تابع چند ­وجهی است اگر ۲ یا بیشتر از ۲ نقطه بهینه‌ی محلی داشته باشد. پیداکردن نقطه‌ی بهینه‌ی سراسری این توابع بسیار سخت است و این پیچیدگی زمانی افزایش می‌یابد که نقاط بهینه‌ در کل فضای جستجو پخش شده باشند.

1. 1. تابع هدف مشتق‌ناپذیر^[۳۹]: تابع هدفی مشتق‌ناپذیر است اگر در هر کدام از نقاط فضای جواب خود مشتق‌ناپذیر باشد.

مسائل بهینه­سازی از دیدگا­ههای مختلف، به دســـته­های متفاوتی تقسیم می­گردند. در شکل ۳-۱، برخی از این دسته­بندی­ها نشان داده شده است. هیچ­کدام از این شاخه­ها به طور کامل مستقل از هم نیستند. برای مثال، یک مسأله­ بهینه سازی دینامیک می ­تواند مقید یا غیر مقید باشد . به علاوه، تعدادی از متغیرها ممکن است گسسته و تعدادی دیگر پیوسته باشند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

در ادامه به توضیح مختصر راجع به این روش­ها می­پردازیم.
شکل ۳-۱ دسته ­بندی­های متفاوت در مسایل بهینه ­سازی.
ایستا و پویا: بهینه سازی دینامیک به این معنی است که خروجی تابعی از زمان می باشد در حالی که استاتیک به معنی مستقل بودن بهینه سازی از تأثیر زمان می باشد. هنگامی که شما در نواحی شهر سکونت دارید، راه­های مختلفی وجود دارد تا شما به مرکز برسید.
اما بهترین مسیر کدام است ؟ در نگاه اول ، ما با یک مسأله­ بهینه سازی استاتیک سر و کار داریم و مسأله می تواند با بهره گرفتن از یک نقشه یا کیلومتر شمار یک اتومبیل حل شود. اما در واقع، این مسأله ساده نیست! زیرا کوتاه­ترین مسیر الزاماً سریع ترین مسیر نیست. یافتن سریع­ترین مسیر یک مسأله دینامیکی است که جواب به زمان روز، آب و هوا، حوادث و … بستگی دارد. برای یافتن بهترین جواب حل مسأله به صورت استاتیکی مشکل است اما با اضافه شدن بعد زمان امکان حل مسأله (به صورت دینامیکی) افزایش می یابد .
مقید و نامقید: متغیرها اغلب دارای محدودیت ها یا قیود هستند. در بهینه سازی غیر مقید، متغیرها مجاز هستند تا هر مقداری را دارا باشند. اما در بهینه سازی مقید، متغیرها فقط مجاز به دارا بودن مقادیری هستند که منافاتی با قیود نداشته باشند. یک متغیر مقید اغلب به یک متغیر غیر مقید تبدیل می شود . بیشتر روش­های بهینه سازی عدد^[۴۰] بهترین جواب را برای متغیرهای غیر مقید ارائه می دهند. یک مثال ساده بهینه سازی همراه با قید بصورت زیر می باشد :
کمینه سازی تابع f(x) روی بازه  را در نظر بگیرید .متغیر x با تغییر متغیر x = sin(u) تبدیل به متغیر غیر مقید u می گردد . و حل مسأله با کمینه سازی f(sin(u)) برای هر مقدار از u بدست می آید .
گسسته و پیوسته: بهینه سازی هم­چنین می تواند بصورت متغیرهای مجزا (گسسته) یا پیوسته، تفکیک گردد. متغیرهای مجزا تنها شامل یک عدد محدود از مقادیر ممکن می باشند، در حالی که متغیرهای پیوسته دارای اعداد نامحدودی از مقادیر ممکن هستند. اگر ما قصد داشته باشیم که به مجموعه ­ای از اهداف دست یابیم، بهینه سازی مجزا به کار گرفته خواهد شد. در حالی که اگر ما بخواهیم مقدار کمینه f(x) را بر روی دامنه­ای از اعداد حقیقی بیابیم با یک مسأله پیوسته رو­به­رو هستیم.
خطی^[۴۱] و غیرخطی^[۴۲] : هنگامی که معادلات و قیود بصورت خطی باشند مسأله ، مسأله­ بهینه سازی خطی است و چنانچه معادلات و قیود غیر خطی باشند با مسأله­ غیر خطی سر و کار داریم.
تصادفی و غیر تصادفی: در یک مسئله بهینه سازی، بسته به آن­که متغیرهای مسأله مقادیر حقیقی، صحیح، باینری و یا تصادفی، اتخاذ شوند، مسأله­ بهینه سازی به دسته­های مختلف حقیقی صحیح، باینری و تصادفی تقسیم بندی می شوند. برخی از الگوریتم­ها سعی در بهینه ساختن تابع با شروع از یک سری مقادیر برای متغیرها دارند. این الگوریتم­ها به آسانی در دام بهینه­های محلی دچار می­شوند؛ اما سریع به جواب می­رسند . تعدادی روش­های تصادفی محاسباتی را برای یافتن احتمال مقادیر متغیرها به­کار می برند که سرعت پایین تری دارند، اما توفیق بیشتری در یافتن بهینه­ مطلق دارند .
تک هدفه و چند هدفه: یک مسأله­ بهینـه‌سازی تک هدفه، دارای تنها یک تابع هدف می باشد. اما در یک مســأله­ی چند هدفه، تعداد تابع هدف­هایی که به­ طور هم­زمان بهینه می­شوند؛ بیش از یکی است. معمولاً در یک مسأله­ بهینه‌سازی چند هدفه، با دادن اهمیت (وزن) به هر یک از توابع هدف و جمع بستن آن­ها، مسأله را تبدیل به یک مسأله­ تک هدفه می­ کنند. حل مسائل بهینه‌سازی چند هدفه، به تنهایی مبحث مستقل و مهمی از حوزه بهینه‌سازی است.
یک بعدی و چند بعدی: اگر تنها یک متغیر وجود دارد، بهینه سازی یک بعدی است . یک مسأله که دارای متغیرهای بیشتر از واحد باشد، نیاز به انجام بهینه­سازی چند بعدی است. بدیهی است که هرقدر تعداد متغیرها بیشتر باشد، بهینه سازی مشکل تر است. بهینه سازی چند بعدی عموماً با تقریب زدن به یک سری بهینه­سازی یک بعدی انجام می شوند .
۳-۳-روش­های حل مسائل بهینه­سازی
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم‌های دقیق^[۴۳] و الگوریتم‌های تقریبی^[۴۴] تقسیم‌بندی می‌شوند[۳۹]. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد.

شکل ۳-۲ روش­های حل مسایل بهینه ­سازی.
روش­ ریاضی که زیر شاخه ای از این روش است، به دو دسته مبتنی بر مشتق (بردار گرادیان و ماتریـس هسیان تابع هدف) و مبـتنی بر جســتجو (در حقیقت از مشــتق در آن استفاده نمی­ شود) تقسیم می­ شود. در این روش اغلب گرادیان تابع هدف مورد استفاده قرار می­گیرد. بنابراین، در جایی که تابع دارای عدم پیوستگی باشد دستیابی به این روش عملاً دچار مشکل می­گردد. متأسفانه روش­های کلاسیک ریاضی دارای دو اشکال پایه­ای می ­باشند؛ نخست این­که برای هر مسأله بایستی روش حل مخصوص آن به­کار گرفته شود. هم­چنین، اغلب نقطه­ی بهینه­ محلی به­عنوان نقطه­ی بهینه­ کلی در نظر گرفته می­ شود. دسته­بندی این روش در شکل ۳-۲ نمایش داده شده است.

شکل ۳-۳ تقسیم بندی روش محاسباتی.
بر خلاف الگوریتم‌های دقیق، الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به دو دسته الگوریتم‌های ابتکاری^[۴۵] و فرا ابتکاری^[۴۶] تقسیم‌بندی می شوند.
در روش­های ابتکاری و فرا ابتکاری بر خلاف روش­های ریاضی، که دارای پایه و اساس ریاضی بوده و همگرایی الگوریتم­های آن اثبات می­گردد، ممکن است همگرایی مستندی نداشته باشند. در حل مسایل بهینه­سازی اگر تابع هدفی که قرار است نقطه­ی بهینه آن یافت شود، محدب یا مقعر نباشد (یعنی ماتریس هسیان تابع مذکور نامعین باشد)، در این صورت تقریباً هیچ الگوریتم ریاضی وجود ندارد که تضمین کند جواب بهینه سراسری مسأله همگراست. به این دلیل، همواره بر ایجاد روش­های مؤثرتر و کاراتر تأکید شده است. لذا، در طی ۲۰ سال اخیر نوع جدیدی از الگوریتم تخمینی، با دستیابی به هدفی قابل استفاده­تر، با عنوان الگوریتم­های ابتکاری و فرابتکاری، پایه­ریزی گردیده است. در این روش در زمان محدود، جوابی نزدیک به جواب بهینه به­دست می ­آید. باید در نظر داشت که اساس این روش جدید بر پایه روش شمارشی بنا نهاده شده است؛ با این تفاوت که از اطلاعات اضافی برای هدایت کردن مسیر جستجو استفاده می‌گردد. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آن­ها در بهینه‌های محلی و عدم قابلیت آن­ها برای کاربرد در مسائل مختلف است. الگوریتم‌های فرا ابتکاری یا متاهیوریستیک‌ها برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فرا­ابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای مکانیزم‌های خروج از بهینه محلی می‌باشند و قابل کاربرد در طیف وسیعی از مسائل هستند.