مقاله استفاده از الگوریتم بهینه سازی کلونی مورچگان برای تشخیص و دسته بندی نفوذ

بخشی از مقاله

استفاده از الگوریتم بهینه سازی کلونی مورچگان برای تشخیص و دسته بندی نفوذ

چکیده

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

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

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

مقدمه

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

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

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

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

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

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

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

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

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

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

مفاهیم کلی

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

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

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

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

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

2

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

اصول رفتار مورچه

مورچهها حشرات اجتماعی زندگی جمعی می باشند. تقریبا دو درصد از حشرات اجتماعی هستند، و مورچهها برای نیمی از این حساب بشمار میروند. تعداد مورچهها در یکی از تک کلنیها ممکن است از 30 تا دهها میلیون متفاوت باشد. مورچهها غالب در حوزه آمازون، بیش از 30٪ از زیست توده از جنگل های محلی را تشکیل می دهند. رفتار مورچهها در حمل و نقل مواد غذایی، غلبه بر موانع، ساختمان مورتپه، و عملیات دیگر تقریبا مطلوب است. بقای مورچههای کلونی شگفت آور است: کاهش تا بالای 40٪ از حشرات عملا هیچ تاثیری بر عملکرد کل جامعه آنها ندارد. کشتار جمعی از مورچه ها (به عنوان مثال، ناشی ازمواد شیمیایی از زیستگاه خود) موجب تقویت حشرات با مورتپههای همسایه خود به عنوان یک خانواده برای نجات جامعه میگردد. رفتار اجتماعی مورچهها براساس خود-سازماندهی است، مجموعهای از مکانیسمهای دینامیکی تضمین میکند که سیستم میتواند به اهداف کلی از طریق فعل و انفعالات سطح پایین بین عناصردست یابد. قابلیتهای کلیدی این تعامل این است که عناصر فقط از اطلاعات محلی استفاده میکنند. باتوجه به این، هر کنترل متمرکز و اشاره به الگوی جهانی نشان میدهد سیستم در دنیای خارجی از بیرون حکومت میشود.

خود سازماندهی نتیجه تعامل چهار جزء زیر است:

(1) تجدید متعدد. (2) غیرمترقبگی. (3) بازخورد مثبت. (4) بازخورد منفی.

دو راه برای انتقال اطلاعات بین مورچهها وجود دارد: یک ارتباط مستقیم (که شامل تبادل غذا ، دیداری، و برخوردهای شیمیایی) و ارتباط غیر مستقیم است که به نام نشانه ورزی.

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

از نظر بیولوژیکی، نشانهورزی از طریق فرومون درک میشود، یک ترشحات شیمیایی خاص که توسط حرکت مورچه ها باقی می ماند. هرچه مورچه های بیشتری از یک مسیر حرکت کنند، فرومون غلظت بیشتری دارد. با گذشت زمان، تبخیر فرومون، اجازه میدهد مورچهها رفتار خود را هنگامی که محیط اصلاح شده است تطبیق دهند. در نمونهای از آزمایشها با مورچهها در پل نامتقارن، میتوان نشان داد که رفتار تعاونی از مورچهها چگونه امکان پیدا کردن کوتاهترین مسیر به غذا را ممکن میکند. پل نامتقارن (شکل (2 لانه مورچه با منبع غذایی توسط دو راه با طول های مختلف متصل میشود. این آزمایش با یک کلونی آزمایشگاهی از مورچههای آرژانتین (Iridomurmex humilis)، انجام شد که فرومون در هر دو مسیر ذخیره شده است.

شکل -2 یک پل نامتقارن

این طرح از آزمایش به شرح زیر بود : (1) پل ABCD ساخته شد. (2) دروازه در نقطه A باز شد. (3) تعداد مورچه ها طولانی تر (ACD) را انتخاب کردند و راه کوتاه تر از پل شمارش شد.

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

به طور کلی، یک الگوریتم ACO را می توان در هر مسئله بهینه سازی اعمال کرد:

3

x نمایش گراف مناسب برای مشکل. مشکل را باید به عنوان یک گراف با مجموعه ای از گره ها و لبه های بین گره ها شرح داده شود. نمودار باید دقیقا موقعیت ها و انتقالات بین انها را نمایش دهد.

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

الگوریتم کلونی مورچگان
هسته الگوریتم ساخت افزایشی از قوانین طبقه بندی به صورت
AND (term n ) THEN (class ) و ...( (term2 و IF (term1)

از داده ها می باشد. هر term یک جفت صفت ارزش مربوط به یک عملیات (عملگر های رابطه ای) است. بخش IF مربوط به سابقه حکومت و بخش THEN نتیجه حکومت، که نشان دهنده قانون پیش بینی شده میباشد. به عنوان مثال "رنگ = قرمز". نام صفت "رنگ" و "قرمز" یکی از مقادیر ممکن است. شبه کد از AntMiner نشان داده شده است:

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

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