منبع پایان نامه ارشد درمورد جستجوی محلی، خوشه بندی، شبیه سازی

5-2- تابع Schewefel
نکته مهم در مورد این تابع آن است که بهینه‌ی سراسری آن در مرکز تابع قرار ندارد و علاوه بر این دارای تعداد زیادی بهینه‌های محلی است. شکل (3-9)، نمایش سه بعدی گرافیکی تابع را نشان می‌دهد. الگوریتم‌ها باید پراکندگی خوبی در اعضای جمعیت خود به وجود آورند تا بتوانند به بهینه‌ی سراسری تابع که در یکی از گوشههای فضای جستجو قرار دارد، دست یابند.
ب)
الف)
شکل 3-9 الف) نماش سه بعدی تابع Schewefel ب) نمایش contour تابع Schewefel
3-5-3- تابع Rastragin
این تابع نمونهای از توابع چندوجهی غیر خطی و غیر محدب است .شکل (3-10)، نمایش سه بعدی گرافیکی تابع را نشان می‌دهد. . ضریب کسینوسی موجود دراین تابع، بهینه‌های محلی زیادی تولید می‌کند. این مسأله و وجود فضای جستجوی گسترده از سوی دیگر، تابع Rastragin را به یک مسأله‌ی پیچیده برای حل تبدیل کرده است. یک الگوریتم بهینه‌سازی باید تعادل بسیار هوشمندی را بین شناسایی و بهره‌برداری ایجاد کند و از طرفی دارای پراکندگی مناسبی در جمعیت خود باشد تا بتواند بر این مسأله غلبه کند[51].
ب)
الف)
شکل 3-10 الف) نماش سه بعدی تابع Rastragin ب) نمایش contour تابع Rastragin
3-5-4- تابع Ackley
این تابع، یک تابع چندوجهی می‌باشد و دارای یک بهینه‌ی سراسری است که در مکانی باریک قرار دارد. چندین بهینه‌ی محلی نیز در نواحی کم عمق اطراف بهینه‌ی سراسری وجود دارد. کم عمق بودن نواحی باعث می‌شود تا الگوریتم شانس بیشتری برای خارج‌شدن از آن‌ها و رفتن به سمت بهینه‌ی سراسری داشته باشد. شکل (3-11)، نمایش سه بعدی گرافیکی تابع Ackley را نشان می‌دهد. در مقایسه با توابع دیگر، این تابع نسبتاً ساده‌تر است .
ب)
الف)
شکل3-11 الف) نماش سه بعدی تابع Ackley ب) نمایش contour تابع Ackley
3-5-5- تابع Greiwank
این تابع بهطور گسترده برای تست الگوریتمهای بهینه‌سازی بهکار میرود. شکل (3-12)، نمایش سه بعدی گرافیکی تابع Greiwank را به همراه contour آن نشان می‌دهد. این تابع دارای تعداد زیادی بهینه‌ی محلی می‌باشد که به طور منظم پراکنده شده‌اند. مؤلفه‌ی دوم باعث ایجاد وابستگی بین متغیرهای کنترلی می‌شود، لذا، این تابع را به یک مسأله‌ی پیچیده تبدیل می‌کند. یک الگوریتم باید تعادل و توازن بسیار سازنده بین شناسایی و کشف برقرار کند تا بتواند خود را به بهینه‌ی سراسری نزدیک کند[52].
ب)
الف)
شکل3-12 الف) نماش سه بعدی تابع Greiwank ب) نمایش contour تابع Greiwank
فصل چهارم: الگوریتم پیشنهادی
4-1- مقدمه
همانطور که قبلاً اشاره گردید، روشهای مبتنی بر رفتار گروهی موجودات زنده در مقایسه با دیگر روشهای بهینهسازی بر روی برخی مسائل دارای کارایی بهتری میباشند . به همین دلیل، گرایش زیادی برای استفاده از این روشها وجود دارد. در این تحقیق از روش جدیدی مبتنی بر ترکیب دو الگوریـتم خفاش وFuzzy c-means ، برای خوشــهبندی اطلاعات استفاده خواهد شد. در واقع هدف این است که دادههای موجود را بتوان بهنحوی با حداقل خطا خوشهبندی نمود. در این راستا، سعی بر آن است تا مزایای هر دو الگوریتم را به کار گرفته و دادهها را به گونهای خوشه بندی کنیم که حداکثر شباهت بین دادههای یک گروه برقرار باشد و از طرفی دادههای موجود در گروههای مجزا کمترین شباهت را داشته باشند.
روش Fuzzy c-means در کنار مزایایی چون همگرا یی و بدون نظارت بودن، معایبی نیز دارد. این معایب را به اختصار میتوان به صورت زیر بیان کرد:
ت وابستگی به شرایط اولیه: انتخاب مقادیر اولیه در این روش پاسخ نهایی را دستخوش تغییرات قرار میدهد و خوشههای بهدست آمده بنا به مقادیر اولیه بسیار متفاوت خواهند بود.
همگرایی به نقاط بهینه محلی
جهت مرتفع نمودن این معایب، در تحقیقات اخیر ایدههای متفاوتی بیان گردیده است که تا حد قابل قبولی کارساز بوده است. از کارهای انجام شده میتوان به ترکیب این الگوریتم با الگوریتمهای اجتماع پرندگان، الگوریتم ممتیک، ژنتیک و آبکاری فولاد اشاره کرد. در این پایان نامه جهت رفع معایب ذکر شده در الگوریتم Fuzzy c-means از ترکیب این الگوریتم با الگوریتم خفاش استفاده شده است.
4-2- خوشه بندی اطلاعات مبتنی بر روش ترکیبی پیشنهادی
در اینجا کاربرد الگوریتم پیشنهادی که مبتنی بر ترکیب الگوریتم بهبود یافته رقابت خفاش و Fuzzy c-means میباشد جهت خوشهبندی اطلاعات توضیح داده خواهد شد. هدف این است که دادههای موجود درخوشههای مناسب دستهبندی شده و در این راستا نیز مراکز خوشه و ماتریس تعلق تعیین گردند. مراحل این روش در ادامه ذکر خواهند شد.
مرحلهی اول: تولید جمعیت اولیه
ابتدا جمعیت اولیه به صورت تصادفی تولید میگردد.
هرX، نمایانگر یک خفاش میباشد. هر خفاش در ابتدا در یک موقعیت تصادفی sol(Xi)
centerنشان دهندهی مرکز خوشه است که از موقعیت خفاشها گرفته شده است. c و d و N به ترتیب تعداد خوشهها، بعد مراکز خوشه و تعداد جمعیت خفاشها می باشد.
مرحلهی دوم: تولید بردار متضاد برای هر عضو از اعضای جمعیت
مرحلهی سوم: ارزیابی تابع هدف
ابتدا ماتریس تعلق به صورت تصادفی مقداردهی اولیه میشود. سپس تابع هدف یکبار با استفاده از Xi به عنوان مرکز خوشهها و بار دیگر با استفاده از ، برای هر دیتای ورودی، محاسبه میگردد. . حال اگر دارای تابع هدف بهتری نسبت به باشد جایگزین آن می‌شود.
n، تعداد دادههای ورودی است و v مرکز خوشه است.
مرحلهی چهارم: مرتبسازی جمعیت اولیه بر اساس تابع هدف
جمعیت، براساس مقدار تابع هدف به صورت صعودی مرتب میشود. سپس موقعیت خفاشی که تابع هدف را مینیمم میکند، به عنوان بهترین موقعیت در نظر گرفته میشود.
* مرحلهی پنجم: انتخاب یکی از دو استراتژی جهش
در ابتدای هر تکرار یکی از دو نوع جهش توسط هر خفاش انجام شده، موقعیت جدید بهدست آمده طبق رابطه (18-3) با بردار اولیه ترکیب میشود. حال اگر بردار جدید تابع هدف کوچکتری نسبت به بردار اولیه داشته باشد جایگزین آن می‌شود، در غیر این صورت الگوریتم با همان بردار اولیه به کار خود ادامه می‌دهد.
* مرحله ششم: بهروزرسانی موقعیتها با اجرای الگوریتم خفاش
در این مرحله موقعیتها با اجرای الگوریتم خفاش بهروز میگردد.
مرحله هفتم: اجرای الگوریتم Fuzzy c-means
بعد از بهروزرسانی موقعیتها، موقعیت بهروز شده به عنوان مراکز جدید خوشهها در نظر گرفته میشود. با استفاده از این مراکز، ماتریس تعلق دادهها با کمک روابطی که پیشتر برای الگوریتم Fuzzy c-means ذکر شد، بهروز میشود و مجدداً تابع هدف محاسبه میگردد.
مرحلهی هشتم: اعمال جستجوی محلی بر روی موقعیت جدید
برای فرار از گیر کردن در بهینه محلی، بعد از بهروز شدن موقعیتها، جستجوی محلی انجام میگیرد. این جستجو در دو مرحله انجام میشود :
• مرحلهی اول: جستجوی محلی اتخاذ شده از الگوریتم PSO
• مرحلهی دوم: جستجوی محلی اتخاذ شده از الگوریتم SA
مرحلهی نهم: اجرای الگوریتم Fuzzy c-means
موقعیت به دست آمده از جستجوی محلی به عنوان مراکز کلاستر در نظر گرفته شده و مطابق با الگوریتم FCM ، تابع هدف محاسبه میشود.
مرحلهی دهم: پذیرفتن موقعیت جدید و بهروزرسانی دامنه و نرخ ارسال پالس
توابع هدف بهدست آمده در مراحل هفتم و نهم با هم مقایسه شده و موقعیت تابع هدف کوچکتر به عنوان موقعیت جدید پذیرفته میشود و خفاش به این موقعیت تغییر مکان میدهد. با حرکت به موقعیت جدید، دامنه و نرخ ارسال پالس طبق روابطی که قبلاً ذکر شد، بهروز میشود.
مرحلهی یازدهم: بهروزکردن موقعت بهینه
بعد از انجام مراحل بالا برای همه اعضای جمعیت، مجدداً جمعیت بر اساس تابع هدف به صورت صعودی مرتب میشود. کوچکیترین مقدار تابع هدف با مقدار بهینه سراسری به دست آمده در مرحلهی سوم، مقایسه شده و در صورت کوچکتر بودن به عنوان بهینه سراسری، جایگزین مقدار قبلی میگردد.
مرحلهی دوازدهم: تست شرط توقف
در هر مرحله تکرار، تابع هدف با شرط توقف مقایسه شده و در صورت برآورده نشدن آن،الگوریتم از مرحله پنجم به بعد تکرار میشود.
4-3- تنظیم پارامترهای الگوریتم پیشنهادی
پارامترهایی که در حین اجرای الگوریتم پیشنهادی بایستی تنظیم گردند، عبارتند از: γ و α و m وN وfmax وfmin. مقادیر انتخابی این پارامترها برای الگوریتم پیشنهادی، در جدول 4-1 آورده شده است.
جدول 4-1 پارامترهای مربوط به الگوریتم های پیشنهادی.
150
تعداد جمعیت(N)
0.9
α
0.9
γ
2
M
500
تعداد تکرارها
fmin
2
fmax
4-4- بررسی نتایج حاصل از الگوریتم پیشنهادی و مقایسه آن با دیگر الگوریتم ها
در این بخش نتایج بهدست آمده از الگوریتم پیشنهادی بر روی دادههای معروف، مورد بررسی قرار خواهد گرفت. آنگاه، پاسخ نهایی الگوریتمهای پیشین با الگوریتم مورد بحث در این تحقیق، با هم مقایسه میگردد.
به طور کلی، مجموعه دادههای مختلفی برای انجام فرآیند خوشهبندی وجود دارد که هر کدام دارای ویژگیهای خاص خود هستند. لذا، برای دستیابی به اهداف موجود، مجموعه دادههای Iris، Wine، CMC، Vowel برگزیده میشوند. در ادامه، این مجموعه از دادهها معرفی و نتایج بهدست آمده به صورت مجزا نمایش داده میشود.
4-4-1- معرفی دادههای استفاده شده و نتایج شبیه سازی مربوط به آن
همانطور که گفته شد، از 4 مجموعه داده معروف، برای ارزیـابی عملکرد سیستمهای خوشهبندی استفاده خواهد شد؛ که به صورت اجمالی تشریح خواهد شد. شایان ذکر است که این مجموعه دادهها در اکثر مسائل خوشـهبندی و طبقهبندی کاربرد دارد.
4-4-1-1-مجموعه داده Iris
این مجموعه در واقع مجموعهای از دادهها میباشد که شامل سه نمونه گل زنبق است که توسط فیشر58 در سال 1936 برای نشان دادن تکنیکهای خطی تفکیکپذیر معرفی گردید. از این رو به نام مجموعه داده گل زنبق فیشر نیز خوانده میشود. از طرف دیگر، به دلیل اینکه ادگار اندرسون59 نیز این مجموعه را بهدلیل کیفیت تنوع جغرافیایی در شبه جزیره گاسپه، گردآوری کرده است، به مجموعه داده زنبق اندرسون نیز مشهور میباشد.
شکل 4-1 نمونه های گلهای زنبق از مجموعه دادهIris.
این مجموعه شامل 50 نمونه از سه نوع گل زنبق با نامهای سیتوسا 60، وریجینیکا61 و ورسیکولار62 میباشد. شاخصههایی که در این مجموعه جهت اندازهگیری مد نظر میباشند عبارت است: از پهنای گلبرگ، طول گلبرگ، پهنای کاسبرگ وطول کاسبرگ [54].
شایان ذکر است که این شاخصهها بر حسب سانتیمتر میباشند. بر اساس مدل خطی فیشر، این دسته از دادها بهعنوان یک دسته رایج از دادهها برای آزمایش تکنیک های کلاسه بندی در زمینه یادگیری ماشین مورد استفاده قرار می گیرد. با این وجود، استفاده از این دادهها برای آنالیز دستهها رایج نمیباشد. بهدلیل اینکه اطلاعات تنها حاوی دو دسته (خوشه) میباشد که نسبتاً به راحتی قابل جداسازی هستند. یکی از دسته ها شامل گونههای سیتوسا است، در صورتیکه دو گونه ورجینیکا و ورسیکولار، تاحد زیادی دارای همپوشانی هستند و جداسازی آن بدون استفاده از اطلاعات گونه هایی که فیشر بهکار برده است، قابل جداسازی نمیباشد. بنابر این، این مجموعه داده مثال خوبی برای توصیف تفاوت بین روشهای با ناظر و بدون ناظر در داده کاوی است. بهعبارت دیگر، مدل خطی فیشر تنها زمانی که

مطلب مرتبط :   منابع مقاله با موضوعشهر تهران، قلب و عروق، کاهش استرس

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