صفحه 1:
صفحه 2:
نات . الگوریتم کلونی مورچه‌ها .شبن
ANT COLONY OPTIMIZATION
لولحبو سلكت
سا هی
AHMADMORADI369@GMAIL.CO
M
صفحه 3:
فهزست طلالت
* مقدمه
* هوش جمعى (Swarm Intelligence)
*؟ جكونكى يبدا كردن كوتاه ترين مسير
2860© مزيتهاى ٠
۰ کاربرد ۸0
ACO الگوریتم ۰
1۲5۳۴ ۰
۶ مثال
alte °
صفحه 4:
مقدمه
*_ یکی از موفق ترین مثال های الگوریتم مورچه هاء الگوریتم بهینه سازی کلونی
مورچه ها است که به اختصار ۸60 نامی‌ده می شود ه
ACO ٠ بسولیلولین‌سار تسوسط دویییگو (00۲190]) در 1992ایلشه شسده
_ الگوریتم ۸060 از رفتار مربوط به پیدا کردن غذا (۴0۲39189) مورچه های
الهام گرفته شده است۰
* الگوریتم ۸60 برای مسئله های بهینه سازی گسسته استفاده می شودء
صفحه 5:
(SWARM INTELLIGENCE) هوش جمعى
نمونه بارز این هوشمندی در رفتار حشراتی که بصورت کلونی زندگی می کنند: دی‌ده می
شوده
جمعی‌تی از اعضا عمل ساده ای را انجام مى دهند ٠
* در نهایت تمام گروه مساله پی‌چی‌ده ای را حل می‌کنند»
بين اعضا هي نوع ارتباط مستقیمی وجود ندارد»
*_آنها تنها بصورت غیر مستقیم و از طریق نشانه‌ها با یکدیگر در تماس اند۰( 51191۴6۲9
صفحه 6:
چگونگی پیدا کردن کوتاه ترین مسير
* مورچه ها هنگام راه رفتن از خود ردی (Pheromone) 452595 los odbe jl
جای می‌گذارند»
تبخیر شدن فرومون در گذر زمان
*_ مورچه‌ها بصورت احتمالاتی (51311581>21) مسیری را انتخاب می کنند که
فرومون بیشتری داشته باشد
صفحه 7:
چگونگی پیدا کردن کوتاه ترین مسیر
مورچه ها روی مسیر ۸٩8 در حرکت اند (در دو جهت مخالف)
اگر در مسير مورچه ها مانعی قرار دهیم مورچه ها دو راه برای انتخاب کردن دارند.
Hast
ati
صفحه 8:
جكونكى يبدا كردن كوتاه ترين مسير
تصادف و احتمال در انتخاب مسير
صفحه 9:
چگونگی پیدا کردن کوتاه ترین مسیر
يافتن كوتاهترين مسير
3
عد
Nast FEB Ray, Fuud
م۳ ریز ی یی
‘tee Ie
قلعم تكظم
صفحه 10:
مزیتهای ۸۵۵
تبخى رشدن فرومو”
احتمال-تصادف
انعطاف
جذابيت كمتر مسير براى مورجههاى بعدى
جندبار طى شدن مسيرها درصورت تبخير نشدن
باقی‌نماندن رد درصورت تمام شدن غذا
10
صفحه 11:
ACO elas Ils
کردن هر مسئله ای که نیازبه
ن کوتاهترین مسیر دارد »
٠.١ مسیر یابی داخل شهری و بین شهری
مسير يابى بين يست های شبکه های توزیع برق ولتاژ بالا
مسیریابی تامین مواد اولیه جهت تولید بهنگام
we
مسیر یابی شبکه های کامپیوتری
ii
صفحه 12:
ACO الگوریتم
استفاده از مورچه های مصنوعی به عنوان عناصری در بهینه سازی برای پیاده سازی کلونی مورچه
تفاوت مورچه‌های مصنوعی و مورچه‌های واقعی
8 . ۱- حافظه :
۲- موانع ساختگی: 5
SEE, تفيبر دادن جزئيات مسشله ale ya gall ol Gy
جدا از کلونی به حیات خود برای بررسی الگور که مسیرهای حرکت را در خود
ادامه دهند به جوابهای متنوع نگه می دارند
12
صفحه 13:
ACO الگوریتم
پروزرسانی فرومون
جواب بدست‌آمده
aero
صفحه 14:
الگوریتم ۸۵60
فرومون احتمال <
از مسیر آ به در زمانی که محاسبات روی گره >1
7 دار احتمال رفت
رم ]: نشان دهنده قدرت اثر فرومون روی مسیر آ تا [
زر []: عكس تابع هدف (در مساله فروشنده دوره گرد عكس قاصله بين كره أ تا ل[ است)
و 3]: بساولسترهليىكسنتوطيبند بسولى تسغى ىر قعدی‌ظثر فسوومون یساهکس سلبع هدف
صفحه 15:
ACO الگوریتم
بروز رسانی فرومون:
al,
ور ارلا 7
0>>1 ,7 > ,۷ ر[ سر[ . (- 1)
2 ضریب محو شدن فرومون
تر/] نشان دهنده قدرت اثر فرومون
صفحه 16:
ACO الگوریتم
شرط های توق
1 - تعداد تکرار
2- زمان
3- عدم بهبود
4- همگرای‌ی
16
صفحه 17:
(فروشنده دوره‌گرد)5۳ 1"
مطرح شده در سده ۱۸ توسط وی‌لیام همیلتون و توماسی کر کمن
17
صفحه 18:
مثال
با چهار شهر
مساله فروشنده دوره گرد با چ
صفحه 19:
مثال
مقدار دهی اولیه:
a=0.4
B=0.9
p=0.4
tij = 0.001
براى همه مقادير مقادير [1[1 در اين مثال برابر عكس فاصله بين شهرها است* یعنی
nij = 1/dij
12 = 1/15= 0.0667
صفحه 20:
مثال
۳ گام‌اول
ابتدا یک شهر به تصادف انتخاب شده و مقادیر احتمال برای انتخاب شهر بعدی محاسبه
می‌شود* ۳
_ اك = tia
=o a Tp Pan eI P= 12
Ima}? + [yg]? Ima? ونیت] + رم( تمب]
0079 2001۳004
= - 0.448
10001۳۴ f0.0667]°%+ 0.001} (0.05]°+ [0.001]°4[0.1]°% 7
20
صفحه 21:
4 2
Tees
Dy = 0.448 a
7, 2و 0 47%
رو 2-0 1 ۳
موه
به روز رسانی فرومون
x 0.001 + 0.6 x .0667 = 0.0404 04 = وی( ۷ (م - 1) + ورم وبرة كا م > سوم ور
”3 گام چهارم. بررسی شرایط توقف تکرار اول
21
صفحه 22:
مثال
گام اول
7 عرر رم
Py -4=0.3622
7 گام دوم
شهر سه با احتمال بیشتر انتخاب می‌شود.
۲ گام سوم
به روز رسانی فرومون ی
OX 0.001 +06 x 125 = 00754 = و (-1) + م2۵ مرو
گام چهارم
پررسی شرایط توقة
تمام شهرها انتخاب نشده اند. به گام یک برو
صفحه 23:
مثال
۲ گام یک و دو
تنها شهر باقیمانده شهر چهار است
گام سل ی
به روزرسانی فرومون
Trot new = 2X Tagore + (1 —p) X Mang = 9.4 0.001 + 0.6 X 0384 = 0.0234
” كام چهار
بررسى شرايط توقف. با توجه به اينكه تمام شهرها طى شده يايان تكرار اول
يي
23
صفحه 24:
ثال
محاسبه تابع برازندكى:
دراين مسأله تابع هدف يا برازندكى برابر مجموع فاصله طى شده مسيرى است كه
توسط الگوریتم انتخاب شده است.
مسیر بدست آمده از اولين تكرار اين الكوريتم:
1 هخ له ب
مقدار مسیر طی شده برابر ۵٩
صفحه 25:
منابع
1.کورش عشقی؛ مهدی کریمی نسب؛ تحلیل الگوریتمها و طراحی روشهای فرابتکاری؛
انتشارات دانشگاه شریف؛ ۱۳۹۵
2»مسئلهی مسیریابی در شبکههای پوی! مقاله. دانشگاه اصفهان
3.www.matlabdl.com
4.www.matlabhome.ir
5.www.matlabanalysis.com