الگوریتم کلونی مورچگان

صفحه 1:


صفحه 2:
۹ 4 بت . ‎q‏ مره 

صفحه 3:
مقدمه - الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات یگ کلونی مورچه هاست. - یکی از مهم ترین و جالب ترین رفتار مورچه ها رفتار آن ها برای یافتن غذا است و به ویژه چگونگی پیدا كردن كوتاه ترين مسير ميان منابع غذایی و آشیانه است. - این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه ها ابتدا به طور تصادفی به این سو و آن سو می روند تا غذا بيابند. 

صفحه 4:
- سپس به لانه برمی گردند و ردی از فرمون به جا می گذارند: = چنین ردهایی پس از باران به رنگ سفید در می آیند و قابل رويت ‎١‏ ‏اند. ‎J‏ - مورچه های دیگر وقتی این مسیر را می يابند. گاه پرسه زدن را رها کرده و آن را دنبال میکنند. 

صفحه 5:
فرمون به مرور تبخیر ۲ 0 ميشود ‎sina | Jin Bo‏ مورچه های بعدی - 2- اگر فرومون اصلا تبخیر نميشد. مسیرهایی که چند بار طى ميشدند, چنان بیش از حد جذاب ميشدند که جستجوی تصادفی برای غذا را بسیار محدود می کردند. - 3- وقتی غذای انتهای یک مسیر جذاب تمام می شد رد باقی مى ماند. 

صفحه 6:
تاریخچه - الگوریتم بهینه سازی کلونی مورچگان که توسط دوریگو(۱۹۹۲) ایجاد شده, از مشاهده کلونی های واقعی مورچگان و بخصوص از رفتار مورچگان برای پیدا کردن کوتاه ترین مسیر از لانه خود تا منبع غذایی و نیز برعکس الهام گرفته شده است. 

صفحه 7:
رفتار بهینه کلونی مورچه ها 

صفحه 8:
- لذا وقتی یک مورچه مسر کوتاهی (خوبی) را از خانه تا غذا بیابد بقية مورچه ها به احتمال زیادی همان مسیر را دنبال میکنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر, به مرور همه مورچه ها هم مسير مى شوند. - هدف الگوریتم مورچه ها تقلید اين رفتار توسط مورچه هایی مصنوعی ست که روی نمودار در حال حرکت اند. = مسئل یافتن کوتاهترین مسیر اس و تلالش این مور سای مصنوعی اند. 

صفحه 9:
= یافته ها حاکی از آن است که مورچه ها هنگامی که بین منبع غذاب و لانه شان در حال رفت و آمد هستند, ماده ای به نام فرمون را از خود بر روی زمین به جای می گذارند که باعث شکل گیری یک مسیر فرمون می شود. 

صفحه 10:
- علی رغم این که یک مورچه ی مجزا به صورت تصادفی سفر می کند. مورچه ها می توانند فرمون را تشخیص داده و از مسیری که ۰ حاوی فرمون بالاتری است, حرکت نمایند و بر فرمون مسیر بیفزایند. - کوتاه ترین مسیر , با بیشترین فرمون, بیش ترین احتمال انتخاب شدن را دارد. 

صفحه 11:


صفحه 12:
کاربرد ها ‎Is‏ لگوریتم مورچکان - ۱-مسیر یابی داخل شهری و بین شهری - ۲- مسیر یابی پست های شبکه های توزیع برق - ۳- مسیر یابی شبکه های کامپیوتری - ۴-مسیریابی وسیله نقلیه ۵- حل مسئله برنامه ریزی تولید کارگاهی - ۶-تحلیل و بهینه سازی اقتصادی ایستگاه ها - ۷- حل مسئله زمان بندی پروژه ها با منابع محدود 

صفحه 13:
- از كابردهاى اين الكوريتم. رسيدن به راه حل تقريبا بهينه در لاا / فروشنده دوره گرد است. ‎Z‏ ‏- به طوری که انواع الگوریتم مورچه ها برای حل این مسئله تهیه - شده. 

صفحه 14:
مزیتهای ۸0۵ - مربی ۸2 تبخیر شدن فرومون» و «احتمال تصادف به مورچه ها امکان كردن كوتاهترين مسير را ميدهد. اين دو ویژگی باعث ایجاد اتعطاف در جل هركونه مسئله بهينه سازى ميشوند. - مثلا در كراف شهرهاى مسئله فروشنده دوره كردء 551 ‎Pts oS‏ گرهها) حذف شود الگوریتم اين توانایی را دارد تابه سرعت مسیر بهت ‎iN‏ ‏توجه به شرایط جدید ‎lay‏ کند. / - به این ترتیب که اگر یال (يا گرهای حذف شود کر رم نیست که أ 1 از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال ۱ (یا گره) هنوز بهترین مسیر را داریم, از اين به بعد مورجه ها مى توانند يس ۱ از مدت کوتاهی مسیر بهینه (کوتاهترین) را بيابند. 

صفحه 15:
Vs ps ۳ ‏ع‎ ‎02 nm 3 pasa 1 000 hoy ٩ 5 i 5 

صفحه 16:
— ۱- سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود. - ۲- سیستم مورچه ماکسیموم - مینیمم: یک مقدار کمینه و بیشینه برای فرمون نعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد و تمام گره‌های مجاور ان به مقدار فرمون بيشينه مقدا أوليه مى شوند. - ۲- سیستم ۳ مورجه: كه در بالا توضيحات كافى داده شده‌است. 

صفحه 17:
- ۴- سیستم مورچه بر اساس رتبه: تمام راه حل‌های بدست آماده بر اساس ‎Job‏ جواب رتبه‌بندی می‌شوند و بر اساس همین رتبه‌بندی مقدار فرمون آزاد / | سازی شده توسط آن‌ها مشخص خواهد شد و راه حل با طول کمتر از راه ‎Ves‏ ‏جل دنک )ا طول ‎sun‏ مقداز فر ون بسشتری اراد مک ۵ - سیستم مورچه متعامد مداوم: در اين روش مکانیزم تولید فرمون به مورچه اجازه می‌دهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه‌ها كسك انجاء ادح با استاده ار زوس ‎IF‏ بای تور ی ار دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب مر هی رن را می‌کند. روش طراحی متعامد می‌تواند به دیگر روش‌های جستجو دی گسترش پیدا کنند تا به مزیت‌های این روش‌های جستجو اضافه کند. 

صفحه 18:
- 1- تعیین مقدار اولیه برای تابع فرمون و ‎wl‏ ابتکاری - 2- قراردادن شهر مبدا برای هر مورچه در لیست ممنوعه که حق گذر مجدد برای آن مورچه وجود نداشته باشد 3- محاسبه تابع احتمال برای انتخاب شهر بعدی برای هر مورچه در هر 4-تعدیل جمعیت شهرها بابت انتخاب هر مورچه به لیست ممنوعه آن مورچه 5- افزودن شهر انتخابی هر مورچه به لیست ممنوعه آن مورچه 6-تعیین بهترین مسیر 7بروزرسانی 

صفحه 19:
Uv توابع و عناصر الگو مورچکا ریتم 

صفحه 20:
- از الگوریتم بهینه سازی کلونی مورچگان برای حل مسائل بهینگالا ۱ ترکیبی گسسته ی ۱۱۳-۳۱۵۴ مانند مسئله ی فروشنده ی دوره گر مسئله تخصیص مضاعف. مسائل مسیریابی تجهیزات و مسئله زمان بندی استفاده می شود. 

صفحه 21:
موارد بررسی شده در این - ۱- حل مثال از فروشنده دوره گرد. ۳ ۲ یل متال ار مستتله تخصیص منال های دفر ده به صررت ۶ برنامه نویسی شده در نرم ]515 ‎matlab‏ انجام شده است . 

صفحه 22:
حل مسئله فروشنده دوره گرد مسئله فروشنده دوره گرد(به انگلیسی: ‎Travelling salesman‏ ۲ به اختصار: ۲50) مسئله ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط ‏ آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت. 

صفحه 23:
۳ ,1 ‏عله‎ A اسیت: - تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می - مطلوب است کم هزینه ترین مسیری که از یک شهر شروع شود تمامی شهرها دقیقا یکبار عبور کند و به شهر شروع بازگردد. 

صفحه 24:
- در مسئله فروشنده دوره گرد در پی یافتن کوتاه ترین مسیر در بين مجموعه ای از شهر ها می باشیم, به گونه ای که هر شهر فقط یک بار در مسیر قرار گرفته و مسیر ساخته شده به شهر اولی منتهی شود. - در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده, به شهرهای دیگر برود و سپس به شهر مبدأً بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. ار اراس شهرهال پاش در مالت کلی این از مر ۱ 10 است. 77 

صفحه 25:
حل مسئله فروشنده دوره گرد - براى مثال مختصات شهر هاى مقابل داده شده است. ا ۶ - كه فاصله بين هر كدام از شهر ها را به مبناى هزينه 2-5 هر کدام در نظر می گیریم. ۱۳۹ - سپس بهترین ترکیب برای حرکت دست پیدا کرد که ۳۷ در ادامه خروجی های نرم افزار ۱۱۵۲۱۵9 گذاشته ۱۷ شا ‎"Rx‏ ‎YA‏ ۱۴۱ yan 

صفحه 26:
- خروجی گرفته شده در نرم افزار ۱۵۲۱۸8 11۳۳6 < 6 - خروجی گرفته شده بهینه ترین حرکت برای فروشنده است. 

صفحه 27:
مسئله تخصیص بهینه زمان و - مسئله مورد بررسی مسئله بهترین روش تخصیص هزینه و کمترین زمان و در کنار آن در نظر كرفتن تركيبى در اين بين ‎oe‏ ایا اب اک بر ترتع برای کمترین هزینه , کمترین زمان, و ترکیب بهینه اين دو بدست آوریم. 

صفحه 28:
مسئله تخصیص بهینه زمان و - مسئله مورد بررسی مطالعه موردی از مرغداری هاست که ترتیب عملکره کاری آها الحاظ شده اروش های آن ها بو کارشناسی شده به صورت بررسی میدانی بدست آمده و در ادامه سعی بر آن داریم با توجه به اطلاعات بدست آمده از هر روش بر مبنای روش کلونی مورچگان بهترین میزان هزینه کمترین زمان و تابع ترکیب این دو را بدست آوریم. - در اسلاید بعد جدول خلاصله بدست آمده از نظر سنجی آمده است. تابع تشکیل شده از ترکیب دو تابع شامل ۰۶ هزینه و ۰.۴ زمان می باشد. 

صفحه 29:
شباهت‌های میان کلونی واقعی مورچکان و کلونی - جمعیت کلوتی‌های واقعی ‎il rs‏ ودنتوكي يكل هدف خاص ‎is A‏ یک کلونی. جمعیتی مشکل از عامل‌های ساگ مستقل و «ناهمگام» ‎L aS cul (Asynchronous)‏ یکدیگر برای یافتن جواب‌های بهینه یک مسأله بهینه‌سازی, همکاری و تعامل - در کلونی مورچگان واقعی, مسأله, پیدا کردن منابع غذایی است. در کلونی مورچه‌های مصنوعی, مسأله, پیدا کردن جواب‌های بهینه برای مسأله بهینه‌سازی داده شده است. - یک مورچه (چه واقعی و چه مصنوعی). به تنهایی قادر به پیدا کردن 

صفحه 30:
- وجود مکانیزمی معادل تبخیر فیزیکی اثر فرومون در روش‌های بهینه‌سازی مورچگان (همانند کلونی واقعی مورچگان), به مورچه‌های مصنوعی این امکان می‌دهد که مسیرهای از پیش پیموده شده را فراموش کرده و بیشتر بر روی جهت‌های جستجوی جدید و امیدوارکننده تمرکز کنند. - در کلونی مصنوعی مورچگان (همانند کلونی واقعی), مورچه‌های مصنوعی, ‎che lex‏ کات ربا <رکت ‎lll‏ خاص مسا يه خالى كر ان حقادیر مفیرهای فسالی ولد میک - مورچه‌های واقعی, بر اساس غلظت فرومون در محیط و نیز یک سیاست کرری وی ود و ات کت وهای ۱ نیز مرحله به مرحله و از طریق تغییر مقادیر متفیرهای مسأله و نیز تصمیم‌گیری‌های تصادفی, اقدام به تولید جواب‌های کاندید برای مسأله مورد نظر می‌کنند. 

صفحه 31:
‎ea‏ مورچگان و کلونی ‎ ‏می‌کنند دوي به مج و پنی عی, مورچه‌های مصنوعی, تاد گر ظلال مسأله (متغیرهای فساله) را تعیر مي‌دهند ‏- به مقادير عددى, ‎(Artificial Pheromones) «Sgiiac sleug09)9”‏ 9 به دنبالهداى از اين مقادير عددى, «رد مصنوعى فرومون» [اق2166 ‎aiaS (Pheromone Trail‏ 1292.90 ‏- برخلاف مورچه‌های واقعی, مورچه‌های مصنوعی در یک جهان گسسته فعالیت می‌کنند. آن‌هاء پی در پی و در یک فضای متناهی متشکل از حالات (متغیرهای) مسأله در حال حرکت و تولید جواب‌های کاندید هستند. ‎ 

صفحه 32:
- فرآیند به‌روز رسانی مقادیر فرومونها (نظير انتشار و تبخير فرومون) در / کلونی مصنوعی مورچگان, دقیقا همانند کلونی واقعی مورچه‌ها انجام ‎Wf,‏ ‏نمی‌شود. - برخی مواقع, به‌روز رسانی فرومون, فقط توسط تعدادی از مورچه‌های مصنوعی و معمولا تنها پس از تولید یک جواب برای مساأله بهینه‌سازی انجام می‌شود. - برخی از پیاده‌سازی‌های انجام شده از الگوریتم کلونی مورچگان, صکاتیرم‌های اصافی را شامل می‌شوید که در جهان وافعی وحوه داز (نظیر مکانیزم جستجوی محلی, مکانیزم عقب‌نشینی و سایر موارد). 

صفحه 33:
<< Zz SS G ~