فهرست
فرمت فایل :power point( قابل ویرایش) تعداد اسلاید: 21 اسلاید
تا کنون روش های بهینه سازی مختلفی برای مسائل متنوع بهینه سازی بکار گرفته
شده اند.
Genetic Algorithm
Artificial neural networks
particle swarm optimization
simulated annealing
ant colony optimization
در این مقاله قصد داریم نکاتی را درباره ی الگورتم کلونی مورچگان بیان کنیم.
فهرست مطالب
1-رفتار طبیعی مورچه ها
2- فاکتورهای موجود در روش مورچه ها
3-مسئله TSP
4- الگوریتم ant system
5- مدلهای مختلف ant system
6- انواع الگوریتم های کلونی مورچه
7- کاربردها
8-منابع
حل مسئله فروشنده دوره گرد با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک
فایل ورد قابل ویرایش
4000تومان
چکیده
مساله فروشنده دوره گرد جزء مسائل مشهور و کلاسیک تحقیق در عملیات می‌باشد. بسیاری از فعالیت‌های علمی را می‌توان به صورت مسئله فروشنده دوره گرد در آورد و سپس حل نمود. روش‌های بهینه یابی موجود برای حل مسائل سخت همچون مسئله فروشنده دوره گرد بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می‌باشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی می‌کاهد بدین علت در دهه‌های اخیر استفاده از الگوریتمهای ابتکاری و فوق ابتکاری مورد توجه قرار گرفته است. در این بین الگوریتمهای فوق ابتکاری به دلیل ساختار ساده و توانایی‌هایی که از خود نشان داده‌اند مورد استفاده محققین تحقیق در عملیات قرار گرفته است.
در این تحقیق با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سعی شده است الگوریتم ترکیبی ساخته شود که تور بهتری را برای مسئله فروشنده دوره گرد بدست آورد. پس از طراحی الگوریتم، تنظیم پارامترهای آن با حل مسائل متعدد صورت گرفته است و برای مقایسه روش پیشنهادی با روش‌های الگوریتم ژنتیک و مورچگان برخی از مسائل حل شده است. نتایج بدست آمده نشان می‌دهد که روش ترکیبی پیشنهادی TSP فروشنده دوره گرد موجود در سایت در اغلب مسائل قادر است جواب بهتری بدست آورد.
واژه‌های کلیدی: فروشنده دوره گرد، الگوریتم ترکیبی، الگوریتم کلونی مورچگان، الگوریتم ژنتیک
فهرست مطالب
فصل اول آشنایی با الگوریتم ژنتیک....................................................................................................... 1
مقدمه .............................................................................................................................................................. 2
1-1 زمینه‌های بیولوژیکی............................................................................................................................... 2
1-2 فضای جستجو......................................................................................................................................... 3
1-3 مسائل NP.............................................................................................................................................. 4
1-4 مفاهیم اولیه در الگوریتم ژنتیک............................................................................................................. 5
1-4-1 اصول پایه............................................................................................................................................ 5
1-5 شمای کلی الگوریتم ژنتیک................................................................................................................... 5
1-6 کد کردن .................................................................................................................................................. 6
1-7 انواع کدینگ............................................................................................................................................. 7
1-7-1 کدینگ مستقیم.................................................................................................................................. 7
1-7-2 کدینگ غیرمستقیم............................................................................................................................ 7
1-8 روش‌های کدینگ.................................................................................................................................... 7
1-8-1 کدینگ باینری.................................................................................................................................... 7
1-8-2 کدینگ جهشی................................................................................................................................... 8
1-8-3 کدینگ ارزشی.................................................................................................................................... 8
1-8-4 کدینگ درختی................................................................................................................................... 9
1-9 مسائل مربوط به کدینگ......................................................................................................................... 9
1-10 فضای کدینگ و فضای جواب............................................................................................................ 10
1-11 کروموزوم............................................................................................................................................. 11
1-12 جمعیت.............................................................................................................................................. 12
1-13 مقدار برازندگی................................................................................................................................... 13
1-13-1 عملگر تقاطعی............................................................................................................................. 13
1-13-2 عملگر جهشی.............................................................................................................................. 15
1-14 مراحل اجرای الگوریتم ژنتیک........................................................................................................... 17
1-15 الگوریتم ترکیبی مورچگان................................................................................................................ 24
1-16 الگوریتم پیشنهادی............................................................................................................................ 27
1-17 الگوریتم ژنتیک با توجه به نوع عملگر............................................................................................. 28
1-18 تحلیل حساسیت پارامترها................................................................................................................ 29
1-19 تجزیه و تحلیل نتایج......................................................................................................................... 31
منابع............................................................................................................................................................... 33
فهرست اشکال
شکل 1-1 نمونه‌ای از فضای جواب................................................................................................................ 3
شکل 1-2 کدینگ درختی.............................................................................................................................. 9
شکل 1-3 تقاطعی دو نقطه‌ای..................................................................................................................... 14
شکل 1-4 عمل تقاطعی یکنواخت.............................................................................................................. 15
شکل 1-5 نمونه‌ای از عمل جهش.............................................................................................................. 15
شکل 1-6 مراحل اجرای الگوریتم ژنتیک.................................................................................................... 18
شکل 1-7 چرخ رولت................................................................................................................................... 19
شکل 1-8 نحوه حرکت مورچه‌ها برای یافتن منبع غذائی وفرومون ریزی................................................ 26
فهرست جداول
جدول 1-1 کدینگ باینری............................................................................................................................. 7
جدول 1-2 کدینگ جهشی............................................................................................................................ 8
جدول 1-3 کدینگ ارزشی............................................................................................................................. 8
جدول 1-4 محل اتصال متغیر‌های فرزند ١ والد ١ فرزند ٢ والد ٢............................................................ 14
جدول 1-5 نمونه‌ای از عمل جهش............................................................................................................. 16
جدول 1-6 انتخاب کروموزوم‌ها با استفاده از مدل چرخ رولت................................................................... 19
جدول 1-7 نمایش جمعیت اولیه................................................................................................................ 22
جدول 1-8 نتایج عمل تقاطع..................................................................................................................... 22
جدول 1-9 نتایج عمل جهش..................................................................................................................... 22
جدول 1-10 کروموزوم با بیشترین مقدار برازندگی.................................................................................... 23
جدول 1-11 نشان می‌دهد که مقادیر کوچک و بزرگ پارامتر آلفا باعث افزایش طول تور می‌شود........ 29
جدول 1-12 تاثیر پارامتر بتا بر عملکرد الگوریتم ترکیبی......................................................................... 30
جدول 1-13 با افزایش مقدار پارامتر مقدار EC به جواب نزدیکتر به بهینه افزایش می‌یابد................... 30
جدول 1-14 با افزایش عملکرد الگوریتم بهبود می‌یابد............................................................................. 31
جدول 1-15 مقایسه نتایج بدست آمده از الگوریتم پیشنهادی................................................................ 31
این محصول در قالب پی دی اف و 77 صفحه می باشد.
این سمینار جهت ارائه در مقطع کارشناسی ارشد کامپیوتر-نرم افزار طراحی و تدوین گردیده است. و شامل کلیه موارد مورد نیاز سمینار ارشد این رشته می باشد. نمونه های مشابه این عنوان با قیمت بسیار بالایی در اینترنت به فروش می رسد.گروه تخصصی ما این سمینار را با قیمت ناچیز جهت استفاده دانشجویان عزیز در رابطه به منبع اطلاعاتی در اختیار شما قرار می دهند. حق مالکیت معنوی این اثر مربوط به نگارنده است. و فقط جهت استفاده از منابع اطلاعاتی و بالا بردن سطح علمی شما در این سایت قرار گرفته است.
چکیده
با گسترش شبکه های کامپیوتری و پیچیده شدن ارتباطات، مسئله مسیریابی اطلاعات برحسب تغییـرات
توپولوژیکی و عموماً ترافیک لحظه ای حائز اهمیت است. وظیفه هر الگوریتم مسـیریابی هـدایت بسـته هـای
اطلاعاتی از مبدأ به سمت مقصد با هدف بهینه کردن میانگین زمان تأخیر بسته هـا، بهـره بـرداری ازمنـابع و
کارایی شبکه مانند توان عملیاتی می باشد. در سالهای اخیر مسئله مسیریابی وفقی در شـبکه هـای دیتـاگرام
باساختارها و توپولوژیهای متفاوت بسیار مورد توجه قرار گرفته است و الگوریتمهـای مختلفـی در ایـن زمینـه
پیشنهاد شده است که از آن جمله می توان الگوریتم مسیریابی کلونی مورچـه را نـام بـرد . الگـوریتم کلـونی
مورچه الهام گرفته شده از مطالعات ومشاهدات بر روی کلونی مورچه هاست. این الگوریتم بر پایه ایـن منطـق
بنا نهاده شده که مورچه ها در مسیرخود برای یافتن غذا از خود ماده ای به نام فرومون بر جـای مـی گذارنـد
که بستگی به طول مسیر و کیفیت غذای یافته شده دارد بر اثر استشمام بوی فرومون توسط دیگر مورچه هـا
آنها نیز جذب مسیر شده و مقدار فرومون را در آن مسیر تقویت می کنند، مسیرهای کوتاهتر از لانـه تـا غـذا
فرومون بیشتری گرفته وبدین ترتیب کوتاهترین مسیر توسط مورچه ها انتخاب می شود، از این رفتار توصیف
شده مورچه ها برای بهینه سازی جداول مسیریاب ها استفاده شده و به این ترتیـب کوتـاهترین مسـیر بـرای
هدایت بسته ها در نظر گرفته می شود.
در سمینار حاضر به بررسی الگوریتم ها ی پیشنهاد شده براساس ایده کلونی کورچه هـا بـرای مسـیریابی
بسته های اطلاعاتی در شبکه دیتا گرام پرداخته می شود.
مقدمه
در طی سالهای اخیر، شبکه های ارتباطی بسیار مورد توجه بوده اند و این بدلیل رشد بی سابقه شـبکه
اینترنت در دهه های اخیر است که در واقع آنرا تبدیل به زیربنای ارتباطات کـرده اسـت و مـی تـوان گفـت
دلیل اصلی موفقیت اینترنت فن آوری راهگزینی بسته ای بدون اتصالش است. این خاصیت سادگی، انعطـاف
پذیری، پایداری و درستی ساختار لایه شبکه را بهمراه دارد.این دقیقا ًبر خلاف شبکه های ارتباطی مبتنی بر
اتصال است که نیاز دارند تابرای برقراری ارتباط یک اتصال(مداری)از پیش رزرو شده بین فرستنده و گیرنـده
درنظر گرفته شود. موفقیت اینترنت محقق هـا را ترغیـب کـرد تـا رویـای محاسـبات جهـانی Ubiquitous
Computingرا درک کنند. در واقع محاسبات جهانی جامعه ای از کاربران را ایجاد کرده است که توان خـود
، تجارت الکترونیکی 1 را در کاربردهایی مانند وب جهان گستر آمـوزش از راه دور
و…. بکـار مـی
برند. مشخصه مشترکی که تمام این کاربردها دارند توانایی ارسال صدا و تصویر به دیگـران تحـت الزامهـای
4 کیفیت خدمات )
(QoS است. کاربران تمام این خدمات را همانگونه که در سایر وسایل سیار وجـود دارد بـر
روی کامپیوترشان نیز می خواهند، و این نیازها برآورده نمی شود مگر اینکه منابع شبکه بطور مناسبی بکـار
برده شوند. بهره برداری مناسب از منابع محدود شبکه بوسیله بهینه کردن عملکرد شبکه های مبتنی بـر IP
میسر می شود که آن نیز مستلزم ایجاد استراتژی های مسیریابی کارآمد و قابل اعتمـاد اسـت . یکـی از چـا
لش های موجود در این زمینه طراحی پروتکل های مسیر یابی است که بتوانند چندین مسـیر مناسـب بـین
فرستنده و گیرنده را کشف کنند .در حال حاضـر الگوریتمهـای مسـیریابی پویـا و وفقـی گونـاگونی توسـط
محققان سراسر جهان با الهام از طبیعت طراحی شده اند. از آنجمله می توان به الگوریتم های کلونی مورچه
اشاره کرد.
5 ایده ی اصلی این مجموعه از الگوریتم ها، بر جا ماندن مـاده ی فر ومـون بـه عنـوان ردپـا در دنیـای
مورچه های واقعی می باشند. مورچه ها از ماده ی فرومون به عنوان یـک وسـیله ی ارتبـاطی اسـتفاده مـی
کنند. در واقع الگوریتم های بهینه یابی مورچگان بر مبنای ارتباط غیـر مسـتقیم مجموعـه ای از مورچگـان
مصنوعی به وسیله ی فرومون مصنوعی بنا نهاده شده اند که در این میان ماده ی فرومون وظیفـه ی انتقـال
تجربه ی مورجه ها به یکدیگر بدون ارتباط مستقیم مورجه ها با هم را به عهده دارد.
الگوریتم های مورچه نمونه های موفقی از سیستم های هوش جمعی هستند و از TSP سنتی تا
مسیریابی در شبکه های ارتباطی راه دور را دربرمی گیرند. الگوریتم های مورچه، سیستم های چندعامله ای
هستند که هر عامل، یک مورچه مصنوعی است. در واقع دانشمندان با الهام گرفتن از مورچه ها عمل
پیچیده مسیریابی را با عاملهای ساده ای که با پیمایش شبکه، اطلاعات مسیر یابی را جمع آوری می کنند،
انجام می دهند. هر گره در شبکه براساس اطلاعات محدودی که از وضعیت شبکه دارد بسته های داده را به
سمت مقصدشان هدایت می کند.الگوریتمهای مسیر یابی مبتنی بر عامل در مقابل تغییرات شبکه بهره
برداری تطبیقی و کارآمد منابع شبکه را جهت ارضا کردن نیازهای توازن بار و مدیریت خطا در شبکه فراهم
می کنند.
در این سمینار ابتدا به بیان مسئله پرداخته شده سپس به مقدمه ای بر بهینه سازی کلونی مورچگان
می پردازیم و بعد از آن مروری بر نحوه مسیر یابی در شبکه های کامپیوتری خواهیم داشت و در ادامه نیز
به بررسی روش والگوریتم های بهینه سازی کلونی مورچگان در مسیریابی شبکه های دیتاگرام پرداخته می
شود و در آخر نتیجه گیری آورده شده است.
فایل پروژه از دو فایل اصلی تشکیل شده است : یکی A C O feature selection m و و یک پایگاه داده که ۴۰۰ تصویر از ۴۰ شخص در ۱۰ حالت متفاوت گرفته شده است. مراحل اجرای پروژه به صورت زیر است
ابتدا با استفاده از اجرای فایل ویژگی های زرنیک و که مربوط به ویولت هست را از ۴۰۰ تصویر بیرون کشیده و در یک ماتریس با ۴۰۰ ردیف ذخیره می کنیم. تعداد ویژگی های استخراجی برای برابر ۱۶۸ ویژگی است. که با توجه به مقاله ی شماره ۲(شکل۴ مقاله) که در فایل پروژه هست پیاده سازی شده است. تصاویر پایگاه داده ۹۲در۱۱۲ می باشد سه سطح رزولوشن آن باستفاده از تبدیل وارون ویولت کم می شود سطح اول ۴۶در۵۶ ، سطح دوم ۲۳در۲۸ و سطح سوم و آخر ۱۲در۱۴ می شود. در این مرحله تصویر با ابعاد سطح سوم را به صورت برداری تک ردیف ارائه می کنیم و اینکار با کنار هم و بهم پیوست ستون ها انجام می دهیم. که برای هر تصویر بردار ویژگی برداری با طول ۱۶۸ خواهد بود زیرا ۱۲در۱۴مساوی۱۶۸ خواهد شد. پس از استخراج ویژگی های آنها را در ماتریس با ابعاد ۴۰۰در۱۶۸ برای استفاده ی الگوریتم A C O ذخیره می کنیم. به منظور استخراج ویژگی-های زرنیک نیز از به جای استفاده مستقیم از تصاویر پایگاه داده از تصاویر کاهش یافته ی ۶۴در۶۴ استفاده شده است. که فقط ۲۰ مرتبه ی اول ویزگی های زرنیک محاسبه می شود. و دراین حالت نیز ماتریس با نام با ابعاد ۴۰۰در۲۰ را به منظور استفاده A C O ذخیره می کنیم.
فهرست :
توضیحات اجرای پروژه
مقاله زبان اصلی
فایل سورس پروژه