الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

توسعه اين الگوريتم از رفتار مورچه‌ها الهام گرفته است. مورچه‌ها حشرات اجتماعي هستند. آنها در دسته‌ بزرگي(Colony) از جمعيت زندگي مي كنند و رفتارشان تابع بقاي كولوني است نسبت به بقاي فردي. از رفتار مورچه‌هاي كارگر كه براي يافتن غذا تلاش مي‌كنند در الگوريتم مورچگان الهام گرفته شده است، اينكه مورچه چگونه كوتاه‌ترين مسير را براي يافتن غذا تا لانه طي مي‌كند.

براي يافتن غذا، مورچه ها ابتدا محدوده دور لانه را بطور تصادفي طي مي‌كنند. در حال حركت، مورچه‌ها اثري از خود به نام فرومون(pheromone) روي زمين به جا مي‌گذارند. مورچه‌ها فرومون را مي‌توانند بو بكشند، در هنگام انتخاب مسير، مسيري كه اثر فرومون قوي‌تري دارد، احتمال انتخاب بيشتري خواهد داشت. به محض اينكه مورچه‌اي منبع غذايي پيدا كرد، كيفيت و مقدار غذا را ارزيابي مي‌كند و مقداري از غذا را با خود به لانه مي‌برد. در طول بازگشت، اثر فرومون به جاي مانده در زمين بستگي به كيفيت و كميت غذاي حمل شده دارد. اثر فرومون ، ساير مورچه ها را در رسيدن به منبع غذا راهنمايي مي‌كند. با توجه به اينكه فرومون در اثر مجاورت با هوا تبخير مي‌شود، از مسيري كه مورچه كمتري عبور كند يعني در اثر تشديد نشدن، فرومون بعد از مدتي كاملاً محو مي‌شود. در واحد زماني يكسان، از مسيرِكوتاه‌تر نسبت به مسير طولاني‌تر مورچه‌هاي بيشتري عبور مي‌كنند پس فرومون بيشتري باقي مي‌ماند. در نتيجه‌ي گذشت زمان پس از مدتي از مسيري كه مورچه نگذشته هيچ اثري از فرومون نخواهد ماند و همه از مسير كوتاه‌تر عبور مي‌كنند(Deneubourg et. al 1990; Grassé 1959). جزئيات بيشتر اين عمل توسط دنبرگ و ديگران(Deneubourg et. al) (1990)آورده شده است كه آنها را قادر مي‌سازد كوتاه ترين مسير را از لانه تا دانه بپيمايند.شكل(1) را ببينيد.

شكل (1) حركت مورچه‌ها براي رسيدن به غذا. اين مثال چگونگي حركت مورچه‌ها براي رسيدن به كوتاه‌ترين مسيرشان را نشان مي‌دهد. در اينجا تنها دو راه براي رسيدن به غذا وجود دارد. مورچه‌ها با كمكِ فروموني كه از بدنشان ترشح مي‌شود كوتاه‌ترين مسير را پيدا مي‌كنند بدين ترتيب در سمتي كه فرومون بيشتري باشد احتمال گام نهادن در آن مسير بيشتر مي‌شود(Tfaili & Siarry 2007)

2. سيستم مورچه‌ها براي مسأله فروشنده دوره گرد:

اولين الگوريتم مورچگان به عنوان يك مثال در اينجا اولين الگوريتم مورچگان ارائه مي‌شود كه سيستم مورچه‌ها(Ant System (AS)) ناميده مي‌شود در كاربرد همين موضوع است كه چنين آمده(Dorigo 1992; Dorigo, Maniezzo and Colorni 1996)

تعريف :

مسأله فروشنده دوره گرد بصورت گرافي نمايش داده مي‌شود كه گره‌ها شهر ها و يال‌ها مسير هاي موجود بين اين شهر‌ها و اندازه بين آنها است. هر مورچه در مسير حركت بين گره ها يك جواب ايجاد مي‌كند. بدين ترتيب كه اولين گره به صورت تصادفي انتخاب مي‌شود. اما براي ساير گره ها احتمال انتخاب محاسبه مي‌شود و گره‌اي كه احتمال انتخاب بيشتري دارد برگزيده مي‌شود(شكل 2 را ببينيد). احتمال انتخاب هر مسير توسط مورچه از رابطه زير محاسبه مي‌شود و مقدار احتمالي كه بيشتر باشد انتخاب مي‌شود.

كه در آن مقدار احتمال رفتن از مسير i به j در زماني كه محاسبات روي گره k انجام مي‌شود، نشان دهنده قدرت اثر فرومون روي مسير i تا j ، عكس تابع هدف كه اين مقدار در مسأله فروشنده دوره گرد عكس فاصله بين گره i تا j است، α و β پارامتر‌هايي كنترلي اند تا قدرت اثر فرومون يا عكس تابع هدف در مسأله را تغيير دهيم كه مقداري بزرگتر مساوي صفر دارند. بعد از انتخاب هر گره بايد مانند شرايط واقعي اثر فرومون مشهود باشد، پس فرومون به روز مي‌شود.

فرومون در طبيعت در مجاورت هوا تبخير مي‌شود بايد اثر آن را نيز در نظر گرفت. به p ضريب محو شدن فرومون مي‌گويند و نشان دهنده قدرت اثر فرومون است.

شكل 2 مثالي براي ساختن جواب مسأله فروشنده دوره‌گرد با چهار شهر.

فلوچارت اين الگوريتم در شكل (3) آمده است.

مثال

مسأله فروشنده دوره گرد با چهار شهر را در نظر بگيريد. جدول مسافت بين شهرها در جدول يك آمده است.

هدف يافتن كوتاهترين مسيري است كه از همه شهر‌ها گذشته و به شهر آغازين بازگردد.

حل: مقدار دهي اوليه.

α = 0.4

β = 0.9

ρ = 0.4

τij = 0.001

براي همه مقادير مقادير ηij در اين مثال برابر عكس فاصله بين شهرها است. يعني: ηij = 1/dij

η12 = 1/15= 0.0667

تكرار اول.

گام اول. ابتدا يك شهر به تصادف انتخاب شده و مقادير احتمال براي انتخاب شهر بعدي محاسبه مي‌شود.

گام دوم.

انتخاب بيشترين مقدار احتمال. در اين حالت مسير يك به دو با مقدار 0.448 بيشترين احتمال را دارد. بنابراين شهر دو انتخاب مي‌شود.

گام سوم.

به روز رساني فرومون

گام چهارم. بررسي شرايط توقفِ تكرار اول. چون همه شهرها انتخاب نشده اند به گام يك برو. در اين حالت همچنان در همان تكرار اول هستيم وگرنه به تكرار بعد برو.

گام اول . در حالتهاي قبلي شهرهاي يك و دو انتخاب شده اند. در اين حالت الگوريتم در شهر دو است از بين شهرهاي باقيمانده بايد يكي انتخاب شود.

گام دوم.

شهر سه با احتمال بيشتر انتخاب مي‌شود.

گام سوم به روز رساني فرومون.

گام چهارم.

بررسي شرايط توقف. تمام شهرها انتخاب نشده اند. به گام يك برو.

گام يك و دو. تنها شهر باقيمانده شهر چهار است.

گام سه. به روزرساني فرومون

گام چهار.

بررسي شرايط توقف. با توجه به اينكه تمام شهرها طي شده پايان تكرار اول.

این مسیر حرکت مورچه اول بود. سایر مورچه ها هم باید این مسیر را طی کنند تا تمام تکرارها (یعنی تعداد مورچه ها) از این مسیر عبور نمایند.

محاسبه تابع برازندگي:

در اين مسأله تابع هدف يا برازندگي برابر مجموع فاصله طي شده مسيري است كه توسط الگوريتم انتخاب شده است. مسير بدست آمده از اولين تكرار اين الگوريتم

و مقدار مسير طي شده برابر 59 است. اين مقدار اولين مقدار براي يك مسير است بدون هيچ شرطي بهترين مقدار پذيرفته مي‌شود. از تكرارهاي دوم به بعد وقتي الگوريتم به اين مرحله رسيد اين مقدار را با مقدار تابع برازندگي آن تكرار مقايسه ميكند اگر بهبودي حاصل شده بود بهترين مقدار همان مقدار تابع برازندگي مي‌شود . مسير طي شده نيز در حافظه الگوريتم باقي مي‌ماند تا در نهايت بهترين مقدار همراه مسير طي شده ارائه شود.

ساير تكرارهاي الگوريتم نيز انجام مي‌شود تا به شرط توقف تكرارها برسد. اين مسأله با كامپيوتر حل شده و جواب نهايي با 20 تكرار بدين صورت مي‌باشد.

الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

مطالب مشابه :

مفاهیم اولیه الگوریتم مورچگان :

پاور پوینت آموزش الگوریتم مورچگان(ACO)

الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

انواع مختلف الگوریتم بهینه سازی مورچگان

الگوریتم AS از کلونی مورچگان :

دانلود چند کتاب مربوط به الگوریتمهای فرا ابتکاری

فیلم آموزشی جامع الگوریتم مورچگان کلاسیک یا ACO در متلب

کد متلب الگوریتم مورچگان برای مسأله فروشنده دوره گرد

کتاب تحقیق در عملیات یا پزوهش عملیاتی با عنوان Introduction to Operations Research

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