دانلود تحقیق الگوريتم مورچه

واژه های کلیدی:الگوریتم مورچه،فرومون،فروشنده دوره گرد، بهینه سازی / دانلود تحقیق الگوريتم مورچه
چكيده
برخي از روشهاي حل مسائل بهينه سازي، جوابهاي بهينه مطلق توليد نموده و برخي ديگر تنها به جوابهاي خوب بسنده مي كنند. فلسفه پيدايش روشهايي كه قادر به رسيدن جوابهاي در حد بهينه (و نه قطعا بهينه) مي باشند را مي توان در اين حقيقت دانست كه برخي از مسائل بهينه سازي NP-hard هستند. الگوريتمهاي فراكاوشي يك نام معمول براي روشهايي است كه عموما برگرفته از طبيعت هستند. در چند دهه اخير، اين روشها به عنوان يك ابزار جستجو و بهينه سازي در بسياري از حوزه ها، بطور عام و حوزه مهندسي به طور خاص توسعه يافته و مورد استفاده قرار گرفته اند. الگوريتم بهينه سازي جامعه مورچه ها (ACO) با الهام از رفتار جستجوي غذا در مورچه هاي طبيعي توسعه يافته و در دهه اخير در بسياري از مسايل مورد استفاده قرار گرفته است. در رساله حاضر چهار هدف عمده مد نظر بوده است. ابتدا معرفي مفاهيم اوليه الگوريتمهاي ACO صورت گرفته و نحوه مدلسازي مسايل با اين الگوريتم ها با ذكر چند نمونه تشريح گرديده است. اين الگوريتم ها نيز همچون ساير روشهاي جستجو و فراكاوشي، از مشكل همگرايي سريع و زودرس رنج مي برد. سعي گرديده است با معرفي سه فرايند ارتقاء فرامان، جايگزيني جزء مسير و دوباره سازي فرامان، پيشرفتي در زمينه همگرايي و افزايش مرغوبيت جواب ها ايجاد گردد.
كارايي اين فرايندها در تركيب با يكديگر با مدلسازي چند تابع رياضي و نيز مساله بهره برداري مخزن تشريح گرديده است. هدف بعد در اين رساله، مدلسازي و حل مسايل بهره برداري سيستم هاي چند مخزنه در زمينه مهندسي آب بود. عموما در اين مسايل كه با افزايش ابعاد و پيچيدگي آن، روشهاي بر پايه برنامه ريزي پويا به دليل نفرين ابعادي دچار مشكل مي گردند، روشهاي فراكاوشي همچون الگوريتمهاي ACO، جدا از پيچيدگيهاي حاصل از مدل غير خطي، كارايي مناسبي از خود به نمايش گذاشته اند. هدف نهايي اين رساله انطباق هرچه بيشتر الگوريتم هاي پيشنهادي ACO با مسايل پيوسته بوده است. در اين زمينه ابتدا فرايند دسته بندي مجدد معرفي گرديده است. اين فرايند در مسايل ساده بسيار كارا بوده اما هميشه اين احتمال را ايجاد مي نمايد كه در گامهاي اعمال آن محدوده بهينه مطلق از دست برود. جهت حل اين مشكل با استفاده از مفاهيم اوليه موازي سازي، الگوريتم چند جامعه اي در ظاهري جديد توسعه داده شد. با استفاده از اين الگوريتم چند جامعه اي پيشنهادي، فضاي جستجو به صورت ناهمگن و پويا گسسته سازي شده و احتمال از دست دادن محدوده بهينه مطلق بسيار كاهش يافت. كارايي اين الگوريتم در چندين مساله طراحي هيدروسيستم ها كه مسايلي غير خطي، غير محدب و چند مرحله اي مي باشند بررسي گرديده است. عدم توفيق روشهاي بهينه سازي بر پايه گراديان و موفقيت الگوريتم پيشنهادي در حل چنين مسايل پيچيده، غير خطي و غير محدب، نشان از توانايي بالقوه الگوريتم دارد.
الگوریتم مورچگان :
سیستم مورچه CE یک سیستم هوشمند پر ازدحام (مانند کندوی زنبوران) است و رفتار کاوش آذوقه مورچگان را تقلید می کند که شامل تعداد زیادی عامل با رفتارهای ساده است که بطور غیر مستقیم و غیر همزمان با هم ارتباط برقرار می کنند . همه عامل ها مأموریت جستجوی مسیرهای حلقه ای و گزارش کیفیت مسیر که بوسیله مفهوم ” عملکرد مسیر ” تعریف می شود , را دارند.
کاربردهای الگوریتم مورچگان :
ایجاد و نگهداری اتصال مسیرهای اولیه و پشتیبانی از هم گسیخته .
حل مسایل مربوط به پیدا کردن و نگهداری مسیرهای مجازی در یک شبکه ارتباطات با تغییر شرایط.
ساختار اتوماتیک سایتهای پرتال در وب .
استفاده در مسیریاب های نرم افزاری و عامل های موبایل ( مثال زیر ) .
مثال :
مورچگان بین منبع غذا و لانه یک مسیر را حفظ می کنند.
نکات کلی :
لانه مورچه در کامپیوتر میزبان است.
مورچگان عاملهای موبایل هستند.
هدف : جلوگیری از بکارگیری اتصالات متراکم .
پاکتهای داده در هر مسیریاب , مسیریابی می شوند.
مسیریاب :
پاکتهای داده با کلیک مسیریابی می شوند.
کد مورچه در Java VM اجرا می شود.
دو زیر سیستم اطلاعاتشان مورد نیازشان را با هم رد و بدل می کنند.
میزبانان :
مورچگان و تست ترافیک تولید می شوند .
آمار نرخ پاکتها برای هر اتصال .
تست انطباق :
تمام اتصالات بین مسیریاب ها دارای ظرفیت 50 پاکت در ثانیه اند.
ابتدا , دو اتصال بدون ترافیک ایجاد می شود.
پس از مدتی , اتصال 1 شروع به فرستادن ترافیک CBR تقویت شده با نرخ 40 پاکت در ثانیه می کند.
نتیجه اتصال 2 :
در ابتدا , کوتاه ترین مسیر ترجیح داده می شود.
ترافیک ناشی از اتصال 1 منجر به افزایش هزینه می شود.
اکنون مسیر دیگری کمترین هزینه را خواهد داشت.
سیستم به مسیر منتخب سویچ می کند.
ارزیابی :
این الگوریتم برای پیاده سازی مسیریاب های نرم افزاری و عاملهای موبایل موجه است.
عملکرد محدود است.
پیاده سازی بر پایه سیستم عامل موبایل است.
برای اجرای سیستم در شبکه بزرگتر , عملکرد باید بهبود یابد.

فهرست مطالب
عنوان صفحه
چكيده
مقدمه 1
Emergence 3
بهينه سازي مسائل بروش کلوني مورچه(ACO) 4
بهینه سازی کلونی مورچه یاAnt Colony Optimization”ACO” 5
مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟ 8
مزيتهايACO : 11
کاربردهاي ACO : 11
مسير يابي شبکه هاي کامپيوتري با استفاده از ACO : 12
استفاده از بهینه سازی کلونی مورچه هادر مسئلهفروشنده دوره گرد 12
كاربردهاي الگوريتم هاي ACO 14
قسمت چهارم -الگوريتم هاي ACO 15
قسمت سوم- متاهيورستيك ACO : 15
قسمت دوم-متاهيور ستيك ACO – 16
قسمت اول- متاهيور ستيك ACO 18
تشابه و تفاوت ها با مورچه هاي واقعی: 19
دنباله فرمون استيمرژي 19
جستجوي كوتاه ترين مسير و حركات محلي : 20
سياست نوسان دار و نزديك براي تصميم گيري : 20
اثر جانبی 22
بهينه‌سازی شبكه‌های كامپيوتری با الهام از كولونی مورچه‌ها: 23
الگوریتم های لانه مورچه و کاربرد آن در نگهداری پیشگیرانه: 24
مدل كردن الگوريتمهاي كلوني مورچه ها با استفاده ازاتوماتاهاي يادگير 25
طراحي بهينه سيستمهاي انتقال آب توسط الگوريتم جامعه مورچه ها 26
استفاده پژوهشگران از الگوي کلوني مورچه ها جهت اداره ترافيک: 26
شبيه‌ساز الگوريتم كلوني مورچه‌ها (Ant Farm Simulator) 28
هوش جمعي : 29
الگوریتم اجتماع مورچه (Ant Colony Algorithm) 30
هر مورچه يك نماينده¬ی ساده باويژگي¬هاي زير است: 32
منابع: 35