1
الگوریتم کلونی مورچه ها Ant Colony Optimization
طراحی و ساخت:
احمد مرادی
ahmadmoradi369@gmail.com
فهرست مطالب
مقدمه
هوش جمعی (Swarm Intelligence)
چگونگی پیدا کردن کوتاه ترین مسیر
مزیتهای ACO
کاربرد ACO
الگوریتم ACO
TSP
مثال
منابع
3
مقدمه
یکی از موفق ترین مثال های الگوریتم مورچه ها، الگوریتم بهینه سازی کلونی مورچه ها است که به اختصار ACO نامیده می شود.
ACO برای اولین بار توسط دوریگو (Dorigo) در 1992ارائه شد.
الگوریتم ACO از رفتار مربوط به پیدا کردن غذا (foraging) مورچه های الهام گرفته شده است.
الگوریتم ACO برای مسئله های بهینه سازی گسسته استفاده می شود.
4
هوش جمعی (Swarm Intelligence)
نمونه بارز این هوشمندی در رفتار حشراتی که بصورت کلونی زندگی می کنند، دیده می شود.
جمعیتی از اعضا عمل ساده ای را انجام می دهند .
در نهایت تمام گروه مساله پیچیده ای را حل می کنند.
بین اعضا هیچ نوع ارتباط مستقیمی وجود ندارد.
آنها تنها بصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند.(Stigmergy)
5
چگونگی پیدا کردن کوتاه ترین مسیر
مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون (Pheromone) جای می گذارند.
تبخیر شدن فرومون در گذر زمان
مورچه ها بصورت احتمالاتی (Statistical) مسیری را انتخاب می کنند که فرومون بیشتری داشته باشد
6
چگونگی پیدا کردن کوتاه ترین مسیر
مورچه ها روی مسیر AB در حرکت اند (در دو جهت مخالف)
اگر در مسیر مورچه ها مانعی قرار دهیم مورچه ها دو راه برای انتخاب کردن دارند.
A
B
A
B
7
چگونگی پیدا کردن کوتاه ترین مسیر
تصادف و احتمال در انتخاب مسیر
A
B
8
چگونگی پیدا کردن کوتاه ترین مسیر
یافتن کوتاهترین مسیر
A
B
9
مزیتهای ACO
تبخیرشدن فرومون
احتمال-تصادف
انعطاف
جذابیت کمتر مسیر برای مورچه های بعدی
چندبار طی شدن مسیرها درصورت تبخیر نشدن
باقی نماندن رد درصورت تمام شدن غذا
10
کاربردهای ACO
بهینه کردن هر مسئله ای که نیاز به یافتن کوتاهترین مسیر دارد ،
1. مسیر یابی داخل شهری و بین شهری
2. مسیر یابی بین پست های شبکه های توزیع برق ولتاژ بالا
3 . مسیریابی تامین مواد اولیه جهت تولید بهنگام
4. مسیر یابی شبکه های کامپیوتری
11
الگوریتم ACO
استفاده از مورچه های مصنوعی به عنوان عناصری در بهینه سازی برای پیاده سازی کلونی مورچه
12
13
الگوریتم ACO
شروع
جواب نهایی
تعداد تکرار ها تمام شد؟
جواب بدست آمده بهتر از بهترین جواب قبلی است؟
مورچه ای مانده؟
مقداردهی اولیه
جایگزینی با بهترین جواب قبلی
انتخاب بیشترین احتمال
بروزرسانی فرومون
محاسبه احتمال
بله
خیر
بله
خیر
بله
خیر
: مقدار احتمال رفتن از مسیر i به j در زمانی که محاسبات روی گره k
: نشان دهنده قدرت اثر فرومون روی مسیر i تا j
: عکس تابع هدف (در مساله فروشنده دوره گرد عکس فاصله بین گره i تا j است)
α و β: پارامتر هایی کنترلی اند برای تغییر قدرت اثر فرومون یا عکس تابع هدف
فرومون احتمال
14
الگوریتم ACO
𝜏 𝑖𝑗
𝑝 𝑘 𝑖𝑗
η 𝑖𝑗
𝑝 𝑖𝑗 𝑘 = [ 𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 𝑙 𝜖𝑁 𝑖 𝑘 [ 𝜏 𝑖𝑙 ] 𝛼 . [ 𝜂 𝑖𝑙 ] 𝛽 𝜂 𝑖𝑗 = ( 1 𝑑 𝑖𝑗 )
الگوریتم ACO
بروز رسانی فرومون:
p ضریب محو شدن فرومون
نشان دهنده قدرت اثر فرومون
15
𝜏 𝑖𝑗
𝜏 𝑖𝑗 + 𝑄 𝑓(𝑥) → 𝜏 𝑖𝑗
(1−𝑝). 𝜏 𝑖𝑗 → 𝜏 𝑖𝑗 ∀ 𝜏 𝑖𝑗 ∈𝑇,0<𝑝<1
𝝉 𝒊𝒋 (𝒕+𝟏) = 𝒑 * 𝝉 𝒊𝒋 𝒕 +(𝟏−𝒑) * 𝜼 𝒊𝒋
الگوریتم ACO
شرط های توقف
1- تعداد تکرار
2- زمان
3- عدم بهبود
4- همگرایی
16
(فروشنده دوره گرد)TSP
مطرح شده در سده ۱۸ توسط ویلیام همیلتون و توماس کرکمن
17
c
c
c
c
c
c
c
c
c
c
c
c
c
c
مثال
مساله فروشنده دوره گرد با چهار شهر
18
هدف یافتن کوتاهترین مسیری است که از همه شهر ها گذشته و به شهر آغازین بازگردد.
مثال
مقدار دهی اولیه:
α = 0.4
β = 0.9
ρ = 0.4
τij = 0.001
برای همه مقادیر مقادیر ηij در این مثال برابر عکس فاصله بین شهرها است. یعنی
ηij = 1/dij
η12 = 1/15= 0.0667
19
مثال
گام اول
ابتدا یک شهر به تصادف انتخاب شده و مقادیر احتمال برای انتخاب شهر بعدی محاسبه می شود.
20
3
1
2
4
1
مثال
گام دوم
انتخاب بیشترین مقدار احتمال
گام سوم
به روز رسانی فرومون
گام چهارم. بررسی شرایط توقفِ تکرار اول
21
𝑝 1→2 =0.448
𝑝 1→3 =0.2040
𝑝 1→4 =0.311
3
1
2
4
مثال
گام اول
گام دوم
شهر سه با احتمال بیشتر انتخاب می شود.
گام سوم
به روز رسانی فرومون
گام چهارم
بررسی شرایط توقف. تمام شهرها انتخاب نشده اند. به گام یک برو
22
𝑝 2→3 =0.6377
𝑝 2→4 =0.3622
3
1
2
4
3
1
2
4
مثال
گام یک و دو
تنها شهر باقیمانده شهر چهار است
گام سه
به روزرسانی فرومون
گام چهار
بررسی شرایط توقف. با توجه به اینکه تمام شهرها طی شده پایان تکرار اول
23
3
1
2
4
3
1
2
4
مثال
محاسبه تابع برازندگی:
در این مساله تابع هدف یا برازندگی برابر مجموع فاصله طی شده مسیری است که توسط الگوریتم انتخاب شده است.
مسیر بدست آمده از اولین تکرار این الگوریتم:
1 2 3 4 1
مقدار مسیر طی شده برابر 59
24
منابع
1.کورش عشقی؛ مهدی کریمی نسب؛ تحلیل الگوریتمها و طراحی روشهای فرابتکاری؛ انتشارات دانشگاه شریف؛ ۱۳۹۵
2.مسئلهی مسیریابی در شبکههای پویا" مقاله، دانشگاه اصفهان
3.www.matlabdl.com
4.www.matlabhome.ir
5.www.matlabanalysis.com
25
شروع
مقدار دهی اولیه به پارامترها
قراردادن مورچه ها در گره مبدا
انتخاب گره بعدی توسط مورچه ها
آیا به هدف رسیده ایم؟
آپدیت کردن فرومون مسیر
شرایط پایانی مساله برآورده شده است؟
پایان
بلی
بلی
خیر
بلی
آیا مورچه ای باقی مانده است؟
خیر
محاسبه تابع هزینه
پارامترها
: تعداد مورچه ها(جمعیت اولیه) n
:Nتعداد تکرار
:اهمیت نسبی فرومونα
: ضریب تبخیر ρ
: میزان فرومونτ
: اهمیت مسافت β
تابع هزینهCost:
شرایط پایانی مساله:
بعد از N تکرار
تکرار چندباره ی یک پاسخ
خیر
فلوچارت الگوریتم
26
آزمایشات پل : Goss و همکاران(1989)
رفتار مورچه ها (جستجو گرانه)
27
آزمایشات پل : Goss و همکاران(1989)
غلظت زیاد فرومون روی مسیر بلند
تبخیر آرام فرومون
رفتار مورچه ها (جستجو گرانه)
28