منبع پایان نامه ارشد درمورد بهینه سازی، خوشه بندی، نقاط بهینه

که در اکثر موراد برای m عدد 2 انتخاب میشود. اگر در فرمول فوق m را برابر 1 قرار دهیم تابع هدف خوشهبندی c میانگین (کلاسیک) غیرفازی بهدست میآید. در فرمول فوق نمونه ام ونماینده یا مرکز خوشه ام و تعداد نمونـهها میباشد. میـزان تعلق نمونه ام در خوشه ام را نشان می دهد. علامت ||*|| میزان تشابه (فاصله) نمونه با (از) مرکز خوشه میباشد که میتوان از هر تابعی که بیانگر تشابه نمونه و مرکز خوشه باشد، استفاده کرد. از روی میتوان یک ماتریس تعریف کرد که دارای سطر وستون میباشد و مؤلفههای آن هر مقداری بین صفر تا 1 را میتوانند اختیار کنند. اگر تمامی مؤلفههای ماتریس به صورت صفر و 1 باشند، الگوریتم مشابه c میانگین کلاسیک خواهد بود. با اینکه مؤلفه های ماتریس می توانند هر مقداری بین صفر تا 1 را اختیار کنند، اما مجموع مؤلفههای هر یک از ستونها باید برابر 1 باشد و داریم:
(2-9)
این شرط به این معنا است که مجموع تعلق هر نمونه به c خوشه باید برابر 1 باشد. برای بهدست آوردن فرمولهای مربوط به و باید تابع هدف تعریف شده، حداقل گردد. با استفاده از شرط فوق و برابر صفر قرار دادن مشتق تابع هدف خواهیم داشت:
(2-10)
با اسـتفاده از دو فرمول فوق، مراحل انجام الگوریتم خوشـهبندی c میانگین فازی بصورت زیر می باشد:
مرحلهی اول: مقدار دهی اولیه برایc، m و U، با توجه به قید 2-9.
مرحلهی دوم: مراکز خوشه ها با استفاده از فرمول 2-10 محاسبه شوند.
مرحلهی سوم: محاسبهی تابع هدف با توجه به فرمول 2-8. در صورتیکه از مقدار آستانهایکوچکتر است، الگوریتم خاتمه یابد در غیر اینصورت برو به مرحلهی دوم.
مرحلهی چهارم: محاسبهی مقدار جدید با استفاده از فرمول 2-11.
برای مشاهده عملکرد خوشهبندی فازی به مثال زیر توجه کنید. در شکل 2-6 یک توزیع یک بعدی از نمونههای ورودی آورده شده است.
شکل 2-6 توزیع یک بعدی نمونه ها.
اگر از الگوریتم c میانگین کلاسیک استفاده کنیم دادههای فوق به دو خوشهی مجزا تقسیم خواهند شد و هر نمونه تنها متعلق به یکی از خوشهها خواهد بود. بهعبارت دیگر، تابع تعلق هر نمونه مقدار صفر یا 1 خواهد داشت. نتیجهی خوشه بندی کلاسیک در شکل 2- 7نشان داده شده است:
شکل 27 خوشه بندی کلاسیک نمونه های ورودی.
در این شکل تابع تعلق مرتبط به خوشهی A را نشان میدهد. تابع تعلق خوشهی B متمم تابع تعلق A میباشد. همانطور که مشاهده میکنید نمونههای ورودی تنها به یکی از خوشهها تعلق دارند و بهعبارت، دیگر ماتریس U بهصورت باینری می باشد. حال اگر از خوشه بندی فازی استفاده گردد، همانطور که در شکل 2-8 مشاهده میکنید، تابع تعلق هموارتر است و مرز بین خوشهها بهطور قطع و یقین مشخص نشده است. بهعنوان مثال، نمونهای که با فلش مشخص شده است با درجه تعلق 0.2 به خوشهی A و با درجهی تعلق 0.8 به خوشهی B نسبت داده شده است.
شکل 2-8 خوشه بندی فازی نمونه ها.
در جدول 2-1 نقاط ضعف و قوت الگوریتم c میانگین فازی نشان داده شده است.
جدول22 معایب و محاسن الگوریتم c میانگین فازی.
نقاط قوت الگوریتم c میانگین فازی
نقاط ضعف الگوریتم c میانگین فازی
همگرایی همیشگی پاسخ
زمان محاسبات زیاد
بدون ناظر
وابسته به مقادیر اولیه
همگرا به کمینه های محلی
حساس به نویز
اگر معیار تشابه در تابع هدف بر اساس فاصله تعریف شود میتوان از تعاریف مختلفی که در مورد فاصله وجود دارد استفاده کرد که در زیر چند نمونه از این توابع آورده شده است.
جدول23 معیارهای تشابه بر اساس توابع فاصله مختلف.
فرمولها
توابع فاصله
فاصله اقلیدسی.
فاصله همینگ
فاصله چبیشف
فاصله مینک اوسکی
فاصله کانبرا
زاویه جدایی
فصل سوم: بهینهسازی بر مبنای الگوریتم خفاش
3-1- مقدمه
بهینهسازی یافتن بهترین جواب در خروجی یک تابع یا فرآیند، بهوسیلهی تغییر ورودیهای می باشد. واژهی بهترین بیان میدارد که بیش از یک جواب و راه حل برای مسأله وجود دارد که یافتن بهترین جواب (جواب بهینه) بستگی به مسألهی در دسترس، روش حل و خطای مجاز دارد[36].
بیت‌لر و دیگران (۱۹۷۹) بهینه‌سازی را چنین شرح می‌دهند : فعل بهینه‌ ساختن که کلمه قوی‌تری نسبت به بهبود می‌باشد عبارت است از دستیابی به بهینه و بهینه‌سازی اشاره به عمل بهینه ساختن دارد . بنابراین تئوری بهینه‌سازی شامل مطالعات کمی بهینه‌ها و روش یافتن آنها است . همچنین بهینه به عنوان یک واژه فنی دلالت بر اندازه‌گیری کمی و تحلیل ریاضی دارد در حالی که بهترین ، دارای دقت کمتر بوده و بیشتر برای امور روزمره استفاده می‌شود .
در بیشتر موارد آنچه که با هدف بهینه‌سازی انجام می‌دهیم بهبود است . بهینه‌سازی به دنبال بهبود عملکرد در رسیدن به نقطه یا نقاط بهینه است .
بهینه سازی مبتنی بر رفتار گروهی موجودات زنده به عنوان دستهای مهم از این الگوریتمها شناخته میشود که در برگیرندهی روشهای محاسباتی بدیعی است که قادر به حل مسائل بهینه سازی به شیوه ای مؤثر و قابل اعتماد می باشند[37].
روشهای بهینه سازی مبتنی بر رفتار گروهی موجودات زنده را میتوان در بازهی وسیعی از کاربردها استفاده کرد. به علت کارایی این روشها در پیدا کردن جوابهای رضایت بخش برای مسائل دینامیک و مشکل در زمان قابل قبول، در سالهای اخیر توجه زیادی به این روشها شده است. همه منظوره بودن این نوع از روشهای بهینه سازی باعث شده است آنها برای بازهی وسیعی از کاربردهای دنیای واقعی مناسب باشند. لیست زیر حوزههای اصلی کاربرد این دسته از الگوریتمها را نشان می دهد:
شبکه های سنسوری[38]، زمانبندی پروژه، خوشه بندی و دسته بندی، بهینه سازی ترکیبی، سیستم های فازی، پردازش سیگنال، تصویر، آنتن، زیست پزشکی، شبکه های مخابراتی، کنترل، طراحی، الکترونیک و الکترومغناطیس، ماشین و موتور، شناسایی خطا، فلزکاری، شبکه های عصبی، سیستم های قدرت، رباتیک، امنیت، ارتش، مدلسازی و پیش بینی.
از این رو، در این فصل ابتدا مبحث بهینـهسازی مورد بررسی اجمالی قرار گرفته و سپس تعدادی از روشهای بهینه سازی مرتبط با اهداف این پایاننامه ارائه میگردد. سپس از آن جا که هدف ما استفاده از الگوریتم خفاش به منظور انجام عمل خوشهبندی میباشد؛ به تشریح و بررسی این الگوریتم اقدام شده است.
3-2- شرح مسأله بهینهسازی
بهینهسازی یکی از زمینههای تحقیقاتی مهم در دهههای اخیر بوده است که نتیجه آن طراحی انواع مختلفی از الگوریتمها بوده است. بهینه‌سازی، تغییر دادن ورودی‌ها و خصوصیات یک دستگاه به نحوی است که بهترین خروجی یا نتیجه به دست آید. ورودی‌ها، متغیرهای فرآیند با تابع مورد بررسی هستند که با نام‌های تابع هدف 34، تابع هزینه35 و یا تابع برازندگی36 نامیده می‌شود. خروجی‌ نیز به صورت هزینه، سود و یا برازندگی تعریف می‌شود. غالب مسائل بهینه‌سازی به صورت کمینه‌سازی مقدار یک تابع هزینه در نظر گرفته شده‌اند. به راحتی می‌توان نشان داد که هر نوع مسأله‌ی بهینه‌سازی را می‌توان در قالب یک مسأله‌ی کمینه‌سازی تعریف نمود .شکل استاندارد مسألهی بهینه سازی به صورت زیر است:
به طوری که:
• ، تابع مورد نظر ما است که می خواهیم بر روی کمینه شود.
• محدودیت نابرابری نامیده می شود.
• محدودیت تساوی نامیده می شود.
طبق قرارداد، شکل استاندارد، یک مسأله به حداقل رساندن را توصیف می کند. یک مسأله به حداکثر رساندن می تواند با منفی کردن تابع هدف به دست آید.
به طور کلی توابع هدف به سه دسته تقسیم میشوند:
1. تابع هدف تفکیک‌ناپذیر37: یک تابع را تفکیک‌ناپذیر گویند اگر نتوان آن را به صورت جمع چند تابع جداگانه نوشت. پیدا کردن نقطهی بهینه‌ی سراسری توابع هدف غیرقابل تفکیک بسیار مشکل است.
2. تابع هدف چند وجهی38 : یک تابع چند وجهی است اگر 2 یا بیشتر از 2 نقطه بهینه‌ی محلی داشته باشد. پیداکردن نقطه‌ی بهینه‌ی سراسری این توابع بسیار سخت است و این پیچیدگی زمانی افزایش می‌یابد که نقاط بهینه‌ در کل فضای جستجو پخش شده باشند.
3. تابع هدف مشتق‌ناپذیر39: تابع هدفی مشتق‌ناپذیر است اگر در هر کدام از نقاط فضای جواب خود مشتق‌ناپذیر باشد.
مسائل بهینهسازی از دیدگاههای مختلف، به دســـتههای متفاوتی تقسیم میگردند. در شکل 3-1، برخی از این دستهبندیها نشان داده شده است. هیچکدام از این شاخهها به طور کامل مستقل از هم نیستند. برای مثال، یک مسألهی بهینه سازی دینامیک میتواند مقید یا غیر مقید باشد . به علاوه، تعدادی از متغیرها ممکن است گسسته و تعدادی دیگر پیوسته باشند.
در ادامه به توضیح مختصر راجع به این روشها میپردازیم.
شکل 3-1 دسته بندیهای متفاوت در مسایل بهینه سازی.
ایستا و پویا: بهینه سازی دینامیک به این معنی است که خروجی تابعی از زمان می باشد در حالی که استاتیک به معنی مستقل بودن بهینه سازی از تأثیر زمان می باشد. هنگامی که شما در نواحی شهر سکونت دارید، راههای مختلفی وجود دارد تا شما به مرکز برسید.
اما بهترین مسیر کدام است ؟ در نگاه اول ، ما با یک مسألهی بهینه سازی استاتیک سر و کار داریم و مسأله می تواند با استفاده از یک نقشه یا کیلومتر شمار یک اتومبیل حل شود. اما در واقع، این مسأله ساده نیست! زیرا کوتاهترین مسیر الزاماً سریع ترین مسیر نیست. یافتن سریعترین مسیر یک مسأله دینامیکی است که جواب به زمان روز، آب و هوا، حوادث و … بستگی دارد. برای یافتن بهترین جواب حل مسأله به صورت استاتیکی مشکل است اما با اضافه شدن بعد زمان امکان حل مسأله (به صورت دینامیکی) افزایش می یابد .
مقید و نامقید: متغیرها اغلب دارای محدودیت ها یا قیود هستند. در بهینه سازی غیر مقید، متغیرها مجاز هستند تا هر مقداری را دارا باشند. اما در بهینه سازی مقید، متغیرها فقط مجاز به دارا بودن مقادیری هستند که منافاتی با قیود نداشته باشند. یک متغیر مقید اغلب به یک متغیر غیر مقید تبدیل می شود . بیشتر روشهای بهینه سازی عدد40 بهترین جواب را برای متغیرهای غیر مقید ارائه می دهند. یک مثال ساده بهینه سازی همراه با قید بصورت زیر می باشد :
کمینه سازی تابع f(x) روی بازه را در نظر بگیرید .متغیر x با تغییر متغیر x = sin(u) تبدیل به متغیر غیر مقید u می گردد . و حل مسأله با کمینه سازی f(sin(u)) برای هر مقدار از u بدست می آید .
گسسته و پیوسته: بهینه سازی همچنین می تواند بصورت متغیرهای مجزا (گسسته) یا پیوسته، تفکیک گردد. متغیرهای مجزا تنها شامل یک عدد محدود از مقادیر ممکن می باشند، در حالی که متغیرهای پیوسته دارای اعداد نامحدودی از مقادیر ممکن هستند. اگر ما قصد داشته باشیم که به مجموعهای از اهداف دست یابیم، بهینه سازی مجزا به کار گرفته خواهد شد. در حالی که اگر ما بخواهیم مقدار کمینه f(x) را بر روی دامنهای از اعداد حقیقی بیابیم با یک مسأله پیوسته روبهرو هستیم.
خطی41 و غیرخطی42 : هنگامی که معادلات و قیود بصورت خطی باشند مسأله ، مسألهی بهینه سازی خطی است و چنانچه معادلات و قیود غیر خطی باشند با مسألهی غیر خطی سر و کار داریم.
تصادفی و غیر تصادفی: در یک مسئله بهینه سازی، بسته به آنکه متغیرهای مسأله مقادیر حقیقی، صحیح، باینری و یا تصادفی، اتخاذ شوند، مسألهی بهینه سازی به دستههای مختلف حقیقی صحیح، باینری و تصادفی تقسیم بندی می شوند. برخی از الگوریتمها سعی در بهینه ساختن تابع با شروع از یک سری مقادیر برای متغیرها دارند. این الگوریتمها به آسانی در دام بهینههای محلی دچار میشوند؛ اما سریع به جواب

مطلب مرتبط :   پایان نامه رایگان با موضوعقانون اساسی، محیط زیست، استاندارد، عدالت اجتماعی

دیدگاهتان را بنویسید