چکیده

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

مطالعات کلنی مورچه به وفور درمجموعه ای از الگوریتمهای هوشمند کمک کرده است. بهینهسازی الگوریتم مورچه (ACO) با موفقیت به کارهای بهینه سازی ترکیبی به خصوص به مشکل طبقهبندی دادهکاوی استفاده گردیده است. الگوریتمهای مبتنی بر مورچه و یا بهینه سازی کلونی مورچه ها (ACO) ، در زمینه دادهکاوی کاربردی برای استخراج طبقه مبتنی بر قواعد بکار برده شده و در زمینه مشکلات بهینه سازی ترکیبی بطور موفق استفاده شده است.

کلمات کلیدی
الگوریتم کلونی مورچگان، تشخیص نفوذ، داده کاوی، الگوریتم مورچه-معدن.

مقدمه

الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچهها حشراتی اجتماعی هستند که در کلونیها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچهها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچهها دارای نوعی هوشمندی تودهای است کهاخیراًمورد توجه دانشمندان قرار گرفته است.

بهینه سازی الگوریتم مورچه (ACO) با موفقیت به کارهای بهینه سازی ترکیبی به خصوص به مشکل طبقه بندی داده کاوی استفاده گردیده است. همچنین اینترنت و شبکه های محلی همه گیر شده اند، بنابراین سازمان به طور فزایندهای از سیستمهای مختلف که نقض امنیتی IT دارند به کار گرفته می شود، زیرا حوادث نفوذ روز به روز در حال رشد است.

در علوم کامپیوتر و تحقیق در عملیات، الگوریتم بهینه سازی کلونی مورچه ها (ACO) از روش احتمالاتی برای حل مسائل محاسباتی است که توانسته پیدا کردن مسیرهای خوب را از طریق نمودار کاهش دهد. یکی از خصلتهای مهم کولونی مورچهها هوشمندی تودهای است، بدین معنا که کولونی مورچهها نه بر اساس هوشمندی یک مغز مرکزی بلکه بر اساس تودهای از عاملهای هوشمند و رابطه بین آنها، عمل میکند.

در این مقاله، الگوریتم کلونی مورچهها در طی جستجو/پیدا کردن مسیر از لانه به منبع غذایی با الهام از رفتار مورچه ها مطالعه می شود. حشرات اجتماعی مثل مورچهها، زنبورعسل و موریانههای خودکار در کارهای ساده خود، مستقل از دیگر اعضای این کلونی رفتار میکنند. با این حال، زمانی که آنها به عنوان یک جامعه عمل میکنند، آنها قادر به حل مسائل پیچیده پدیدار شده در زندگی روزمره خود، با استفاده از همکاری دو جانبه هستند. این رفتار ناشی از یک گروه از حشرات اجتماعی به عنوان “هوش جمعی” شناخته شده است.

کارهای انجام شده

اولین بار الگوریتم مورچگان توسط مارکو دیگو در سال ۱۹۹۱ در قالب رساله دکتری برای حل مسئله دوره گرد با ۷۵ شهر با نام سیستم مورچگان که مدل اولیه الگوریتم بود عرضه شد. دوریگو این الگوریتم را با ویژگیهایی معرفی مینماید از قبیل: تطبیقپذیری، که با این الگوریتم می توان مسائل دیگر در بهینهیابی ترکیبی را حل نمود. فرآیند الگوریتم عبارت است از: تعیین مقدار اولیه برای تابع فرومون و تابع ابتکاری، قرار دادن شهر مبدا برای هر مورچه در

×اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر

First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering×
. . . W W W . T D E C O N F . I R . . .

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

در سال ۲۰۰۵ با توجه به ویژگی مورچهها که قادر به پیدا کردن کوتاهترین مسیر بین منبع غذا و لانه بدون کمک از اطلاعات بصری، و همچنین برای انطباق با محیط در حال تغییر هستند ایده بعدی مطابق شکل زیر ارائه گردید. این یعنی که راه مورچهها بر اساس دنباله فرومون با یکدیگر ارتباط برقرار می کند. این نوع رفتار مورچهها دارای نوعی هوشمندی تودهای است. در دنیای واقعی مورچهها ابتدا به طور تصادفی به اینسو و آنسو میروند تا غذا بیابند. سپس به لانه بر میگردند و ردی از فرومون (Pheromone) به جا میگذارند. چنین ردهایی پس از باران به رنگ سفید در میآیند و قابل رویت اند. مورچههای دیگر وقتی این مسیر را می یابند، گاه پرسه زدن را رها کرده و آن را دنبال میکنند. سپس اگر به غذا برسند به خانه بر میگردند و رد دیگری از خود در کنار رد قبل میگذارند؛ و به عبارتی مسیر قبل را تقویت میکنند.

شکل ۱ دنبال کردن مسیر بین لانه و منبع غذا توسط مورچگان

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

مفاهیم کلی

الگوریتمهای اکتشافی الگوریتمهایی هستند، که به منظور فرار از حالت محلی کنونی، در پی برخی اکتشافات اولیه هستند: یا روش اکتشافی که از یک راه حل پوچ اغاز شده و با اضافه کردن عناصر به یک روش کامل دست یافته، و یا روش اکتشافی جستجوی محلی با شروع از یک راه حل کامل و اصلاح مکرر برخی از عناصر خود در جهت رسیدن به یک بهتر است.

عمل دستهبندی یک تکنیک دادهکاوی مطالعه شده توسط آمارشناسان و محققان متکی بر ماشین، برای یک دوره بسیار طولانی از زمان مورد مطالعه است. این یک فرایند است که در آن کلاسها از پیش تعریف شده است و یک طبقه ساخته شده است که نمونه دادهها را به کلاس اختصاص داده است. قوانین پیشبینی اغلب در IF THEN نشان داده ، و به این صورت توصیف می گردد:

< × کلاس > then> شرط IF<

در هر قانون، بخش (شرط) معمولا شامل یک ترکیب منطقی ازخصوصیات قابل پیش بینی به شکل: term1 و term2 و … و ¡term می باشد. و هر ترم سه گانه است، از جمله (خصوصیت، عملیات، مقدار) مثل (رنگ=قرمز). بخش نتیجه نشان می دهد کلاس پیش بینی شده با شرط برآورده شده است یا نه. با استفاده از این قوانین، مردم میتوانند یک پدیده خاص را پیشبینی کنند و یا از مقدار زیادی از اطلاعات دیدکلی به دست آوردند.