الگوریتم بهینه سازی کلونی مورچگان چيست؟
 

ادامه...
 

الگوریتم Ant colony Optimization که به اختصار ACO نامیده می شود و به نامهای الگوریتم کلونی مورچگان و بهینه سازی کلونی مورچه ها در ایران شناخته می شود یکی از شناخته شده ترین الگوریتم های بهینه سازی تکاملی است. بر آن شدیم تا در وبسایت الگوریتم رقابت استعماری در پستی کوتاه به معرفی این الگوریتم بپردازیم. مورچه‌ها اين قابليت را دارند که مي‌توانند با توليد فرومون، کوتاه‌ترين مسير به غذا را بيابند. مورچه‌ها مسير غذا را توسط فرمون، پيدا مي‌کنند. مورچه‌هايي که کوتاه‌ترين مسير را انتخاب مي‌کنند، نسبت به آن‌هايي که مسير طولاني‌تري را انتخاب مي‌کنند، دنباله‌ي فرمون شديدتري، ايجاد مي‌کنند. از آنجاکه فرمون شديدتر، مورچه‌ها را بهتر جذب مي‌کند، مورچه‌هاي بيشتر و بيشتري، مسير کوتاه‌تر را انتخاب مي‌کنند تا آنجاکه همه‌ي مورچه‌ها، کوتاه‌ترين مسير را يافته و از آن مسير حرکت مي‌کنند. براي بررسي بيشتر موضوع، فرض مي‌کنيم که به عنوان مثال، سه مسير به منبع غذا وجود دارند که داراي طول متفاوتي هستند. مورچه‌ها، هر سه مسير را با احتمالات يکسان، انتخاب مي‌کنند. مورچه‌هايي که مسير کوتاه‌تر را رفته و برگشته‌اند، بيشترين فرمون را زودتر از بقيه توليد مي‌کنند. در نتيجه، مورچه‌هاي ديگر اين مسير را زودتر انتخاب کرده و به نوبه‌ي خود، سطح فرمون اين مسير را تقويت مي‌کنند. در نهايت همه‌ي مورچه‌ها، کوتاه‌ترين مسير به غذا را مي‌پيمايند.

عملکرد مورچه‌هاي آرژانتيني(1) در يافتن کوتاه‌ترين مسير بين لانه و منبع غذايي، بسيار عجيب و حيرت انگيز است. مورچه‌ي آرژانتيني عملا کور است و طبعا کوتاه‌ترين مسير براي او مفهومي ندارد و توسط او قابل شناخت نمي‌باشد. اما با وجود چنين کمبودي، توده‌اي از اين مورچه‌ها مي‌توانند با همکاري يکديگر، کوتاه‌ترين مسير موجود بين لانه و محل مواد غذايي را پيدا کنند. براي پي بردن به اين خاصيت، آزمايشي در محيطي شبيه به شکل 2-10 ترتيب داده شده است. در ابتدا تمامي مورچه‌ها در محل لانه هستند و قبلا هيچ مورچه‌اي از مسير بين لانه و محل مواد غذايي رد نشده است. آزمايش نشان مي‌دهد که مورچه‌ها پس از مدتي کوتاه‌ترين مسير بين لانه و محل مواد غذايي را انتخاب خواهند نمود. اين آزمايش توسط گاس و همکارانش انجام گرفته است و نتايج آن طي مقالاتي در سال‌هاي 1989 و 1992 منتشر گرديده است.


اولين الگوريتم بهينه‌سازي کلوني مورچه‌ها (ACO) براي حل مسئله‌ي فروشنده‌ي دوره‌گرد طراحي شد [1]. در اين بخش به طور خلاصه چگونگي عملکرد ACO براي حل اين مسئله مورد بررسي قرار مي‌گيرد. در اين مسئله، ACO با يک تعداد اوليه از مورچه‌ها که مسير‌ي را در اطراف شهرها، طي مي‌کنند، شروع مي‌شود. هر مورچه، فرموني را در طول مسير آزاد مي‌کند. الگوريتم با اختصاص هر مورچه به يک شهر که بطور تصادفي انتخاب مي‌شود، شروع مي‌گردد. شهر بعد با يک احتمال وزن‌دار، که تابعي از شدت فرمون موجود در مسير و طول آن است، انتخاب مي‌شود. احتمال اينکه مورچه‌ي kام مسير شهر mام به شهر nام را طي کند برابر است با

http://artificial3.persiangig.com/im...%20%281%29.png

که در آن

http://chart.apis.google.com/chart?c...&chl=%5Ctau%20، شدت فرمون
q، شهر‌هاي موجود در مسير k که بعد از شهر m مي‌آيند.
a، وزن‌دهي فرمون؛ زماني که a=0، نزديک‌ترين شهر انتخاب مي‌شود.
b، وزن‌دهي فاصله؛ زماني که b=0، فاصله ميان شهر در نظر گرفته نمي‌شود.

کوتاه‌ترين مسير، با بيش‌ترين فرمون، بيش‌ترين احتمال انتخاب شدن را دارد. در استفاده‌هاي اوليه‌ي از ACO، اين نتيجه حاصل شد که يک استراتژي نخبه‌گرايي نيز همانند آنچه که براي GA وجود دارد، مي‌تواند کارايي الگوريتم را بهبود ببخشد. در نتيجه، در محاسبه‌ي سطوح فرمون، به فرمون در طول بهترين مسير، وزني داده مي‌شود. فرمول بهينه‌سازي فرمون، به صورت زير بيان مي‌شود.

که در آن
http://chart.apis.google.com/chart?c...n}^{elite}}%20


http://chart.apis.google.com/chart?c...0_%7Bmn%7D%5Ek، فرمون ايجاد شده توسط مورچه‌ي k بين شهر‌هاي m و n
http://chart.apis.google.com/chart?c...0&chl=%5Cxi%20، ضريب تبخير فرمون
http://chart.apis.google.com/chart?c...Cvarepsilon%20، ثابت وزن‌دهي مسير نخبه
http://chart.apis.google.com/chart?c...%5E%7Belite%7D، فرمون ايجاد شده روي بهترين مسيري که تاکنون، توسط الگوريتم يافته شده است.
یک حل نوعی از مسئله فرشنده دوره گرد توسط الگوریتم کلونی مورچگان را در شکل زیر می بینید:


ACO براي حل مسائل ديگر بهينه‌سازي نيز استفاده مي‌شود. الگوریتم کلونی مورچگان در ورژن اولیه خود برای حل مسائل گسسته از نوع جایگشتی معرفی شد. بیشترین استفاده از این الگوریتم به حل مسائل مسیریابی در شبکه های کامپیوتری، تخصیص منابع در مهندسی صنایع، تقسیم وظایف در پردازنده ها و میان ماشین آلات بر می گردند. در مقابل ACO، الگوریتم های PSO و رقابت استعماری که به اختصار ICA نامیده می شود برای حل مسائل پیوسته معرفی شدند. اما هر دو الگوریتم در مدت کوتاهی پس از معرفی شدن، با معرفی نسخه های گسسته به ابزاری برای حل مسائل گسسته و بطور ویژه مسائل جایگشتی تبدیل شدند.

لازم به ذکر است که بر روی وبسایت الگوریتم رقابت استعماری کدهای حل مسئله فرشنده دوره گرد توسط الگوریتم کلونی مورچه ها نیز قرار داده شده است. در انتهای پست چند شکل دیگر مربوط به رفتار بهینه مورچه ها در یافتن مسیر غذا را می بینیم.
-------------------------------------------------------------------------------------------
(1) نام علمي اين گونه‌ي خاص Linepithema Humile است که قبلا به نام Iridomyrmex Humilis نيز خوانده مي‌شد. مورچه‌ي آرژانتيني بسيار ريز و تيره رنگ است. زيستگاه اين موجود در بخش‌هاي شمالي آرژانتين، اوروگوئه و پاراگوئه و همچنين بخش‌هاي جنوبي برزيل است.