1
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه: Ant Colony Optimization
ارائهء یک الگوریتم جستجوی مبتنی بر روشهای مبنی برجمعیت در بهینه سازی ترکیبی
Presenting a Search Algorithm Based on Population-based Methods in Combinatorial Optimization
2
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
بهینه سازی ترکیبی شاخه ای از بهینه سازی در ریاضیات کاربردی و علوم کامپیوتر است که بین هوش محاسباتی، ریاضی و مهندسی نرم افزار، مشترک است.
الگوریتم های بهینه سازی ترکیبی، به این ترتیب مساله را حل می کنند که فضای حالت را برای یافتن یک پیکربندی جستجو می کنند که تابع هدف از پیش تعریف شده، روی متغیرهای مساله را بهینه کند و در ضمن محدودیتهای تعریف شده بین متغیرهای مساله را هم نقض نکند.
3
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
4
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
5
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
Ant Colony Optimization
الگوریتم های مورچه، سیستم های چندعامله ای هستند که هر عامل، یک مورچه مصنوعی است.
الگوریتم های مورچه نمونه های موفقی از سیستم های هوش گروهی هستند و از TSP سنتی تا مسیریابی در شبکه های ارتباطی راه دور را دربرمی گیرند.
ایده : مورچه ها در مسیر خود ماده شیمیایی به نام فرومون ترشح می کنند. وقتی سر دوراهی ( مسیرکوتاهتر و طولانی تر ) قرار می گیرند، براساس میزان فرومون استشمام شده از هر مسیر، یک انتخاب مسیر احتمالی انجام می دهند. به این ترتیب احتمال انتخاب مسیرهای دارای فرومون زیاد، به تدریج افزایش می یابد (اثر autocatalytic).
6
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
7
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
Ant Colony Optimization
دیده می شود که بعد از یک فاز گذرا، اکثر مورچه ها کوتاهترین شاخه را انتخاب می کنند و این احتمال با افزایش تفاوت طول مسیرها، افزایش می یابد. این رفتار توسط نوعی ارتباط غیر مستقیم به نام stigmergy به وسیله اصلاحات محلی در محیط، توضیح داده می شود.
برای اجتناب از همگرایی سریع به مسیرهای زیربهینه از مکانیزم تبخیر (evaporation) استفاده می شود. فراموش کردن (تبخیر) باعث کاوش نواحی خوب جدید می گردد.
8
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
9
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
10
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
1
2
4
3
3
5
2
2
4
3
11
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
α = 1 β= 5 ρ=0.5
12
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
تکرار اول
13
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
مقدار 12/1 به مقادیر مربوط به یالهای پیموده شده توسط هر مورچه اضافه می شود.
برای یالهایی که یکبار پیموده شده اند: Δτ = 0.08
برای یالهایی که دوبار پیموده شده اند: Δτ = 0.17
14
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
Ant Colony Optimization
روشهای ACO فقط وقتی که الگوریتم های کلاسیک نمی توانند به نحو موثری اعمال گردند، جالب توجهند مثل:
مسایل NP-hard که بعد گراف فضای حالت، نمایی است.
ویژگیهای گراف مساله همزمان با فرایند بهینه سازی تغییر می کند (وقتی نرخ تغییر هزینه ها افزایش می یابد یا دانش مربوط به فرایند تغییر کاهش می یابد، ACO مناسب تر می شود)
معماری محاسباتی از لحاظ فضایی توزیع شده است.
15
آزمایشکاه سیستم های هوشمند (http://ce.aut.ac.ir/islab)
موضوع ارائه : Ant Colony Optimization
Ant Colony Optimization
به طور کلی سه نوع موازی سازی وجود دارد:
موازی سازی در سطح مورچه ها: NC گروه را درنظر می گیرد که هر کدام روی نمونه مساله مشابهی اجرا می شوند.
موازی سازی در سطح داده : تقسیم مساله و حل هر کدام با یک گروه مورچه .
موازی سازی در سطح تابع: تبخیر ، daemon و فعالیت مورچه ها، به طور همزمان انجام شوند.