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

**Astaraki** · ۰۶-۲۸-۱۳۸۸, ۱۲:۴۸ بعد از ظهر

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

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

الگوریتم بهینه سازی کلونی مورچه ها یا ACO، از رفتار مورچه های طبیعی که در مجموعه ها بزرگ در کنار هم زندگی می کنند الهام گرفته شده است. الگوریتم های دیگری نیز بر اساس الگوریتم مورچه ها ساخته شده اند که همگی سیستم های چند عاملی هستند و عامل ها مورچه های مصنوعی یا به اختصار مورچه هایی هستند که مشابه با مورچه های واقعی رفتار می کنند. الگوریتم مورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند. این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل بهینه سازی به کار برده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنین مسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود.

**Astaraki** · ۰۴-۱۳-۱۳۸۹, ۱۱:۲۵ قبل از ظهر

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

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

شکل: رفتار مورچه‌هاي آرژانتيني در آزمايش گاس و همکارانش

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

که در آن

$\tau$ ، شدت فرمون
q، شهر‌هاي موجود در مسير k که بعد از شهر m مي‌آيند.
a، وزن‌دهي فرمون؛ زماني که a=0، نزديک‌ترين شهر انتخاب مي‌شود.
b، وزن‌دهي فاصله؛ زماني که b=0، فاصله ميان شهر در نظر گرفته نمي‌شود.

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

که در آن
${\tau _{mn}} = (1 - \xi ){\tau _{mn}} + \sum\limits_{k = 1}^{{N_{ants}}} {\tau _{mn}^k + \varepsilon \tau _{mn}^{elite}}$

$\tau _{mn}^k$ ، فرمون ايجاد شده توسط مورچه‌ي k بين شهر‌هاي m و n
$\xi$ ، ضريب تبخير فرمون
$\varepsilon$ ، ثابت وزن‌دهي مسير نخبه
$\tau _{mn}^{elite}$ ، فرمون ايجاد شده روي بهترين مسيري که تاکنون، توسط الگوريتم يافته شده است.
یک حل نوعی از مسئله فرشنده دوره گرد توسط الگوریتم کلونی مورچگان را در شکل زیر می بینید:

شکل: یک حل نوعی از مسئله فرشنده دوره گرد توسط الگوریتم کلونی مورچگان

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

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

شکل: رفتار بهینه کلونی مورچه ها